Une introduction à la programmation parallèle avec Open MPI et OpenMP

Avant d’entrer dans le vif du sujet, je tiens à préciser que, hormis une connaissance des bases du C++, aucune connaissance de l’algorithmique distribuée n’est requise pour aborder cet article.

1. Algorithme séquentiel vs. Algorithme parallèle

Un algorithme est une méthode de résolution d’un problème par la description finie d’une séquence d’opérations (qui elle peut être infinie) [1]. Par exemple, le matin je me lève et je te bouscule, tu ne te réveilles pas (comme d’habitude) [2].

Lorsque la séquence est représentable par une suite d’états totalement ordonnée, alors l’algorithme est dit séquentiel. Lorsque la suite d’états n’est que partiellement ordonnée (au moins deux actions se déroulent en parallèle) alors on parlera d’algorithme parallèle. Par exemple, le matin le réveil se déclenche. D’un côté ma femme se lève puis me bouscule, d’un autre côté, le réveil diffuse une musique trop forte et indépendamment les volets s’ouvrent automatiquement éclairant la pièce d’une lumière agressive. Au final, je ne me réveille toujours pas, comme d’habitude.

In fine, un algorithme parallèle peut être vu comme plusieurs sous-algorithmes séquentiels qui se déroulent en parallèle. On distinguera cependant les communications entre les sous-algorithmes, selon qu’ils se partagent une même zone d’informations (et potentiellement y accèdent de manière concurrente) ou bien qu’ils utilisent un vecteur de communication dédié pour se partager certaines informations. Dans le premier cas, on parle de parallélisme léger (multithreading en anglais) tandis que dans le second cas de parallélisme lourd (multiprocessing en anglais).

1.1 Parallélisme léger

Le parallélisme léger traduit le fait que des instructions s’exécutent en parallèle tout en se partageant une même zone mémoire. Cela signifie que si plusieurs blocs d’instructions B₁, B₂, …, B_n s’exécutent en parallèle, rien n’empêche par défaut les blocs d’écrire ou lire l’état d’une variable simultanément, pouvant aboutir à une situation imprévisible et chaotique. Ainsi sont apparues les fameux MutEx, variables particulières dont le rôle est d’obtenir un verrou exclusif (Mutual Exclusion) sur la mémoire partagée. Pour faire une analogie, imaginons plusieurs voitures (nos processus parallèles) circulant sur un réseau routier (zone de mémoire partagée).Tant que chaque voiture ne rencontre pas les autres, il n’y a pas de problème. Si par contre, deux voitures empruntent la même route, sur la même voie, les problèmes peuvent survenir assez rapidement (surtout si les véhicules roulent à contresens l’un de l’autre). Dès lors, il est prudent avant de s’engager sur cette route que chacune des voitures puisse s’assurer un usage exclusif de celle-ci. Cela passe par une demande d’autorisation pour emprunter ladite route à un agent de la sécurité routière (le système d’exploitation). Si la route est libre, l’agent autorise la voiture qui a fait la demande et interdit à tout autre véhicule de l’emprunter. Une fois que la voiture qui s’est engagée a quitté la portion de route dangereuse, il avertit l’agent que la route est à nouveau libre. A contrario, si lorsqu’un véhicule effectue la demande d’accès, la route est déjà utilisée par une autre voiture, alors l’agent met le demandeur en attente jusqu’à ce que la route soit libérée. Bien évidemment, la gestion des MutEx est un sujet important. En effet, il faut tout d’abord s’assurer qu’une fois la tâche effectuée, le MutEx est bien relâché. Dans le cas contraire, le risque est de bloquer le système, certains processus demeurant en attente d’obtention du MutEx. En outre, les MutEx créent des goulots d’étranglement, il faut donc les demander le plus tard possible et les relâcher dès que possible. Pour reprendre l’analogie avec les voitures, si je demande l’autorisation exclusive de circuler sur la route menant de mon travail à mon domicile (plusieurs km) alors que la zone de danger ne représente que quelques mètres, je bloque inutilement tout le monde (ce n’est pas très grave, au moins je suis tranquille sur ma route, par contre si quelqu’un faisait ça, je le gratifierai de plusieurs noms d’oiseaux). Bien évidemment, le fait de demander un MutEx a un coût, donc il est important de veiller à regrouper les instructions sensibles dans un même bloc lorsque cela est possible.

1.2 Parallélisme lourd

Le parallélisme lourd peut s’apparenter quant à lui au déroulement de plusieurs algorithmes distincts en simultané. Chacun des algorithmes ayant un objectif spécifique et plus ou moins indépendant des autres. Les algorithmes peuvent cependant avoir besoin d’échanger quelques informations, auquel cas un protocole de communication doit être mis en œuvre. Par exemple, pour modéliser un serveur web, il faut un algorithme principal qui écoute sur un port donné jusqu’à ce qu’un client se connecte. Quand un client se connecte un nouvel algorithme prend en charge le client et l’algorithme principal se remet tout simplement en écoute d’un nouveau client. Chaque prise en charge d’un client est indépendante.

