Les Threads
Hello world !
On souhaite maintenant que les threads affichent Hello from thread n, où n est un entier qui identifie chaque thread. Ce n doit donc varier de 0 à 3 et deux threads ne peuvent pas avoir le même identifiant.
Pour obtenir un identifiant, vous pouvez définir une variable static dans la fonction exécutée par les threads. Cette variable compte le nombre de threads déja créés, et peut être incrémentée pour chaque thread.
Si plusieurs threads incrémentent la variable au même moment, on risque de manquer certains incréments et plusieurs threads risquent d'avoir le même identifiant. Une solution est d'accéder à cette variable en exclusion mutuelle (avec un mutex), ou de rendre la variable atomique (avec le mot-clé _Atomic).
On souhaite maintenant que les threads s'attendent avant de disparaître. Voici un exemple d'exécution souhaitée:
Sans synchronisation entre les threads, les affichages sont désordonnés, par exemple:
Pour synchroniser les threads, il est nécessaire d'implémenter une barrière. Définissez une structure barrier contenant:
- barrier_size: un entier indiquant le nombre de threads que la barrière doit synchroniser;
- count: un entier indiquant le nombre de threads ayant atteint la barrière;
- mutex: un mutex protégeant l'accès à count.
Implémentez les fonctions suivantes:
- void barrier_init(struct barrier* barrier, int barrier_size): initialise une barrière. Cette fonction est appelée une fois au démarrage du programme pour initialiser une barrière à barrier_size threads.
- void barrier_wait(struct barrier* barrier): cette fonction est appelée par les différents threads du programme pour se synchroniser.
Modifiez le programme pour initialiser une barrière à n threads au démarrage. Modifiez également code exécuté par les threads pour qu'ils appellent barrier_wait entre le message "Hello" et le message "Goodbye".
Lorsqu'un thread atteint la barrière, il faut incrémenter count. Si count != barriere_size, il faut attendre que les autres threads aient atteint la barrière.La fonction sched_yield() "relache" le processeur et permet aux autres threads de s'exécuter. Elle est particulièrement utile lorsqu'il y a plus de threads que de CPUs.
Pour aller plus loin
Une implémentation naïve de la barrière rencontre généralement un problème lorsque les threads appellent la barrière plusieurs fois de suite. Vérifiez si votre implémentation est capable de synchroniser les threads plusieurs fois en ajoutant une boucle autour des affichages des threads. On souhaiterait obtenir :
Si votre implémentation de la barrière ne produit pas cet affichage, il est nécessaire de la corriger.
Une manière simple de corriger le problème est d'ajouter à la structure barrier un entier round qui compte le nombre de barrières ayant été complétées (c'est à dire pour lesquelles tous les threads ont atteint la barrière).Parallélisation de l'équation de la chaleur
Le programme heat.c résout de manière itérative l'équation de la chaleur dans un domaine à 2 dimension. A chaque itération, et pour chaque point (i, j) du domaine, on calcule la moyenne des points autour de (i, j). Lorsque le domaine est grand, le programme nécessite beaucoup de ressources de calcul. L'objectif de cet exercice est de paralléliser le programmer afin de l'accélérer.
- Le thread 0 traitera les lignes 1 à 7
- Le thread 1 traitera les lignes 8 à 15
- Le thread 2 traitera les lignes 16 à 23
- Le thread 3 traitera les lignes 24 à 30
Dans un premier temps, modifiez le programme pour qu'il crée 4 threads. Le thread principal attend ensuite que les threads se terminent. Chaque thread doit recevoir en paramètre une structure thread_param contenant:
- Un pointeur vers le struct map à calculer
- Un entier i_start correspondant à la borne inférieure qu'il doit traiter
- Un entier i_stop correspondant à la borne supérieure qu'il doit traiter
Chaque thread doit récupérer un identifiant unique et afficher un message indiquant les bornes qui lui sont attribuées:
Modifiez le programme pour que les threads traitent les lignes qui leur sont affectées. Pour chaque point (i, j), le thread doit appeler la fonction compute_next_value.
Pour afficher les valeurs calculées, ajoutez un appel à swap_values et à print_map à la fin de la fonction main, après la terminaison des threads.
Pour calculer plusieurs itérations, il est nécessaire que les threads se synchronisent. En effet, le calcul de l'itération N nécessite les valeurs calculées à l'itération N-1. Un thread ne peut donc commencer l'itération N qu'après que ses voisins aient calculé l'itération N-1.
La barrière que vous avez implémentée dans le premier exercice de ce TP est le type de synchronisation le plus adapté pour ce problème. Vous pourriez donc recopier le code du premier exercice. Mais au lieu de dupliquer du code, utilisez plutôt l'implémentation des barrières fournie par la bibliothèque pthread.
Ajoutez un pthread_barrier_t à la structure map, et initialisez ce champs dans main en appelant int pthread_barrier_init(pthread_barrier_t *restrict barrier, const pthread_barrierattr_t *restrict attr, unsigned count). Ici, count doit être égal à NB_THREADS+1 car outre les NB_THEADS threads de calcul, le thread main sera chargé d'afficher les données calculées à chaque itération.
Dans main, ajoutez (après la création des threads) une boucles de niter itérations qui:
- Attend que les threads aient calculé une itération. Pour cela, appelez la fonction int pthread_barrier_wait(pthread_barrier_t * barrier)
- Appelle les fonction swap_values et print_map
- Signale aux threads de calcul que les données ont été affichées et qu'ils peuvent calculer la prochaine itération. Là encore, vous pouvez appeler pthread_barrier_wait
- Attend une seconde (en appelant sleep) pour laisser le temps à l'utilisateur d'admirer ces jolies couleurs.
Modifiez le code des threads pour qu'ils effectuent niter itérations du calcul. A la fin de chaque itération de calcul, les threads doivent appeler pthread_barrier_wait (une fois pour signaler au thread main que les données sont prêtes, et une fois pour attendre la fin de l'affichage des données).
Pour aller plus loin
On souhaite maintenant mesurer les performances du programme parallèle. Pour cela, supprimez l'affichage dans la fonction main, et augmentez la taille de la matrice à traiter (par exemple, choisissez une matrice 4096 x 4096).
Afin d'étudier les performances du programme, il faut mesurer le temps de calcul. Pour cela, appelez clock_gettime(CLOCK_MONOTONIC, &t1) avant la création des threads, et clock_gettime(CLOCK_MONOTONIC, &t2) après leur terminaison. La durée du calcul est alors la différence entre t2 et t1. Affichez cette durée en secondes.
On mesure souvent les performances d'une application parallèle en calculant son accélération (ou speedup) pour différents nombres de threads. L'accélération d'un programme pour N threads est calculé de la manière suivante:
Faites varier le nombre de threads et mesurez le temps d'exécution. Tracez une courbe qui présente le speedup en fonction du nombre de threads.
Vous pouvez ensuite implémenter plusieurs optimisation pour améliorer les performances de votre programme. Vous pouvez par exemple faire du loop tiling.
