J'essaie de mettre en œuvre un algorithme de stencil 2D qui manipule une matrice. Pour chaque champ de la matrice, les champs ci-dessus, ci-dessous, gauche et droite doivent être ajoutés et divisés par 4 afin de calculer la nouvelle valeur. Ce processus peut être itéré plusieurs fois pour une matrice donnée.Exécution paralellée dans imbriquée pour utiliser Cilk
Le programme est écrit en C et compile avec le binaire cilkplus gcc.
** Edit: je me suis dit que vous pourriez intéressé par les drapeaux du compilateur:
~/cilkplus/bin/gcc -fcilkplus -lcilkrts -pedantic-errors -g -Wall -std=gnu11 -O3 `pkg-config --cflags glib-2.0 gsl` -c -o sal_cilk_tst.o sal_cilk_tst.c
S'il vous plaît noter que le vrai code deimplique un peu d'arithmétique de pointeur pour garder tout cohérent. L'implémentation séquentielle fonctionne. J'omets ces étapes ici pour améliorer la compréhensibilité.
Un pseudo-code ressemblerait à quelque chose comme ça (pas de traitement de cas limite):
for(int i = 0; i < iterations; i++){
for(int j = 0; j < matrix.width; j++){
for(int k = 0; k < matrix.height; k++){
result_ matrix[j][k] = (matrix[j-1][k] +
matrix[j+1][k] +
matrix[j] [k+1] +
matrix[j] [k-1])/4;
}
}
matrix = result_matrix;
}
Le calcul du pochoir lui-même est alors déplacé vers la fonction apply_stencil(...)
for(int i = 0; i < iterations; i++){
for(int j = 0; j < matrix.width; j++){
for(int k = 0; k < matrix.height; k++){
apply_stencil(matrix, result_matrix, j, k);
}
}
matrix = result_matrix;
}
et parallélisation est tentée:
for(int i = 0; i < iterations; i++){
for(int j = 0; j < matrix.width; j++){
cilk_for(int k = 0; k < matrix.height; k++){ /* <--- */
apply_stencil(matrix, result_matrix, j, k);
}
}
matrix = result_matrix;
}
Cette version compile sans erreur s/warning, mais tout droit produit un Floating point exception
lorsqu'il est exécuté. Au cas où vous vous poseriez la question: Peu importe laquelle des boucles for est faite dans les boucles cilk_for. Toutes les configurations (sauf no cilk_for) produisent la même erreur.
possible autre méthode:
for(int i = 0; i < iterations; i++){
for(int j = 0; j < matrix.width; j++){
for(int k = 0; k < matrix.height; k++){
cilk_spawn apply_stencil(matrix, result_matrix, j, k); /* <--- */
}
}
cilk_sync; /* <--- */
matrix = result_matrix;
}
Ce produit 3 avertissements lors de la compilation: i, j
et k
semblent être non initialisée. Lors de la tentative d'exécution, la fonction qui exécute l'étape matrix = result_matrix;
semble être indéfinie.
Maintenant pour la vraie question: pourquoi et comment Cilk rompt mon code séquentiel; ou plutôt comment puis-je l'empêcher de le faire?
Le code réel est bien sûr également disponible, si cela vous intéresse. Cependant, ce projet est destiné à une classe universitaire et donc sujet au plagiat d'autres étudiants qui trouvent ce fil, c'est pourquoi je préférerais ne pas le partager publiquement.
** MISE À JOUR:
Comme suggéré que je tentais d'exécuter l'algorithme avec seulement 1 thread de travail, ce qui rend effectivement la séquence de mise en œuvre de CILK. Ce a fait, étonnamment, fonctionne bien. Cependant dès que je change le nombre de travailleurs à deux, les erreurs familières reviennent.
Je ne pense pas que ce comportement soit causé par les conditions de course. Comme la matrice de travail est modifiée après chaque itération et que cilk_sync
est appelée, il n'y a effectivement pas de section critique. Tous les threads ne dépendent pas des données écrites par d'autres dans la même itération.
Les prochaines étapes que je vais essayer est d'essayer d'autres versions du compilateur cilkplus, pour voir si c'est peut-être une erreur de leur côté.