Cohérence des caches dans une architecture manycore à mémoire partagée

Caches et cohérence des caches dans les architectures manycores

Nous avons vu que les architectures étaient composées de plusieurs types de mémoires. Dans cette partie, nous allons nous focaliser sur les caches qui sont les plus petites mémoires en dehors des registres des processeurs. Au cours d’une exécution d’un programme, il existe un principe de localité temporelle : lorsqu’une donnée est accédée, il y a de fortes chances qu’elle soit de nouveau accédée dans un futur plus ou moins proche. Les caches permettent de ranger les données déjà accédées dans une mémoire proche des cœurs qui les utilisent, ce qui permet de réduire la latence d’accès.
Architecture des caches : Quel que soit le niveau d’un cache, ce dernier est organisé de la même manière. Il est structuré sous la forme d’agrégations de lignes de cache. Les lignes de cache ont une taille fixe et permettent de mémoriser des données présentes à des adresses mémoires consécutives. Une ligne de cache contient donc plusieurs mots mémoire. Le choix de mémoriser plusieurs mots en un seul bloc a été fait en s’appuyant sur le principe de localité spatiale. En effet, lorsque l’on exécute l’instruction i, il y a de fortes chances que l’instruction suivante à exécuter soit l’instruction i + 1. Pour les données, si l’on est en train de lire une donnée comme un tableau à l’instant t, à l’instant t + 1 il y a une forte probabilité que l’on accède à la suite du tableau qui est rangée en mémoire à l’adresse suivante. En augmentant la granularité lors des requêtes auprès de la mémoire principale, le nombre de messages échangés entre les caches et avec la mémoire principale diminue, en particulier lorsque l’on travaille sur des données proches. Pour faire correspondre une adresse physique à un emplacement dans un cache, il existe plusieurs stratégies possibles : les caches à correspondance directe : chaque adresse mémoire correspond à un seul emplacement dans le cache.
les caches totalement associatifs : les données peuvent être rangées n’importe où dans le cache. les caches associatifs par ensemble : une adresse mémoire correspond à un ensemble d’emplacements et la donnée est rangée dans l’une des lignes réservées à cet ensemble. Chacun de ces types possède des avantages et des inconvénients. Le calcul de l’entrée pour un cache à correspondance directe est facile à réaliser, il s’agit de l’adresse mémoire modulo la taille du cache. En revanche, si plusieurs données importantes pour le programme correspondent à la même ligne, elles vont se gêner en s’évinçant l’une l’autre à chaque accès, et ce même lorsque d’autres lignes du cache sont libres.
Les caches totalement associatifs n’ont pas ce problème, car une donnée peut être rangée dans n’importe quelle case. En revanche, il n’existe pas de fonction simple pour savoir à quel endroit est rangé une donnée. Il faut donc tester toutes les entrées pour trouver où se trouve la ligne de cache qui nous intéresse.
Pour remédier à ce problème, les caches associatifs par ensemble combinent les avantages de chacun de ces deux types. Le cache est divisé en plusieurs ensembles, eux-mêmes composés de plusieurs voies. Ainsi, une donnée peut être rangée dans l’une des voies d’un ensemble donné. Le calcul de l’entrée correspond donc à l’adresse modulo le nombre d’ensembles, puis il faut tester chacune des voies de l’ensemble afin de trouver la ligne de cache à laquelle on souhaite accéder.

Évaluation des représentations de la liste des copies

