Le jeu de la vie, inventé par J. Conway en 1970, simule une forme très basique de vie en partant de deux principes simples: pour pouvoir vivre, il faut avoir des voisins; mais quand il y en a trop, on étouffe.
Le «monde» est un grand damier qui contient des cellules vivantes ou mortes. Le temps est découpé en étapes: à chaque étape, pour chaque cellule , on compte le nombre de cellules voisines (parmis les 8) qui sont vivantes et on en déduit si la cellule survit ou si elle meurt en fonction de son nombre de voisin.
Pour information: si la cellule c était morte mais qu’exactement 3 cellules voisines étaient vivantes, la cellule c devient vivante, sinon elle reste morte. Si la cellule c était vivante: si seulement 0 ou 1 cellule voisine était vivante, la cellule c meurt d’isolement ; si 2 ou 3 cellules voisines étaient vivantes, la cellule c survit ; si 4 ou plus cellules voisines étaient vivantes, la cellule c meurt par étouffement.
Le projet git LifeGame contient une implémentation séquentielle du jeu de la vie. Le monde y est représenté par un grand tableau de booléens de taille int *board, chaque case valant 1 si une cellule y vit, 0 sinon. Pour chaque étape (le contenu de la grande boucle for), on calcule le nombre de voisins de chaque cellule dans le tableau nbngb, puis l’on calcule le nouvel état des cellules vivantes. Pour éviter de traiter de manière particulière les cellules sur les bords, le tableau est indicé de 1 à BS, et les indices 0 et BS+1 restent figés avec une valeur particulière qui est relativement neutre. Dans la version fournie, un petit tas de cellules est placé de manière particulière. En principe il se déplace de manière régulière. Cela vous permettra de vérifier que votre programme fonctionne bien.
Comme le jeu de la vie est par essence parallèle (chaque cellule devient vivante ou meurt en ne se souciant que de ses voisines proches), on se propose de le paralléliser pour accélérer son exécution sur des architectures parallèles: le domaine est découpé en morceaux, chaque thread effectuant alors l’ensemble des itérations sur un morceau.
Dans chaque partie de ce TD, on tracera des courbes de speedup pour comparer les performances obtenues, en faisant varier par exemple le nombre de threads/processus (passage à l’échelle fort), ou bien la taille du problème, ou bien les deux de la même façon (passage à l’échelle faible).
Pour les mesures, il faudra bien sûr utiliser une valeur de N plutôt grande (4096 par exemple), un nombre d’itérations suffisants (50 ou plus par exemple), et ne pas activer l’affichage! Le calcul num_alive est là pour vérifier rapidement si le résultat a l’air de rester correct selon le nombre de threads/processus mais aussi pour empêcher le compilateur d’optimiser trop agressivement.
Notes à propos des compte-rendus
Les expériences se feront sur les machines du cluster plafrim. Vous penserez a fournir un makefile/cmake pour compiler l’ensemble des versions demandées, ainsi que les scripts de tests et de génération de courbes. Le rapport devra à la fois discuter des choix d’implémentation et montrer des courbes de speedup (en fonction du nombre de threads, en fonction de la taille du domaine), en fonction de la machine, mais aussi et surtout les commenter. De bonnes courbes non analysées valent moins que de mauvaises courbes bien commentées. Commenter, cela veut non seulement dire l’allure général de la courbe (par exemple «comportement linéaire jusqu’à un palier à partir de »), mais aussi donner votre avis: pourquoi la courbe a-t-elle cette forme, pourquoi c’est mieux que les précédentes, ou bien pourquoi elle est mauvaise, etc.
Version mémoire partagée
Version OpenMP
Commencez par paralléliser le code fourni à l’aide de directives OpenMP. Attention, vérifiez bien que le nombre de cellules vivantes reste bien toujours le même d’une exécution à l’autre, sinon c’est qu’il y a un problème de partage de variable entre threads ou bien un problème de dépendance de données (remarquez bien que le calcul de chaque nouvel élément de board dépend du calcul des nbngb des voisins, il y a donc des dépendances aux frontières entre morceaux de domaines, on ne peut pas utiliser de clause nowait!)
Voici quelques questions qui pourront vous guider
- Vaut-il mieux paralléliser à la fois les boucles en
iet enj, ou seulement une des deux dimensions (et laquelle)? Pourquoi? - Le travail des threads est-il équilibré?
- Le caractère NUMA de la machine influe-t-il sur les performances? Est-il intéressant de fixer les threads sur un coeur de calcul?
- A-t-on intérêt à utiliser l’hyperthreading si il est présent?
- Le caractère privée/partagée des variables influe-t-il sur les performances?
Enfin, il peut être possible d’améliorer le rendement du cache en utilisant une technique de pavage à l’aide de macro-cellules. Discutez de l’intérêt de cette technique pour le jeu de la vie en fonction du nombre de threads utilisés, de la taille du problème et des caractéristiques du processeur visé.
Version pthread
Dans la version OpenMP, la directive pragma openmp for effectue une barrière de synchronisation globale. C’est certes simple à implémenter, mais c’est abusif: les threads n’ont vraiment besoin de se synchroniser qu’avec les threads voisins. On atteint ici les limites de la facilité d’expressivité d’OpenMP.
Ecrivez donc une version utilisant des pthreads. Il vous faudra déplacer le code de la boucle depuis main le vers une fonction qui sera exécutée par chaque thread. main se chargera désormais de créer un certain nombre de threads, chacun exécutant la boucle sur une portion du tableau board. Pour synchroniser les threads entre eux et pour respecter les dépendances de données, vous pourrez utiliser des mutex/sémaphores. Note: n’hésitez pas à utiliser de nombreux mutex/sémaphores, sinon vous risquez de rencontrer des scénarios d’interblocage ou de sérialisation.
Raffinement
En y regardant de plus près, on peut s’apercevoir que cette synchronisation pourrait être scindée en deux temps si chaque thread pouvait distinguer le calcul des cellules « intérieures » à sa zone du calcul des cellules sur les bords (qui devront par conséquent attendre des résultats des voisins et du centre). Ainsi, à chaque itération, chaque thread pourrait d’abord calculer les bords de sa zone, puis signaler qu’il a terminé ce calcul, puis calculer l’intérieur et enfin attendre que ses voisins aient terminé leurs bordures respectives.
Quel est l’intérêt d’une telle décomposition de la synchronisation? Modifiez votre code en conséquence.
Version mémoire distribuée: MPI
Nous nous intéressons maintenant à l’implémentation d’une version MPI du jeu de la vie, pour tirer parti de plusieurs noeuds du cluster plafrim et de son réseau Infiniband. On pourra bien sûr garder sous les yeux les pages de man de ces fonctions MPI, mais sur http://mpi.deino.net/mpi/mpi_functions/ la documentation est plus fournie et d’autres exemples de codes sont disponibles. Une documentation très détaillée est disponible sur http://www.netlib.org/utk/papers/mpi-book/mpi-book.html.
Pour l’instant faisons simple: un seul thread par machine.
Chaque noeud va devoir traiter une portion du tableau board. Les processus MPI voisins devront s’échanger les résultats obtenus sur les frontières de leurs portions avant de passer à l’étape suivante.
Communications synchrones
Dans un premier temps, on souhaite tester une version basée sur un découpage similaire à l’approche OpenMP. Ecrivez une version utilisant des processus MPI, et dont les bords sont échangés par le biais de la fonction . Rq: les topologies MPI peuvent permettre de faciliter le découpage et les communications.
Communications Asynchrones
Cette première version comme la version OpenMP est limitée par les synchronisations qui apparaissent aux bord. Une solution consistent à faire du recouvrement calculs/communications en essayant de recouvrir la communication des bords par le calcul de la partie centrale. Modifiez la version précédente pour exploitez les communications asynchrones pour permettre ce recouvrement.
Communications Persistantes
On s’aperçoit rapidement que l’implémentation de ce problème repose sur un ensemble de communication qui est répété à l’identique à chaque étape de calcul. Pour éviter de devoir recalculer les données d’entête et de placement des données à chaque envoi, MPI propose des communications persistantes que l’on peut relancer autant de fois que
nécessaire. Modifiez la version précédente pour utiliser des communications persistantes en remplacement des appels asynchrones.
Comparez l’ensemble des versions implémentées, en mémoire partagée et distribuée, sur un noeuds de calcul, et sur plusieurs pour les versions MPI.
Remarque
Selon la répartition initiale des cellules, il arrive que l’état de toute une zone reste inchangé après une étape de calcul (lorsqu’il n’y a aucune cellule vivante, par exemple). Cette zone ne changera donc plus tant que les bordures ne changeront pas non plus. Pour de telles zones, on peut économiser du temps de calcul en ne faisant simplement rien!
Est-ce que le temps de calcul global de la simulation va s’en trouver accéléré ? Discutez en fonction du nombre de threads par rapport au nombre de processeurs et du jeu de données.
Il peut découler de ce phénomène des irrégularités entre les temps de calcul des différentes portions de tableau. En particulier, si le contenu d’une portion ne change pas à l’étape i, calculer cette même portion à l’étape i+1 demandera peu d’effort car dans ce cas seules les frontières sont à recalculer. Certains coeurs peuvent donc se retrouver inactifs alors que d’autres n’ont pas fini leur travail.
Discutez (sans coder) de l’élaboration d’un procédé pour répartir efficacement la charge sur le cluster de machines Infini.