Programmation Multicoeur - TP 3

Parallélisation de boucle

L’un des intérêts des threads est qu’ils permettent d’améliorer les performances d’un programme lorsqu’il est exécuté sur une machine multicoeur (autrement dit à peu près n’importe quelle machine aujourd’hui). Il existe plusieurs “patrons” de parallélisation de code qu’il faut connaitre, nous allons nous intéresser pour le moment au plus simple d’entre eux, la parallélisation de boucle, et nous allons le faire sur un problème très simple, le comptage du nombre d’occurrences d’une valeur donnée dans un tableau.

Exercice

  1. Récupérez l’archive du TP précédent. Exécutez et lisez le code dans le répertoire exo3_nbOccurs/.

  2. Implémentez la méthode nbOccursParallel2 qui calcule le nombre d’occurences en utilisant deux threads qui se partagent la première et la deuxième moitié du tableau. Exécutez et vérifiez que le résultat est correct et le speedup raisonnable.

  3. Implémentez la méthode nbOccursParallelN qui calcule le nombre d’occurrences en utilisant N threads. Exécutez et vérifiez que le résultat est correct et le speedup raisonnable (attention, la création de thread coûte cher, vous serez loin d’un speedup de N).

  4. Ré-implémentez la méthode nbOccursParallelN en utilisant un ExecutorService et un ArrayList de Future.

Map Reduce

Map Reduce est un patron de parallélisation de boucle très utilisé en analyse de données pour lequel un certain nombre d’intergiciels (middleware) ont été développés (le plus célèbre étant certainement Hadoop). Le but de cet exercice n’est pas de découvrir l’un de ces intergiciels, mais de comprendre ce qu’est Map Reduce et découvrir quelques applications possibles.

Qu’est-ce que Map Reduce?

C’est la combinaison de deux fonctions d’ordre supérieur (des fonctions qui prennent en argument des fonctions, comme vous avez du en voir en programmation fonctionnelle) - map f coll renvoie une nouvelle collection dont les items sont les f(x) où x parcours la collection coll. Par exemple, si la collection coll est un tableau [x1,...,xn], map f coll renvoie le tableau [f(x1),...,f(xn)]. - reduce plus zero coll est la “somme au sens de plus et zero” des éléments de la collection coll. Ce n’est pas nécessairement une somme de nombres au sens de l’addition sur les entiers (ou les flottants). On peut aussi “sommer en concaténant” des chaines de caractères (et dans ce cas zero est la chaîne de caractère vide), moyenner des valeurs pondérées (plus est la moyenne pondérée), composer des chemins dans un graphe, etc.

Exercice

  1. Récupérez le code et allez dans exo1_map_reduce/. Que font les fonctions nbItems et concat?

  2. Utilisez la fonction mapReduceSequential pour redéfinir la fonction nbOccurs de l’exercice précédent. Testez votre code.

  3. Optionnel (si vous avez un peu d’avance): à l’aide de mapReduceSequential, définissez une fonction nearestNeighbor(x, distance, coll) qui renvoie le (ou plutot, “un”) plus proche voisin de x au sens de distance parmi les items de coll.

  4. Donnez une version parallèle mapReduceParallel2 de mapReduceSequential utilisant deux threads, puis une version mapReduceParallelN utilisant N threads.

  5. Donnez une version mapReduceStream de mapReduceSequential dont l’argument coll est un flot (Stream), puis utilisez le parallélisme sur les flots pour rendre votre code parallèle (voir un tutoriel ici)

Simulation d’automate cellulaire

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

  1. Récupérez le code et allez dans exo2_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.

  2. 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.

  3. 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).