Dans certains cas plus complexes, il faut tout de même que les différents processus communiquent un minimum sur leur état ou bien échangent ponctuellement des données. Cela peut s’opérer par l’utilisation de fichiers (type fifo) lorsque les processus s’exécutent sur la même machine (ou disposent d’un espace de stockage commun (e.g., montage NFS). Dans un cas plus général, cela peut passer par une communication réseau (e.g., protocoles UDP ou TCP).

1.3 Parallélisme léger + parallélisme lourd

Et non, parallélisme léger + parallélisme lourd, ça ne fait pas du parallélisme moyen, mais c’était bien tenté !

On parle dans ce cas-là de parallélisme hybride. L’idée est de tirer parti des deux paradigmes et c’est ce qu’on va faire dans la suite donc je n’en écris pas plus pour le moment…

1.4 Quand/Comment/Pourquoi paralléliser un algorithme ?

Dans certains cas, la conception d’algorithmes parallèles découle du bon sens et s’avère plus simple à mettre en œuvre qu’en séquentiel (e.g., mise en place d’un serveur web). Dans d’autres cas, paralléliser les traitements n’est pas toujours intuitif. Cependant, avec l’arrivée, cette dernière décennie, d’un volume de données à traiter et analyser toujours plus important, cela devient une nécessité.

Dans cet article, je présenterai deux standards permettant de faire l’un du parallélisme léger et l’autre du parallélisme lourd. Le code fourni est écrit en C++, tout d’abord parce que cela me semble cohérent d’utiliser l‘un des langages les plus performants pour faire des calculs intensifs et d’autre part parce que le C++ dispose (par rapport au C) des facilités offertes par la STL (qui n’existe plus stricto sensu puisqu’elle a été intégrée au standard C++ [3]).

2. OpenMP

Le standard OpenMP [4] est clairement dédié aux parallélismes légers. Pour celles et ceux qui ont déjà fait des programmes parallèles (e.g., avec pthreads en C/C++), vous allez constater que l’interface OpenMP simplifie grandement les mécanismes de parallélisation du code. Pour ceux qui n’ont jamais fait de programmes parallèles, vous allez découvrir que vous pouvez probablement paralléliser une partie de vos programmes avec très peu d’effort.

Il est à noter que les implémentations d’OpenMP existent pour les langages C/C++ et Fortran. Dans la suite de cet article, je n’évoquerai que l’API C/C++ d’OpenMP.

2.1 Principe de fonctionnement

Lorsque l’on envisage de paralléliser tout ou partie d’un algorithme, il faut identifier les blocs d’instructions qui sont complètement indépendants entre eux, ceux qui ne le sont que partiellement et ceux qui ne le sont pas du tout.

Un exemple simple d’algorithme permettant de calculer la moyenne d’une série de 20 valeurs :

En l’état, cet algorithme paraît difficilement parallélisable, et pourtant l’étape 1 peut être clairement parallélisée en se rappelant que la moyenne de 20 valeurs peut être obtenue en calculant indépendamment d’un côté la somme S₁ des 10 premières valeurs et d’un autre côté la somme S₂ des 10 dernières valeurs, puis en sommant S₁ et S₂. La somme S₁ peut également se décomposer en sommant les 5 premières valeurs d’un côté (somme S_1a) et les 5 suivantes de l’autre (somme S_1b), et ainsi de suite. Cependant, l’implémentation d’un tel algorithme (appelé « réduction ») demeure fastidieuse alors que cette décomposition reste assez courante et s’adapte à d’autres opérations (trouver le maximum parmi un ensemble de valeurs, calculer leur produit…).

L’idée d’OpenMP (en tout cas, l’idée que moi j’en ai), c’est de faire ce travail pour vous en expliquant juste au compilateur que cette partie doit être parallélisée en faisant une réduction.

Pour cela, OpenMP définit d’une part des directives et schémas de constructions et d’autre part des fonctions. Les directives sont des pragmas qui sont analysés par le préprocesseur et qui réécrivent les blocs d’instruction concernés selon le schéma de construction spécifié par la directive. Les fonctions permettent d‘écrire des instructions spécifiques lorsqu’aucun schéma de construction ne correspond.

Ainsi, l’algorithme de calcul de la moyenne précédent peut se réécrire :

C’est de la magie où je ne m’y connais pas, Bibbidi Babbidi Bou [5].

2.2 Installation

Si vous êtes frustrés de ne pas encore avoir eu de code C++ sous les yeux, c’est probablement que j’ai réussi à vous mettre l’eau à la bouche… Encore un peu de patience, ça va venir. Mais avant cela, il faut installer la librairie de développement OpenMP pour le compilateur gcc/g++.

Pour les chanceux qui utilisent une distribution Debian/Ubuntu, rien de plus simple :

Et si vous voulez installer les symboles de debuggage (typiquement pour une utilisation de gdb ou de valgrind) :

Pour les autres distributions, il faudra chercher sur les forums dédiés à vos distributions.

Si vous envisagez d’utiliser un autre compilateur, alors il faudra également chercher sur les forums dédiés.

Les chanceux sont donc ceux qui n’ont pas besoin de chercher sur les forums :-p.

2.3 L’exemple qui ne sert à rien, mais qui sert quand même

Pourquoi faire un exemple qui ne sert à rien quand on peut en faire plusieurs ?

Tout d’abord, notre premier exemple a pour objet de vérifier que le compilateur (ou plus précisément l’éditeur de lien) résout correctement la liaison avec la librairie OpenMP.

Commençons par créer un fichier helloworld.cpp assez rudimentaire :

Compilons-le avec une ligne de commande tout aussi rudimentaire :

Si tout se passe bien, vous n’avez aucun avertissement sur la sortie standard (je laisse le soin aux lecteurs dubitatifs d’aller regarder l’intérêt des options -Wall, -ansi et -pedantic qui ne sont pas l’objet de cet article). Vous remarquerez l’option -fopenmp qui signifie tout simplement de gérer les directives OpenMP.

Exécutons ce programme avec quelques arguments et voyons ce que l’on obtient :

Bon, c’était vraiment un exemple qui ne sert pas à grand-chose. Mais nous allons le modifier afin de paralléliser les itérations de la seule et unique boucle du programme. Après tout, chaque itération est indépendante et les zones mémoires accédées sont distinctes et peuvent donc être traitées en parallèle…

Pour cela, on insère avant la boucle une directive OpenMP (#pragma omp) indiquant d’utiliser le schéma de construction de boucle pour paralléliser (parallel for) :

On compile comme précédemment et on exécute avec les mêmes arguments et on observe une sortie réellement chaotique !!!

C’est vrai que vu sous cet angle, ça valait vraiment le coup de paralléliser cette boucle. Que se passe-t-il ? Et bien tout simplement, chaque tour de boucle est exécuté en parallèle et donc l’affichage aussi. Tous les processus légers écrivent en même temps sur la sortie standard (qui est une variable partagée, contrairement à ce qui est écrit précédemment, zut alors !!!). Il faut donc protéger l’instruction d’écriture sur la sortie standard en réclamant un MutEx, ou mieux en expliquant à OpenMP que l’instruction est une instruction critique.

On retrouve bien l’accès à la variable commune (cout) protégée comme étant une section critique. Après compilation et exécution, on a le résultat attendu :

2.4 Retour en arrière : compiler sans OpenMP

Un des gros inconvénients d’une exécution en parallèle est que cela peut devenir assez rapidement difficile à debugger. Fort heureusement, désactiver OpenMP à la compilation est assez facile, il suffit de compiler sans l’option -fopenmp. Dans ce cas, vous obtiendrez quelques avertissements :

Si comme moi vous avez du mal avec les compilations qui émettent des avertissements (c’est sale, beurk) il est possible d’utiliser un mécanisme de compilation conditionnelle afin de n’utiliser les directives OpenMP que lorsque l’option -fopenmp est fournie. En effet, OpenMP définit la macro _OPENMP (qui contient l’année et le mois au format yyyymm de la spécification supportée par l’implémentation courante).

Ainsi, un beau code intégrant des directives OpenMP qui ne sert donc toujours à rien ressemblerait à :

Compilez ce code avec et sans l’option -fopenmp et vous verrez que vous n’aurez aucun avertissement.

2.5 Quelques fonctions OpenMP bien pratiques

Outre les directives, OpenMP propose également quelques fonctions assez utiles, telles que :

• omp_get_max_threads(), qui renvoie le nombre maximum de processus légers qui pourront être déclenchés après l’appel de cette fonction ;
• omp_get_num_procs(), qui renvoie le nombre de processeurs disponibles sur la machine au moment de l’appel ;
• omp_get_num_threads(), qui renvoie le nombre de processus légers correspondants à un bloc d’instruction ;
• omp_get_thread_num(), qui renvoie le numéro d’un processus léger dans un bloc parallèle.

Ces fonctions sont déclarées dans le fichier omp.h qu’il faudra bien évidemment inclure pour pouvoir les utiliser.

2.6 Quelques schémas de construction bien pratiques

Nous allons revenir au premier algorithme permettant de calculer la moyenne de 20 valeurs, et bien évidemment ne pas commencer par se restreindre à exactement 20 valeurs.

Le programme prendra donc comme valeurs les arguments qui lui seront passés, les stockera dans un vecteur, calculera la moyenne puis l’affichera sur la sortie standard.

On commence par inclure les déclarations qui nous seront utiles :

On déclare utiliser l’espace de nommage standard (histoire de ne pas préfixer par std:: ce que l’on utilisera de cet espace) :

La fonction moyenne permet de prendre un vecteur de réels double précision (paramètre passé en référence constante, car on travaillera sur l’original plutôt qu’une copie et qu’on ne modifiera en aucun cas les valeurs de ce vecteur). On récupère la taille du vecteur dans une variable n, on initialise la somme à 0 dans la variable res, puis on lance le calcul de la somme en appliquant le schéma de conception de boucle pour paralléliser avec réduction de l’opérateur + sur la variable res. Dit autrement, chaque itération sera traitée par un processus léger, qui travaillera sur une copie de la variable res (qui vaut donc 0), puis les copies seront sommées par réduction (sommes partielles et récurrences).

Enfin, le programme principal s’assure dans un premier temps d’avoir au moins un argument (c’est toujours mieux pour calculer une moyenne). On crée un vecteur de réels v de la taille du nombre d’arguments passés en option (le -1 provient du fait que le nom du programme n’est pas à prendre en compte dans le décompte).

La lecture des arguments est faite en parallèle, mais on limitera le nombre de processus simultanés à 3 (clause num_threads(3)). On en profite pour ajouter un peu d’infos de debuggage qui nous permettent d’utiliser deux des fonctions présentées précédemment.

Pour changer, on compile et on teste avec quelques valeurs :

C’est cohérent.

2.7 Aller plus loin…

Comme vous l’aurez compris, une directive OpenMP s’écrit sous forme d’un pragma juste avant l’instruction concernée. Si on souhaite faire porter une directive sur un bloc d’instruction, il suffit d’encapsuler le bloc d’instruction entre accolades.

L’objet de cet article n’est pas de détailler l’API complète d’OpenMP, mais d’illustrer son utilisation. Si vous avez compris le principe de fonctionnement, il ne vous reste qu’à lire la « summary card » disponible sur le site d’OpenMP [4] pour avoir la liste exhaustive des directives, schémas de construction et fonctions disponibles.

3. MPI

Contrairement à la parallélisation légère, la parallélisation lourde implique surtout de prévoir un protocole de communication entre les différents processus. C’est ce que propose le standard MPI (Message Passing Interface) [6].

3.1 Open MPI

Il existe plusieurs implémentations du standard MPI. Comme vous l’aurez compris, Open MPI [7] est une implémentation libre et open source de ce protocole. Il en résulte qu’en théorie, je parlerai tout autant de MPI que d’Open MPI (et que de toute autre implémentation) dans la suite.

Écrire un programme avec Open MPI se résume à trois grandes étapes :

1. Initialisation de la communication entre les processus ;
2. Instructions à exécuter ;
3. Terminer la communication entre les processus.

Au sein d’un groupe de communication, certaines fonctions de MPI nécessitent que tous les processus du groupe communiquent ensemble. Ces routines sont dites collectives. A contrario, certaines fonctions peuvent s’exécuter indépendamment de tout ou partie des autres processus. Ces routines sont alors dites non collectives.

Une des difficultés existantes que l’on rencontre fréquemment lorsque l’on établit des communications entre processus, c’est le blocage de la communication. Cela peut se produire si deux (ou plusieurs) processus parlent en même temps. MPI définit deux catégories de communications. Les communications synchrones (i.e., si Mickey parle à Dingo – Pluto c’est son chien – alors Dingo doit écouter Mickey, et seulement ensuite Mickey peut s’occuper de Pluto) des communications asynchrones (i.e., si Mickey parle à Dingo, Dingo pourra écouter son message plus tard, cela n’empêche pas Mickey d’aller plus tôt s’occuper de Pluto).

3.2 La documentation

C’est ici que les choses se compliquent. Jusqu’à présent, je n’ai jamais trouvé de tutoriel satisfaisant sur MPI (sauf pour dire bonjour au monde et calculer des moyennes, ce qui n’est quand même pas très passionnant – sauf quand c’est vraiment bien écrit ;-) ) et la documentation disponible sur le site d’Open MPI [7] manque clairement d’exemples (on dirait mes documentations de code – et je documente le minimum syndical). Donc il reste surtout à tester, coder, debugger et re-tester.

3.3 Installation

Pour les moyennement chanceux qui utilisent une distribution Ubuntu, rien de plus simple pour avoir une version relativement obsolète :

Ceux qui sont sous Debian (sid) auront la chance d’avoir la dernière version. Ceci étant, à partir de la version 1.8.0 d’Open MPI, tout ce dont nous aurons besoin pour cet article est fonctionnel. Au moment de la rédaction de cet article, j’utilise la version 1.10.2 (package officiel de la distribution Ubuntu 16.04). Rien n’interdit bien évidemment de télécharger les sources, de les compiler et de les installer.

Pour les autres distributions, il faudra chercher sur les forums dédiés à vos distributions.

Si vous envisagez d’utiliser un autre compilateur, alors il faudra également chercher sur les forums dédiés.

À noter également que depuis la version 2.0.0, les numéros majeurs et mineurs de version d’Open MPI correspondent aux spécifications de MPI. Enfin, les liaisons syntaxiques du C++ (bindings) sont déconseillées depuis la version 2.2 de la spécification (c’est dommage, j’aime bien ce sucre syntaxique) et ne seront plus implémentées pour les nouvelles fonctionnalités. Dans cet article, les codes Open MPI fournis utiliseront la syntaxe C++ quand celle-ci est disponible. Si vous installez vous-même Open MPI à partir des sources (récentes), pensez à passer l’option ‑‑enable‑mpi‑cxx au script ./configure.

3.4 L’exemple qui ne sert à rien, mais qui sert quand même

Un bel exemple qui ne sert à rien : lancer des processus qui disent simplement bonjour.

La routine MPI::Init() permet d’initialiser la communication entre les processus (c’est typiquement une routine collective). Cela permet notamment de créer un communicateur universel MPI::COMM_WORLD qui permettra à tous les processus de communiquer. Chaque processus peut récupérer son rang (méthode Get_rank()) au sein d’un communicateur (entre 0 et n-1 pour n processus), ainsi que le nombre total de processus de ce communicateur (méthode Get_size()).

Chaque processus peut également récupérer le nom de la machine sur laquelle il est exécuté (MPI::Get_processor_name()), la version de la librairie Open MPI installée (MPI_Get_library_version()) ou encore la version du standard MPI que cette librairie implémente (MPI::Get_version()).

Enfin, la fin de la communication est actée par la routine (MPI::Finalize()).

La compilation d’un programme utilisant Open MPI doit être effectuée via un compilateur dédié (en réalité, c’est une surcouche de votre compilateur préféré) : mpic++ alias mpicxx (pour le C++) ou mpicc (pour le C). Ce compilateur exploite pleinement les variables d’environnement usuelles CXX/CC pour le compilateur à utiliser en interne.

Donc pour compiler notre programme :

Si on l’exécute (un peu bêtement), on obtient une instance qui affiche les informations demandées :

Eh oui, ma machine s’appelle spartacus (parce que c’est une bête de compét’), mais ce n’était pas ça la bonne question. La bonne question était : mais comment lance-t-on plusieurs processus ? Pour cela, il faut utiliser le programme mpirun, dont la syntaxe est mpirun [options mpirun] <programme> [args prog].

L’option -np permet de spécifier le nombre de processus à lancer. Il est également possible de spécifier plusieurs hôtes possibles (machines devant être accessibles en réseau et disposer du même programme – typiquement sur un lecteur réseau) avec l’option -host, ou encore de fournir un fichier contenant ces informations, et bien d’autres possibilités de configuration encore.

C’est bien beau tout ça, mais si on faisait des processus qui communiquent, ce serait mieux…

Donc je propose d’attaquer un autre exemple qui ne sert à rien : calculer (inefficacement) la moyenne d’une série de notes !

Pour cela, détaillons l’écriture du fichier moyenne-mpi.cpp, qui commencera comme il se doit par quelques inclusions :

La première ligne permet d’inclure toute l’API Open MPI. La seconde nous permettra de faire des entrées/sorties (donc ici surtout des sorties). Les troisième et quatrième lignes serviront respectivement à transformer les arguments (chaînes de caractères) en réels, enregistrer des fonctions à exécuter à la fin du programme et à récupérer le nom du programme (un petit man 3 atof / man 3 atexit / man 3 basename devrait suffire à comprendre l’utilisation de ces fonctions). Enfin, nous allons stocker (choix plus que discutable) les valeurs passées en argument dans des vecteurs.

Afin de ne pas nous embêter à préfixer les objets/fonctions de l’espace de nom std, nous allons expliquer que nous utiliserons cet espace de nom :

Pour calculer la moyenne, il faut d’abord calculer la somme d’une série de valeurs :

La fonction somme() prend en entrée une référence constante sur un vecteur de réels double précision (ainsi le vecteur en entrée ne sera pas recopié et nous garantissons qu’il ne sera pas modifié).

Au passage, nous nous assurerons que la fonction somme() est appelée après que l’environnement MPI a été initialisé (vérification à la ligne 11 ; si le test échoue – donc que l’environnement n’est pas initialisé – alors on lance une exception (ligne 12)). Le reste du code est somme toute assez classique.

Je profite de cet article pour présenter une astuce permettant de finaliser proprement les communications MPI quelle que soit la raison mettant fin aux instances. Pour cela, il suffit de définir une fonction ne prenant aucun paramètre et ne renvoyant rien, dont le corps contient le code qui devra être exécuté à la fin de l’exécution du programme :

Puis, après avoir initialisé la communication Open MPI, il suffit d’empiler cette fonction dans les fonctions à exécuter à la fin du programme.

Comme dans le précédent exemple, il est de bon ton de récupérer le rang du processus courant et le nombre total de processus qui tournent en parallèle :

Nous nous assurons que le programme (ou plutôt les programmes) a été appelé avec au moins un argument, ce qui est toujours mieux pour calculer une moyenne. Dans le cas contraire, seul le processus ayant le rang 0 (et celui-ci existe nécessairement) affichera un message d’usage sur la sortie d’erreur. Le programme renverra 1 au système pour signifier un fonctionnement anormal et du fait de l’utilisation de la fonction atexit() à la ligne 31, nous avons la garantie que tous les processus termineront correctement la session MPI.

Si le programme arrive jusqu’ici, c’est qu’au moins un argument a été saisi. Nous allons donc commencer à identifier quel processus travaillera sur quelles données… Nous savons que le programme a été lancé avec argc arguments, incluant le nom de l’exécutable. Ainsi le nombre de valeurs à traiter est égal à (argc – 1). Nous savons également qu’il y a nb_process en cours d’exécution pour traiter ces valeurs. Nous allons donc répartir ces valeurs équitablement sur chacun des processus. Chaque processus aura au moins q (= (argc – 1) / nb_process) valeurs à traiter. Il reste r (= (argc – 1) % nb_process) à répartir sur les processus (calculs des lignes 45 et 46). Arithmétiquement, r est strictement inférieur à nb_process. Aussi, chaque processus ayant un rang (rank) strictement inférieur à r traitera q + 1 valeurs et chaque processus ayant un rang supérieur ou égal à r traitera q valeurs (calcul de la valeur vec_size à la ligne 47). Il reste à calculer l’indice de la première valeur à traiter par le processus au rang rank. Si rank est strictement inférieur à r, alors les processus précédents traiteront (q + 1) * rank valeurs. Si rank est supérieur ou égal à r, alors les processus précédents traiteront (q * rank + r) valeurs. Ces calculs se factorisent assez facilement à la ligne 48. Nous en profitons pour afficher une sortie de debuggage indiquant l’intervalle des indices traités par le processus en cours (lignes 50 à 53).

Maintenant que chaque processus connaît son nombre de valeurs à traiter ainsi que l’indice de la première valeur à traiter, nous construisons un vecteur de la bonne dimension (ligne 55) que nous initialisons en convertissant les arguments de la ligne de commandes (chaînes de caractère C) en réels (lignes 57 à 59).

Chaque processus est ainsi capable de calculer la somme des valeurs dont il assure le traitement dans la variable m. Nous aurons également besoin d’une variable m2 pour calculer la réduction de la somme à travers tous les processus (l’initialisation à 0 n’est pas une nécessité dans l’absolu, mais cela fait partie de mes bonnes pratiques de programmation).

La réduction passe simplement par l’appel (ligne 63) de la méthode Reduce de l’objet MPI::COMM_WORLD (qui est le communicateur universel). Le premier argument est l’adresse de la zone mémoire contenant les valeurs initiales. Le second argument est l’adresse de la zone mémoire qui contiendra le résultat de la réduction. Le troisième argument définit le nombre de valeurs initiales fournies par le processus (donc ici, nous n’avons qu’une seule valeur) et le quatrième argument définit le type de valeurs à réduire (ici, le type double (MPI_DOUBLE) – voir encadré sur les types de données échangeables entre les processus MPI). Le cinquième argument définit la réduction à appliquer (ici, une somme (MPI_SUM) – voir encadré sur les types de réductions proposées entre les processus MPI). Enfin, le dernier argument spécifie le rang du processus qui récupèrera le résultat de l’opération de réduction (ici le processus 0 – qui existe nécessairement).

Enfin, toujours à des fins de debuggage, nous afficherons les valeurs calculées/récupérées dans les variables m et m2 pour le processus courant.

Il est à noter que chaque processus travaille à son rythme. Toutefois, les opérations collectives (Init, Reduce, Finalize…) imposent aux processus de s’attendre mutuellement. Toutefois, avant d’afficher le résultat final du calcul de la moyenne, il est préférable de s’assurer que tous les processus ont fini d’écrire les informations de debuggage (lignes 65 à 68). Pour cela, il suffit de poser une barrière (ligne 70), c’est-à-dire une opération collective qui ne fait rien de plus que d’empêcher un processus de poursuivre tant que tous les autres processus ne sont pas au même point du programme.

L’usage de barrières est pratique, puisqu’il permet de synchroniser l’exécution des processus, toutefois – et l’analogie avec la barrière est très pertinente – cela les ralentit également. Ainsi, mettre une barrière juste avant l’opération de réduction ne présente aucun intérêt puisque la réduction elle-même fait office de barrière. De même, si le code de debuggage (lignes 65 à 68) est à terme supprimé, alors la barrière de la ligne 70 ne présente plus aucune utilité non plus.

Revenons au calcul de la moyenne. Suite à l’opération de réduction, seul le processus de rang 0 connaît le résultat de la réduction (on aurait pu utiliser la méthode Allreduce qui distribue le résultat à tous les processus, mais dans le cas présent, cela n’aurait rien apporté). Seul le processus de rang 0 (ligne 72) va donc diviser la somme globale par le nombre de valeurs (ligne 73 ; je rappelle à toutes fins utiles que nous avons garanti que argc est supérieur ou égal à 2 – ligne 36 – et donc que (argc – 1) est non nul). Enfin, ce processus va afficher la moyenne sur la sortie standard.

Il reste à remercier une fois de plus la fonction atexit de faire le travail de finalisation de la communication MPI tout en renvoyant 0 au système d’exploitation pour lui signifier que le programme s’est correctement exécuté.

Compilons maintenant ce programme :

Et exécutons-le d’abord sans MPI :

Cela semble fonctionner (c’est heureux).

Essayons maintenant dans l’environnement MPI, avec un seul processus :

On obtient le même résultat, ce qui est plutôt rassurant.

Augmentons le nombre de processus, si possible avec une valeur qui ne soit pas un diviseur de 8 pour éviter de tomber dans un cas trop particulier :

On peut vérifier que nos 8 valeurs sont correctement réparties sur les 3 instances. On s’aperçoit également que seul le processus de rang 0 connaît la valeur de m2 (tous les autres n’ont pas modifié la valeur par défaut de m2 – quelle bonne habitude de programmation que de systématiquement initialiser ses variables ;-) ).

