Programmation sur un cluster : calculer pi avec MPI
icone programmation
Signature :
GNU/Linux Magazine
Sommaire de l'article :

Retrouvez cet article dans : Linux Magazine 89

Ne vous êtes-vous jamais demandé comment font les scientifiques et informaticiens pour faire tourner un unique calcul sur les centaines de nodes des clusters dont on entend régulièrement parler ? Ou peut-être vous demandez-vous comment faire pour utiliser toute la puissance de vos multiples machines personnelles pour effectuer un même calcul ? Ou encore voulez-vous peut-être impressionner vos amis ? ;) Quelles que soient vos motivations, cet article vous introduira les concepts d’algorithmes parallèles et de cluster, ou comment exécuter un programme sur plusieurs machines en parallèle. En guise d’exemple, nous expliquerons comment calculer pi sur un cluster avec MPI : des connaissances en langage C sont préférables.

L’idée de combiner la puissance de plusieurs machines/processeurs pour effectuer un même calcul existe depuis longtemps. C’est nécessaire lorsqu’il n’existe pas de matériel individuellement assez puissant, et peut-être intéressant financièrement, car il est souvent moins cher d’utiliser beaucoup de matériel standard/bas de gamme qu’un gros super-calculateur ou le processeur dernier cri. Pour vous en convaincre, sachez que c’est la stratégie choisie par Google : des dizaines voire centaines de milliers de petites machines un peu partout dans le monde plutôt que quelques milliers de super-calculateurs. Cependant, ce choix n’est pas anodin au niveau de la programmation, car les algorithmes doivent être adaptés au calcul parallèle. Paralléliser n’est pas non plus toujours intéressant en fonction du calcul à effectuer et de l’architecture matérielle, car les performances peuvent chuter drastiquement dans certains cas. Dans cet article, nous introduirons des notions sur le calcul parallèle et les illustrerons grâce à un exemple : le calcul de pi. Ce sera aussi l’occasion de découvrir MPI (Message-Passing Interface), qui est une bibliothèque destinée à l’envoi et réception de messages (ou données) pour les calculs distribués et les clusters.

Le calcul parallèle

Calcul séquentiel, calcul parallèle

Une architecture séquentielle peut être définie comme la combinaison d’un processeur avec de la mémoire (mémoire vive, disque dur...). Il s’agit d’un ordinateur personnel " standard " mono-processeur, où toutes les instructions d’un programme sont exécutées les unes après les autres. Une architecture parallèle correspond à un ensemble de processeurs qui coopèrent pour effectuer un même calcul. Les instructions d’un programme tournant sur une telle architecture sont alors exécutées en parallèle, simultanément sur tous les processeurs.

Les architectures matérielles

Il existe un certain nombre de critères visant à comparer les architectures matérielles du point de vue du parallélisme, avec en particulier l’organisation de la mémoire et du réseau d’interconnexion. La mémoire d’une architecture parallèle peut être distribuée, auquel cas chaque processeur dispose de sa propre mémoire avec son propre espace d’adressage. La communication entre processeurs se fait alors par " messages " envoyés par le réseau d’interconnexion. L’alternative est d’avoir un seul espace d’adressage mémoire partagé, ce qui est par exemple le cas pour les machines multiprocesseurs. Cet espace d’adressage partagé peut être implémenté à l’aide d’une banque mémoire unique, auquel cas on parle d’Uniform Memory Access (UMA), car tous les processeurs ont le même temps d’accès pour toute la mémoire, ou bien à l’aide de mémoire distribuée à chaque processeur, ce qui correspond à la Non-Uniform Memory Access (NUMA), où un processeur met moins de temps à accéder à la mémoire qui lui est rattachée qu’au reste de la mémoire (on peut aussi avoir des hiérarchies plus complexes pour les temps d’accès à la mémoire). Pour les réseaux d’interconnexion, on distingue les réseaux statiques (ou directs), où les communications entre processeurs/nœuds se font point à point avec un câble reliant directement les deux machines, des réseaux dynamiques (ou indirects), où les connexions entre processeurs sont construites dynamiquement, par exemple par un switch. Dans les cas des réseaux statiques, chaque nœud peut être relié à tous les autres nœuds (nœuds " complètement connectés "), ce qui est l’idéal pour les performances, mais difficilement réalisable en pratique, ou les nœuds peuvent être reliés par des réseaux en anneau ou en grille (ou autre), auquel cas un message peut avoir à passer par plusieurs nœuds avant d’arriver à son destinataire. Dans cet article, nous nous placerons dans le cas d’un cluster, c’est-à-dire d’une grappe d’ordinateurs " standards " reliés par un réseau commuté et fonctionnant ensemble pour réaliser un calcul. La mémoire est donc distribuée, chaque ordinateur ayant sa propre mémoire avec son propre espace d’adressage.

