Pour cette troisième séance, on commence par terminer le TP de la dernière fois sur la parallélisation de boucle puis on fait un cours sur la linéarisabilité, l’algorithme de Peterson, et diverses structures de données concurrentes à bases de listes chaînées.
La simulation numérique est l’un des meilleurs clients du calcul parallèle. Pour en donner un petit aperçu sans s’embarquer dans des schémas numériques trop matheux, on va s’intéresser à quelque chose que vous avez déjà vu (je crois?) avec M. Formenti: les automates cellulaires. Ce sera aussi l’occasion de réviser ce qu’on a vu la semaine dernière.
Exercice
Récupérez le code et allez dans exo1_autocell/. Donnez une nouvelle version séquentielle nthConfigRecycling de nthConfig qui évite d’allouer de manière répétée des tableaux en “recyclant” le tableau utilisé précédemment. Comparez le temps d’exécution et le résultat.
Définissez la méthode nthConfigurationParallel. Faites d’abord avec ce que vous connaissez, en créant puis supprimant des threads (ou des tâches) à chaque calcul d’une configuration.
Pour “recycler” des threads, il suffit de les mettre en attente des autres threads (au moins, des deux voisins) à la fin de chaque itération. À vous de jouer! Vous pourrez utiliser une barrière de synchronisation qui bloque tous les threads, ou les sémaphores de la semaine dernière, qui permettent d’attendre seulement que les deux voisins aient terminé (et permet donc de paralléliser un peu plus).
Les transparents de cours sont ceux de M. Herlihy qui accompagnent le livre The Art of Multiprocessor Programming, et que je remercie d’avoir mis en licence Creative Commons.
On n’en verra qu’une petite partie, selon le temps disponible.