Conception et développement d’un programme MPI

Nous allons maintenant nous intéresser à la démarche à adopter pour concevoir un programme parallèle.

Tout d’abord, rappelons que le but est d’améliorer les performances d’un algorithme, notamment en terme de temps. Il faudra donc tout particulièrement s’attacher à produire un code optimisé et le plus rapide possible en exécution. En effet, comme nous allons le développer par la suite, un programme MPI nécessite d’utiliser plusieurs variables tampons pour préparer les données à envoyer, ou préparer la mémoire pour recevoir les données envoyées.

Il faudra également déterminer comment répartir les tâches à traiter sur l’ensemble des processeurs.

Pour compiler en C un programme développé avec MPI :

1. Echanges de messages entre les processus

Dans le cas du simulateur utilisé jusqu’à maintenant en TP, la mémoire est partagée. Dans le cas de MPI, nous utilisons un parc de machines, ce qui fait que nous avons une mémoire distribuée.

Les programmes MPI étant basés sur des échanges de messages, il va falloir essayer de diminuer au maximum ce nombre d’échanges, afin de ne pas ralentir l’exécution du programme.

Pour cela, nous allons faire une sélection des données à envoyer à chaque processus, puis nous allons copier ces données dans un tableau afin de l’envoyer. De la même manière il faudra préparer un tableau pour pouvoir accueillir ces données. En effet si un processus est chargé d’effectuer des calculs sur une partie des éléments d’un tableau (ou d’une matrice), il n’a pas besoin des autres éléments ; on ne lui envoie donc que le strict nécessaire.

2. Parallélisation d’un programme / prise en main de MPI

Dans cette partie, nous allons décrire quelques petits programmes pour se familiariser avec l’environnement MPI, et quelques fonctions très utiles.

2.1. Choix du langage :

Nous avons choisi de développer en C. Dans un premier temps, il nous avait été demandé de développer en Fortran. Le problème qui s’est posé est que nous n’avions à notre disposition qu’un compilateur Fortran77. Hors, d’après nos connaissances, le Fortran77 ne permet pas l’allocation dynamique, ce qui est indispensable pour faire des programmes efficaces. Nous nous sommes donc tourné vers le C. Ce qui, à nos yeux ne pose pas de problème, car la différence entre le C et le Fortran90 est uniquement d’ordre syntaxique, le reste étant assez similaire.

2.2. « Hello world » parallèle :

Voici un premier programme qui permet de prendre contact avec l’environnement MPI.

/////////////////////////////////////////////
//	hello.c
//	Hello world parallèle
/////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>

int main(int argc, char** argv)
{
	int myrank, size;

	MPI_Init(&argc,&argv);
	MPI_Comm_size(MPI_COMM_WORLD,&size);
	MPI_Comm_rank(MPI_COMM_WORLD,&myrank);

	printf("Hello world, je suis le processus %d.\n",myrank);
	
	MPI_Finalize();

	exit(EXIT_SUCCESS);
}

Après compilation : %hcc –o hello hello.c
et exécution : %mpirun –np 2 hello, on obtient le résultat suivant :

Hello world, je suis le processus 0.
Hello world, je suis le processus 1.

Examinons le listing :

Tout d’abord les inclusions de fichiers : nous avons besoin de mpi.h qui est le seul fichier à inclure pour utiliser MPI. Puis on remarque que MPI_Init() exige qu’on lui donne les arguments de la ligne de commande, il faut donc les récupérer même si on ne s’en sert pas. On récupère le nombre de processeurs actifs sur ce programme à l’aide de MPI_Comm_size(), et notre rang qui est compris entre 0 et le nombre de processeurs –1. Puis on demande un affichage, on quitte MPI, et on renvoi un message de succès.

Chaque processeur lancé va exécuter exactement le même code, linéairement. Mais le résultat différera en fonction du rang, ici seul l’affichage change, mais ensuite on va pouvoir de la même manière affecter des tâches différentes à chaque processeur.

Après cette première prise de contact, nous allons pouvoir tester quelques fonctions très pratiques.

2.3. Utilisation de MPI_Bcast() :

Rappel : Cette fonction va permettre de diffuser un message à l’ensemble du groupe de processeurs. Voici le source du programme :

/////////////////////////////////////////////
//	MPI_Bcast.c
//	Test de la fonction de diffusion MPI_Bcast()
/////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>

int main(int argc, char** argv)
{
	int myrank, size, valeur;

	MPI_Init(&argc,&argv);
	MPI_Comm_size(MPI_COMM_WORLD,&size);
	MPI_Comm_rank(MPI_COMM_WORLD,&myrank);

	if (myrank==0) {
	  printf("Entrez la valeur a diffuser : ");
	  scanf("%d",&valeur);
	}

	MPI_Bcast(&valeur,1,MPI_INT,0,MPI_COMM_WORLD);
	printf("Moi processus %d, j'ai reçu la valeur %d\n",
	        myrank,valeur);

	MPI_Finalize();

	exit(EXIT_SUCCESS);
}

