Débuter en programmation parallèle avec OpenMP*

Introduction

Bien que les processeurs comportent de plus en plus de coeurs, la programmation parallèle est encore quelque chose de relativement peu répandu. La raison principale est sans doute qu'elle fait peur : on s'attend à quelque chose de très technique nécessitant des semaines d'apprentissage avant de pouvoir faire fonctionner le moindre petit programme.

C'est ce que je pensais moi aussi, jusqu'à ce que je parallélise mon premier morceau de code. Les recherches sur Internet mènent souvent à des exemples ardus ou des documentations de plusieurs centaines de pages. Cela est très bien lorsque l'on veut se perfectionner, mais cela constitue souvent une barrière à l'entrée très décourageante. Pourtant, derrière cette apparente complexité, se cache en réalité un univers très accessible lorsque l'on sait par où commencer. Et c'est là tout l'objectif de cet article.

Le but ne sera pas ici donc pas ici de rentrer dans des détails trop techniques mais au contraire de présenter un exemple très simple pouvant être mis en oeuvre en un quart d'heure. A la fin, vous disposerez d'un programme en C++ parallélisé avec OpenMP sur lequel vous pourrez expérimenter tout ce qui vous passera par la tête. Bonne lecture et bons tests !
 

Problème considéré

Ce que je vais vous proposer n'est peut être pas l'exemple le plus fun du monde, mais cela a le mérite d'être simple et de bien se prêter à diverses expérimentations. Si vous vous demandez d'où m'est venue l'idée, cet exemple s'inspire de l'un des aspects du second problème du concours de programmation parallèle Intel Acceler8.

L'objectif va être de lister (dans un fichier) le plus rapidement possible tous les nombres premiers inférieurs ou égaux à 1 000 000 (dans l'ordre) avec comme contrainte imposée d'utiliser l'algorithme le plus basique qui soit. Cet algorithme est directement inspiré de la définition suivante : "Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même) (le premier nombre premier est 2)" (je rappelle que le but n'est pas d'optimiser un algorithme mais d'apprendre à paralléliser un programme). La stratégie adoptée va donc consister à tester si chaque nombre N compris entre 2 et 1000000 est divisible par au moins un n compris entre 2 et N-1 : si un tel n existe alors N n'est pas premier, sinon il l'est.
 

Programme de base

Voici le programme de base, non parallélisé : monothreaded.cpp

Cela devrait compiler sans trop de problème (vous pouvez activer le niveau d'optimisation -O3). Une fois lancé, le programme calcule les nombres premiers de 0 à 1 000 0000 et les écrit dans un fichier primelist.txt. Pour ma part j'obtiens la sortie suivante :

 

1 thread(s) available for computation
Thread 0 is ready for computation

STARTING COMPUTATION
Indicator (current N) : 100000
Indicator (current N) : 200000
Indicator (current N) : 300000
Indicator (current N) : 400000
Indicator (current N) : 500000
Indicator (current N) : 600000
Indicator (current N) : 700000
Indicator (current N) : 800000
Indicator (current N) : 900000
Indicator (current N) : 1000000
END OF COMPUTATION

78498 primes were found between 0 and 1000000
Execution time : 150 s
Si vous surveillez l'activité de votre système et si votre ordinateur est dôté d'au moins deux cores (ce qui est le cas de la plupart des ordinateurs actuels) vous verrez que l'un des coeurs se charge de tout le travail pendant que les autres se reposent tranquilement. Et si seulement on pouvait réparer cette injustice en répartissant le travail de manière un peu plus équitable (avec en prime un gain sur le temps d'exécution) ! C'est justement ce que je vous propose dans la suite.
 

Choix de la bibliothèque

Pour paralléliser un code, de nombreuses bibliothèques existent : Intel Threading Building Blocks, OpenMP, MPI... Chacune d'entre elles est unique par sa complexité de mise en oeuvre, par sa façon de gérer la mémoire et la communication entre les processus et par le niveau de gestion des tâches qu'elle permet.

Dans le cadre de ce tutoriel, je vous propose d'utiliser OpenMP : sa mise en place grâce à des directives #pragma est relativement simple et elle est livrée avec la plupart des compilateurs.

Pour l'utiliser, il suffit de faire un #include <omp.h> dans le code et de compiler avec l'option -openmp pour le compilateur icpc d'Intel et -fopenmp pour g++ (si vous passez par un Makefile, il faut aussi mettre l'option dans les LDFLAGS).

