Portail informatique Année 2018 – 2019

PAAM – Programmation avancée des architectures multicoeurs

Le but de cet exercice est d'explorer une architecture à accès mémoire non uniforme. En listant le répertoire /proc/cpuinfo, donnez le nombre de coeurs de la machine. $ cat /proc/cpuinfo | grep processor | wc -l 48 En vous promenant dans le répertoire /sys/devices/system/node donnez le nombre de domaines NUMA de la machine. $ ls -d /sys/devices/system/node/node* | wc -l 8 A titre d'exemple, listez les cores associés au noeud 3. $ echo /sys/devices/system/node/node3/cpu[0-9]* /sys/devices/system/node/node3/cpu42 /sys/devices/system/node/node3/cpu43 /sys/devices/system/node/node3/cpu44 /sys/devices/system/node/node3/cpu45 /sys/devices/system/node/node3/cpu46 /sys/devices/system/node/node3/cpu47 En explorant le fichier distance du noeud 3 et en sachant qu'un accès local coûte environ 150 cycles, donnez des estimations des temps d'accès aux différents noeuds à partir du noeud 3. $ cat /sys/devices/system/node/node3/distance 22 22 16 10 16 16 22 16 On en conclut que 10 correspond à un accès local et que les latences d'accès sont les suivantes :
  • Noeud 0, 1, 6 : 2.2 * 150 = 330 cycles
  • Noeud 2, 4, 5, 8 : 1.6 * 150 = 240 cycles
Ces chiffres sont bien sûr des estimations. Personnellement, je mesure exactement : 142 cycles en local, 248 à un saut, 345 à deux sauts.
On s'intéresse maintenant au coeur numéro 43. En vous promenant dans le répertoire cache, donnez la taille des différents caches (fichier size), leur niveau (fichier level), leur type (fichier type) et les coeurs qui partagent les caches (fichier shared_cpu_list). $ for f in /sys/devices/system/cpu/cpu43/cache/index[0-9]*; do echo "cache $f"; cat $f/size $f/type $f/level $f/shared_cpu_list; done cache /sys/devices/system/cpu/cpu43/cache/index0 64K Data 1 43 cache /sys/devices/system/cpu/cpu43/cache/index1 64K Instruction 1 43 cache /sys/devices/system/cpu/cpu43/cache/index2 512K Unified 2 43 cache /sys/devices/system/cpu/cpu43/cache/index3 5118K Unified 3 42-47
Le but de cet exercice est de mesurer les différentes latences d'accès mémoire. Pour cela, vous allez vous servir de l'archive se trouvant ici, qui contient principalement le fichier source latencies.c dont le code est donné ci-après :

L'expérience, une fois que vous aurez fini de la mettre en oeuvre, consiste en mesurer le temps d'accès moyen à l'ensemble des lignes de cache d'un tampon. La taille du tampon est donné en premier paramètre de latencies. Ensuite, vous allez forcer le thread du processus latencies à s'exécuter sur un coeur particulier (second paramètre de latencies) et la mémoire du tampon à être alloué sur un noeud NUMA particulier (troisième paramètre de latencies).

L'ensemble des fonctions vous seront expliquées au fur et à mesure des besoins. Pour commencer, vous devez comprendre que allocate alloue le tampon. La boucle principale de la fonction main entre les lignes 88 et 90 s'occupe d'effectuer NB_LOOPS accès en lecture à chacune des lignes de cache du tampon. Vous devrez prendre des mesures de temps aux lignes 86 et 92, ce qui vous permettra de connaître le temps moyen en lecture à une ligne de cache et de l'afficher à la ligne 94. Modifiez la fonction allocate de façon à allouer un tampon de n octets. Pour allouer votre espace mémoire, utilisez la fonction mmap avec le drapeau MAP_ANON.

Afin d'éviter de mauvaises surprises par la suite, pensez à vérifier que votre allocation a réussi avant de renvoyer un pointeur vers votre espace mémoire. struct cache_line* allocate(uint64_t n) { struct cache_line* buf = mmap(0, n, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, 0, 0); if(buf == MAP_FAILED) { perror("mmap"); exit(1); } return buf; }
Avant de passer à la suite, vous allez apprendre à mesurer des cycles. Pour cela, remplacez les valeurs 666 dans les lignes déclarant les variables start et end pour appeler PAPI_get_real_cyc().

A cette étape, la boucle s'exécute en un centaine de cycles. Vous devriez donc avoir un affichage du type : $ ./latencies 32768 0 0 0 cycles to access a cache line (total: 142 cycles) uint64_t start = PAPI_get_real_cyc(); /* start of experiment */ uint64_t end = PAPI_get_real_cyc(); /* end of experiment */
Maintenant, nous allons effectivement accéder au tampon. Dans une première version, on vous demande de modifier la fonction access de façon à accéder séquentiellement à chacune des lignes de cache du tampon. De façon à effectuer des lectures qui ont un sens, on vous demande de calculer la somme de chaque premier entier de chaque ligne de cache du tampon (argument buf). Le nombre de lignes de cache du tampon est donné en second argument. Votre fonction doit renvoyer cette somme.