Le résultat de l’exécution de ce programme sur trois processeurs est :

Entrez la valeur a diffuser : 5
Moi processus 0, j'ai reçu la valeur 5
Moi processus 2, j'ai reçu la valeur 5
Moi processus 1, j'ai reçu la valeur 5

On voit ici, que seulement le processus 0 s’occupe de la saisie de la variable.

Ce qu’il y a d’étonnant, c’est que tous les processus appellent la même fonction mais en fonction de leur rang, la variable valeur servira soit de variable à émettre, soit de variable de réception, c’est le quatrième argument de la fonction MPI_Bcast() qui précise qui est l’initiateur de la diffusion.

On notera également que la fonction MPI_Bcast(), comme beaucoup de fonction de communication servent à synchroniser les processus entre eux.

2.4. Utilisation de MPI_Scatterv() :

Maintenant que nous avons vu comment fonctionnait un programme MPI, nous allons pouvoir étudier une des fonctions les plus intéressantes.

Cette fonction est dérivée de la fonction MPI_Scatter(), qui sert à disperser une variable. Par exemple, elle permet de diviser un tableau en 4 parties égales et d'envoyer ces parties aux 4 processus. La fonction complémentaire associée est MPI_Gather(), qui fait l'inverse. Ces fonctions sont très pratiques en algorithmique parallèle. En effet cela permet aux processus de travailler sur une partie réduite d'une variable. Seul petit problème, c’est que la dimension de la variable n'est pas toujours proportionnelle au nombre de processus.

Par exemple, si l’on veut distribuer un tableau de 15 éléments à 4 processus, MPI_Scatter permettra seulement d'envoyer 4 tableaux de 3 éléments, et il restera 3 éléments à la charge du processus maître. On pourrait ensuite redistribuer les éléments restants un par un, mais le tableau perdrait probablement son intégrité (le processus 0 aurait les 3 premiers éléments et le troisième élément en partant de la fin). C'est là qu'intervient MPI_Scatterv(), qui permet d'envoyer des parties de taille variable pour chaque processus, elle permet également de ne pas prendre tous les éléments (de laisser des "trous" entre les parties prélevées) et d'ajuster le découpage de la variable à disperser.

Le programme suivant permet d'illustrer, en partie, l'utilité de cette fonction. Le maître alloue un tableau égal à 10*(nombre de processus), puis le distribue aux processus, en envoyant au processus i, (10-i) éléments du tableau, sans laisser de "trous".

Par exemple, si on lance le programme sur 4 processus, on obtient :
processus 0 : [ 0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ]
processus 1: [ 10 ; 11 ; 12 ; 13 ; 14 ; 15 ; 16 ; 17 ; 18 ; ]
processus 2 : [ 19 ; 20 ; 21 ; 22 ; 23 ; 24 ; 25 ; 26 ]
processus 3 : [ 27 ; 28 ; 29 ; 30 ; 31 ; 32 ; 33 ]

Voici le listing de ce programme :

/////////////////////////////////////////////
//	MPI_Scatterv.c
//  test de la fonction MPI_Scatterv
/////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>

#define DIMENSION 10

int main(int argc, char** argv)
{
  int myrank, i, n_procs;
  int * sendbuf;      //buffer à disperser
  int * tab_indice;   //indice de début de chaque subdivision
  int * tab_taille;   //nombre d'éléments à envoyer
                      // pour chaque processus
  int * rbuf;         //buffer de reception
  int taille;         //taille de la partie reçue

  //Initialisation de MPI
  MPI_Init(&argc,&argv);
  MPI_Comm_size(MPI_COMM_WORLD,&n_procs);
  MPI_Comm_rank(MPI_COMM_WORLD,&myrank);

  if (myrank==0) {
    //allocation mémoire
    sendbuf=(int *)malloc(n_procs*DIMENSION*sizeof(int));
    tab_indice=(int *)malloc(n_procs*sizeof(int));
    tab_taille=(int *)malloc(n_procs*sizeof(int));
    //remplissage du buffer à disperser
    for (i=0;i<n_procs*DIMENSION;i++) sendbuf[i]=i;
    //initialisation des subdivisions
    for (i=0;i<n_procs;i++){
      //nombre d'éléments à envoyer
      tab_taille[i] = DIMENSION-i;
      //indice de début du processus i 
      // = celui de i-1 + nombre d'éléments
      // envoyés par i-1
      if (i!=0) tab_indice[i]=tab_indice[i-1]+tab_taille[i-1];
      else tab_indice[i]=0;
    }
  }

  //communication de la taille de la partie reçue à chaque processus
  MPI_Scatter(tab_taille,1,MPI_INT,&taille,1,MPI_INT,0,MPI_COMM_WORLD);
  //allocation du buffer de reception
  rbuf=(int *)malloc(taille*sizeof(int));

  //dispersion
      MPI_Scatterv(sendbuf,tab_taille,tab_indice,MPI_INT,rbuf,
         DIMENSION,MPI_INT,0,MPI_COMM_WORLD);

  //affichage
  printf("processus %d : [ ",myrank);
  for(i=0;i<taille;i++) printf("%d ",rbuf[i]);
  printf("]\n");

  //desallocation mémoire
  free(rbuf);
  if (myrank==0) {
    free(sendbuf);
    free(tab_indice);
    free(tab_taille);
  }

  MPI_Finalize();
  exit(EXIT_SUCCESS);
}

