Portail informatique Année 2018 – 2019

PAAM – Programmation avancée des architectures multicoeurs

Le but de cet exercice est de mettre en oeuvre une pile sans verrou et de comparer les performances de cette pile à celle d'une pile avec verrou. Pour cela, nous allons mettre en oeuvre la pile sans verrou proposée par Mellor-Crummey et Scott (Synchronization Without Contention, publié à ASPLOS en 1991). Dans un premier temps, vous allez créer un environnement dans lequel nous pourrons tester nos piles. Dans ce premier exercice, vous devez créer N threads, N étant un paramètre du programme. Chaque thread doit afficher le message "Hello World!!!" puis se terminer.

Pour créer des threads, on vous rappelle qu'il faut utiliser la fonction pthread_create (man pthread_create) et qu'il faut lier votre exécutable avec la bibliothèque pthread (option -lpthread pour gcc).
Vous devez maintenant ajouter la structure suivante struct node { struct node* next; int value; }; à votre code et définir deux piles : struct node* volatile stack_lock_free = 0; struct node* stack_lock = 0;

La variable stack_lock sera utilisée pour construire une pile avec un algorithme reposant sur un verrou, alors que la variable stack_lock_free pour un algorithme lock free. Nous allons maintenant créer la version avec verrou de la pile. Mettez en oeuvre les fonctions push_lock(int value) et int pop_lock() permettant d'ajouter et de retirer des éléments à votre pile stack_lock. Pour cela, utilisez un algorithme avec verrouillage.

Testez votre fonction dans le thread en ajoutant et retirant 1'000 éléments dans votre pile à partir de chaque thread.
Mettez en oeuvre les fonctions push_lock_free(int value) et int pop_lock_free() permettant d'ajouter et de retirer un entier dans la liste stack_lock_free. Pour cela, utilisez l'algorithme sans verrou vu en cours. Votre fonction pop() doit bloquer tant qu'il n'y a pas d'élément dans la pile. Lorsque vous ajoutez un noeud, vous devez préalablement allouer sa mémoire. On vous demande, dans cette question, de le pas libérer la mémoire d'un noeud dans pop()

Vous testerez votre code en ajoutant et retirant 1'000'000 éléments dans votre pile à partir de chaque threads. Testez votre programme avec 10 threads.
On vous demande maintenant de libérer la mémoire des structures allouées dans la fonction pop(). Pour quelle raison votre programme plante-t-il? Nous n'allons pas résoudre le problème, donc, retirez votre free. Le programme subit le célèbre problème ABA : A puis B puis A. Le problème se comprend facilement sur un exemple.

La liste vaut initialement A -> B -> C.

Un premier thread lit A et lit B avant de modifier la liste avec le compare and swap.

Pendant se temps, un autre thread supprime A, supprimer B. La liste vaut C. Enfin, cet autre thread alloue un nouveau noeud, il recycle la zone occupée puisque cette dernière est libre.

A ce moment, lorsque le thread d'origine fait son compare and swap, il voit bien A, donc le compare and swap réussi. Il place B en tête de liste, qui n'a plus de sens puisque cette structure a été libérée.
En utilisant la fonction gettimeofday, faîtes quelques mesures. Quel algorithme est le plus efficace?
Commencez par écrire un programme lançant autant de threads que le nombre de cœurs de votre machine. Chaque thread doit afficher le message Hello. Assurez-vous que la fonction main quitte bien après tous les threads créés. Modifiez votre code de façon à ce que chaque thread ne puisse s'exécuter que sur un cœur unique. Pour cela, donnez en paramètre à chaque thread un numéro, sachant que le premier thread créé doit avoir le numéro 0 et le dernier le numéro n-1, où n est le nombre de cœurs de la machine. Nous appelons ce paramètre i dans la suite. Enfin, utilisez la fonction pthread_setaffinity_np pour forcer un thread à être schedulé sur le cœur i. Écrivez un programme multi-threads permettant d'ajouter ou de retirer des éléments d'une liste chaînée triée. À cette question, on vous demande de faire une liste chaînée protégée par des verrous. Techniquement, il faut que vous testez et mettiez en œuvre les functions :
  • void list_init(struct list** list) : initialise la liste.
  • void list_insert(struct list** list, int val) : ajoute le nombre val à la liste.
  • int list_remove(struct list** list, int val) : supprime le nœud val.
  • int list_has(struct list** list, int val) : vérifie si la valeur val est dans la liste.
On souhaite maintenant mesurer le temps d'insertion d'un élément dans la liste. Pour commencer, nous nous occupons de synchroniser les threads avant de commencer l'expérience. Pour cela, définissez une variable volatile started que chaque thread incrémentera avec la primitive __sync_fetch_and_add. Les threads doivent attendre que started atteignent n, où n est le nombre de cœurs

À cause d'optimisations de bas niveau, le temps de redémarrage d'un thread après la barrière que vous venez d'écrire a tendance à être lent. Pour cette raison, il est conseillé d'appeler la fonction pause dont le code est donné ci-après à chaque tour de la boucle qui attend que started atteigne n. static inline void pause() { asm volatile("pause"); }

La fonction read_tscp permet de connaître le nombre de cycles écoulés depuis le démarrage de votre machine. En utilisant cette fonction, dont le code est donné ci-après, mesurez le temps qu'il faut à un thread pour insérer 10000 éléments dans la liste chaînée. static inline uint64_t read_tscp(void) { uint32_t eax, edx; asm volatile("rdtscp" : "=a" (eax), "=d" (edx)); return eax | ((uint64_t)edx)<<32; } En utilisant l'algorithme présenté en cours, rendez vos listes lock free. Conservez la version avec verrou de votre liste, vous en aurez besoin à la question suivante. Comparez le temps d'insertion d'éléments en lock free et en avec verrou. Pour vous entraînez, vous pouvez aussi essayer d'assurer que l'élément val n'existe qu'un unique exemplaire dans la liste.