De façon amusante, malgré les lectures, votre boucle devrait toujours s'exécuter en une centaine de cycles : $ ./latencies 32768 0 0 0 cycles to access a cache line (total: 143 cycles) uint64_t access(struct cache_line* buf, uint64_t nbc) { uint64_t r = 0; for(uint64_t i=0; i<nbc; i++) { r += buf[i].val[0]; } return r; }
Pour quelle raison, si vous remplacez le return 0 à la fin de la fonction main par un return r, vous obtenez maintenant des temps d'accès différents?

Sur l'exemple précédent, dans ce cas, l'accès en lecture à une ligne de cache se met alors à couter dans les 17 cycles : ./latencies 32768 0 0 17 cycles to access a cache line (total: 94259331 cycles) Le programme est compilé avec l'option -03 qui optimise beaucoup le code. En particulier, la fonction access est inlinée, c'est à dire que l'appel à la fonction est remplacé par le code la fonction. Ensuite, l'option -03 se rend compte que la variable somme des différents appels à access n'est jamais utilisé en lecture. Le compilateur élimine donc entièrement le calcul de r. Ensuite, la boucle de boucle devenant totalement inutile, elle est éliminée.

Lorsque la fonction main se termine avec un return r, la valeur r calculée est alors utilisée, donc plus aucun code n'est éliminé.
On souhaite maintenant mesurer l'accès aux différents niveau de cache. Pour cela, nous allons nous focaliser sur l'exécution de ./latencies 2 0 0. Dans ce cas, vous accédez à chaque ligne de cache d'un tampon de 2KiB qui doit tenir dans le cache de données L1 puisque ce cache fait 64KiB.

Avec votre code actuel et dans cette configuration, quelle est la latence d'accès à une ligne de cache? $ ./latencies 2 0 0 21 cycles to access a cache line (total: 6823 cycles)
La spécification du cache L1 indique qu'un accès devrait prendre moins de dix cycles. Pour quelle raison votre mesure actuelle est trop grande? Corrigez votre code pour n'observer que des accès au cache. Il suffit d'accéder une première fois à chaque ligne de cache avant de faire la mesure. Le plus simple est d'ajouter la ligne : r = access(buf, nbc); /* access the buffer */ avant le début de la mesure, c'est à dire juste avant la ligne : uint64_t start = PAPI_get_real_cyc(); /* start of experiment */ Lancez ./latencies 32768 0 0. Sachant que le cache L3 fait un peu plus de 4MiB et qu'un accès à la mémoire fait dans les 150 cycles, que pouvez vous en conclure?

Techniquement, votre programme fait des accès séquentiels à la mémoire. Le processeur repère assez vite ce motif d'accès et se met à charger les lignes de cache en avance : lorsque vous accédez à une ligne à l'adresse K, le processeur charge alors automatiquement, et en avance, la ligne à l'adresse K + cache_line_size.

Pour mesurer réellement la latence d'accès à la mémoire, il faut donc empêcher le processeur de prédire quel sera votre prochain accès. On vous propose la solution suivante : lors de lecture d'une ligne de cache k, le numéro de ligne de cache suivant se trouve dans le premier entier 64 bits de la ligne de cache (buf[k].val).

Dans un premier temps, construisez une liste aléatoire dans les entrées buf[k].val[0].

