CSC5101 – Advanced Programming of Multicore Architectures

Parallel and Distributed Systems track

Contrôle final 20016-2017

La pile (14 points)

On souhaite programmer une pile contenant des entiers de quatre façons différentes : sans se préoccuper des problèmes de synchronisations, en utilisant des verrous, en utilisant un mémoire transactionnelle, et en utilisant un algorithme sans verrou.

Pour vous guider, on vous propose de partir du squelette suivant :
struct node { struct node* next; int value; }; struct node* head = 0; pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

4 points

Nous commençons par une version initiale dans laquelle on ne soucie pas des problèmes de synchronisation. Donnez le code des fonctions void push_unsafe(int value) et int pop_unsafe() permettant d'ajouter et de retirer un élément de la pile.
Si la pile est vide, la fonction int pop_unsafe() doit retourner la valeur -1.
void push_unsafe(int value) { struct node* node = malloc(sizeof(struct node)); node->next = head; node->value = value; head = node; } int pop_unsafe() { struct node* node = head; if(node) { int res = node->value; head = node->next; free(node); return res; } else return -1; }

2 points

Nous programmons maintenant la version protégée par un verrou. Donnez le code des fonctions push_lock(int value) et int pop_lock() utilisant un verrou.
Pensez à réutiliser les fonctions que vous avez précédemment programmées.
void push_lock(int value) { pthread_mutex_lock(&mutex); push_unsafe(value); pthread_mutex_unlock(&mutex); } int pop_lock() { pthread_mutex_lock(&mutex); int res = pop_unsafe(); pthread_mutex_unlock(&mutex); return res; }

2 points

On suppose maintenant que votre langage dispose des mots clés atomic et retry. Donnez le code des fonctions void push_tm(int value) et int pop_tm() utilisant une mémoire transactionnelle.
void push_tm(int value) { atomic { push_unsafe(value); } } int pop_tm() { atomic { return pop_unsafe(); } }

2 points

On souhaite maintenant écrire une fonction int pop_tm_wait() qui attend qu'il existe au moins un élément dans la pile avant de le retourner. La fonction int pop_tm_wait() doit utiliser la fonction int pop_tm() pour retirer un élément de la pile.
int pop_tm_wait() { atomic { int res = pop_unsafe(); if(res == -1) retry; return res; } }

4 points

On souhaite maintenant écrire une version sans verrou permettant d'accéder à la pile. Donnez le code des fonctions void push_lock_free(int value) et int pop_lock_free().
void push_lock_free(int value) { struct node* node = malloc(sizeof(struct node)); node->value = value; do { node->next = head; } while(__sync_val_compare_and_swap(&head, node->next, node) != node->next); } int pop_lock_free() { struct node* node; do { node = head; } while(__sync_val_compare_and_swap(&head, node, node->next) != node); return node->value; }

Questions de cours (6 points)

2 points

Dans un modèle mémoire TSO, pour quelle raison le code suivant, dans lequel il existe un unique thread sender et un unique thread receiver, est-il correct ?
char* msg = 0; int go = 0; void sender() { msg = "coucou"; go = 1; } void receiver() { while(!go); printf("%s\n", msg); }

4 points

On suppose une architecture à mémoire non uniforme. Chaque cœur possède un cache L1 unifié. Les cœurs d'un nœud NUMA partagent un cache L2 unifié. En partant de l'adresse virtuelle @v d'une variable x, décrivez étape par étape comment le matériel exécute un accès en écriture à la variable. Pensez à expliquer ce qui se passe dans les différents caches.

On suppose que votre machine possède quatre nœuds NUMA. On suppose aussi que l'accès est effectué par le cœur 5 du nœud 0, que la variable est gérée par le nœud 1 et qu'elle est se trouve dans le cache L1 du cœur 3 du nœud 2 à l'état Modified.
Transforme @v en @p via la table des pages Demande à L1 un accès exclusif à @p Demande à L2 un accès exclusif Demande à Noeud 1 un accès exclusif Noeud 1 enregistre @p sur noeud 0/coeur 5 Noeud 1 forward la requête à noeud 2/coeur 3 Noeud 2/coeur 3 invalide @p et envoie @p à noeud 0/coeur 5 L2 ajoute @p à son cache en exclusif L1 ajoute @p à son cache en exclusif Processeur effectue l'accès