Nous avons expérimenté l'utilisation des protocoles MPI pour un problème de multiplication de matrices. énoncé

La stratégie de parallélisation était de distribuer des blocs contigu de lignes et de colonnes, puis faire circuler les colonnes de façon ordonnée pour que chaque processus garde son bloc de lignes et traite (reçoive et transmette) chaque bloc de colonnes une seule fois (moins 1 pour les transmissions). Les blocs de colonnes étaient transposés pour optimiser l'exploitation d'ajacence en cache des données pour opérations successives.

Les trois façons d'implanter l'algorithme étaient en utilisant

• MPI_Sendrecv_replace.
• MPI_Bsend et MPI_Recv.
• MPI_Ibsend et MPI_Irecv.

L'utilisation de Sendrecv_replace est le plus simple: on n'a qu'un simple appel à passer, MPI gère tout du buffer; c'est appel est simple mais bloquant, le programme appelant attend le retour.

Dans l'utilisation de Bsend, c'est notre programme qui gère le passage d'un buffer à Bsend et récupération du buffer de Recv. Bsend est bloquant, le programme appelle ensuite Recv et attend.

Dernière protocole testée, Ibsend/Irecv n'est pas bloquant, mais demande plus d'attention à l'organisation des opérations pour exploiter le “temps masqué” de la circulation pour continuer à calculer, sans risque d'avoir les données locales écrasée par une écriture trop tôt des données attendues.

Les blocs de code pour les parties ainsi variées figurent en annexe.

Nous avons mesuré les performances sur les PC de salle J3 alors qu'elles n'étaient pas occupées par d'autres processus (sauf si deux tests concouraient sur des mêmes machines accidentellement, mais nous avons fait attention pour éviter cela). Chaque stratégie était testé sur une machine, puis 2, 4, 8, et 16. En dernière instance, ayant constaté que dans ces conditions 4 processus avaient les même performances sur 2 ou 4 machines, 8 processus sur 4 ou 8 machines avaient les mêmes performances, nous avons testé 32 processus sur 16 machines.

Nos mesures sont “loop time” et “Mflops”. La comparaison de “loop time” sur un processus sur la machine maitre permet de calculer le “speed-up” : par quel facteur le temps de calcul est réduit par une configuration donnée. Tenant compte du nombre de processus utilisés pour réaliser un SU permet de calculer l'efficacité. Pour nos tests, nos SU ont avoisinaient 8, mais pour 32 processus cela signifie une efficacité de seulement 25 pour cent!

On note que, lorsqu'une seule machine (à processeur dual core) est utilisée, les performances sont quasi identique pour un processus que pour deux, voir plus rapide pour un seul: visiblement le système d'exploitation utilise les deux cores et on peut en déduire que nos étalonnages sont faux par un facteur de deux, on n'a pas la possibilité de mesurer (facilement) le temps d'un traitement purement séquentiel.

Des questions subsistant quant à la performance “de référence” dans chaque batterie de tests, comparons sur la base de deux processus sur chaque machine (base Mflops, tableau suivant).

Mise à part une apparente anomalie pour 4 processus avec Bsend, les résultats paraissent plus cohérents.

Pour ce problème, pour une configuration de machines homogènes sans autre charges, les performance différent peu entre stratégies. Peut être est-ce la raison pour laquelle Ibsend ne montre pas d'avantage à calculer en temps masqué.

Le code pour MPI_Sendrecv_replace n'était pas optimisé pour le étalonnage avec un seul processus

// Call "OneStepCirculation" and "SeqLocalProduct"

  for (step=0;step<NbPE;step++){
  SeqLocalProduct(step);
  OneStepCirculation(step);
}

void OneStepCirculation(int step)
{
 MPI_Status status;
 MPI_Sendrecv_replace(&A[0][0]
, Blocksize
, MPI_DOUBLE
, (Me-1+NbPE)%NbPE
, 0
      , (Me+1)%NbPE
, 0
, MPI_COMM_WORLD
, &status);

On ne prépare un buffer et n'appelle la routine de circulation des données que lorsque plus d'un processus est utilisé :

if(NbPE>1){
 	int SizeOneMsg;
 	MPI_Pack_size(block_size,MPI_DOUBLE,MPI_COMM_WORLD,&SizeOneMsg);
	int Size = (SizeOneMsg + MPI_BSEND_OVERHEAD);
	double * buf = (double *) malloc(Size); /* Buffer allocation */

 for(step = 0; step < NbPE; step ++){
   SeqLocalProduct(step);
   OneStepCirculation(step, Size, buf);
  }
 free(buf);
}else{ 

for(step = 0; step < NbPE; step ++){
   SeqLocalProduct(step);
  }
}   

La routine de circulation des données :

void OneStepCirculation(int step, int Size, double * buf)
{
  MPI_Status status;
  MPI_Buffer_attach(buf,Size); /* Buffer attachement */
  MPI_Bsend( A, block_size,  MPI_DOUBLE, (Me-1+NbPE)%NbPE, 0, MPI_COMM_WORLD);
  MPI_Recv( A, block_size,  MPI_DOUBLE, (Me+1)%NbPE, 0, MPI_COMM_WORLD, &status);
  MPI_Buffer_detach(&buf,&Size);
}

void OneStepCirculation(int step, int Size, double * buf)
{
  int i,j;
  MPI_Status statusSend;
  MPI_Status statusRecv;
  MPI_Request requestSend;
  MPI_Request requestRecv;
 
  MPI_Buffer_attach(buf,Size); /* Buffer attachement */
  MPI_Ibsend( A, block_size,  MPI_DOUBLE, (Me-1+NbPE)%NbPE, 0, MPI_COMM_WORLD, &requestSend);
  MPI_Irecv( A2, block_size,  MPI_DOUBLE, (Me+1)%NbPE, 0, MPI_COMM_WORLD, &requestRecv);
  SeqLocalProduct(step);
  MPI_Wait( &requestSend, &statusSend);
  MPI_Wait( &requestRecv, &statusRecv);
  MPI_Buffer_detach(&buf,&Size);
  
  memcpy(A,A2,LOCAL_SIZE*SIZE*sizeof(double));
}

La routine de gestion est peu différente de celle de Bsend :

void ComputationAndCirculation()
{
  int step;
  
  if(NbPE>1){
	int SizeOneMsg;

MPI_Pack_size(block_size,MPI_DOUBLE,MPI_COMM_WORLD,&SizeOneMsg);

int Size = (SizeOneMsg + MPI_BSEND_OVERHEAD);
double * buf = (double *) malloc(Size); /* Buffer allocation */

      for(step = 0; step < NbPE; step ++){
         OneStepCirculation(step, Size, buf);
      }
      free(buf);
  }else{ 
      for(step = 0; step < NbPE; step ++){
         SeqLocalProduct(step);
      }
}