Performance

Paralléliser un algorithme induit une surcharge (overhead) dont la principale cause provient des latences dans les communications entre processeurs. En effet, il est beaucoup plus long pour un nœud d’envoyer/recevoir un message par le réseau que de l’écrire/lire dans sa mémoire. Or ce temps n’est pas directement utilisé pour faire le calcul et n’est rendu nécessaire que par le fait que l’algorithme a été parallélisé. Le temps nécessaire à l’envoi d’un message dépend de sa taille, du débit du réseau, du nombre de sauts pour arriver à sa destination, et de la méthode utilisée pour envoyer un message. Par exemple, dans le cas de la méthode store-and-forward, où un nœud attend d’avoir totalement reçu un message avant de le transmettre au nœud suivant, le temps d’envoi d’un message peut être calculé par la formule suivante :

 

/img-articles/lm/89/art-7/fig-1.jpg

 

avec Tcomm le temps de communication, Ts le temps de démarrage (préparation du message et initialisation de la route, ce qui arrive une seule fois par message), m la taille du message, Tw le temps d’envoi par mot sur un lien (ce qui est directement lié au débit du lien), Th le temps de latence par saut (ce qui se produit pour chaque lien direct processeur à processeur), et l le nombre de sauts pour arriver à destination. A partir d’une telle formule, on peut calculer le temps de différentes opérations fréquemment utilisées pour faire des calculs parallèles, comme l’envoi d’un message d’un processeur à un autre, la diffusion un-vers-tous (one-to-all) ou tous-vers-tous (all-to-all broadcast). On définit plusieurs mesures pour quantifier la performance d’un algorithme parallèle. Le Speed-Up Sp (avec p le nombre de processeurs), tout d’abord, est le facteur d’accélération du calcul en le parallélisant, défini par :

 

 

 

/img-articles/lm/89/art-7/fig-2.jpg

avec T1 temps d’exécution du meilleur algorithme séquentiel sur un unique processeur et Tp le temps d’exécution de l’algorithme parallèle sur p processeur. L’efficacité Ep, quant à elle, est la fraction de temps durant laquelle un processeur fait du travail utile (par opposition à la surcharge de travail provoquée par la parallélisation de l’algorithme) et se calcule ainsi :

/img-articles/lm/89/art-7/fig-3.jpg

Idéalement, chaque processeur ne fait que du travail utile et l’efficacité vaut donc 1.

Présentation de MPI

Introduction

MPI (Message-Passing Interface) est une spécification pour des bibliothèques destinées à l’envoi de messages : elles facilitent en particulier la communication entre processus dans un cluster et ainsi le développement de programmes destinés à tourner sur un cluster. Une telle bibliothèque contient, par exemple, des fonctions pour envoyer des données d’un processus à un autre (" Le résultat de ma partie des calculs est 33 "), qu’ils soient exécutés sur la même machine ou non, ou encore la synchronisation entre les processus (" Je suis prêt, tu peux m’envoyer les données "). Il existe plusieurs implémentations de MPI, avec en particulier LAM et MPICH. Nous utiliserons ce dernier dans cet article. En plus de la bibliothèque MPI elle-même, MPICH inclut des logiciels destinés à la compilation ou l’exécution des programmes parallélisés. C’est grâce à eux que vous pourrez lancer un programme sur un ensemble de machines presque comme si vous le lanciez sur une seule. MPI est assez similaire à PVM (Parallel Virtual Machine) dans ses objectifs et sa réalisation. Cependant, MPI a certaines particularités intéressantes, comme une spécification complète et plusieurs implémentations indépendantes, le déterminisme ou une communication entre processus plus avancée (voir [2]). MOSIX (voir [6]), quant à lui, a une approche un peu différente. En effet, MOSIX a pour but de faire apparaître, à un programme, un cluster comme une seule machine multiprocesseur. Il n’est notamment pas nécessaire d’utiliser une API spécifique pour programmer le logiciel pour le cluster – les classiques threads suffisent –, ni même de compiler ce logiciel avec des outils MOSIX. Par contre, MOSIX requiert un noyau particulier pour arriver à cette transparence du point de vue programme utilisateur. MOSIX gère aussi les migrations de threads/processus entre nœuds du cluster de façon à équilibrer la charge automatiquement. MOSIX requiert donc une installation et configuration plus longue et complexe, mais ne nécessite pas de modifications des applications – à condition qu’elles soient déjà multithreadées. MOSIX paraît plus adapté lorsque les machines du cluster peuvent aussi être utilisées indépendamment du cluster, par exemple pour faire tourner des calculs coûteux sur les ordinateurs personnels d’une entreprise lorsqu’ils sont inutilisés, tandis que PVM et MPI sont plutôt destinés aux clusters composés de machines dédiées uniquement, et qui font les calculs les uns après les autres (mode " batch "). Enfin, MOSIX est nettement moins portable que MPI, et n’est implémenté que sur les systèmes Linux. Pi est un nombre irrationnel, c’est-à-dire qu’il n’est pas le rapport de deux nombres entiers naturels. Il est également appelé " constante d’Archimède ".