La question que nous avons jusqu’alors passée sous silence est de savoir ce qu’il se passe si nous exécutons notre programme avec plus d’instances que de valeurs. Eh bien, théoriquement ça fonctionne, puisque dans ce cas, les premiers processus auront une seule valeur à traiter et les suivants n’en auront pas. Vérifions rapidement :

Cela fonctionne encore. C’était un petit pas dans le calcul de la moyenne, mais un grand pas dans le calcul distribué.

4. OpenMP ou Open MPI ?

La question qui pourrait se poser maintenant serait de savoir s’il est préférable d’utiliser OpenMP plutôt qu’Open MPI, ou inversement. Je pourrais faire une réponse de normand en expliquant que cela dépend du contexte, et c’est finalement la seule véritable bonne réponse, mais dans le cas présent, l’objectif est d’illustrer les deux paradigmes. Par conséquent, la réponse sera pour cet article de ne pas les opposer, mais de les utiliser conjointement (le « ou » n’étant pas exclusif en français, le titre de cette section n’est donc finalement pas fallacieux).

4.1 Parallélisme hybride

Pour cela, nous allons reprendre les codes précédents et les fusionner allègrement sans nous poser trop de questions.

Plutôt que de détailler le code, je commenterai le fichier de patch créé à partir de la commande :