Pour cela, nous vous proposons l'algorithme suivant pour la fonction randomize dont vous n'avez que la signature. L'algorithme que nous vous proposons est loin d'être optimal mais présente l'avantage d'être relativement simple : /* * buf est un pointeur vers le tableau de tampons * n est le nombre d'entrées de ce tableau */ void randomize(struct cache_line* buf, uint64_t n) { c = 0 /* c est la case courant */ Pour i va de 0 à n-1 /* on remplit n - 1 cases, la dernière va aller vers l'entrée 0 pour avoir une liste circulaire */ Marque la ligne de cache numéro c comme occupée en mettant 1 dans le premier entier Trouve une entrée aléatoire r qui n'est pas encore occupée Marque la ligne de cache numéro c comme allant vers r en mettant r dans le premier entier c prend maintenant la valeur r pour passer à la case suivante Fin pour La dernière ligne revient vers la case 0 pour avoir une liste circulaire } /* * Prepare the buffer to perform a randomized access */ void randomize(struct cache_line* buf, uint64_t n) { uint64_t c = 0, r; srand(time(NULL)); for(uint64_t i=0; i<(n-1); i++) { buf[c].val[0] = 1; do { r = rand() % n; } while(buf[r].val[0]); buf[c].val[0] = r; c = r; } buf[c].val[0] = 0; }

Maintenant, il faut donc que vous modifiez votre function access de façon à suivre cette liste. Cette fonction doit renvoyer le numéro trouvé dans la dernière ligne de cache.

À la fin de cette étape, vos mesures de latence devraient être correcte. Vous devriez pouvoir observer les latences d'accès :
  • au cache L1 avec ./latencies 4 0 0 qui devrait donner environ 4 cycles.
  • au cache L2 avec ./latencies 256 0 0 qui devrait donner environ 15 cycles
  • au cache L3 avec ./latencies 2048 0 0 qui devrait donner environ 46 cycles
  • à la mémoire locale avec ./latencies 32768 0 0 qui devrait donner environ 148 cycles
uint64_t access(struct cache_line* buf, uint64_t nbc) { uint64_t r = 0; for(uint64_t i=0; i<nbc; i++) { r = buf[r].val[0]; } return r; }
On souhaite maintenant pouvoir mesurer la latence d'accès à une mémoire distante. Pour commencer, on vous demande d'utiliser la fonction pthread_setaffinity_np pour clouer votre thread sur un coeur. Complétez la fonction pine_thread(int core_id) qui s'occupe de clouer le thread courant (obtenu avec pthread_self() sur le coeur core_id.

En lançant htop dans un autre terminal, vous pouvez vérifier que votre programme fonctionne bien en lançant ./latencies 200000 12 0. Si vous voyez que le coeur 13 est solicité pendant l'exécution, c'est que votre code est correcte. void pine_thread(int core_id) { cpu_set_t cpuset; CPU_ZERO(&cpuset); CPU_SET(core_id, &cpuset); if(pthread_setaffinity_np(pthread_self(), sizeof(cpu_set_t), &cpuset) == -1) { perror("pthread_setaffinity_np"); exit(1); } }
Pour finir, on souhaite allouer le buffer à partir d'un noeud NUMA passé en argument. Complétez la fonction bind_memory en utilisant la fonction mbind.

Vérifiez que les latences d'accès distante sont d'environ :
  • 264 cycles pour un accès distant à un saut;
  • 365 cycles pour un accès distant à deux sauts.
void bind_memory(struct cache_line* buf, uint64_t nbc, uint32_t node_id) { uint64_t nodemask = (1 << node_id); if(mbind(buf, nbc*sizeof(struct cache_line), MPOL_BIND, &nodemask, 64, MPOL_MF_MOVE) == -1) { perror("mbind"); exit(1); } } Le programme final vous est donné ici :
Le but de cet exercice est de comprendre comment améliorer la gestion du cache et par la même occasion de vous introduire la notion de vectorisation.

Vous allez travailler avec à partir du fichier exo-vector.tar.bz2 qui se trouve ici.

Pendant tout le TP, il vous ait demandé de bien utiliser le Makefile qui vous est fournit. En effet, ce Makefile utilise des options qui vont vous permettre de voir les effets des instructions de vectorisation. Sans ces options, vous risquez de ne pas pouvoir observer les effets de la vectorisation.

Le programme s'occupe d'élever à la puissance POW chacun des flottants du tableau vector.as_float. Il y a AS_FLOAT_N éléments dans le tableau.

La fonction principale du programme est arrayPow_v0. La fonction effectue une boucle de 0 à POW. A chaque pas de la boucle, la fonction élève au carré chacun des éléments du tableau. La fonction qui vous est fournie ne profite pas du cache L1. En effet, à chaque pas de la boucle i, chacun des éléments du tableau doit être rechargé dans le cache L1 : le tableau fait 8MiB éléments, soit 64MiB, ce qui est nettement supérieur à la taille du cache L1 qui fait 64KiB.

Écrivez une nouvelle version du calcul dans la fonction arrayPow_v1 en profitant mieux du cache L1. Techniquement, on vous propose d'englober les deux boucles de arrayPow_v1 dans une nouvelle boucle. Cette première boucle en k parcourt le tableau par bloc de L1_FIT éléments. A chaque pas de cette boucle, vous devez effectuer une boucle de 0 à POW, et une sous boucle de k à k + min(L1_FIT, AS_FLOAT_N), dans laquelle vous élevez au carré chacun des éléments de la partie du tableau.

La technique d'optimisation qui vous est proposée ici s'appelle le loop tilling, elle consiste à partitionner une boucle de façon à améliorer la localité dans les caches.
Comme seconde optimisation, nous vous proposons d'utiliser les instructions de vectorisation du processeur (SSE). Ces instructions permettent d'effectuer, en un cycle, la même opération sur un vecteur de scalaire au lieu d'un unique scalaire. Votre processeur est capable d'effectuer des opérations sur des blocs que 4 flottants (128 bits).

En C avec gcc, vous pouvez utiliser ces instructions en déclarant des vecteurs. Typiquement, de la façon suivante : typedef float vsf_t __attribute__((vector_size VEC_NBBYTES)); /* vector of single floats */ vfs_t a, b, c;

Ensuite, vous pouvez alors effectuer une opération comme c = a * b qui va effectuer l'opération sur chacun des éléments du vecteur.

Dans notre programme, vous pouvez accéder au tableau de flottants par petits vecteurs via vector_t.as_vsf. Écrivez une nouvelle version du calcul dans la fonction arrayPow_v2. Vous partirez de votre code de arrayPow_v1 et utiliserez les opérations vectorielles pour multiplier les éléments quatre par quatre.