En observant la partie déclarative, on peut voir l’essentiel de ce qu’il faut retenir de l’usage de cette fonction. Il faut bien sûr une variable contenant les variables à envoyer (sendbuf) et une autre destinée à recevoir les données que le processus maître va envoyer. Mais aussi un tableau contenant la taille de la partie attribuée à chaque processeur, et un autre contenant l’indice de début de la zone attribuée à chaque processus dans la variable à disperser.

Il faut maintenant se pencher sur un point important : la propriété des variables. En effet, toutes les variables déclarées ne seront pas utilisées par tous les processus. Par exemple, tous les processus, sauf le processus maître (0), n’ont pas besoin de la variable sendbuf, puisqu’on ne désire pas envoyer l’intégralité de cette variable à tous les processus. Il en est de même pour tab_index et tab_taille. Il faudra donc, selon le rang de chaque processus, allouer ou pas une variable, si on l’alloue, le faire en utilisant les bonnes dimensions.

Une fois que le processus maître a initialisé correctement ses variables. C’est-à-dire que sa variable sendbuf est initialisée et prête à envoyer, et qu’il a calculé les indices et tailles des parties à envoyer pour chaque processus. Il faut maintenant qu’il communique la taille des parties envoyées à chaque processus, pour que ceux-ci allouent leur variable de réception rbuf, en conséquence.

Ceci étant fait, MPI_Scatterv() s’occupe du reste, et on récupère dans rbuf, la partie de la variable initiale sendbuf désirée.

2.5. Utilisation d’une boucle partagée :

Nous avons maintenant à notre disposition les outils nécessaires pour effectuer un premier calcul reparti. Nous allons utiliser dans l’exemple suivant la méthode de la boucle partagée pour calculer la somme des éléments d’un vecteur. Cette méthode consiste simplement à diviser une boucle en tranches. Voici le listing de ce programme :

/////////////////////////////////////////////
//	somme_partagee.c
//
//	Boucle partagee pour calculer la somme
//   des éléments d'un vecteur
/////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>

//nombre d’éléments du tableau
#define DIMENSION 30