Pour ceux qui ne sont pas familiers de cette commande (pourtant bien pratique), le premier élément composant la sortie du diff (avec l’option --unified) est l’indication des fichiers concernés par le différentiel ainsi que leurs dates respectives de dernière modification. Le premier fichier est préfixé de --- et le second de +++. Dans la suite, chaque ligne présente uniquement dans le premier fichier sera préfixée d’un - et chaque ligne présente uniquement dans le second fichier sera préfixée d’un +. Autour de chaque différence, un contexte de 3 lignes identiques est également affiché, les lignes sont alors préfixées d’un espace.

Ensuite, chaque bloc de différence commence par un entête entre @@. Cet entête précise les numéros de la première ligne de chaque bloc et le nombre de lignes correspondant dans chaque fichier (le - et le +).

Le premier bloc de différence montre que j’ai ajouté l’inclusion du fichier omp.h.

Le second bloc montre que la boucle permettant de calculer la somme des valeurs du vecteur v (dans la fonction somme) est parallélisée avec un schéma de réduction par OpenMP.

Le troisième et dernier bloc montre que l’initialisation du vecteur v (dans la fonction main) est parallélisée avec 3 processus légers et qu’une information de debuggage est affichée.

Outre une lecture centrée sur les différences entre les deux fichiers, ce fichier peut être utilisé par la commande patch pour créer le fichier moyenne-hybride.cpp à partir du fichier moyenne-mpi.cpp.