Si comme moi, vous utilisez un IDE, il faut faire quelques modifications dans la configuration du compilateur. Par exemple, sous Code::Blocks, pour compiler un code utilisant OpenMP avec g++, il faut ajouter -fopenmp dans "Settings/Compiler and debugger/Compiler Settings/Other options" et le lien vers le fichier libgomp dans "Settings/Compiler and debugger/Linker settings" (pour moi il s'agit de libgomp.so sous Linux et de libgomp-1.dll sous Windows).

Et c'est tout ce qu'il y a a configurer !
 

Principe de la parallélisation de l'algorithme

Contrairement à MPI qui repose sur l'exécution de threads complètement indépendants qui communiquent entre eux au cours de l'exécution, OpenMP permet de gérer un programme avec des zones parallélisées et des zones qui ne le sont pas. Aussi, pour éviter que les processus ne se perturbent les uns les autres, il est nécessaire de définir des variables partagées qui sont communes à tous les threads et des variables privées qui sont propres à chaque thread (pour OpenMP, si le statut d'une variable n'est pas précisé, cette dernière est partagée par défaut).

Par exemple, si l'on souhaite paralléliser la boucle for du code donné plus haut, il ne faut pas laisser la variable isprime comme partagée car sinon il n'y aurait qu'une instance de cette variable et les différents threads viendraient tous écrire au même emplacement mémoire : les processus interfèreraient entre eux, isprime ne cesserait de passer de true à false et des nombres premiers seraient déclarés comme composites. Pour que tout se passe bien il faut que chaque processus ait sa propre variable isprime, et c'est que l'on fait en la déclarant privée.

Paralléliser la boucle for, c'est justement ce que je vous propose de faire. Le principe en est simple : chaque itération de la boucle sera vue comme une tâche indépendante et cet ensemble de tâches sera réparti entre les différentes unités de calcul (processeurs ou coeurs). Toutefois, pour que la parallélisation "basique" fonctionne, il faut que chaque itération soit indépendante de la précédente.

Dans les faits voici, ce que l'on va faire : le thread principal va d'abord compter le nombre de cpus disponibles, et chacun d'entre eux va ensuite répondre présent à l'appel. Je rappelle que tout cela est à des fins didactiques et que vous ne demanderez jamais (enfin pour le moment encore) aux unités de calcul si elles sont d'accord ou pas pour faire le travail ou si elles préfèrent rester dormir. Une fois cette initialisation effectuée, le calcul va être lancé au travers de la boucle parallélisée, et comme dans le  programme monothreadé, les statistiques sur l'exécution seront affichées à la sortie de la boucle.
 

Directives et fonctions OpenMP

Avant d'aller plus loin, passons en revue quelques directives OpenMP. Une liste plus complète avec une description détaillée est disponible ici et .

  • #pragma omp parallel : section parallèle
  • #pragma omp parallel for : boucle for parallèle
  • #pragma omp master : section qui ne sera exécutée que par le thread principal
  • #pragma omp critical : région "critique" qui ne doit être éxécutée que par un thread à la fois (doit par exemple être utilisé lorsque des threads doivent écrire dans une variable partagée ou dans un fichier)
  • #pragma omp ordered : section qui doit être exécutée dans l'ordre
  • #pragma omp barrier : barrière qui permet d'attendre que tous les threads soient arrivés à ce point avant d'éxécuter la suite

On peut ensuite ajouter un certain nombre d'options après les directives (voir les sites cités plus haut pour une description plus complète).

  • private(var1) : var1 sera une variable privée de la section parallèle (à noter que la valeur originale déclarée dans la partie non parallèle du programme n'est pas recopiée)
  • shared(var2) : var2 sera une variable partagée de la section parallèle (ce qui est le cas par défaut de toute variable qui n'est pas déclarée private)
  • firstprivate(var3) : semblable à private sauf que cette fois la valeur privée de var3 est initialisée à la dernière valeur de var3 dans la partie non parallélisée qui précède
  • lastprivate(var4) : à la fin de la section parallèle, la valeur que prend var4 pour le dernier thread sera affectée à var4 dans la section non parallèle qui suit
  • ordered : la section parallèle comporte un bloc #pragma omp ordered
  • schedule(static) : option par défaut qui réparti les tâches de façon statique entre les threads
  • schedule(dynamic) : option qui permet de répartir les tâches de façon dynamique, particulièrement utile lorsque les temps d'exécution des tâches sont différents
  • reduction(op:val) : permet de "réduire" la variable val par l'opérateur op en sortie de la section parallélisée : par exemple reduction(+:val) permet de sommer toutes les variables privées val à la fin de la parallélisation.

Enfin, deux fonctions bien utiles :

  • omp_get_num_threads() : renvoie le nombre de threads qui exécutent une section parallèle
  • omp_get_thread_num() : renvoie un entier qui correspond au numéro du thread (en partant de 0)

Une première (mauvaise) parallélisation

Avec ces fonctions et directives, on peut commencer à paralléliser le code en le réécrivant de cette façon : badparallel.cpp

Les changements par rapport au code original sont les suivants :
 
  • #include <omp.h> : inclusion du header d'OpenMP
  • #pragma omp parallel private(threadid) : parallélisation de la section destinée à récupérer les informations sur les threads : threadid, le numéro du thread doit être déclaré comme privé, car propre à chaque thread
  • #pragma omp parallel for ordered private(n,isprime) : parallélisation de la boucle de façon ordonnée car on veut que les nombres premiers soient écrits dans l'ordre dans le fichier (remarque : il n'y a pas besoin d'accolades car le for à paralléliser se trouve sur la ligne suivante)

En faisant tourner le programme, j'obtiens la sortie :

22 thread(s) available for computation
 thread(s) available for computation
Thread 1 is ready for computation
Thread 0 is ready for computation

STARTING COMPUTATION
Indicator (current N) : 100000
Indicator (current N) : 200000
Indicator (current N) : 300000
Indicator (current N) : 400000
Indicator (current N) : 500000
Indicator (current N) : 600000
Indicator (current N) : 700000
Indicator (current N) : 800000
Indicator (current N) : 900000
Indicator (current N) : 1000000
END OF COMPUTATION

78498 primes were found between 0 and 1000000
Execution time : 160 s
Et là c'est le drame ! D'une part le programme m'annonce qu'il y a 22 threads disponibles, tout simplement car la sortie avec std::cout n'a pas été déclarée comme critical : chaque thread a donc détecté qu'il y avait 2 threads qui exécutaient la partie parallèle, mais ils l'ont affiché simultanément. D'autre part le temps d'exécution qui est  de 160 secondes. Comme gain de la programmation parallèle on a fait mieux ! Cela est en fait lié à l'exécution ordonnée de la boucle qui fait perdre beaucoup des avantages du multithreading. On obtient un temps d'exécution total supérieur au cas monothreadé tout simplement parce que la programmation parallèle engendre un coût supplémentaire en temps (temps de synchronisation par exemple).
 

Une parallélisation efficace

Et si l'on recodait ça plus proprement avec pour objectif d'obtenir une parallélisation qui serve à quelque chose ?

Par rapport au code précédent voici les changements que l'on va effectuer :
  • Seul le thread principal va mesurer le nombre de thread disponibles grâce à #pragma omp master.
  • On va attendre que la mesure du nombre de threads soit effectuée avant de passer à l'affichage des id grâce à #pragma omp barrier.
  • Tout ce qui s'apparente à de l'écriture vers des zones partagées (variables, fichier, stdout) va être protégé par des directives critical.
  • La gestion des tâches dans la boucle for va être déclarée comme dynamique avec schedule(dynamic) pour prendre en compte le fait qu'il est par exemple plus long de vérifier la primalité de 999983 que de 11.
  • Pour compter le nombre total de nombres premiers trouvés on va se servir de reduction(op:val) qui est fait pour ce genre de choses.
  • Pour laisser la parallélisation s'effectuer dans l'ordre où elle le souhaite, on va utiliser un std::vector partagé que l'on triera avant d'effectuer la sortie sur le fichier. Il existe des méthodes plus efficaces et élégantes, mais celle-ci a le mérite d'être très simple à mettre en place.
Au final on obtient donc le code suivant : multithreaded.cpp

On a donc deux zones parallélisées, la première permettant de récupérer certaines informations sur les threads et la seconde permettant d'effectuer la détermination des nombres premiers de façon parallèle. Puis, dans un ensemble non parallélisé, à la fin du programme, les nombres premiers sont reclassés dans l'ordre et écrits dans un fichier.

J'obtiens alors la sortie suivante :
2 thread(s) available for computation
Thread 1 is ready for computation
Thread 0 is ready for computation

STARTING COMPUTATION
Indicator (current N) : 100000
Indicator (current N) : 200000
Indicator (current N) : 300000
Indicator (current N) : 400000
Indicator (current N) : 500000
Indicator (current N) : 600000
Indicator (current N) : 700000
Indicator (current N) : 800000
Indicator (current N) : 900000
Indicator (current N) : 1000000
END OF COMPUTATION

78498 primes were found between 0 and 1000000
Execution time : 78 s

 

Alors c'est pas beau ça ? Et si vous regardez le taux d'occupation des différents cores de votre machine vous pourrez découvrir avec émerveillement que chacun d'entre eux s'est mis au travail. Non seulement vous avez réparé l'injustice du programme monothreadé mais en plus vous avez considérablement diminué le temps d'exécution.
 

Conclusion

Et voilà votre premier programme parallèle terminé. Comme vous avez pu le voir ce n'était pas si difficile finalement. Une configuration de la compilation très simple, quelques directives à apprendre, un ou deux tests et le tour est joué. Le but ici n'était pas d'optimiser au mieux la parallélisation ni de faire un inventaire de toutes les méthodes qui existent mais plutôt de présenter un petit exemple histoire de comprendre comment cela pouvait être mis en place. J'espère que vous n'hésiterez plus à paralléliser vos programmes et à vous documentez sur le sujet, mais je ne me fais pas trop de souci : maintenant que vous y avez goûtez vous ne pourrez bientôt plus vous en passez !

Un mot sur l'auteur

Vincent Reverdy est élève ingénieur en dernière année à PHELMA, l'Ecole Nationale Supérieure de Physique, Electronique et Matériaux en filière Physique et Nanosciences. Il a également suivi une formation en Astrophysique au sein du Master Recherche AMD de l'Université Joseph Fourier dans le cadre d'un double cursus. Il effectue actuellement son projet de fin d'études au Laboratoire Univers et Théories de l'Observatoire Paris-Meudon où il travaille sur des simulations numériques de formation de l'Univers.

如需更全面地了解编译器优化,请参阅优化注意事项