Bonsoir,

Je suis en train d'essayer de la paralléliser la multiplication de deux matrices supposées carrées de même taille à l'aide de MPI en partant du principe que je me trouve sur un cluster de type anneau.

J'ai commencé à écrire un morceau de code en C en suivant l'algorithme suivant :

Soit deux matrices A et B de taille 4x4 chacune. Je pars du principe qu'on a 4 proc lors de l'execution de MPI (ensuite je généraliserai). Soit i=0, le proc maître fait un Send de la ligne i puis un Send de la colonne i au proc i tant que i <nb_proc.

Ensuite chaque proc récupère sa ligne/colonne. Il fait le calcule courant avec ce qu'il a comme ligne/colonne pour calculer la première case de la colonne résultat. Ensuite il envoie sa ligne à son successeur (Send) et reçoit une ligne de son prédécesseur (Recv). Ceci nb_proc - 1 fois afin que chaque proc ai reçu la ligne de chaque autre proc.

Mon problème vient du fait que lorsque chaque proc tente de récupérer sa ligne/colonne envoyée précédemment par le proc maître, seul le maître y parvient, les autres semblent rester bloquant (MPI_RECV est bloquant) et je n'arrive pas à trouver pourquoi.

Je vous ai joint ci-dessous une partie de mon code pour les personnes voulant bien m'aider à comprendre :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
int main(int argc, char ** argv) {
  matrix A;
  matrix B;
  matrix C;
 
  matrix rows_from_A;
  matrix cols_from_B;
  matrix result;
 
  int nb_proc, proc_id, i, j, k, l, successor, predecessor;
  int average = 0;
  int extra;
  int sum;
 
  MPI_Status status;
 
  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_WORLD, &nb_proc);
  MPI_Comm_rank(MPI_COMM_WORLD, &proc_id);
 
  average = 4 / nb_proc;
  extra = 4 % nb_proc;
 
  printf("-------------\n");
  printf("proc = %i\n", proc_id);
  printf("average = %i\n", average);
 
  rows_from_A = create_matrix(average, 4);
  cols_from_B = create_matrix(4, average);
  result = create_matrix(average, average);
 
  /* Processus maître */
  if (proc_id == MASTER) {
    A = create_matrix(4, 4);
    B = create_matrix(4, 4);
    C = create_matrix(A.rows, B.cols);
 
    init_random_matrix(&A);
    init_random_matrix(&B);
    init_matrix(&C);
 
    printf("-- Matrice A --\n");
    display_matrix(A);
 
    printf("-- Matrice B --\n");
    display_matrix(B);
 
    /* On distribue les lignes de A et
       les colonnes de B sur les nb_proc procs */
    for (i = 0; i < nb_proc; i++) {
      printf("i=%i, ", i);
      rows_from_A.data = get_rows_from_matrix(A, i, average);
      cols_from_B.data = get_cols_from_matrix(B, i, average);
 
      printf("-- Lignes de A envoyées au proc %i\n", i);
      display_matrix(rows_from_A);
 
      printf("-- Colonnes de B envoyées au proc %i\n", i);
      display_matrix(cols_from_B);
 
      MPI_Send(rows_from_A.data, average * A.cols, MPI_INT, i, MASTER, MPI_COMM_WORLD);
      MPI_Send(cols_from_B.data, average * B.rows, MPI_INT, i, MASTER, MPI_COMM_WORLD);
    }
  }
 
  /* Chaque proc reçoit les données initiales du MASTER */
  printf("Tentative de réception depuis MASTER sur proc %i\n", proc_id);
  MPI_Recv(rows_from_A.data, 4 * average, MPI_INT, MASTER, proc_id, MPI_COMM_WORLD, &status);
  MPI_Recv(cols_from_B.data, 4 * average, MPI_INT, MASTER, proc_id, MPI_COMM_WORLD, &status);
 
  printf("-- Réception Proc %i --\n", proc_id); 
  display_matrix(rows_from_A);
  display_matrix(cols_from_B);
  printf("-- fin réception\n");
 
  /* Calcul des colonnes résultats */
  for (i = 0; i < nb_proc - 1; i++){
    successor = (proc_id + 1) % nb_proc;
    predecessor = proc_id - 1;
    if (predecessor < 0)
      predecessor = nb_proc - 1;
 
    printf("Calcul local\n");
    /* Calcul local à refaire car incorrect */
    for (j = 0; j < average; j++) {
      for (k = 0; k < average; k++) {
	result.data[j][k] = 0;
	for (l = 0; l < average; l++) {
	  sum = result.data[j][k];
	  result.data[j][k] = sum + rows_from_A.data[j][l] * cols_from_B.data[l][k];
	}
      }
    }
 
    printf("Envoie au successeur %i des lignes de A de %i\n", successor, proc_id);
    /* Envoie à son successeur des lignes et des colonnes */ 
    MPI_Send(rows_from_A.data, 4 * average, MPI_INT, successor, proc_id, MPI_COMM_WORLD);
 
    printf("Réception de son prédecesseur %i des lignes de A\n", predecessor);
    /* Réception de son prédécesseur des lignes et des colonnes */
    MPI_Recv(rows_from_A.data, 4 * average, MPI_INT, predecessor, proc_id, MPI_COMM_WORLD, &status);
 
    printf("-- Réception du predecesseur %i --\n", status); 
    display_matrix(rows_from_A);
    printf("-- fin réception\n");
  }	
 
  /* Chaque proc envoie au proc maître sa matrice résultat */
  // todo
 
  /* Le maître recopie les résultats dans sa matrice C résultat */
  // todo
 
  MPI_Finalize();
 
  return EXIT_SUCCESS;
}
Lorsque je l'exécute on remarque que seul le proc 0 (master) arrive bien à récupérer les lignes/colonnes les autres semblent être en attente comme si rien ne leur a été envoyé. Pourtant les indices dans la boucle qui effectue l'envoie sont bien corrects.

$mpirun -n 4 mul
-------------
proc = 0
average = 1
-- Matrice A --
807 249 73 658
930 272 544 878
923 709 440 165
492 42 987 503

-- Matrice B --
327 729 840 612
303 169 709 157
560 933 99 278
816 335 97 826

i=0, -- Lignes de A envoyées au proc 0
807 249 73 658

-- Colonnes de B envoyées au proc 0
327
303
560
816

-------------
proc = 1
average = 1
Tentative de réception depuis MASTER sur proc 1
i=1, -- Lignes de A envoyées au proc 1
930 272 544 878

-- Colonnes de B envoyées au proc 1
729
169
933
335

i=2, -- Lignes de A envoyées au proc 2
923 709 440 165

-- Colonnes de B envoyées au proc 2
840
709
99
97

i=3, -- Lignes de A envoyées au proc 3
492 42 987 503

-- Colonnes de B envoyées au proc 3
612
157
278
826

Tentative de réception depuis MASTER sur proc 0
-- Réception Proc 0 --
807 249 73 658

327
303
560
816

-- fin réception
Calcul local
Envoie au successeur 1 des lignes de A de 0
Réception de son prédecesseur 3 des lignes de A
-------------
proc = 2
average = 1
Tentative de réception depuis MASTER sur proc 2
-------------
proc = 3
average = 1
Tentative de réception depuis MASTER sur proc 3
Ai-je mal utilisé MPI ? ou bien es-ce un problème de logique ?

Merci à ceux qui voudrons bien essayer de m'aider à comprendre.

Cordialement,

Laurent