Il reste à compiler notre nouveau programme (sans oublier l’option -fopenmp) :

Puis à exécuter notre programme (sans mpirun) :

Puis avec mpirun :

That’s (presque) All, Folks !!!

4.2 Et dans la vraie vie ?

Quelle question ! Vous lisez GLMF, vous êtes donc dans la vraie vie… En tout cas, c’est ce qu’aurait pu dire un certain Blaise P. s’il avait vécu à notre époque. Toutefois, j’ai volontairement omis une complication majeure liée à la programmation hybride avec OpenMP et Open MPI.

En effet, il n’y a pas de soucis tant que la parallélisation légère n’émet ni ne reçoit de messages MPI. Là où cela se complique, c’est effectivement lorsqu’au moins un parmi plusieurs processus légers d’un même processus lourd doit communiquer dans l’univers MPI. Dans ce cas, l’initialisation MPI doit être effectuée avec MPI::Init_thread() au lieu de MPI::Init(). La méthode statique MPI::Init_thread() – à l’instar de la méthode statique MPI::Init() – existe en deux versions, l’une qui prend en paramètres les arguments argc, argv de la fonction main (et ne s’en sert absolument pas) et une qui ne les prends pas. Cependant, contrairement à la méthode statique MPI::Init(), la méthode statique MPI::Init_thread() requiert un argument supplémentaire qui correspond au niveau de parallélisme léger supporté. Les quatre niveaux proposés sont représentés par quatre constantes :