Nous venons de voir que les protocoles de cohérence de caches ont des difficultés à passer à l’échelle pour les architectures manycores. Au cours du développement des nouveaux protocoles de cohérence de caches, les architectes peuvent utiliser différentes stratégies pour leur permettre d’évaluer les performances de leur protocole, allant des approches analytiques à gros grain [JF96] à la simulation.
Dans cette thèse, nous nous intéressons aux techniques de simulation pour des architectures manycores. Afin d’évaluer les performances des protocoles, les architectes peuvent utiliser des simulateurs plus ou moins précis. Plus le simulateur est précis, plus la description du protocole doit l’être, et donc le temps de développement d’un protocole augmente. De même, plus la description du protocole est détaillée, plus on augmente le temps de simulation. Il existe un nombre important de simulateurs et gem5 [BBB+11], qui permet de simuler des architectures multiprocesseurs au niveau système, est l’un des plus utilisés par les architectes. Dans le cas du simulateur gem5, le temps de simulation nécessaire au boot d’un Linux sur 64 cœurs Alpha est de 20 minutes.
Si l’on ajoute de la précision en utilisant par exemple SystemCASS [Sys], un simulateur basé sur SystemC, il faut 14 minutes pour démarrer linux avec un seul cœur, plusieurs heures pour une plateforme avec 4 cœurs et plus de 3 jours avec 16 cœurs.
Le temps de simulation augmente plus rapidement que linéairement avec le nombre de cœurs, ce qui rend la simulation d’une architecture manycore trop lente pour être exécutée dans un temps raisonnable. Une simulation du système complet décrit au niveau Register Transaction Level (RTL) n’est pas possible pour une architecture manycore car cela est encore plus lent qu’avec les simulations basées sur SystemC. Par contre, si l’on dispose d’un modèle RTL et d’un émulateur, l’émulation est une solution viable car rapide. Avec un émulateur, le RTL doit être synthétisé puis le design est chargé sur l’émulateur. Pour l’exécution, l’émulateur dispose de matériel dédié (principalement de la logique reconfigurable) qui permet de reproduire le comportement du RTL. En revanche, pour de l’exploration architecturale, il faut développer chacun des modèles au niveau RTL, ce qui n’est pas négligeable en temps de développement.
Les architectes doivent donc trouver le bon compromis entre précision et temps (développement et exécution). Pour cela, nous pouvons par exemple ne modéliser qu’une partie de l’architecture et nous concentrer sur une modélisation fine des caches, du protocole de cohérence, et du réseau. Une autre solution est de modéliser une partie du système avec un niveau d’abstraction plus élevé et ainsi modéliser seulement les états stables. Dans ce cas, on ne pourra pas prouver que la proposition est stable, sans deadlock. Par contre, cette solution permet de fixer la borne maximale des performances atteignables. Ainsi, l’évaluation du protocole ne correspond pas à l’évalution d’une implémentation matérielle mais bien des capacités du protocole en supposant que l’on peut atteindre les conditions optimales.

Protocoles basés sur l’espionnage

Parmi les protocoles basés sur l’espionnage, on observe que des filtres sont de plus en plus utilisés afin de réduire le nombre de messages. Ces filtres permettent également de diminuer la latence car les requêtes ne doivent plus attendre les réponses de l’ensemble des cœurs.
Flexible snooping : Dans flexible snooping [SST06] les auteurs proposent d’ajouter des prédicteurs afin de se rapprocher de la solution optimale du point de vue de la latence. Dans leur exemple, le réseau a une topologie en anneau.
Dans le cas lazy, à chaque nœud le cache est interrogé, et lorsqu’il ne possède pas la donnée, la requête est transférée au cache suivant. Lorsque la donnée est présente, la réponse est envoyée au demandeur sans interroger les autres caches. La latence dépend donc de la distance sur l’anneau entre le demandeur et le premier cache possédant la donnée. Néanmoins, la topologie du réseau étant un anneau, la réponse doit traverser l’ensemble des nœuds suivants avant de revenir au demandeur mais ces nœuds ne sont pas interrogés, ils transfèrent simplement la requête au nœud suivant. Dans l’exemple eager, lorsqu’un nœud reçoit une requête, il la transfère au nœud suivant puis il interroge son cache. Tous les caches qui disposent de la donnée répondent à la requête. Cette solution permet de réduire la latence, car la requête est transférée directement. Néanmoins, tous les caches sont interrogés pour chaque requête et le nombre de messages générés est plus élevé. Enfin, le troisième type de communication oracle montre la solution idéale que les auteurs souhaitent atteindre. Dans ce cas, la requête est transférée directement au nœud dont le cache possède la donnée et seulement ce cache est interrogé. Cette solution permet de minimiser la latence d’accès aux données. Dans flexible snooping, le choix du type de traitement à effectuer à chaque nœud est fait à l’aide d’un prédicteur.
Ce dernier permet de choisir si la requête est traitée avant d’être transférée, si elle est transférée puis traitée ou si elle est simplement transférée.

Protocoles de cohérence de caches dynamiques

