Chapter 2 Réseau de machines sous PVM

2.1 Introduction

PVM veut dire ``Parallel Virtual Machine'':

Elle contient une librairie C (et Fortran) de communication par passage de messages, cf. http://www.epm.ornl.gov/pvm/, développée au ``Oak Ridge National Laboratory'',
Elle contient également un processus ``démon'' pvmd3 (chaque type de machine doit avoir son propre pvmd3) et de bibliothèques d'interfaçage (libpvm3.a et libgpvm3.a pour le C)

Elle peut fonctionner sur les architectures suivantes:

Stations	OS	Super-calculateurs
DEC	BSD	Convex C2, Exemplar
IBM	System-5	Cray C90, T-3D
HP	Linux	Intel Paragon, Hypercube
Silicon Graphics		IBM SP-2, 3090
Sun		TMC CM-2, CM-5
NeXT		Kendall Square
Data General		Sequent
386/486/586 Unix		Maspar
		Encore
		Fujitsu
		Stardent
...	...	...

La machine PVM (voir figure 2.1) est une collection de machines réelles sur un même réseau sur lesquelles s'exécute un démon pvmd3. pvmd3 est un processus UNIX qui contrôle les processus utilisateurs au sein d'une application PVM et qui coordonne les communications entre les machines qui composent la machine PVM. Un démon pvmd3 est présent par ordinateur et par utilisateur de la machine PVM et maintient la configuration globale et locale de la machine PVM.

La librairie PVM permet de communiquer avec ces démons pvmd3 pour créer et détruire des processus, gérer des tampons de communication, envoyer, recevoir (point à point ou par broadcast) des messages (de façon bloquante ou non-bloquante), synchroniser des processus (par barrières de synchronisation) connaître l'état de la configuration de la machine PVM et pour la modifier (dynamiquement)...

Figure 2.1: La machine PVM

2.2 Démarrer par l'exemple

Supposons que nous voulions calculer p en parallèle par la formule suivante,

ó
õ

1+x²

i=1

æ
ç
ç
è

(i-

)

ö
÷
÷
ø

Une solution est le paradigme Maître/Esclave: Un maître va lancer N esclaves chargés de calculer les sommes partielles,

P_k =

(k+1)*n/N

i=k*n/N

æ
ç
ç
è

(i-

)

ö
÷
÷
ø

pour k=0,···,N-1.

C'est une parallélisation par décomposition fonctionnelle (que l'on reverra avec la FFT, section 5.2.2). On pourrait aussi faire de la décomposition de domaine pour calculer une fonction s'appliquant indépendemment à des sous-blocs d'un tableau.

Donc le maître pi_control va lancer N copies d'un esclave pi avec l'entier k correspondant, puis attendre que tous aient terminé leur exécution, enfin effectuer la somme de tous les résultats partiels (voir figure 2.2).

Figure 2.2: Flot de contrôle du calcul parallèle de p

2.2.1 La base pour démarrer: le contrôle des processus.

pvm_mytid

C'est une instruction obligatoire en début de code PVM ¹ qui permet de raccrocher le processus à un démon pvmd. Sa syntaxe est:

int tid;
tid=pvm_tid();

Cela renvoie tid qui est l'identificateur de tâche du processus. Ce tid permet de définir de façon unique ce processus et de s'adresser à lui. Il y a un cas d'Erreur si cela renvoie tid < 0 (démon PVM inexistant par exemple).

pvm_exit

C'est une instruction (presque) obligatoire en fin de code PVM. Elle permet de dire au démon pvmd que la tâche quitte PVM.

int info;
info=pvm_exit();

Il y a un cas d'Erreur si cela renvoie info < 0.

pvm_spawn

C'est l'instruction qui permet de lancer n tâches PVM exécutant un même code ("programme"):

int numt; 
numt=pvm_spawn(char *task,char **argv,int flag,char 
                          *where,int ntask,int *tids);

On se contentera pour le plus souvent de (voir cependant la section 5.2.2 pour une application de la forme de ``spawn'' la plus générale),