Installer MPICH

MPICH est disponible sous de nombreuses plateformes : Linux (paquets pour Debian/Ubuntu, Fedora, Slackware...), ou encore FreeBSD et même Windows, tant en 32 qu’en 64 bits. Le plus simple pour installer MPICH sera certainement d’utiliser votre gestionnaire. Pi est un nombre transcendant. Il n’existe pas de polynôme à coefficients entiers ou rationnels dont pi soit une racine. Cette caractéristique établit l’impossibilité de résoudre le problème de la quadrature du cercle : il est impossible de construire, à l’aide de la règle et du compas, un carré dont la surface soit rigoureusement égale à la surface d’un cercle donné. de paquet préféré. A titre d’exemple, les paquets à installer sous une Debian sont : libmpich1.0, libmpich1.0-dev, mpich-bin et (optionnel) mpi-doc. Si vous le souhaitez, vous pouvez aussi le compiler à partir des sources (voir [4]). Vous n’avez pas besoin d’installer MPICH sur toutes vos machines, mais seulement sur la machine " serveur ", autrement dit sur celle à partir de laquelle vous lancerez l’exécution d’un programme avec mpirun (voir plus loin). Si vous êtes curieux, vous avez peut-être remarqué que nous utilisons MPICH et non pas MPICH2, qui est une nouvelle implémentation de MPI-1, version d’origine de MPI sur laquelle nous nous concentrons, et son extension MPI-2. En effet, au moment où est écrit cet article, MPICH semble plus disponible que MPICH2 (il n’y a pas de paquet MPICH2 inclus dans Debian par exemple), et nous n’avons pas besoin des extensions de la norme MPI-2 qui n’est pas implémentée dans MPICH. Cet article devrait de toute façon être facilement adaptable à MPICH2 qui supporte toujours MPI-1. Selon votre distribution ou votre choix, MPICH utilisera rsh ou ssh pour lancer les processus sur les machines distantes. Il conviendra donc d’installer et configurer correctement rsh ou ssh sur toutes les machines. Si vous utilisez ssh, vous pouvez vous reporter à [5] pour configurer vos machines de façon à ne pas avoir à taper les mots de passe à chaque exécution d’un programme par MPICH.

Calculer pi

Algorithme pour calculer pi

Il existe de nombreuses méthodes pour calculer pi, avec certaines plus originales et distrayantes que d’autres. Dans le cas présent, nous allons utiliser une méthode assez simple et facilement parallélisable. Ne vous inquiétez pas si les détails des calculs qui suivent vous échappent : ils n’ont aucune importance pour l’objet de cet article et ne sont là que pour satisfaire la curiosité des lecteurs amateurs de mathématiques. Seule la dernière formule de cette partie sera réutilisée dans l’algorithme. On remarque que l’intégrale suivante vaut pi :

/img-articles/lm/89/art-7/fig-4.jpg

 Nous allons exprimer cette intégrale grâce à un découpage en trapèzes. En effet, on a dans le cas général :

/img-articles/lm/89/art-7/fig-5.jpg

 avec :

/img-articles/lm/89/art-7/fig-6.jpg

et :

/img-articles/lm/89/art-7/fig-7.jpg

L’approximation (nécessaire vu qu’on ne peut pas calculer numériquement une somme infinie sur une machine !) consistera à utiliser un n fini, et non plus le faire tendre vers l’infini. Plus n sera grand, plus l’approximation sera bonne :

/img-articles/lm/89/art-7/fig-8.jpg

 En appliquant cette formule à notre cas particulier, on obtient :

/img-articles/lm/89/art-7/fig-9.jpg

Notre programme va donc calculer cette somme finie pour un n grand, ce qui nous donnera comme résultat une (bonne) approximation de pi.

Implémentation sur une machine

De façon à avoir une bonne précision, nous utiliserons des doubles et non des floats. On affichera aussi 12 décimales pour pi, ce qu’on obtient grâce à %.12f dans les printf(). Le code n’a pas de difficulté particulière : on lit le nombre de trapèzes (i. e. le n dans l’algorithme ci-dessus) à utiliser du premier argument de la ligne de commande, on utilise une boucle for et la fonction f() pour calculer la somme vue dans la partie précédente, puis la valeur de pi est affichée à la fin du programme :
 /* 
 * pi - calculer pi
 * Copyright 2006 Thibault GODOUET
 */
