181 lines
5.6 KiB
Markdown
181 lines
5.6 KiB
Markdown
# TP : Threads
|
||
|
||
#### Ex1
|
||
```c
|
||
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <pthread.h>
|
||
#include <assert.h>
|
||
|
||
#define NUM_THREADS 16
|
||
|
||
void *thread(void *thread_id) {
|
||
int id = *((int *) thread_id);
|
||
printf("Hello from thread %d\n", id);
|
||
|
||
return NULL;
|
||
}
|
||
|
||
int main() {
|
||
pthread_t threads[NUM_THREADS];
|
||
for (int i = 0; i < NUM_THREADS; i++)
|
||
assert( pthread_create(&threads[i], NULL, thread, &i) == 0);
|
||
|
||
for (int i = 0; i < NUM_THREADS; i++)
|
||
assert( pthread_join(threads[i], NULL) == 0);
|
||
|
||
return EXIT_SUCCESS;
|
||
}
|
||
```
|
||
|
||
1. Est-ce que l’exécution de ce programme est correcte? Vous pouvez vous en assurer en l’exécutant plusieurs fois.
|
||
2. Si vous pensez (et avez constaté) que ce n’est pas le cas, expliquez pourquoi.
|
||
3. Modifiez le code pour qu’il donne le résultat attendu.
|
||
|
||
#### Ex2
|
||
Ecrire un programme max.c qui accepte la ligne de commande :
|
||
|
||
```
|
||
./max n1 n2 n3 n4 n5 n6 n7 n8
|
||
```
|
||
|
||
et qui calcule le maximum des entiers (n1, n2, ..n8) en utlisant le schéma suivant (tournoi) :
|
||
|
||
```
|
||
n1 n2 n3 n4 n5 n6 n7 n8
|
||
2 5 17 26 -3 12 1 3 <--- 4 duels (threads)
|
||
\ / \ / \ / \ /
|
||
\ / \ / \ / \ /
|
||
5 26 12 3 <--- 2 duels (threads)
|
||
\ / \ /
|
||
\ / \ /
|
||
26 12 <--- 1 duel (thread)
|
||
\ /
|
||
\ /
|
||
\ /
|
||
\ /
|
||
26
|
||
|
||
```
|
||
|
||
- Chaque duel est un thread.
|
||
- Le thread prinicpal organise le tournoi, et proclame le vainqueur.
|
||
|
||
|
||
|
||
#### Ex3
|
||
On veut écrire un programme calculant la somme des entiers
|
||
de `1` à `N` à l’aide de `M` threads. Chaque thread calculera la somme
|
||
d’un sous-ensemble de ces entiers et la somme globale sera obtenue en
|
||
calculant la somme des résultats intermédiaires de chaque thread.
|
||
|
||
Les entiers sont répartis uniformément entre les threads comme suit (exemple avec 3 threads) :
|
||
|
||
Thread 1 : 1, 4, 7, ...
|
||
Thread 2 : 2, 5, 8, ...
|
||
Thread 3 : 3, 6, 9, ...
|
||
|
||
|
||
Le programme doit lancer `M` threads, attendre qu’ils se terminent, faire la somme des résultats
|
||
intermédiaires et afficher le résultat. Les valeurs `N` et `M` seront passées en ligne de commande.
|
||
|
||
Il est important que le programme respecte les points suivants :
|
||
|
||
- L’implémentation ne doit utiliser aucune variable globale.
|
||
- Le travail à effectuer pour chaque thread créé doit être aussi équitable que possible, quelles
|
||
que soient les valeurs `N` et `M` choisies par l’utilisateur (ex : N=20, M=8).
|
||
- Évitez d’utiliser un tableau pour contenir les valeurs à additionner.
|
||
- Réaliser un test de validation automatiquement du résultat obtenu (vous devez connaître le résultat !).
|
||
|
||
|
||
Comparez le temps d'éxecution en fonction du nombre de threads.
|
||
|
||
|
||
|
||
```c
|
||
/* pour "mesurer" le temps */
|
||
static inline double tstamp(void)
|
||
{
|
||
struct timespec tv;
|
||
clock_gettime(CLOCK_REALTIME, &tv);
|
||
return tv.tv_sec + tv.tv_nsec * 1.0e-9;
|
||
}
|
||
```
|
||
|
||
#### Ex4
|
||
On souhaite écrire une petite librairie implantant une pile d'entiers. Sa taille sera statique, et determinée au moment
|
||
de sa création. Voici l'interface :
|
||
|
||
```c
|
||
stack_t * stack_create(int max_size);
|
||
```
|
||
crée une pile de taille `max_size`
|
||
|
||
```c
|
||
int stack_destroy(stack_t *s);
|
||
```
|
||
|
||
détruit la pile
|
||
|
||
```c
|
||
int stack_push(stack_t *s, int val);
|
||
```
|
||
|
||
empile la valeur `val` renvoie 1 en cas de succès, 0 sinon.
|
||
|
||
```c
|
||
int stack_pop(stack_t *s,int *val);
|
||
```
|
||
|
||
dépile dans `*val`. renvoie 1 en cas de succès, 0 sinon.
|
||
|
||
|
||
( Décider ce que contiendra la structure stack_t définissant un objet de type pile et penser à insérer des assertions dans le code aux endroits nécessaires.)
|
||
|
||
1. Testez votre implantation avec une utilisation monothreadé.
|
||
2. Testez votre implantation avec ube utilisation multithreadé (une même pile utlisé par plusieurs threads). Cela fonctionne-t-il ?
|
||
3. Ajoutez des primitives d'exclusions mutuelles afin de garantir un comportement cohérent et déterministe dans le cas d’une exécution multi-threadée.
|
||
|
||
|
||
#### Ex5 (Mutltiplication matrice/vecteur, problème du false sharing)
|
||
Le but de l'exercice est de parallèliser le calcul du produit matrice/vecteur.
|
||
|
||
Pour rappel, le produit d'une matrice `A[N][P]` par un vecteur `x[P]` donne un vecteur
|
||
`y[N]` par :
|
||
|
||
```c
|
||
for(i=0;i<N;i++){
|
||
y[i]=0;
|
||
for(j=0;j<P;j++)
|
||
y[i] += A[i][j]*x[j]
|
||
}
|
||
```
|
||
|
||
1. Écrire un programme qui prend en argument un entier `n`, et qui crée autant de threads pour
|
||
le cacul du produit. Chaque thread recevra en argument l'intervalle des indices `i in [start,end]` pour lequels il doit
|
||
effectuer le calcul `y[i]`. Pour le test, utilisez des matrices de type `int` en variables globales préalablement
|
||
initialisées aléatoirement.
|
||
|
||
2. Remplissez le tableau suivant :
|
||
<table>
|
||
<tbody>
|
||
<tr><td rowspan=3>nb Threads</td><td colspan=3>Dimensions</td>
|
||
</tr>
|
||
<tr><td>8000000x8</td><td>8000x8000</td><td>8x8000000</td></tr>
|
||
<tr><td>temps</td><td>temps</td><td>temps</td></tr>
|
||
<tr><td>1</td><td></td><td></td><td></td></tr>
|
||
<tr><td>2</td><td></td><td></td><td></td></tr>
|
||
<tr><td>4</td><td></td><td></td><td></td></tr>
|
||
<tr><td>8</td><td></td><td></td><td></td></tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
Que constatez-vous pour la dernière colonne ?
|
||
[ chaque processeur utilise un cache de premier niveau (L1) dont les lignes font
|
||
64 octets. Les composantes du vecteur `y` ne sont pas accèder de manière concurrente. Mais il se peut qu'une ligne d'un cache contienne une composante écrite par un autre thread dans un autre cache rendant la ligne ```dirty``` ]
|
||
|
||
Modifiez le code pour remédier au problème.
|
||
|
||
|
||
|