Skip to topic | Skip to bottom
Home
Minfo
Minfo.ParallTDM1r1.9 - 14 Oct 2011 - 08:29 - 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.

Correction affinité CPU

L'affinité CPU peut être reglée au niveau processus, ou au niveau thread. L'API est différente suivant l'implémentation des threads de l'OS considéré. Nous nous basons ici sur les NPTL implémentées dans les noyaux Linux >= 2.6.

La première chose à faire est d'écrire le bout de code permettant de changer l'affinité d'un thread donné:

void change_affinity(int cpu, pthread_t thread) {
    cpu_set_t mask; 
    __CPU_ZERO( &mask ); 
    __CPU_SET( cpu, &mask ); 
    pthread_setaffinity_np(thread, sizeof(mask), &mask);   
}
Ce code est volontairement simplifié et ne fait aucune vérification, en particulier sur le numéro de CPU passé en paramètre.

Ensuite, il faut rajouter, dans la méthode exécutée par chacun des threads un appel

  /* Demande le placement du thread sur le CPU/Core 1 */
  change_affinity(1,pthread_self());

Finalement, pour que l'effet soit visible, modifions le programme pour que les threads consomment du CPU avec la méthode suivante, qui devra être appelée immédiatement après avoir fixé l'affinité

void 
mange_cpu(void ) {
    /*
     On mange du CPU en mettant du code qui ne devrait pas
     etre supprimé par le compilateur
     */
    int i=1;
   while (1) {
    i=i*2+1;
    if (i%2==0)
      break;
  } 
}

Il ne reste plus qu'à tester

2 threads mangeurs de CPU sur le même Core

On met dans 2 threads le code suivant
  change_affinity(1,pthread_self());
  mange_cpu();

Une fois le programme compilé/lancé, il est possible de voir les threads avec top

   top -H -p `ps  -fe | grep filter3th-Linux | grep -v grep | awk '{print $2}'`
ce qui donne (extrait) sur ma machine

PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
19922 fhuet     20   0     0    0    0 R   50  0.0   0:03.41 filter3th-Linux
19924 fhuet     20   0     0    0    0 R   50  0.0   0:03.40 filter3th-Linux
On voit bien que chaque thread a 50% du cpu, ce qui ici signifie qu'ils ont chacun la moitié d'un core.

2 threads mangeurs de CPU sur deux Core différents

On met dans 1 threads le code suivant
  change_affinity(1,pthread_self());
  mange_cpu();
et dans un autre le code
  change_affinity(2,pthread_self());
  mange_cpu();

Avec top, on obtient

PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
19949 fhuet     20   0     0    0    0 R   99  0.0   0:12.30 filter3th-Linux
19951 fhuet     20   0     0    0    0 R   96  0.0   0:12.14 filter3th-Linux

Cette fois, chacun des processus a 100% du CPU, donc on a bien chacun sur un Core différent.
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