/*
 * A compiler avec:
 * gcc -Wall -O2 pi-seq.c -o pi-seq
 * puis lancer avec par exemple:
 * ./pi-seq 100000000
 */
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
/* Fonction à intégrer
 * pour calculer pi: */
/* NOTE: le "inline" n’est là que pour
 * (peut-être!) améliorer
 * les performances et peut être enlevé
 * sans problème */
inline
double
f(double x)
{
  return ( 4.0 / (1.0 + x*x) );
}
int
main(int argc, char **argv)
{
  /* nombre de trapèzes: */
  long long int num_trap = 0;
  long long int i = 0;
  double x = 0;
  double h = 0;
  double sum = 0;
  /* En cas de problème (deadlock,
   * boucle infinie, etc), arrêter le 
   * programme au bout de 60 secondes: */
  alarm(600);
  /* Lire le nombre de trapèzes à
   * utiliser pour le calcul de
   * l’intégrale */
  num_trap = atoll(argv[1]);
  printf("Nombre de trapèzes: %Ld\n",
	 num_trap);
  /* Calculer la somme approximant
   * l’intégrale et donc pi: */
  h = 1 / (long double)num_trap;
  x = 0;
  sum = 0;
  for ( i = 2; i < num_trap; i++) {
    sum += f(x) * h;
    x += h;
  }
  sum += (f(0) + (f(1))) * h 
    / ( (long double) 2);
  printf("pi=%.12f\n", sum);
  return 0;
}
Reste à compiler et à exécuter, par exemple avec 100 000 000 de trapèzes :
$ gcc -Wall -O2 pi-seq.c -o pi-seq
$ time ./pi-seq 100000000
Nombre de trapèzes: 100000000
Pi=3.141592653590
real    0m1,490s
user    0m1.472s
sys     0m0.000s
Comme vous pouvez le constater, le temps d’exécution est d’environ une seconde et demi sur l’ordinateur de test : ce n’est pas forcément très long, mais on le sent déjà. Vous pouvez vous amuser à rajouter quelques zéros pour voir le temps que ça prendra ! Quant à la précision, elle est déjà très bonne, vu que les 12 premières décimales de pi que nous avons calculées sont bonnes (en fait, elles finissent normalement par 89, mais vu que la décimale suivante est un 7, le tout est arrondi à 90). Remarque : Il se peut selon les machines que vous utilisez que la précision ne soit pas si bonne. En effet, certaines erreurs d’arrondi peuvent se produire lorsqu’on additionne un très grand nombre de floats/doubles entre eux, en particulier quand on additionne un nombre float/double avec un autre qui est beaucoup plus petit que lui : c’est ce qu’on fait ici lors du sum += f(x)*h, car sum est beaucoup plus grand que f(x)*h après un certain nombre d’itérations. Nous avons préféré garder notre approche simpliste pour ne pas noyer le lecteur qui découvre déjà le calcul parallèle et MPI, mais pour éviter toute erreur d’arrondi, il faudrait additionner les f(x) deux à deux, puis additionner les résultats deux à deux, et ainsi de suite jusqu’à trouver la somme finale, ce qui crée un arbre de profondeur log2(num_trap). Le lecteur intéressé trouvera plus d’information sur ce sujet en [7]. Journée de pi : la date du 14 mars, écrit 3/14 au format américain à 1h59 (parce que 3,14159) est généralement utilisée pour célébrer la constante. On notera que le 14 mars est également le jour de l’anniversaire d’Albert Einstein. 

Paralléliser le calcul de pi avec MPI

Introduction

Nous allons paralléliser cet algorithme en découpant la grosse somme en plusieurs sous-sommes de même taille : chaque sous-somme sera exécutée sur un nœud distinct. Ensuite, un nœud maître récupérera les valeurs des sous-sommes calculées par les différents nœuds, et les additionnera pour obtenir la valeur de pi. Il est important que chaque nœud ait le même temps de calcul et donc la même quantité de travail si les nœuds sont identiques, car le nœud maître devra attendre tous les résultats intermédiaires avant de pouvoir fournir le résultat final. Aussi, si une machine finit son travail 10 secondes avant les autres, alors ces 10 secondes auraient pu (dû !) être utilisées pour finir le calcul général plus rapidement. Plus généralement, la règle est d’affecter autant de processus à un nœud qu’il a de processeurs, à condition bien entendu que tous les processus aient la même " charge de travail " et que tous les processeurs soient identiques. Alors, pourquoi la somme finale est-elle faite par une seule machine me demandez-vous ? Tout simplement parce que, dans ce cas précis, la somme finale est très rapide à faire, comparée aux calculs des sous-sommes. Aussi il ne paraît pas nécessaire de rendre le code sensiblement plus compliqué pour un gain très minime.

