CSC5101 – Advanced Programming of Multicore Architectures

Portail informatique

PAAM – Contrôle final 2020-2021

Durée: 2h, tout document autorisé
Vous devez envoyer par mail votre contrôle à l'adresse gael.thomas@telecom-sudparis.eu sous la forme d'une archive (fichier tar.gz ou zip par exemple).
Vous devez avoir fait la question 1.a pour pouvoir faire l'exercice 2.

Synchronisation maître/esclaves (10,5 points)

Le but de cet exercice est d'écrire un petit répartiteur de charges. Un répartiteur de charge, appelé le maître, prend en entrée des commandes à exécuter et délègue leur exécution à des threads que nous appellerons des esclaves. Pour cet exercice, on vous demande d'écrire votre code dans le fichier synchro.c que vous ajouterez à votre archive. Un bonus sera donné aux programmes qui compilent et s'exécutent correctement.

2 points

Écrivez une méthode main qui :

  • s'assure que le programme reçoit bien un argument,
  • stocke dans une variable n de type entier cet argument après l'avoir converti en chaîne de caractères (fonction atoi),
  • créé n threads esclaves qui chacun exécute la fonction slave,
  • appel la fonction master,
  • et enfin attend la terminaison des n threads esclaves.

Une fois que votre programme fonctionne, copiez le dans le fichier rcl.c : vous en aurez besoin pour faire le second exercice.

0,5 point

Le thread maître va donner du travail aux esclaves en utilisant une structure de donnée de type queue (FIFO) mise en œuvre avec une liste de nœuds. Pour cette raison, commencez par ajouter à votre programme la définition de la structure node contenant :

  • Un pointeur vers l'élément suivant de la file,
  • Une commande à exécuter (une chaîne de 256 caractères).

Ensuite, ajoutez à votre programme une structure struct queue permettant de gérer la queue des travaux en attente, et une variable globale nommée jobs contenant les travaux en attente.

3 points

En veillant à synchroniser le maître et les esclaves à l'aide de mutex et variables conditions, modifiez votre fonction master de façon à exécuter dans une boucle infinie :
  • Lecture d'une commande à partir de l'entrée standard,
  • Ajout de la commande à la queue des commandes en attente de traitement,
  • Retour dans la fonction main si la commande est égale à la chaîne de caractères "quit" (pensez à utiliser la fonction strcmp).

3 points

En veillant à synchroniser le maître et les esclaves avec des mutex et variables conditions, modifiez votre fonction slave de façon à exécuter dans une boucle infinie :
  • Attente tant que la pile des commandes en attente est vide,
  • Retire la dernière commande de la pile,
  • Quitte le thread si la commande est égale à "quit" (fonction pthread_exit),
  • Exécute la commande reçue sinon (fonction system).

2 points

On suppose maintenant que vous disposez d'une mémoire transactionnelle. Copiez votre fichier synchro.c en stm.c que vous ajouterez à l'archive que vous devez rendre. Modifiez vos fonctions master et slave de façon à synchroniser le maître et les esclaves à l'aide d'une mémoire transactionnelle.
À cette question, on ne vous demande bien sûr pas de compiler votre programme puisque vous ne disposez pas de mémoire transactionnelle.

Remote core locking (6,5 points)

Lorsqu'un thread doit exécuter une section critique, le fait que ce soit lui qui l'exécute ou un autre thread n'est pas essentiel. Tant que la section critique est exécutée en exclusion mutuelle, le code reste correct. L'algorithme de Remote Core Locking (RCL) part de ce principe pour optimiser les mouvements de lignes de caches que ce soit celles accédées dans la section critique et celles accédées pour entrer en section critiques. Le principe du RCL est qu'un thread unique, appelé le thread serveur, exécute les sections critiques pour les autres.

En pratique, le programme utilise un tableau de n pointeurs vers des structures struct cs où n est le nombre de threads. Nous appelons ce tableau pendings.

Une structure struct cs représente une demande d'exécution d'une section critique. Elle contient les champs suivants :

  • func : un pointeur vers la fonction à exécuter en exclusion mutuelle. On considère que cette fonction prend en argument un entier et ne renvoie pas de valeur (le type d'une telle fonction en C est (void (*)(int)).
  • arg : l'argument de la fonction func (donc de type int),
  • completed : un booléen indiquant si la fonction a été exécutée.

Chaque thread client (autre que le serveur) possède une variable locale (thread local storage, c'est-à-dire avec l'attribut _Thread) nommée request de type struct cs. Lorsque le thread client numéro K souhaite exécuter une section critique, il prépare sa structure request et l'écrit à l'entrée numéro K du tableau pendings. Ensuite, il attend que la variable completed passe à vrai pour continuer.

De son côté, le thread serveur passe son temps à parcourir le tableau pendings Si l'entrée K ne pointe pas vers NULL, ça signifie que le thread numéro K lui a envoyé une requête. Le serveur exécute alors la section critique en appelant pendings[K]->func(pendings[K]->arg), puis passe la variable completed associée à la requête à vrai de façon à débloquer le thread client.

Le but de cet exercice est de mettre en œuvre cet algorithme sans jamais prendre un unique verrou POSIX.

Nous allons partir du code que vous avez réaliser à la question 1.a. Un thread client est un thread qui exécute la fonction slave. Le serveur est le thread maître (le thread initial du processus).

0,5 point

Dans le fichier rcl.c que vous avez réalisé à la question 1.a, ajoutez les structures de données et les variables utilisées par le programme (la structure struct cs, la variable globale pendings et la variable locale au thread request).

0.5 point

Les clients vont demander à ajouter des valeurs à une variable globale de type entier nommée var que vous devez définir à cette question. Écrivez une fonction void add(int v) ajoutant v à var. Il n'est pas nécessaire de synchroniser l'accès à var puisque cette fonction ne pourra que être exécutée par le thread serveur.

0.5 points

Modifiez votre programme de façon à ce chaque client (fonction slave) reçoivent en argument son index dans le tableau pendings (un numéro K unique compris entre 0 et N-1, où N est le nombre de threads).

3 points

Écrivez le code d'un client (fonction slave). Un client doit exécuter une boucle infinie dans laquelle il demande au serveur d'exécuter add(2) puis add(-1).

2 points

Écrivez le code du thread serveur. Pour cela, il suffit d'écrire le code du serveur dans la fonction master. On considère que le thread serveur ne termine jamais non plus (il exécute aussi une boucle infinie).

Questions de cours (3 points)

Vous devez répondre aux questions dans un fichier cours.txt que vous ajouterez à l'archive. Répondez à chaque question succinctement (2/3 lignes devraient suffire).

1 point

D'après-vous, pour quelle raison, lorsqu'on relâche un verrou, il faut exécuter une opération atomique avec la sémantique memory_order_release ?
Car il faut que les écritures qui précédent soit exécutées avant de lâcher le verrou.

1 point

Sur une architecture NUMA, dans quel cas un placement interleaved est préférable à un placement first-touch?
Lorsqu'un thread alloue de la mémoire pour les autres threads et accède à cette mémoire en premier. Dans ce cas, la mémoire se retrouve sur le noeud NUMA de l'allocateur et les autres threads finissent par écrouler le noeud NUMA de l'allocateur.

1 point

Expliquez brièvement la différence entre psync et pfence.
pfence assure que les pwb et lectures/écritures mémoires ne sont pas réordonnancées, alors que psync assure en plus que les lignes de caches de la flush queue ont bien été propagées.