Une autre possibilité pour représenter la liste des copies à l’intérieur du répertoire est d’utiliser des structures dynamiques. Ces structures sont rangées dans un espace partagé entre les caches d’un niveau donné. Chacune de ces structures a une taille fixe. Par nature les protocoles utilisant un répertoire dynamique sont également des répertoires limités.
Les limites de ces répertoires sont fixées par la taille de l’espace partagé. Lorsque cet espace est plein, il faut libérer de l’espace et donc on perd des informations. Néanmoins, les protocoles dynamiques ajoutent de la flexibilité par rapport aux répertoires purement limités.
Liste chaînée : Une première représentation de la liste des copies utilisant des structures dynamiques est proposé par Thapar et al. dans [TDF93]. Dans cet article, les auteurs utilisent des listes chaînées de CIDs (Linked list en anglais). Cette liste chaînée est mémorisée dans un tas partagé et, lorsque le tas est plein, les messages de cohérence sont envoyés en diffusion.
Champ de bits limité : Les auteurs de segment directory [CP99] proposent d’utiliser des segments pour encoder un sous-ensemble de la liste des copies sous forme de champs de bits. Dans cette proposition, le répertoire est composé d’un champ de bits limité ainsi qu’un identifiant de début de segment.

Présentation du concept du protocole DCC

Les protocoles de cohérence de caches avec répertoire peuvent utiliser un champ de bits complet pour mémoriser la liste des copies. Or, ce champ de bits est majoritairement creux. En effet, nous avons observé que le taux de partage de chaque ligne de cache est assez bas, 93% des lignes de cache étant partagées par au plus 8 cœurs. De plus, les auteurs de [FNW15] ont montré à l’aide d’analyses basées sur la loi d’Amdahl que le taux de partage n’augmente pas avec le nombre de cœurs. Nous avons également observé que les systèmes d’exploitation placent les tâches communicantes à proximité les unes des autres [DCA+16]. En s’appuyant sur ces deux observations, nous proposons une nouvelle représentation de la liste des copies. Pour ce faire, nous introduisons les structures suivantes :
un champ de bits de taille C pour représenter les copies à l’intérieur d’un rectangle de cohérence contenant C cœurs,
un identifiant de taille k pour l’origine (x,y) du rectangle de cohérence où k est une fonction de N, et N est le nombre de cœurs,
un identifiant de taille I pour encoder la forme du rectangle, où I est une fonction de C, un tas partagé composé de H entrées pour mémoriser des listes chaînées de CID, un pointeur vers une entrée du tas pour chaque entrée du répertoire.
Le principe du protocole est basé sur une partition de la liste des copies en deux sous-ensembles. Le premier correspond à un rectangle (au sens du produit du nombre de cœurs en x par le nombre de cœurs en y), d’aire maximale C, englobant une partie des caches copiant la ligne, l’idée étant que la forme et l’origine de ce rectangle permettent de recouvrir le maximum d’éléments de la liste des copies. Les copies ne pouvant être placées dans ce rectangle sont mémorisées sous forme de liste chaînée. Lorsque le nombre d’éléments dans la liste chaînée dépasse un seuil T , la ligne de cache est passée en mode diffusion, de sorte à ce que les messages de cohérence soient envoyés par précaution à tous les cœurs. Ce mode est également utilisé lorsque le tas est saturé.

Table des matières

1 Introduction
2 Problématique
2.1 Architectures manycores
2.1.1 Modèle mémoire
2.1.2 Hiérarchie mémoire
2.2 Caches et cohérence des caches dans les architectures manycores
2.2.1 Architecture des caches
2.2.2 Cohérence des caches
2.3 Représentation de la liste des copies
2.4 Caractéristiques des applications parallèles
2.5 Évaluation des représentations de la liste des copies
2.6 Conclusion
3 Cohérence des caches dans une architecture manycore à mémoire partagée
3.1 Protocoles basés sur l’espionnage
3.1.1 Flexible snooping
3.1.2 In-Network Coherence Filtering
3.2 Protocoles avec répertoire limité
3.2.1 Ackwise
3.2.2 Coarse bit-vector directory
3.2.3 Virtualisation des CIDs
3.3 Protocoles de cohérence de caches dynamiques
3.3.1 Liste chaînée
3.3.2 Champ de bits limité
3.3.3 Sponge directory
3.3.4 SPACE
3.4 Autres propositions
3.4.1 Scalable Interface Coherence
3.4.2 In-Network Cache Coherence
3.4.3 Classifications des données
3.4.4 Fenêtres temporelles
3.5 Conclusion
4 Représentation dynamique de la liste des copies
4.1 Présentation du concept du protocole DCC
4.2 Représentation du répertoire du protocole Dynamic Coherent Cluster (DCC)
4.2.1 Entrée du répertoire
4.2.2 Liste chaînée
4.2.3 Exemple d’entrée du répertoire DCC
4.2.4 Coût matériel du répertoire
4.3 Algorithmes de placement du rectangle cohérent
4.3.1 Algorithme idéal
4.3.2 Algorithme premier touché
4.3.3 Algorithme combinatoire
4.4 Détails de l’algorithme combinatoire
4.4.1 Comportement de l’algorithme combinatoire
4.4.2 Évaluation théorique du coût matériel
4.5 Conclusion
5 Méthode d’évaluation de la représentation de la liste des copies
5.1 Méthodes de simulation existantes
5.1.1 Simulations par interprétation d’instructions
5.1.2 Simulations basées sur l’injection de traces
5.2 Flot de simulation
5.3 Extraction des requêtes d’accès mémoire
5.3.1 Choix des paramètres de gem5
5.3.2 Modifications apportées à gem5
5.3.3 Choix des applications
5.3.4 Simulation et extraction du trafic
5.4 PyCCExplorer : un simulateur haut niveau pour la cohérence de caches
5.4.1 Architecture logicielle
5.5 Choix des métriques et instrumentations du simulateur
5.5.1 Latence d’accès aux données
5.5.2 Trafic induit par la cohérence de caches
5.5.3 Évaluation du nombre de messages de diffusion
5.6 Conclusion
6 Évaluation de l’influence de la représentation de la liste des copies
6.1 Expérimentations avec le simulateur PyCCExplorer
6.1.1 Implémentation dans le simulateur
6.1.1.1 Protocole basé sur l’espionnage (snoop)
6.1.1.2 Répertoire avec champ de bits complet (bit-vector)
6.1.1.3 Répertoire Ackwise
6.1.1.4 Répertoire utilisant une liste chaînée
6.1.2 Exploration architecturale avec PyCCExplorer
6.1.2.1 Exploration architecturale pour Ackwise
6.1.2.2 Exploration architecturale du protocole basé sur une liste chaînée
6.1.3 Classement des représentations de la liste des copies
6.1.3.1 Latence
6.1.3.2 Trafic
6.1.4 Validation du simulateur PyCCExplorer
6.1.4.1 Comparaison entre PyCCExplorer et gem5 concernant l’évaluation de la représentation de la liste des copies .
6.1.4.2 Comparaison des résultats à ceux d’autres travaux
6.1.4.3 Complexité de PyCCExplorer
6.2 Évaluation du protocole DCC avec PyCCExplorer et implémentation matérielle
6.2.1 Simulation avec PyCCExplorer
6.2.1.1 Environnement de simulation
6.2.1.2 Étude des paramètres du protocole
6.2.1.3 Comparaison des représentations de la liste des copies
6.2.1.4 Conclusion sur l’ensemble des métriques
6.2.2 Implémentation matérielle du protocole DCC
6.2.2.1 Paramètres de synthèse
6.2.2.2 Fréquence de fonctionnement
6.2.2.3 Surface du bloc tiling
6.3 Conclusion
7 Travaux futurs
7.1 Améliorations à apporter à PyCCExplorer
7.1.1 Simulation d’architecture avec plus de 64 cœurs
7.1.2 Ajout d’autres topologies de réseau
7.1.3 Ajout d’autres représentations de la liste des copies
7.1.4 Ajout de méthodes décentralisées
7.2 Limites des simulations du protocole DCC
7.2.1 Simulation des applications avec l’initialisation
7.2.2 Simulation sans le placement optimal des cœurs
7.2.3 Simulation avec d’autres architectures
7.3 Pistes de recherche autour du protocole DCC
7.3.1 Choix du keeper
7.3.2 Intégration du bloc tiling dans une architecture
7.3.3 Ajouter un tas partagé pour mémoriser les rectangles de cohérence
8 Conclusion
A Algorithme de placement des tâches
A.1 Présentation de l’algorithme de recuit simulé
A.2 Placement des caches sur la grille avant et après l’algorithme
Publications
Bibliographie