Programmer avec MPI

MPI est une bibliothèque contenant plus de 120 fonctions, mais seules quelques-unes (moins d’une dizaine) sont nécessaires pour un programme simple comme celui que nous écrivons. Nous nous contenterons ici d’une courte introduction à la programmation avec MPI : le lecteur souhaitant approfondir ce sujet pourra se reporter à [3]. Pour utiliser MPI, un programme doit inclure le header de MPI :
#include "mpi.h"
Ensuite, MPI_Init(argc, argv) doit être appelé avant toute autre fonction de la bibliothèque MPI, et MPI_Finalize(void) doit être appelé à la fin de l’exécution du logiciel pour libérer les ressources. Les communications dans un cluster MPI sont organisées par groupes de communication. Cette fonctionnalité peut s’avérer très utile pour des programmes un peu complexes, mais, dans notre cas, nous nous contenterons du groupe de communication MPI_COMM_WORLD qui, vous l’aurez deviné, contient tous les nœuds du cluster. On peut obtenir la taille du groupe de communication (et donc du cluster avec MPI_COMM_WORLD) en appelant la fonction int MPI_Comm_size(MPI_Comm, int *size), par exemple :
MPI_Comm_size(MPI_COMM_WORLD, &size);
Chaque nœud du cluster MPI a un rang dans son groupe de communication, et il s’obtient en appelant la fonction int MPI_Comm_rank(MPI_Comm comm, int *rank) comme dans :
 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
Pour envoyer un message de façon bloquante, int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) est votre ami : buf contient les données à envoyer, rank est le rang du nœud (comme obtenu par MPI_Comm_rank()) à qui on envoie la donnée et tag permet de savoir à quoi correspond cette donnée. Par exemple :
#define TAG TAG_NB_TRAPEZES 1000
int nb_trapezes = 100000;
MPI_Send(&nb_trapezes, 1, MPI_INT, 0,
         TAG_NB_TRAPEZES, MPI_COMM_WORD);
La fonction réciproque, pour recevoir un message de façon bloquante, est int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status); comme dans :
 int nb_trapezes;
MPI_Status status;
MPI_Recv(&nb_trapezes, 1, MPI_INT, 
     MPI_ANY_SOURCE, TAG_NB_TRAPEZES,
     MPI_COMM_WORLD, &status);
status contenant des informations sur le message reçu :
 status.count      = message length
status.MPI_SOURCE = message sender
status.MPI_TAG    = message tag
A noter qu‘on peut aussi utiliser MPI_ANY_TAG pour accepter des messages quel que soit leur tag. Il est de plus possible d’envoyer une donnée à tous les nœuds, en utilisant int MPI_Bcast(void* buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm) : selon que le nœud en question envoie (son rang est alors égal à la valeur de root) ou reçoit, buffer contient la valeur à envoyer ou est l’endroit où sera écrite la valeur reçue (pensez à allouer la mémoire nécessaire !). Par exemple :
 long long int num_trap = 100000;
 MPI_Bcast((void *) &num_trap, 1,
    MPI_LONG_LONG_INT, 0,
    MPI_COMM_WORLD);
Pour récupérer sur un nœud une valeur de chacun des nœuds du cluster, il convient d’utiliser int MPI_Gather(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm). Les noms des arguments sont assez explicites. A noter que recvcount correspond au nombre de données reçues par nœud du cluster, pas du nombre total pour tout le cluster. Voici un exemple d’utilisation :
 int size;
int rank;
double *sum_buf = NULL;
double sum = 0;
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if ( rank == 0 )
  sum_buf = malloc(sizeof(double) 
         * size);
MPI_Gather((void *)&sum, 1, 
           MPI_DOUBLE, sum_buf, 1,
           MPI_DOUBLE, 0,
           MPI_COMM_WORLD);
Avec ces connaissances, nous pouvons maintenant passer à l’implémentation de notre programme calculant pi.

Implémentation

Nous reprenons le code du programme séquentiel et le modifions pour obtenir le code suivant :
 /* 
 * pi - calculer pi
 *      sur un cluster avec MPI
 * Copyright 2006 Thibault GODOUET
 */
/*
 * A compiler avec:
 * mpicc -Wall -O2 pi-parallel.c \
   -o pi-parallel
 * puis lancer avec par exemple:
 * mpirun -machinefile machines \
   -np 1 pi-parallel 100000000
 */
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
/* Inclure les déclarations
 * des fonctions MPI */