MPI_THREAD_SINGLE	Un seul processus léger est exécuté (donc pas de parallélisme léger – a minima lors des communications MPI).
MPI_THREAD_FUNNELED	Seul le processus léger qui a appelé la méthode MPI::Init_thread() communiquera dans l’univers MPI.
MPI_THREAD_SERIALIZED	Lorsque plusieurs processus légers sont en cours d’exécution, un seul parmi eux communiquera dans l’univers MPI.
MPI_THREAD_MULTIPLE	Tous les processus légers peuvent communiquer parallèlement dans l’univers MPI.

Bien évidemment, plus le niveau autorise des opérations de communication complexes, plus cela impacte les performances.

Comme vous l’aurez compris, l’appel de MPI::Init() équivaut à l’appel de MPI::Init_thread() au niveau MPI_THREAD_SINGLE.

Là où les choses se compliquent encore, c’est que toutes les implémentations de MPI ne gèrent pas nécessairement le 4^e niveau (qui crée des complications qui ne sont pas nécessairement encore très bien gérées). Le cas échéant, l’initialisation se fera au 3^e niveau.

Pour savoir si votre implémentation d’Open MPI supporte le niveau MPI_THREAD_MULTIPLE, il suffit de le lui demander :

Comme vous pouvez le constater, chez moi, je n’ai pas cette chance…