int numt,etid[n];
numt=pvm_spawn("programme",NULL,PvmTaskDefault,NULL,n,&etid[0]);

Le tid de chacune des tâches est rangé dans une entrée du tableau etid. Cette instruction Renvoie numt <= n qui est le nombre de tâche(s) effectivement lancée(s).

Pour les autres champs:

argv est la liste d'arguments (type ligne de commande UNIX) à passer à "programme",
flag donne des options à pvm_spawn,
pour certaines de ces options where indique sur quel type d'hôte lancer les processus.

pvm_parent

Cette instruction retourne tid valant le tid de son processus parent (celui qui a crée le processus courant):

int tid; 
tid=pvm_parent();

Elle peut également renvoyer tid=PvmNoParent si le processus courant n'a pas été crée par pvm_spawn.

2.2.2 La base: passage de messages

L'envoi des messages est non-bloquant. Ceci est géré grâce à un tampon d'envoi. Celui-ci doit être,

crée (pvm_initsend),
rempli (pvm_pk...),
son contenu, envoyé (pvm_send).

La réception peut être bloquante ou non-bloquante. On a aussi un tampon pour la réception mais que l'on n'a pas besoin de créer explicitement. On peut,

recevoir un contenu (pvm_recv),
en extraire les données une à une (pvm_upk...),
en tester l'état (avec pvm_bufinfo, surtout utile pour les réceptions non-bloquantes).

pvm_initsend

C'est une instruction obligatoire avant l'envoie d'un message: elle initialise le tampon d'envoie des données:

int info; 
info=pvm_initsend(int encoding);

encoding est un entier permettant de spécifier comment coder les données (surtout utile en milieur hétérogène). Ici on emploiera toujours PvmDataDefault. Il y a une Erreur si pvm_initsend renvoie info < 0.

pvm_pk...

Ce sont les fonctions qui effectuent le compactage de différentes données d'un processus, destinées à être envoyées, dans le tampon d'envoi:

int info; 
info=pvm_pkint(int *ip,int nitem,int stride);

ip est un tableau d'entiers d'au moins nitem*stride de long. ip peut être également un pointeur sur une variable entière.
nitem est le nombre d'éléments de ip que l'on veut compacter dans le tampon d'envoi.
stride est le décalage entre deux éléments de ip à compacter. Par exemple, si int ip[6]; stride=2; nitem=3; alors les éléments compactés de ip seront ip[0], ip[2], ip[4].

Il y a eu une Erreur si cela renvoie info < 0. Il y a une fonction de compactage par type de données possible, donc on trouvera également pvm_pkfloat, pvm_pkdouble, pvm_pkstr etc.

pvm_send

Cette instruction envoie un message de façon non-bloquante:

int info; 
info=pvm_send(int tid,int msgtag);

tid est l'identificateur de processus du destinataire du message. msgtag est un entier identifiant une classe de messages. Cela permet de filtrer les messages (à la réception). Il y a un cas d'Erreur si elle renvoie info < 0.

pvm_upk...

Elles correspondent aux instructions pvm_pk...:

int info; 
info=pvm_upkint(int *ip,int nitem,int nstride);

Elles ont les mêmes arguments que pour les fonctions pvm_pk.... Il y a une Erreur si elles renvoient info < 0.

pvm_recv

Cette instruction reçoit un message de type msgtag de l'expéditeur tid:

int bufid; 
bufid=pvm_recv(int tid,int msgtag);

Elle bloque le processus receveur tant que le message n'est pas reçu. Si tid vaut -1, peut recevoir de n'importe qui. Si msgtag vaut -1, peut recevoir de n'importe qui. Il y a un cas d'Erreur si pvm_recv renvoie info < 0.

2.2.3 L'exemple complet

Le code du maître est:

/* Maitre pi_control.c */
#include <stdio.h>
#include "pvm3.h"
#define NPROC 10
#define N 1000
#define SUMTAG 1
#define INPUTTAG 2

