Le broadcast (TP1)

Le broadcast est une opération collective qui consiste à répartir sur tous les processus une donnée se trouvant sur un processus source. La primitive MPI permettant d'effectuer cette opération est MPI_Bcast.

Dans ce TP, vous aurez en plus besoin de savoir comment synchroniser des processus et comment mesurer un temps écoulé dans un programme MPI, une bonne explication de ces différents points se trouve à cette adresse.

MPI Broadcast

Exemple d'utilisation de MPI broadcast :

#include <mpi.h>
#include <iostream>
#include <vector>
 
int main(int argc, char **argv) {
  int myRank, nProc;
 
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &myRank);
  MPI_Comm_size(MPI_COMM_WORLD, &nProc);
 
  std::vector<int> vector(100, 0);
  if(myRank == 0) vector = std::vector<int>(100, 1);
 
  MPI_Bcast( vector.data(), vector.size(), MPI_INT, 0, MPI_COMM_WORLD );
 
  std::cout << "myRank : " << myRank << ", value in the vector : " << vector.at(0) << std::endl;
 
  MPI_Finalize();
}

Mesures de performances

Effectuez vos mesures de performances sur la machine baobab avec un broadcast d'un tableau de 100'000'000 de int avec 1, 2, 4, 8, 16, 32 et 64 coeurs.

Pour calculer un temps d'exécution, vous devez d'abord vous assurer que tout les processus atteignent le même point avant de commencer puis que tout les processus aient terminé l'opération. Pour ce faire, vous devez utiliser les primitives MPI_Barrier et MPI_Wtime.

Par exemple:

#include <mpi.h>
#include <iostream>
 
int main(int argc, char **argv) {
  int myRank, nProc;
 
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &myRank);
  MPI_Comm_size(MPI_COMM_WORLD, &nProc);
 
  MPI_Barrier(MPI_COMM_WORLD);
  double start = MPI_Wtime();
 
  // execution de l'algorithme
 
  MPI_Barrier(MPI_COMM_WORLD);
  double end = MPI_Wtime();
 
  if(myRank==0) std::cout << "temps de l'operation : " << end-start << "[s]" << std::endl;
 
  MPI_Finalize();
}

Broadcast simple

pseudo code du broadcast simple (tout les pseudo codes sur cette page supposent que la source est le processus 0):

si rang = 0
  pour i de 1 à nproc-1
    envoyer data à i
sinon
  recevoir data

Broadcast en anneau

pseudo code du broadcast en anneau:

si rang = 0
  envoyer data à 1 et à 2 si ils existent
sinon
  recevoir data
  envoyer data à rang+2 si il existe

Broadcast sur un hypercube

pseudo code du broadcast sur un hypercube:

dimension est log2(nproc)
pour étape de 0 à dimension-1
  si source à cette étape
    voisin est le processus voisin dans la dimension étape+1
    envoyer data à voisin
  si récepteur à cette étape
    recevoir data

La difficulté du broadcast sur un hypercube réside dans le fait qu'il faut être capable de déterminer si un processus est une source ou un récepteur à l'étape courante et quel est son voisin si le processus est une source.

Pour cela, il faut considérer que les processus sont disposés et adressés comme sur la figure 3.12 page 72 du cours, c'est à dire que les voisins d'un processus dans un hypercube sont les processus dont la valeur du rang ne diffère que d'un bit. Ensuite, on applique l'algorithme décrit sur la figure 3.14 page 74 du cours.

Pour savoir si un processus est une source à l'étape i, il faut regarder si il y a des 1 en position i ou plus de son adresse. Si ce n'est pas le cas, le processus est une source à cette étape. Pour savoir si un processus est un récepteur à l'étape i, il faut regarder si le bit i de son adresse vaut 1 et si il n'y a que des 0 sur la gauche. Si c'est le cas, le processus est un récepteur à cette étape.

Ensuite, pour calculer le voisin auquel envoyer le message si le processus est une source, il suffit d'inverser le bit se trouvant en position i de l'adresse du processus.

Par exemple si step va de 0 à dimension-1, test pour savoir si le processus est une source:

if(rank >> step == 0)

Test pour savoir si le processus est une destination:

if(rank >> step == 1)