J'essaie de déterminer quelle est la meilleure pratique lors de la conception d'un algorithme parallèle pour le modèle de distribution de données. Quels pourraient être les avantages et les inconvénients de la distribution en bloc par rapport à la distribution cyclique des données en mémoire. Toute aide serait appréciée.Conception d'algorithmes parallèles
La "Programmation parallèle en C avec MPI et OpenMP" de Quinn offre de nombreux exemples de différentes manières de distribuer des données en programmation parallèle. Il y a même un arbre de décision qui vous aide à déterminer quelle approche est la plus pratique, selon vos besoins.
La distribution de blocs dans la mémoire partagée convient le mieux aux algorithmes qui décomposent leur travail en blocs qui nécessitent peu (ou pas) de synchronisation pendant l'exécution de l'algorithme.
La conception d'un algorithme parallèle devrait se concentrer sur la réduction des goulets d'étranglement de synchronisation entre les processus. Un exemple serait une méthode de relaxation de Gauss-Seidel sur une grille à deux dimensions, où la grille est divisée en bandes (1 par processeur) et aucune synchronisation n'est effectuée. Chaque processeur calcule une valeur de convergence indépendante et se termine lorsque ce chiffre est atteint.
Vous devez également prendre en compte la localité de référence des données, ce qui peut avoir un effet marqué sur les algorithmes parallèles et séquentiels.
"La distribution de blocs dans la mémoire partagée convient le mieux aux algorithmes qui se décomposent en blocs qui nécessitent peu (ou pas) de synchronisation pendant l'exécution de l'algorithme." - Cette déclaration n'est pas forcément une vraie, puisque je peux trouver une décomposition cyclique qui me donnera un ensemble de tâches indépendantes, alors que dans le bloc je ne pourrai pas le faire. –
@Artem Barger: vous avez raison. J'aurais dû mentionner la topologie sous-jacente, c'est-à-dire la grille, le tore, etc ... –
Gauss-Seidel est un algorithme presque pathologique à «faire» en parallèle. Ce que vous suggérez, c'est la ligne-Jacobi avec Gauss-Seidel dans chaque bande, un algorithme qui converge extrêmement lentement (par rapport à Gauss-Seidel qui est déjà terrible). – Jed