Skip to topic | Skip to bottom
Home
Minfo
Minfo.ParallTDM1r1.8 - 14 Sep 2010 - 09:04 - FabriceHuettopic end

Start of topic | Skip to actions
Le but de ce TP est de se (re)familiariser avec la notion de programmation multithread à travers des mettant en avant différents modèle de parallélisme. Ces exercices sont directement inspirés du programme de L3. Certains programmes devront être écrits en Java, d'autres en C. Pour certaines questions, l'utilisation d'une machine multi-core est indispensable.

Exercice 1, 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.

a) Téléchargez, compilez et exécutez le code disponible ici : dalle-thread.h, Makefile, filter3th.c

b) Que fait ce programme ?

c) Quel est le nombre de threads crée? Est-il dépendant de la taille des données ?

d) Créez des fichiers de données aléatoires de taille 1k, 100k, 1M, 10M

e) À l'aide de la commande time, mesurez le temps d'exécution du programme filter3th sur les fichiers précédents.

f) Testez différentes valeurs de taille de buffer et vérifiez si la vitesse d'exécution varie

g) En utilisant l'API d'affinité CPU expliquée sur http://www.cyberciti.biz/tips/setting-processor-affinity-certain-task-or-process.html et http://www.thinkingparallel.com/2006/08/18/more-information-on-pthread_setaffinity_np-and-sched_setaffinity , essayez de placer certains threads sur un core particulier. Selon-vous, quelle positionnement pourrait être le plus efficace ?

h) Trouvez une façon de mesurer le temps total pris par chacun des threads (API, ligne de commande...).

Exercice 2, Tri fusion parallel

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

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

Une version parallèle simple consiste à créer un thread pour chacun des appels à la méthode de 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 disponible ici : http://deptinfo.unice.fr/~grin/mescours/linfo/poo/tp/tpthreads/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) 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?

5) En utilisant la notion d'affinité CPU, forcez tous les threads de la JVM sur le même core. Y'a-t-il une différence de performance par rapport aux cas précédents? Comment pouvez vous vérifier que l'affinité a bien été respectée ?

6) Proposez (sans l'implémenter) une version parallèle plus efficace de cet algorithme

Exercice 3, 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 frown Quel est le problème ? Proposez une solution.


to top

I Attachment sort Action Size Date Who Comment
dalle-thread.h manage 2.4 K 11 Sep 2008 - 16:34 FabriceHuet  
Makefile manage 0.6 K 11 Sep 2008 - 16:39 FabriceHuet  
filter3th.c manage 5.8 K 11 Sep 2008 - 16:35 FabriceHuet  
BugThread.java manage 0.9 K 14 Sep 2010 - 08:58 FabriceHuet  
Deadlock.java manage 1.2 K 14 Sep 2010 - 08:58 FabriceHuet  
ParallelHighLevel.java manage 1.3 K 14 Sep 2010 - 08:58 FabriceHuet  
ParallelLowLevel.java manage 1.3 K 14 Sep 2010 - 08:58 FabriceHuet  

You are here: Minfo > ParallRepa > ParallTDM1

to top

Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback