TP – Architectures mulicœures
Caches et vectorisation
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 (k va de 0 à AS_FLOAT_N par pas de L1_FIT). A chaque pas de cette boucle, vous devez effectuer une boucle de 0 à POW, et enfin une sous boucle de k à min(k + L1_FIT, AS_FLOAT_N), dans laquelle vous élevez au carré chacun des L1_FIT éléments de la partie du tableau traitée à l'itération k.
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. Nous allons utiliser les instructions permettant 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 :
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 votre 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 utilisant les opérations vectorielles pour multiplier les éléments quatre par quatre.
À la recherche de la topologie perdue
- Noeud 0, 1, 6 : 2.2 * 150 = 330 cycles
- Noeud 2, 4, 5, 8 : 1.6 * 150 = 240 cycles
Mesure des latences d'accès mémoire
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.
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 read_tscp().
A cette étape, la boucle s'exécute en un centaine de cycles. Vous devriez donc avoir un affichage du type :
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 :
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 :
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?
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 :
avant le début de la mesure, c'est à dire juste avant la ligne :
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).
Vous devez construire cette liste aléatoire en complétant la fonction randomize.
Dans cette aide, nous décrivons l'algorithme que vous trouverez dans la fonction randomize de la solution Cet algorithme s'avère simple à mettre en œuvre mais il n'est pas très efficace. À haut niveau, cet algorithme simple consiste à tirer de façon aléatoire des numéros de cases et à vérifier que la case tirée n'a pas été tirée précédemment. Dans le corrigé, nous vous proposons aussi un algorithme plus efficace dans la fonction randomize_other_soluce. Le schéma d'algorithme est donné ici :
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
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.
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.
Le programme final vous est donné ici :