int main(int argc, char** argv) 
{ 
  int * tab;         //tableau de départ
  int * sous_tab;    //partie du tableau que possèdent les processus
  int * tab_index;   //indexation des parties à envoyer
  int * tab_tailles; //taille des parties à envoyer

  int taille;        //taille de la partie reçue
  int myrank, i, j, n_procs, resultat;

  MPI_Init(&argc,&argv);
  MPI_Comm_size(MPI_COMM_WORLD,&n_procs);
  MPI_Comm_rank(MPI_COMM_WORLD,&myrank);

  if (myrank==0) {
    //allocation mémoire
    tab_index=(int *)malloc(n_procs*sizeof(int));
    tab_tailles=(int *)malloc(n_procs*sizeof(int));
    tab=(int *)malloc(DIMENSION*sizeof(int));
    //remplissage du tableau
    for (i=0;i<DIMENSION;i++) tab[i]=i+1;
    //initialisation des tailles
    for (i=0;i<n_procs;i++) {
      tab_tailles[i]=DIMENSION/n_procs;
      //On distribue aux premiers processus le reste du tableau,
      // lorsque sa taille n'est pas proportionnelle
      //  au nombre de processus.
      if (i < (DIMENSION%n_procs)) tab_tailles[i]++;
    }
    //calcul des index
    resultat=0; // variable temporaire
    for (i=0;i<n_procs;i++) {
      tab_index[i]=resultat;
      resultat+=tab_tailles[i];
    }
  }

  //communication de la taille de la partie reçue à chaque processus
  MPI_Scatter(tab_tailles,1,MPI_INT,&taille,1,MPI_INT,0,MPI_COMM_WORLD);
  //allocation mémoire du buffer de reception
  sous_tab=(int *)malloc(taille*sizeof(int)); 

  //dispersion du tableau de départ
  MPI_Scatterv(tab,tab_tailles,tab_index,MPI_INT,sous_tab,taille,
               MPI_INT,0,MPI_COMM_WORLD); 

  //calcul (somme des éléments)
  for (i=1;i<taille;i++) sous_tab[0] += sous_tab[i]; 
  
  //le processus récolte tous les résultats en faisant la somme 
  MPI_Reduce(sous_tab,&resultat,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
  if (myrank==0) printf("  somme = %d\n",resultat);
	  
  MPI_Finalize(); 
	
  exit(EXIT_SUCCESS); 
}

Lorsqu’on lance ce programme, le résultat fourni est :

Et ce, quel que soit le nombre de processeurs. Le résultat est bien celui attendu, en effet le tableau contient les entiers de 1 à 30, donc la somme fait bien 30*31/2=465. On peut remarquer l’utilisation de la fonction MPI_Reduce(), qui permet de récolter les résultats de l’ensemble des processus en appliquant une fonction de réduction (ici, une somme). En fait, ce programme ne gagne pas à être parallélisé, car le calcul au sein même de la boucle est réduit à une somme qui est une opération élémentaire, et donc les échanges de messages font perdre plus de temps que l’on en gagne en utilisant plusieurs processeurs. Pour plus de détails sur les résultats obtenus, référez-vous à la partie consacrée au « benchmarking ».

Nous savons donc maintenant utiliser la bibliothèque MPI pour réaliser un calcul en parallèle.

3. Techniques d’optimisation complémentaires

Nous allons, dans cette partie, donner quelques moyens supplémentaires pour mieux utiliser l’environnement MPI. Nous n’avons pas testé ces méthodes, mais elles nous paraissent assez intéressantes pour figurer dans ce rapport.

3.1. Création de type de données personnalisées prêt à être utilisé par MPI :

Dans les communications MPI, les données transmises sont typées. On dispose des types prédéfinis par MPI comme MPI_INTEGER, MPI_DOUBLE_PRECISION, MPI_SHORT_INT, etc,

On peut construire des structures de données plus complexes : homogènes (toutes les données sont du même type comme les éléments d'un tableau) ou hétérogènes (comme les structures en C ou les types dérivés en Fortran) pour effectuer les communications point à point.

• Types homogènes :

  Ce sont des ensembles de données élémentaires de même type prédéfini mais leur distribution au sein du tableau peut être quelconque.

  Définir de tels types sera plus particulièrement utile lorsqu’on veut communiquer des éléments d’une matrice. Dans les programmes que nous avons réalisés, nous utilisons des tableaux temporaires, que nous remplissons avec les valeurs à envoyer, et que nous envoyons.

  On peut ainsi définir des types colonnes, lignes, ou encore des types ayant pour cible des éléments non contigus dans une matrice, par exemple des diagonales, des triangles.

• Types hétérogènes :

  Ils seront eux très utiles si l’on veut communiquer des types dérivés (ou struct en C).

3.2. Optimisation des fonctions de diffusion :

La fonction fournit est MPI_Bcast(), qui permet à un processus de diffuser un message à l’ensemble des processus de son groupe. Le principe utilisé est que le processus initiateur envoie successivement à tous les autres processus son message (figure 1.).

Figure 1 - principe de la fonction MPI_Bcast()

On pourrait cependant implémenter une alternative à cette fonction, en utilisant le principe suivant : la diffusion suit un schéma isomorphe à un arbre binaire, c’est-à-dire que le processus initiateur envoie son message à un autre processus, à cette étape deux processus ont maintenant le message et l’envoie maintenant à un autre processus chacun, et ainsi de suite, comme illustré sur le schéma suivant (figure 2.) :

Figure 2 - Méthode plus intelligente pour la diffusion de messages

La quantité de données est la même dans les deux cas. En revanche le nombre d’étape est de l’ordre de log(n) dans la deuxième approche, contre (N-1)*p dans la seconde. (N étant le nombre de processeurs et p, la taille du message envoyé)

Cette technique peut également être appliquée aux autres fonctions utilisant des procédés similaires, comme MPI_Scatter.

3.3. Utilisation des variables d’environnement MPI :

Les variables d'environnement que l'on peut utiliser sont les suivantes :

MPI_DSM_PPM indique le nombre de processus que l'on met par nœud (dans le cas d’utilisation de machines bi-processeur).

MPI_DSM_MUSTRUN indique au système que le processus doit rester sur le même processeur pour toute.

MPC_GANG permet d'activer ou désactiver le gang scheduling, c’est-à-dire le fait que tous les processus doivent tourner en même temps.