main()
{
int i, n, nproc, numt, bufid, tid[10];
float psum,sum;
n = N;
nproc = NPROC;
printf("I'm t%x spawning %d partial computations\n",pvm_mytid(),NPROC);
numt = pvm_spawn("pi",(char **) 0,PvmTaskDefault,"",NPROC,&tid[0]);
if (numt != NPROC)
{
  printf("could not spawn %d tasks\n",NPROC);
  exit(1);
}
 for (i=0; i<NPROC;i++)
   {
     pvm_initsend(PvmDataDefault);
     pvm_pkint(&i,1,1);
     pvm_pkint(&n,1,1);
     pvm_pkint(&nproc,1,1);
     pvm_send(tid[i],INPUTTAG);
   }
 sum = 0;
 for (i=0; i<NPROC; i++)
   {
     bufid = pvm_recv(tid[i], SUMTAG);
     pvm_upkfloat(&psum,1,1);
     printf("Partial sum received from t%x: %f\n", tid[i], psum);
     sum = sum+psum;
   }
 printf("From master process: Pi = %f\n",sum);
 pvm_exit();
 exit(0);
}

Le code unique des esclaves est:

/* Esclave pi.c */
#include "pvm3.h"
#include <stdio.h>
#define SUMTAG 1
#define INPUTTAG 2

main()
{
  int i, j, n, nproc, bufid, mtid;
  float psum;
  mtid = pvm_parent();
  bufid = pvm_recv(mtid, INPUTTAG);
  pvm_upkint(&i,1,1);
  pvm_upkint(&n,1,1);
  pvm_upkint(&nproc,1,1);
  printf("I am slave %d with parent t%x\n",i,mtid);
  psum = 0;
  for (j=(n/nproc)*i+1;j<=(n/nproc)*(i+1);j++) 
    psum = psum+4.0/(1+(j-.5)*(j-.5)/n/n);
  psum = psum/n;
  pvm_initsend(PvmDataDefault);
  pvm_pkfloat(&psum,1,1);
  pvm_send(mtid, SUMTAG);
  pvm_exit();
  exit(0);
}

Un exemple d'exécution avec NPROC=10 (nombre de processeurs, défini dans le maître) et N=1000 itérations (défini également dans le maître):

pvm> spawn -1 -> pi_control       
[1]
1 successful
t4008b
pvm> [1:t4008b] I'm t4008b spawning 10 partial computations
[1:t4008c] I am slave 0 with parent t4008b
[1:t40091] I am slave 5 with parent t4008b
[1:t40092] I am slave 6 with parent t4008b
[1:t40090] I am slave 4 with parent t4008b
[1:t40093] I am slave 7 with parent t4008b
[1:t4008b] Partial sum received from t4008c: 0.398675
[1:t4008e] I am slave 2 with parent t4008b
[1:t4008c] EOF
[1:t40092] EOF
[1:t40091] EOF
[1:t4008f] I am slave 3 with parent t4008b
[1:t40095] I am slave 9 with parent t4008b
[1:t40093] EOF
[1:t40090] EOF
[1:t4008d] I am slave 1 with parent t4008b
[1:t4008e] EOF
[1:t40095] EOF
[1:t4008f] EOF
[1:t4008b] Partial sum received from t4008d: 0.390908
[1:t4008b] Partial sum received from t4008e: 0.376245
[1:t4008b] Partial sum received from t4008f: 0.356198
[1:t4008b] Partial sum received from t40090: 0.332565
[1:t4008b] Partial sum received from t40091: 0.307088
[1:t4008b] Partial sum received from t40092: 0.281226
[1:t4008b] Partial sum received from t40093: 0.256060
[1:t4008d] EOF
[1:t40094] I am slave 8 with parent t4008b
[1:t4008b] Partial sum received from t40094: 0.232297
[1:t4008b] Partial sum received from t40095: 0.210332
[1:t4008b] From master process: Pi = 3.141593
[1:t40094] EOF
[1:t4008b] EOF
[1] finished

1: On pourra se reporter au livre [GBD⁺94] pour plus de détails.