Exercice 1.
Réaliser un programme C qui
lance 3 threads. Ces trois threads exécutent la fonction
ma_nouvelle_sequence_control
ci-dessous :
//Cette fonction doit recevoir comme argument
//le nom donné au thread
void *ma_nouvelle_sequence_control (void * arg)
{
int i;
for (i = 0 ; i < 10 ; i++) {
printf ("Thread %s: %d\n", (char*)arg,
i);
sleep (1);
}
pthread_exit (0);
}
Exécuter votre programme et interpréter son comportement.
Exercice 2.
(Tri fusion parallèle)
Paralléliser l'algorithme de
tri
fusion en utilisant les threads. On procédera récursivement
: pour trier un morceau de tableau (initialement ce morceau de tableau
est le tableau en entier), un thread commence par découper le morceau de
tableau en deux moitiés, puis crée 2 nouveaux threads, chacun étant
chargé d'appliquer récursivement l'algorithme sur une moitié de tableau,
puis, lorsque les 2 nouveaux threads ont terminé, fusionne les 2 moitiés
triées grâce à la fonction
fusion donnée ci-dessous pour
finalement obtenir le morceau de tableau trié. NB: Si le morceau de
tableau se réduit à 1 élément, le thread n'a rien à faire : Le morceau
de tableau est déjà trié.
Voici une fonction qui fusionne les 2 moitiés triées d'un morceau de
tableau
t[debut..fin]
défini par un indice de début et un indice de fin
:
#define MAX ... // nombre maximum d'éléments dans le tableau à
trier
int t[MAX]; // le
tableau à trier
int temp[MAX]; // un tableau temporaire utilisé par
la fonction fusion
void fusion(int debut, int fin) {
int i1,i2,i,mil;
mil = (debut + fin)/2;
i1 = debut;
i2 = mil+1;
i = debut;
while((i1<=mil) && (i2<=fin)) {
if(t[i1]<t[i2])
{temp[i] = t[i1]; i++; i1++;}
else
{temp[i] = t[i2]; i++; i2++;}
}
while(i1<=mil) {temp[i] = t[i1]; i++; i1++;}
while(i2<=fin) {temp[i] = t[i2]; i++; i2++;}
for(i=debut;i<=fin;i++)
t[i] = temp[i];
}
Exercice 3.
(Fibonacci) Voici ci-dessous une
fonction séquentielle qui calcule le n-ième terme de la suite de
Fibonacci :
int fib (int n)
{
if (n<2) return n ;
else {
int x, y ;
x = fib (n-1) ;
y = fib (n-2) ;
return x + y ;
}
}
L'objectif de l'exercice est de paralléliser ce calcul.
1. Réaliser une première parallélisation en attachant un thread à chacun
des appels récursifs à la fonction
fib(). On construit
ainsi un arbre de threads. Avant de retourner son résultat, un thread
attend que ses deux fils aient terminé.
2.
On propose d'améliorer la solution précédente de la manière suivante :
plutôt que de créer un thread alors que la valeur a déjà été calculée
auparavant par un autre thread, on récupère cette valeur. Pour cela,
on garde les résultats intermédiaires calculés dans un tableau partagé
entre les threads. (Les éléments de ce tableau sont par exemple
initialisés à la valeur INCONNUE pour dénoter que la
valeur n'a pas encore été calculée.)
#define
INCONNUE (-1)
int * fibtab ;
Exercice
4.
(Tri
aléatoire) Ecrire un programme qui trie un tableau t de la façon
suivante : Le thread principal crée plusieurs threads "esclaves".
Chaque thread "esclave" réalise dans une boucle infinie le traitement
suivant : tirer au hasard deux indices de tableau i et j et si les
éléments t[i] et t[j] sont dans le désordre, alors les échanger.
Le thread principal est chargé de surveiller le travail et d'arrêter
les "esclaves" lorsque que le tableau est trié.
Exercice 5.