Les Threads
Hello world !
Cet exercice va vous permettre de vous échauffer avec les threads !
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 doit être unique pour chaque thread.
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éjà 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 d'afficher un message d'au revoir et 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 devra être 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 sera 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 le 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() "relâche" 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 CPU.
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 dimensions. À 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 (vous pouvez commenter la boucle de simulation dans main pour l'instant). 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 pour l'instant, se contente d'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 (une seule itération). Pour chaque point (i, j) (hors première et dernière colonnes), 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 au nombre de threads plus un, car outre les threads de calcul, le thread main sera chargé d'afficher les données calculées à chaque itération.
Puis, dans main, ajoutez (après la création des threads) une boucles de niter (valeur initiale de 10) 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 (au lieu des appels que vous avez ajoutés après la terminaison des threads)
- Indique 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 deux fois : une première fois pour signaler au thread principal que les données sont prêtes, et une seconde 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 tout affichage dans la fonction main (et la synchronisation correspondante), 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.
int clock_gettime(clockid_t clockid, struct timespec *tp); récupère le temps courant de l'horloge spécifiée par clockid, dans une structure de type struct timespec. Le champ tv_sec de cette dernière donne le temps mesuré en secondes. Ici nous utilisons l'horloge CLOCK_MONOTONIC qui a la particularité d'être monotone, c'est-à-dire de ne pas être affectée par des changements d'horloge (comme un changement d'heure réelle).
De plus, 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.
Réduisons le temps d'exécution de compteurBOOM.c (vu en cours) et apprenons quelques trucs (niveau Ninja ou Padawan curieux·se)
Cet exercice étudie différentes pistes pour réduire le temps d’exécution de l’exemple compteurBOOM.c vu en cours. Cela permet de :
- Mieux comprendre le lien entre fréquence du processeur de la machine et durée d’exécution d’un programme,
- Montrer que paralléliser un programme ne suffit pas pour obtenir une meilleure durée d’exécution (la parallélisation peut même fortement empirer cette durée),
- Prendre conscience que les mutex ne sont pas l’unique solution à tout problème de parallélisme,
- Implémenter le patron de conception MapReduce,
- Mieux comprendre la philosophie de la bibliothèque pthread,
- Jouer avec les priorités de processus.
- A tout instant, vous pouvez visualiser les résultats de nos propres mesures en cliquant sur les champs C'est ici que nous vous présenterons nos mesures.
- Nous allons faire du benchmarking (mesure de performances) dans cet exercice. Pour que ces mesures soient les plus fiables possibles, il est important de ne pas faire tourner d’autres programmes sur votre machine pendant que vous faites vos mesures. Par exemple, évitez de faire tourner votre client de messagerie, votre lecteur de musique, etc. Pendant que vous faites vos mesures, vous pouvez faire tourner un terminal pour exécuter vos commandes, un éditeur de texte pour écrire votre code et un navigateur pour afficher cet énoncé.
Comprendre le temps d’exécution de compteurBOOM_v0_monothread.c
Téléchargez l'archive compteurBoom.tgz et extrayez son contenu.
Vérifiez que vous comprenez ce que fait compteurBOOM_v0_monothread.c, compilez-le et enfin exécutez la commande /usr/bin/time ./compteurBOOM_v0_monothread : la commande /usr/bin/time affiche le temps d’exécution (l’elapsed), le temps CPU utilisé et le pourcentage de CPU utilisé par l'exécution de ./compteurBOOM_v0_monothread.
- Le temps d’exécution (elapsed) est de 0.58 seconde,
- Le temps CPU utilisé est de 0.57+0.00 = 0.57 seconde,
- Le pourcentage de CPU utilisé est de 98%.
Comment estimer le temps d’exécution sans exécuter ce programme ?
Pour répondre à cette question, rappelons que, pour exécuter votre programme, le processeur de votre machine exécute les instructions assembleur générées par le compilateur. Pour visualiser ces instructions, tapez la commande gcc -S -fverbose-asm -Wall -Werror compteurBOOM_v0_monothread.c, puis affichez le fichier compteurBOOM_v0_monothread.s qui a été généré par l'option -S (l'option -fverbose-asm permettant de commenter l'assembleur généré). Retrouvez les instructions correspondant à votre boucle for (i = 0; i < FINAL_COUNTER; i++) et déduisez-en le nombre d’instructions exécutées à chaque tour de boucle.
Dans le code assembleur, repérez la première ligne ayant pour commentaire for (i = 0; i < FINAL_COUNTER; i++). Vous devriez pouvoir identifier les instructions correspondant à l’initialisation de la variable i, à la condition i < FINAL_COUNTER et à l’incrémentation de i.
Voici un exemple d'extrait de compteurBOOM_v0_monothread.s :
Les 4 premières lignes correspondent à l’initialisation de i à 0. Les lignes entre l’étiquette .L3: et l’étiquette .L2: correspondent au corps de votre boucle et à l’incrément i++. Enfin, Les lignes suivant l’étiquette .L2: correspondent au test i < FINAL_COUNTER.
Donc, chaque tour nécessite l’exécution des instructions entre .L3: et .L2: (4 instructions) et celles suivant .L2: (2 instructions), soit un total de 6 instructions.
Déterminez maintenant le temps que met un cœur de votre processeur pour exécuter une instruction. Approximativement, un cœur de votre processeur a besoin d’un cycle d’horloge pour exécuter une instruction. Or, la fréquence de votre processeur désigne le nombre de cycles d’horloge que fait votre processeur (par exemple, un processeur à 1 Mhz exécute 106 cycles d’horloge par seconde) :
- Affichez le modèle de votre processeur (et éventuellement sa fréquence) avec la commande cat /proc/cpuinfo | grep -i "^model name" | awk -F": " '{print $2}' | head -1 | sed 's/ \+/ /g' Sur la machine ssh.imtbs-tsp.eu, cette commande affiche Intel Xeon Processor (Cascadelake) (NB : la commande n'affiche pas de fréquence). Sur la machine de salle TP a005-19, cette commande affiche Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz.
- Affichez sa fréquence en Mhz avec la commande cat /proc/cpuinfo | grep -i "^cpu MHz" | awk -F": " '{print $2}' | head -1 Sur la machine ssh.imtbs-tsp.eu, cette commande affiche 2095.078 (NB : la commande n'affiche pas de fréquence). Sur la machine de salle TP a005-19, cette commande affiche 1088.393.
- Ne gardez que la fréquence qui vous semble la plus plausible. Pour la machine ssh.imtbs-tsp.eu, seule une commande affiche une fréquence (2095.078 MHz). Sur la machine de salle TP a005-19, nous gardons la valeur de fréquence la plus haute qui semble la plus plausible vu la qualité des machines de salle TP, soit 2.90 GHz.
- Déduisez-en une approximation du temps nécessaire pour exécuter la boucle for.
Par exemple, sur la machine ssh.imtbs-tsp.eu, nous retenons la fréquence 2095.078 MHz, soit 2.095078 GHz, soit 2.095078×109 cycles d’horloge par seconde.
Donc, un cycle d’horloge dure environ 1/(2.095078×109) secondes, soit environ 0.477 nanosecondes (ns). Comme chaque tour de boucle nécessite l’exécution de 6 instructions, et que chaque instruction nécessite un cycle d’horloge, alors chaque tour de boucle nécessite environ 6×0.477 ns = 2.86 ns. Enfin, comme la boucle doit être exécutée FINAL_COUNTER = 200000000 fois, le temps nécessaire pour exécuter la boucle est d’environ 200000000×2.862 ns = 0.5724 s, valeur théorique très proche du temps d’exécution mesuré de 0.58 s.
Pistes pour améliorer ce temps d'exécution
Une première piste est d'augmenter la fréquence du processeur pour que chaque cycle d'horloge soit plus court. Cette solution a été pratiquée durant de nombreuses années, mais est confrontée à une limite physique depuis les années 2000. En survolant l'article cet article explique que "2025 commence avec un nouveau record absolu de fréquence CPU : 9121,61 MHz, réalisé avec un exceptionnel Core i9-14900KF refroidi à -258 °C"), (re)trouvez quelle est cette limite physique. Augmenter la fréquence au delà de 3-4 GHz dégage trop de chaleur et nécessite un refroidissement trop important.
Une deuxième piste est de réduire le nombre d'instructions exécutées. Vu que le code semble trop simple pour être optimisé manuellement, demandons au compilateur de le faire en ajoutant l'option -O3 (optimisation maximale, cf. man gcc) à la commande de compilation. Que pensez-vous du résultat de /usr/bin/time ./compteurBOOM_v0_monothread` ? Le temps d'exécution est devenu nul ! Qu'a fait l'optimisation (N'hésitez pas à générer l'assembleur et à l'étudier si vous ne devinez pas ce que l'optimiseur a fait). En générant le code assembleur, on constate que l'optimiseur a supprimé la boucle et stocke directement dans counter l'effet qu'aurait eu l'exécution de la boucle. Pour notre exercice, l'optimiseur fait donc un travail parfait. C'est pourquoi, quand une équipe de développement met en production l'application informatique sur laquelle elle travaille, elle active l'optimisation du compilateur pour être certaine d'avoir des performances optimales. Toutefois, cette activation doit être faite avec circonspection, car elle peut introduire des bugs de fonctionnement (il faut donc vérifier que l'application fonctionne toujours correctement en repassant ses tests unitaires et d'intégration) et rend le debug plus compliqué. De ce fait, il faut parfois être moins ambitieux quant au niveau d'optimisation (option -O2, -O1, voire -O0, valeur par défaut, c'est-à-dire aucune optimisation)
La troisième piste consiste à exploiter le fait que, pour pallier l'impossibilité d'augmenter la fréquence du processeur tout en profitant des progrès en finesse de gravure des circuits, un processeur héberge désormais plusieurs cœurs. Les questions suivantes approfondissent cette idée.
Passage en multithread
Compilez et exécutez /usr/bin/time ./compteurBOOM_v1_2_threads. Vous constatez que :
- Votre programme affiche “BOOM !” pour dire que votre exécution est fausse (des incrémentations de counter ont été perdues).
- L’elapsed est proche, voire supérieur à elapsedmonothread. Sur la machine ssh.imtbs-tsp.eu, nous avons mesuré 1.13 seconde d'elapsed contre 0.58 seconde en monothread.
- Le taux d’utilisation de la CPU est supérieur à 100%. Sur la machine ssh.imtbs-tsp.eu, nous avons mesuré 189% d’utilisation de la CPU, ce qui est logique vu que 2 cœurs s'exécutent simultanément durant la majorité des 1.13 seconde d’exécution.
Nous n’avons exploité que 2 cœurs de votre machine. Tapez la commande cat /proc/cpuinfo | grep -i ^processor | wc -l pour connaître le nombre de cœurs de votre machine, puis écrivez un programme compteurBOOM_v2_N_threads.c (inspiré de compteurBOOM_v1_2_threads.c et utilisant NB_THREAD qui est défini dans ce code) permettant de lancer autant de threads que vous avez de cœurs.
Exécutez /usr/bin/time ./compteurBOOM_v2_N_threads :
- Votre programme affiche toujours “BOOM !” pour dire que votre exécution est fausse.
- L’elapsed est proche, voire supérieur à elapsedmonothread. Sur la machine ssh.imtbs-tsp.eu qui a 16 cœurs, nous mesurons 1.10 seconde contre 0.58 seconde en monothread.
- Le taux d’utilisation de la CPU est de l’ordre de N*100%. Sur la machine ssh.imtbs-tsp.eu qui a 16 cœurs, nous avons mesuré 1514% d’utilisation de la CPU, ce qui est logique vu qu’on exploite 16 cœurs durant la majorité des 1.10 seconde d’exécution.
Comment expliquer l'elapsed proche, voire supérieur, de elapsedmonothread alors que nous exploitons NB_THREAD cœurs et qu'intuitivement, on devrait obtenir un elapsed de l'ordre elapsedmonothread/NB_THREAD ? Il s'agit d'un problème dû à la cohérence de cache: lorsqu'on exécute le programme compteurBOOM_v0_monothread.c, le thread charge la variable counter dans le cache du processeur, et tous les accès à counter sont donc rapides. Mais lorsqu'on exécute NB_THREAD threads, les threads modifient counter de manière concurrente, ce qui invalide le cache des autres threads. Ces derniers doivent donc aller chercher la valeur de counter qui est stockée dans la RAM, ce qui est beaucoup plus couteux (environ 100 ns, contre seulement 0.5 ns pour un accès au cache L1). Les threads passent donc beaucoup de temps à accéder à la mémoire, et peu de temps à exécuter les instructions du programme.
Utilisation d'un mutex pour éviter les pertes d'incrémentations de counter
Nous savons qu'un mutex résout les conflits d'accès simultanés à une variable. Testons s'il résout aussi les problèmes d'elapsed.
cp compteurBOOM_v2_N_threads.c compteurBOOM_v3_N_threads_mutex.c
Modifiez compteurBOOM_v3_N_threads_mutex.c pour éviter les pertes d'incrémentation de counter.
Commencez par tester votre programme en mettant #define FINAL_COUNTER 20000.
Quand vous êtes sûr·e qu’il fonctionne correctement, remettez #define FINAL_COUNTER 200000000, recompilez et exécutez /usr/bin/time ./compteurBOOM_v3_N_threads_mutex (soyez patient·e, car cette exécution peut prendre plusieurs dizaines de secondes) et commentez. le résultat.
La valeur de counter est redevenue correcte. Toutefois, les NB_THREAD cœurs passent leur temps à attendre de pouvoir prendre le mutex : cette implémentation multiplie elapsedmonothread par plusieurs dizaines.
Utilisation d'une variable 'atomique' pour éviter les pertes d'incrémentations de counter
Comme la définition d'un mutex pour accéder à une variable partagée est lourde en termes d'écriture de code et de performances, il existe des variables dites "atomiques" qui permettent d'éviter les pertes d'incrémentation de counter sans utiliser de mutex. Ces variables améliorent-elles l'elapsed ?
cp compteurBOOM_v2_N_threads.c compteurBOOM_v4_N_threads_atomic.c
Le standard C11 définit le mot-clé _Atomic qui permet de déclarer une variable atomique (par exemple _Atomic int n; déclare un entier atomique n). Modifiez compteurBOOM_v4_N_threads_atomic.c pour utiliser une variable atomique pour counter.
Exécutez /usr/bin/time ./compteurBOOM_v4_N_threads_atomic et commentez le résultat.
La valeur de counter reste correcte et les performances sont plusieurs fois meilleures que celles observées avec un mutex. Toutefois, cette implémentation multiplie elapsedmonothread par plusieurs unités.
Utilisation du patron de conception MapReduce pour résoudre les pertes d'incrément de counter
Comme expérimenté dans les deux questions précédentes, réduire le temps d’exécution de compteurBOOM avec un mutex ou une variable "atomique" a l’effet inverse.
C’est pourquoi, dans cette question, nous étudions une autre technique : le patron de conception MapReduce. L’idée est de faire travailler chacun des threads sur des données qu’il est seul à manipuler (donc, plus besoin de mutex ou de variable "atomique"), de centraliser le fruit de leur travail, et de synthétiser ensuite leur résultat.
cp compteurBOOM_v2_N_threads.c compteurBOOM_v5_N_threads_MapReduce.c
Éditez ce fichier de sorte que :
-
Dans la fonction main() :
- Vous définissez un tableau int map_counter[NB_THREAD] = {0};
- Quand vous appelez pthread_create(), vous mettez en argument l’adresse de la case du tableau sur laquelle votre thread son incrémentation de compteur.
- Une fois que vous avez invoqué pthread_join(), vous ajoutez à counter la valeur de la case de map_counter[] du thread qui vient de se terminer.
- Dans start_routine(), vous incrémentez la case de map_counter[] dont pthread_create() vous a passé l’adresse (et non counter).
Exécutez /usr/bin/time ./compteurBOOM_v5_N_threads_MapReduce et commentez.
Il s'agit d'un problème appelé faux partage: les NB_THREAD cœurs travaillent chacun sur des zones de mémoire locales. Toutefois, ces zones sont contiguës et se trouvent sur la même ligne de cache! De ce fait, le cache de chaque cœur est systématiquement invalidé nécessitant l'accès à la mémoire partagée entre les cœurs.
Corrigez ce problème en faisant travailler chacun de vos threads sur une variable vraiment locale (et pouvant donc être manipulée dans le cache du cœur) :
- cp compteurBOOM_v5_N_threads_MapReduce.c compteurBOOM_v6_N_threads_MapReduce_local.c
-
Modifiez ce nouveau fichier pour que :
- La boucle de start_routine() travaille sur un compteur my_local_counter défini localement dans start_routine().
- Une fois la boucle terminée, affectez ce compteur local à la case de map_counter[] dont pthread_create() vous a passé l’adresse.
Exécutez /usr/bin/time ./compteurBOOM_v6_N_threads_MapReduce_local et commentez.
L'elapsed observé est nettement meilleur qu'elapsedmonothread, mais est encore loin de l'elapsed qu'on pourrait espérer intuitivement, elapsedmonothread / NB_THREAD cœurs. Sur la machine ssh.imtbs-tsp.eu, 0.58 seconde / 16 cœurs ~ 0.04 seconde. Or, nous observons 0.09 seconde, soit 2 fois plus.
Les questions suivantes explorent des pistes d'explication et d'amélioration.
Utilisation du patron de conception MapReduce respectant la philosophie de la bibliothèque pthread
Au fond, le souci de performances observé dans compteurBOOM_v5_N_threads_MapReduce.c et que nous avons corrigé dans compteurBOOM_v6_N_threads_MapReduce_local.c est dû au non-respect de la philosophie de la bibliothèque pthread. Explications :
- Quand un thread ta crée un thread ta1 avec pthread_create(), il précise avec l'argument arg les données d’entrée sur lequel ta1 doit travailler.
- ta1 est sensé travailler localement avec ces données et, si jamais ce sont des données partagées, idéalement, seulement les lire.
- Quand ta1 a fini son travail, il communique son résultat grâce à l’argument retval de pthread_exit(), résultat que le thread tb qui attend la fin de ta1 (en général, tb est ta, mais d’autres architectures de code peuvent être envisagées) récupère dans l’argument retval du pthread_join() qu’exécute tb.
Ainsi, dans notre implémentation de MapReduce, main() n’a pas besoin de partager une case du tableau map_counter à chaque thread start_routine(). Il suffit que chaque thread transmette la valeur finale de my_local_counter dans son pthread_exit()
- cp compteurBOOM_v6_N_threads_MapReduce_local.c compteurBOOM_v7_N_threads_MapReduce_philosophie.c
-
Modifiez compteurBOOM_v7_N_threads_MapReduce_philosophie.c pour que le code respecte la philosophie de la bibliothèque pthread (NB : Pour être certain·e que votre code respecte cette philosophie, commencez par supprimer la déclaration int map_counter[NB_THREAD] = {0};).
Le point délicat est comment ajouter retval (qui est un pointeur) à counter (qui est un int). Nous pourrions faire un malloc pour allouer de la mémoire pour le retval (cette mémoire étant ensuite libérée par le thread appelant une fois qu'il a récupéré son contenu), mais ce n’est pas nécessaire dans notre cas. Déjà, nous savons que nous sommes sur une machine 64 bits. Donc, un pointeur est stocké sur 64 bits. De plus, pthread_exit() peut stocker directement la valeur de son compteur dans le pointeur et cette valeur est sur 32 bits. Donc, nous sommes certain·e que les 32 bits de poids fort de votre retval sont inutilisés. nous pouvons donc écrire : counter += (int64_t)retval;
Exécutez /usr/bin/time ./compteurBOOM_v7_N_threads_MapReduce_philosophie et commentez.
Respecter la philosophie de la bibliothèque pthread n’a pas permis d’améliorer les performances de notre programme. Toutefois, il est important de respecter cette philosophie pour que le code soit plus facilement compréhensible et maintenable par d’autres développeurs, et pour éviter les bugs liés à des partages de données non maîtrisés.
Étudions une autre piste d'amélioration des performances de notre programme : les priorités d'ordonnancement.
Modification des priorités d'ordonnancement pour que notre programme ne soit pas en compétition avec d'autres programme pour accéder à la CPU
Comme nous l'avons vu dans les questions précédentes, même en exploitant les NB_THREAD cœurs de votre machine, nous n'obtenons pas un elapsed proche de elapsedmonothread/NB_THREAD. Une piste d'explication serait que notre programme est en compétition avec d'autres programmes pour l'accès aux différents cœurs de la machine. En modifiant les priorités d'ordonnancement de notre programme, nous pouvons faire en sorte que notre programme soit prioritaire sur les autres programmes pour accéder à la CPU.
Utilisez la commande nice (pour les utilisateurs de Linux) ou renice (pour les utilisateurs de MacOS) (utilisez man pour obtenir de l'aide) pour augmenter la priorité d'ordonnancement de /usr/bin/time ./compteurBOOM_v7_N_threads_MapReduce_philosophie (NB : Vous aurez besoin de faire précéder la commande nice par sudo) et commentez le résultat.
L'utilisation de nice ne donne pas une amélioration systématique. Essayons d'utiliser une priorité temps réel pour garantir que notre processus est le seul à accéder à la CPU pendant l'expérience. Tapez sous Linux la commande suivante pour exécuter votre programme avec une priorité temps réel (man chrt pour comprendre les arguments et paramètres) :
En conclusion, même en donnant la priorité maximale à notre programme pour accéder à la CPU, nous n'obtenons pas un elapsed proche de elapsedmonothread/NB_THREAD.
Augmenter le nombre de tours de boucle pour que l'elapsed soit plus significatif
Voyons si augmenter le nombre de tours de boucle permet de s'approcher de elapsedmonothread/NB_THREAD en réduisant les incertitudes de mesure.
- Modifiez compteurBOOM_v0_monothread.ccompteurBOOM_v7_N_threads_MapReduce_philosophie.c pour que counter et i soient stockés dans un int64_t.
- Mesurez l'elapsed pour les valeurs 200*106, 2000*106, 20000*106, et 200000*106 pour FINAL_COUNTER (NB : soyez patient·e, car ces exécutions peuvent prendre plusieurs minutes).
- Commentez les résultats.
| Valeur de FINAL_COUNTER x 106 | elaspedmonothread en secondes | elaspedmultithread en secondes | Rapport entre elapsed |
| 200 | 0.62 | 0.09 | 6.9 |
| 2000 | 5.70 | 0.50 | 11.4 |
| 20000 | 54.57 | 4.21 | 13.0 |
| 200000 | 618.14 | 46.18 | 13.4 |
Les mesures semblent tendre vers elapsedmonothread/NB_THREAD, mais très lentement.
L'équipe pédagogique CSC4103 espère qu'il vous a permis de découvrir que les performances d'un programme ne sont pas toujours intuitives, et que l'optimisation de code peut être une tâche complexe qui nécessite de comprendre les interactions entre le code, le compilateur, le système d'exploitation et le matériel.
D'autres pistes d'amélioration des performances de notre programme pourraient être explorées, comme l'utilisation de threads légers ou l'utilisation de GPU pour faire du calcul parallèle. Mais elles sortent du cadre de ce TP.