Mais vous imaginez bien que le programme doit pouvoir détecter si le niveau demandé est supporté pour éventuellement afficher un message d’avertissement, dérouler une stratégie alternative, ou tout simplement quitter proprement. C’est pour cette raison que la méthode statique MPI::Init_thread() retourne la valeur du niveau qui a été réellement utilisé par l’initialisation.

Ainsi, un code judicieux dans ce cas serait :

Notez au passage que cet exemple m’a permis de subrepticement glisser la méthode Abort() du communicateur MPI::COMM_World dont l’intérêt réside dans l’arrêt de tous les processus, y compris de ceux qui travaillaient tranquillement sans rencontrer de problème particulier.

Conclusion

Bien évidemment, certains langages intègrent plus ou moins implicitement et naturellement les paradigmes de parallélisme, tels que NodeJS ou Go. Comme toujours, le choix du langage doit dépendre des objectifs et non de notre champ de compétence ou de notre affinité. Ce n’est pas parce que je n’aime pas le Java que je m’interdis de programmer dans ce langage (bon, c’est un mauvais exemple parce qu’il y a toujours une alternative préférable Java :-p).

Ceci étant, si le problème que l’on souhaite résoudre est simple et ne nécessite que peu de ressources matérielles, le choix reste assez libre. Dès lors que le volume de données à traiter devient colossal (ère du Big Data) le besoin de performance devient primordial et le passage à des langages tels que le C++ voire le C (qui contrairement à ce que l’on peut lire parfois – y compris dans d’illustres revues comme GNU/Linux Mag, Linux Pratique HS… – est un langage de haut niveau) sont une nécessité et les implémentations des standards OpenMP et Open MPI sont clairement opportunes.

Références

[1] « Qu’est-ce qu’un algorithme ? » Philippe Flajolet et Étienne Parizot (http://interstices.info/jcms/c_5776/qu-est-ce-qu-un-algorithme)

[2] « Comme d’habitude », novembre 1967. Chanson écrite par Gilles Thibaut et Claude François, musique de Jacques Revaux et Claude François.

[3] http://en.cppreference.com/

[4] http://www.openmp.org/

[5] « Bibbidi-Bobbidi-Boo », 1950. Chanson écrite et composée par Mack David, Al Hoffman et Jerry Livingston pour le long-métrage Disney Cendrillon.

[6] http://www.mpi-forum.org/

[7] http://www.open-mpi.org/