#include "mpi.h"
/* Nombre de noeuds dans le cluster,
 * et rang de ce noeud */
int size, rank; 
/* Pour calculer le temps de calcul: */
double start_time, end_time; 
/* printf() avec le rang du noeud
 * affiché au début de la ligne */
void
xprintf(char *fmt, ...)
{
  va_list args;
  va_start(args, fmt);
  printf("noeud %d: ", rank);
  vprintf(fmt, args);
}
/* Sortir propremment du programme,
 * et afficher le temps de calcul */
void
xexit(int code)
{
  if ( rank == 0 ) {
    end_time = MPI_Wtime();
    xprintf(“TEMPS DE CALCUL: “
      “%f secondes\n”,
      end_time - start_time);
  }
  MPI_Finalize();
  exit(code);
}
/* Fonction à intégrer
 * pour calculer pi: */
/* NOTE: le "inline" n’est là que pour
 * (peut-être!) améliorer
 * les performances et peut être enlever
 * sans problème */
inline
double
f(double x)
{
  return (4.0 / (1.0 + x*x));
}
/* Calcul de la partie de la somme
 * approximant l’intégrale de f()
 * à faire par ce noeud */
double
sub_sum(long long int start_i, 
        long long int stop_i, double h)
{
  double f_xi, f_xi1;
  long long int i = 0;
  double sum = 0;
  double x = 0;

  xprintf(“Sous-somme de %Ld à %Ld\n",
	  start_i, stop_i);
  sum = 0;
  x = h*(start_i-1);
  f_xi1 = f(x);
  for ( i = start_i; i <= stop_i; i++ ) {
    f_xi = f_xi1;
    f_xi1 = f(x+h);
    sum += (f_xi+f_xi1);
    x += h;
  }
  sum *= h/2.0;
  return sum;
}
int
main(int argc, char **argv)
{
  /* nombre de trapèzes: */
  long long int num_trap = 0;
  long long int i = 0, 
    start_i = 0, stop_i = 0;
  double h = 0;
  double sum = 0;
  /* buffer pour récupérer 
   * les sous-sommes des différents
   * noeuds: */
  double *sum_buf = NULL;
  size = rank = -1;
  /* En cas de problème (deadlock,
   * boucle infinie, etc), arrêter le 
   * programme au bout de 60 secondes: */  alarm(600);
  MPI_Init(&argc, &argv);
  MPI_Barrier(MPI_COMM_WORLD);
  start_time = MPI_Wtime();
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  if (rank == 0) {
    /* Noeud maître*/
    xprintf("Taille du cluster: %d\n",
            size);
    /* Lire le nombre de trapèzes à
     * utiliser pour le calcul de
     * l’intégrale */
    num_trap = atoll(argv[1]);
    xprintf("Nombre de trapèzes: %Ld\n",
           num_trap);
  }
  /* Envoyer/recevoir le nombre
   * de trapèzes */
  MPI_Bcast((void *) &num_trap, 1,
            MPI_LONG_LONG_INT, 0,
            MPI_COMM_WORLD);
  /* Calculer notre partie
   * de la somme: */
  h = ( 1.0 - 0.0 ) / (double)num_trap;
  start_i = 1 + num_trap * rank / size;
  stop_i = num_trap * (rank + 1) / size;
  sum = sub_sum(start_i, stop_i, h);  
  /* récupérer toutes les valeurs
   * des sous-sommes */
  if ( rank == 0 )
    /* Noeud maître: c’est nous qui
     * récupérons les valeurs, nous
     * devons donc allouer de la mémoire
     * à cette fin */
    sum_buf = malloc(sizeof(double) 
                     * size);
  MPI_Gather((void *)&sum, 1, 
             MPI_DOUBLE, sum_buf, 1,
             MPI_DOUBLE, 0,
             MPI_COMM_WORLD);
  if ( rank == 0 ) {
    /* noeud maître: sommer
     * les sous-sommes pour obtenir
     * la valeur de pi */
    sum = 0;
    for (i=0 ; i < size ; i++ ) {
      xprintf(“somme=%.12f pour le “
	      "noeud %d\n",
	      sum_buf[i], i);
      sum += sum_buf[i];
    }
    xprintf(“pi=%.12f\n”, sum);
  }
  xexit(0);
  /* Nous n’arrivons jamais ici,
   * mais la ligne suivante est
   * nécessaire pour éviter un warning
   */
  return 0;
}
Pour clarifier le code et la sortie des exécutions, nous avons créé deux nouvelles fonctions, xprintf() et xexit(). xprintf() se comporte comme printf(), mais en rajoutant le numéro du nœud qui a imprimé un message, tandis que xexit() quitte proprement le programme en appelant MPI_Finalize(). A noter aussi que le temps d’exécution est chronométré grâce à deux appels à MPI_Wtime(), destiné à cet effet. Le temps chronométré est le véritable temps d’exécution, en excluant le temps d’initialisation de MPI et de lancement des processus sur les machines distantes : ce temps ne nous intéresse pas pour évaluer la qualité de notre algorithme et est généralement négligeable pour un gros calcul, mais ce n’est pas forcément le cas pour nos tests. Immédiatement avant le début du chronométrage, on appelle MPI_Barrier(), qui sert à synchroniser les processus : la fonction ne retourne que quand elle a été appelée par tous les processus du cluster. On a aussi introduit une fonction sub_sum() qui s’occupe de calculer la sous-somme d’un nœud donné. Le calcul a été un peu optimisé, par exemple en ne multipliant par h/2 qu’une seule fois et pas à chaque itération de la boucle. Cela peut paraître assez superficiel, mais ne faire qu’une seule multiplication au lieu de plusieurs millions finit par se ressentir ! De même, on a choisi de calculer la somme de la façon la plus proche possible de la formule mathématique vue plus haut, principalement pour clarifier les choses et ainsi éviter les erreurs d’indices, mais aussi pour limiter les erreurs d’arrondi évoqués plus haut (de façon imparfaite pour simplifier, voir la note plus haut à ce sujet pour plus de détails). En début de programme, le nœud maître (de rang 0) lit le nombre de trapèzes à utiliser de la ligne de commande, et le communique à tous les nœuds grâce à MPI_Bcast(). S’en suivent les calculs sur chaque nœud, puis le nœud maître récupère les valeurs de tous les nœuds avant de les additionner et d’afficher le résultat de pi.

