TP1 (Multithread en Java et C)

Tri fusion parallèle

Nous allons étudier une version parallèle du tri fusion dont l'algorithme séquentiel s'écrit

Tri-Fusion(A[X..Y]) { si X<Y { q = (Y+X)/2 Tri-Fusion(A[X..q]) Tri-Fusion(A[q+1..Y]) Fusionner(A[X..q],A[q+1..Y]) } }

Une version parallèle simple consiste à créer un thread pour chacun des appels à la méthode de tri-fusion et d'attendre leur terminaison pour effectuer la fusion.

1. Dans le cas du tri d'un tableau de 10 entiers, combien de thread seront crées ?
2. Téléchargez, compilez et exécutez le code Trieur.java
3. Modifier le programme pour créer un tableau de nombre aléatoires dont la taille est passée en paramètre sur la ligne de commande.
4. Mesurer la performance de ce code en fonction de la taille du tableau (tracer un graphique)
5. Quelle relation y'a-t-il entre le nombre de threads et la taille du tableau? Que pensez-vous de l'efficacité de cet algorithme?
6. Mesurez le nombre de threads crées et le nombre de threads actifs pour des tableaux de grande taille. En déduire le nombre maximum de threads autorisés sur votre machine.
7. Proposez (sans l'implémenter) une version parallèle plus efficace de cet algorithme.

Multithread en Posix/C

Un producteur-consommateur est une exploitation simple de parallélisme de type pipeline. On associe un thread à chaque étape du traitement, ce qui dans notre cas, revient à avoir un thread qui produit des données et un autre qui les consomme. Il est possible d'étendre ce modèle pour avoir un pipeline à 3 étapes : Reader-Modifier-Writer.

1. Téléchargez, compilez et exécutez le code disponible ici : dalle-thread.h, Makefile, filter3th.c
2. Que fait ce programme ?
3. Quel est le nombre de threads crée? Est-il dépendant de la taille des données ?
4. Créez des fichiers de données aléatoires de taille 1k, 100k, 1M, 10M
   1. Utilisez la commande dd et /dev/random
   2. Linux seulement : testez avec /dev/random et /dev/urandom. Lequel est le plus rapide ? pourquoi ?
5. À l'aide de la commande time, mesurez le temps d'exécution du programme filter3th sur les fichiers précédents et représentez les sur une courbe
   1. Linux seulement : vous avez accès à /usr/bin/time qui est beaucoup plus détaillé que la commande time du shell.
   2. OSX : dtrace est votre ami
6. Testez différentes valeurs de taille de buffer et vérifiez si la vitesse d'exécution varie
7. En utilisant l'API d'affinité CPU expliquée sur http://www.glennklockwood.com/hpc-howtos/process-affinity.html, changez le nombre de coeurs disponibles pour votre programme. Expliquez ce que vous observez.
8. Trouvez une façon de mesurer le temps total pris par chacun des threads (API, ligne de commande...).

De la difficulté du code multithread en Java

Java fournit un modèle de parallélisme explicite qui oblige le programmeur à gérer finement la synchronisation des threads. Le mécanisme de base utilise des moniteurs mais il a depuis était étendu avec une API riche décrite en partie dans ce tutorial.

1. La classe BugThread.java illustre le problème de l'accés concurrent à une variable. Quel est le résultat attendu de ce code? Quel résultat obtenez vous à l'éxécution? Expliquez cette différence, et proposez une correction du programme
2. Les classes ParallelHighLevel.java et ParallelLowLevel.java montrent un pattern simple où un thread principal crée deux threads fils et attend qu'ils aient fini. L'une de ces classes utilise un compteur explicite tandis que la deuxième repose sur un mécanisme de plus haut niveau, les Executors. Modifiez ces deux classes pour créer 4 thread fils et comparez les modifications nécessaires.
3. La classe Deadlock.java ne marche pas Quel est le problème ? Proposez une solution.