Compilation et exécution

Comme évoqué précédemment, un ensemble de programmes pour effectuer la compilation et l’exécution est fourni avec MPI. Pour compiler, nous utiliserons mpicc avec les mêmes arguments que gcc : mpicc s’occupera de lier le binaire avec la bibliothèque de façon transparente. On lance ensuite le calcul à l’aide de mpirun, en indiquant un fichier machines contenant les noms des machines à utiliser pour le calcul (un par ligne, et, si besoin, le nom complet avec le nom de domaine), et le nombre de processus parallèles qu’on veut lancer (argument -np), suivi du nom du programme à exécuter et des arguments de ce programme : mpirun lancera lui-même les processus sur les machines distantes. On pensera bien à vérifier que les machines sont non utilisées avant de lancer nos calculs, histoire que les temps de calcul ne soient pas faussés.
$ mpicc -Wall -O2 pi-parallel.c -o pi-parallel
$ mpirun -machinefile machines  -np 1 ./pi-parallel 10000000
noeud 0: Taille du cluster: 1
noeud 0: Nombre de trapèzes: 10000000
noeud 0: Sous-somme de 1 à 10000000
noeud 0: somme=3.141592653590 pour le noeud 0
noeud 0: Pi=3.141592653590
noeud 0: TEMPS DE CALCUL: 1.441362 secondes
$ mpirun -machinefile machines  -np 2 ./pi-parallel 10000000
thib@machine2’s password:
noeud 0: Taille du cluster: 2
noeud 0: Nombre de trapèzes: 10000000
noeud 0: Sous-somme de 1 à 5000000
noeud 0: somme=1.854590436003 pour le noeud 0
noeud 0: somme=1.287002217587 pour le noeud 1
noeud 0: Pi=3.141592653590
noeud 0: TEMPS DE CALCUL: 0.723543 secondes
noeud 1: Sous-somme de 5000001 à 10000000
$ mpirun -machinefile machines  -np 4 ./pi-parallel 10000000
thib@machine2’s password:
thib@machine3’s password:
thib@machine4’s password:
noeud 0: Taille du cluster: 4
noeud 0: Nombre de trapèzes: 10000000
noeud 0: Sous-somme de 1 à 2500000
noeud 0: somme=0.979914652507 pour le noeud 0
noeud 0: somme=0.874675783496 pour le noeud 1
noeud 0: somme=0.719413999170 pour le noeud 2
noeud 0: somme=0.567588218417 pour le noeud 3
noeud 0: Pi=3.141592653590
noeud 0: TEMPS DE CALCUL: 0.365046 secondes
noeud 2: Sous-somme de 5000001 à 7500000
noeud 3: Sous-somme de 7500001 à 10000000
noeud 1: Sous-somme de 2500001 à 5000000
Comme vous pouvez le constater, les sorties des différents nœuds arrivent de façon désordonnée. Plus précisément, les sorties d’un unique nœud sont bien dans l’ordre chronologique, mais une sortie du nœud 2 peut être affichée après une sortie du nœud 0 même si elle a été émise avant. Si cela posait un problème, on pourrait utiliser des fflush(stdout) par exemple dans xprintf() pour forcer l’envoi et l’affichage des sorties au fur et à mesure. Les performances pourraient cependant en être dégradées.

Performance et analyse

L’algorithme de calcul de pi étudié est hautement parallélisable : en effet, comme vous avez pu le constater grâce aux exécutions ci-dessus, le temps de calcul est divisé par deux quand on utilise deux fois plus de processeurs. C’est ce à quoi on s’attend, mais c’est loin d’être évident ! Le principal problème qui empêche cela est la communication entre processeurs. Ici, elle est très limitée : on envoie le nombre de trapèzes au début, et on envoie le résultat de chaque sous-somme à la fin. Au final, on a de l’ordre de 2 messages par nœud (selon l’implémentation du MPI_Gather()) de chacun la taille d’un double ou d’un long long int. Pour d’autres applications, comme une multiplication de matrice par un vecteur, la quantité de communication entre nœuds, tant en nombre qu’en taille, est beaucoup plus importante. Or, cette communication se fait par le biais d’un réseau qui est très lent comparé à un simple accès disque et encore plus un accès mémoire. Ceci est illustré par le graphe représentant l’efficacité de l’algorithme en fonction du nombre de nœuds et du nombre de trapèzes utilisés :

/img-articles/lm/89/art-7/fig-10.jpg

 

Comme vous pouvez le constater, l’efficacité est très bonne (très proche de 1) dans tous les cas, sauf pour 1 000 000 de trapèzes où elle se dégrade rapidement quand on augmente le nombre de processeurs. En effet, la durée des calculs est alors réduite par rapport aux cas où il y a plus de trapèzes, alors que chaque nœud passe toujours autant de temps à communiquer avec les autres nœuds : le temps de calcul utile sur le temps total est plus faible, donc l’efficacité est elle-même plus faible.

Conclusion

Utiliser un cluster pour faire de longs calculs est souvent intéressant financièrement par rapport à d’autres solutions et peut être indispensable quand aucun matériel existant ne peut individuellement faire le calcul dans un temps raisonnable. Cependant, tous les problèmes ne se parallélisent pas aussi bien les uns que les autres sur un cluster. En effet, les coûts (en termes de temps) des communications par le réseau sur un cluster sont très importants comparés à des accès disque ou mémoire, ce qui explique que les calculs nécessitant beaucoup de communications ne sont pas faits aussi efficacement sur un cluster qu’on pourrait l’imaginer au premier abord. MPI facilite beaucoup le développement de programmes destinés à des clusters, tant par sa bibliothèque que par ses outils de compilation et d’exécution, tout cela pour le modeste prix de l’apprentissage de quelques fonctions de son API.

Retrouvez cet article dans : Linux Magazine 89

Il y a : 0 commentaire(s)

Donnez votre avis

Vous devez avoir ouvert une session pour écrire un commentaire.

Brèves
Édito : Linux Pratique Essentiel N°24
Édito : Linux Pratique HS N°23
Édito : GNU/Linux Magazine 146
Édito : GNU/Linux Magazine HS N°58
Édito : Open Silicium N°5
Communication
Linux Pratique HS 23 – Communiqué de presse
Linux Pratique Essentiel N°24 – Communiqué de presse
Gnu/Linux Magazine sponsor et partenaire de PROLOGIN
Linux Essentiel partenaire des Rencontres du Libre de Lion sur Mer (Normandie)
GNU/Linux Magazine HS 58 – Communiqué de presse
prochainement moteur de recherches des articles
 
:
:
Jours heures minutes secondes
En kiosque
Le tout nouveau Linux Pratique Essentiel est disponible dès maintenant chez votre marchand de journaux et sur notre site...

Lire la suite...

Le tout nouveau Linux Pratique est disponible dès maintenant chez votre marchand de journaux et sur notre site...

Lire la suite...

Le tout nouveau GNU/Linux Magazine est disponible dès maintenant chez votre marchand de journaux et sur notre site...

Lire la suite...

Le tout nouveau GNU/Linux Magazine HS est disponible dès maintenant chez votre marchand de journaux et sur notre site...

Lire la suite...

Le tout nouveau Open Silicium est disponible dès maintenant chez votre marchand de journaux et sur notre site...

Lire la suite...

Le tout nouveau Linux Pratique est disponible dès maintenant chez votre marchand de journaux et sur notre site...

Lire la suite...

Le tout nouveau Misc est disponible dès maintenant chez votre marchand de journaux et sur notre site...

Lire la suite...

Le tout nouveau GNU/Linux Magazine est disponible dès maintenant chez votre marchand de journaux et sur notre site...

Lire la suite...