Stratégies d'écriture et évaluations des protocoles de cohérence de caches pour les architectures manycore CC-Numa

Durée :

6 mois

Financement :

Suivant les règles de l'université UPMC.

Laboratoire LIP6, Département SoC, équipe Alsoc

Ce stage s’inscrit dans le cadre du projet Européen SHARP piloté par BULL, dont les partenaires Français sont THALES, le LIP6 et le CEA/LETI. Ce projet vise la définition et l’implémentation d’une architecture de processeur many-cores utilisable dans des ordinateurs de type serveurs, c'est-à-dire une architecture matérielle supportant la mémoire virtuelle, et fournissant un mécanisme de cohérence des caches garantie par le matériel.

L’architecture TSAR a été définie dans le cadre d’un premier projet Européen. Cette architecture NUMA (Non Uniform memory Access) supporte des systèmes d’exploitation généralistes de type UNIX (ou LINUX). Son originalité est d’utiliser un grand nombre de "petits" coeurs de processeurs RISC 32 bits, plutôt que quelques gros processeurs, pour minimiser la consommation énergétique. L’architecture doit donc être réellement scalable (pour atteindre plusieurs milliers de coeurs sur une seule puce), tout en fournissant une mémoire partagée cohérente.

Motivations

La particularité du protocole de cohérence de l'architecture, appelé DHCCP (décrit dans la thèse de Yang Gao) est de mettre en oeuvre une stratégie "Write-Through" hybride qui mélange des mises à jour et des invalidations. Des expérimentations ont été menées pour essayer de déterminer la scalabilité du protocole, mais ce point est délicat. En effet, si pour pouvoir conclure que le protocole est scalable, il faut obtenir un speedup proportionnel au nombre de coeurs utilisés sur l'application, il faut que tous les maillons de la chaine logicielle et matérielle soit scalables. En particulier, cela nécessite que :

• le système d'exploitation ne comporte pas de goulots d'étranglement qui se manifestent lors de l'exécution (par exemple, structures de données centralisées telles que la table des pages)
• le réseau physique supporte la charge en terme de bande passante
• le protocole de cohérence soit effectivement scalable en nombre de messages
• l'algorithme de l'application parallèle passe intrinsèquement à l'échelle
• l'application ne doit pas comporter trop d'éléments de synchronisation et éviter de faire du faux partage

C'est précisément ce dernier point qui pose problème : une ligne partagée en écriture entre plusieurs threads provoquera du faux partage avec un protocole write-back mais pas avec un protocole write-through. En allant plus loin, on peut même dire qu'une application parallèle qui accède à beaucoup de données partagées est pensée pour un type de protocole, ce qui rend difficile une évaluation objective des performances d'un protocole de cohérence.

Néanmoins, on pourrait aussi argumenter que là où un protocole efficace se démarque d'un protocole non efficace, c'est justement lorsqu'il est stimulé, et donc que la quantité de requêtes de cohérence est grande.

Ceci montre la difficulté à évaluer un protocole de cohérence. Une première idée a été d'implémenter un protocole write-back MESI conservant certaines caractéristiques de DHCCP : stratégie hybride de stockage de la liste des copies d'une ligne (explicite ou implicite), requêtes de types multicast ou broadcast. Ce protocole a été nommé HMESI.

Si la comparaison est intéressante, elle ne permet pas de déterminer le surcout lié au protocole car déjà en mono-thread les performances entre le write-through et le write-back peuvent être très différentes. Par ailleurs, HMESI est une alternative intéressante à DHCCP car les résultats préliminaires montrent qu'il offre de meilleures performances que DHCCP dans la plupart des cas.

C'est pourquoi dernièrement une autre approche a été adoptée : concevoir un protocole de cohérence "idéal" afin de pouvoir mesurer le surcout lié à la cohérence, tout en s'affranchissant des autres paramètres limitant la scalabilité d'une application. L'idée de ce protocole idéal est d'avoir une exécution avec une cohérence à cout zéro, et il n'a donc pas pour but d'avoir une réalité matérielle. On peut le voir comme une borne inférieure du surcout induit par la cohérence.

Ce protocole "idéal" doit se décliner en deux variantes : une write-through et une write-back. La variante write-through a déjà été conçue et implémentée, et elle est en cours d'évaluation.

Réalisation

Le sujet de ce stage consiste en la spécification, l'implémentation et l'évaluation de la variante write-back du protocole idéal. Il comportera notamment les étapes suivantes :

1. Étude et compréhension de l’architecture TSAR et du protocole DHCCP
2. Prise en main du prototype virtuel SystemC de l'architecture
3. Analyse approfondie de l’architecture interne des contrôleurs de cache L1 et L2
4. Spécification d'un protocole write-back cohérent "idéal", c'est-à-dire dans lequel la cohérence a un cout nul.
5. Modélisation en langage SystemC du cache L1 et du cache L2.
6. Validation de la modélisation par exécution d’applications logicielles multi-tâches existantes.
7. Comparaison des performances de ce protocole au protocole HMESI afin de mesurer le cout de sa cohérence.

Si le stage se déroule suffisamment vite, un autre problème pourra être abordé. En effet, l'implémentation actuelle du protcole write-through idéal n'est pas compatible avec une exécution sur la version parallèle du simulateur SystemCass, et il est probable que la première version du protocole write-back idéal ne le soit pas non plus. Le travail associé consistera donc à réfléchir à une technique permettant d'utiliser ce simulateur parallèle.

Compétences souhaitées

• Architecture des machines : hiérarchie mémoire, caches, MMU
• Protocole de cohérence (write-through, write-back)
• Langages : C++, python

Références

[1] Tera Scale ARchitecture. Project Home Page. web: tmp-soc.lip6.fr/trac/tsar

[2] Soclib. Project Home Page. web: www.soclib.fr

[3] JOUPPI, Norman P. Cache write policies and performance. ACM, 1993.

[4] ADVE, Sarita V., ADVE, Vikram S., HILL, Mark D., et al. Comparison of hardware

and software cache coherence schemes. ACM, 1991.

[5] DAYA, Bhavya K., CHEN, Chia-Hsin Owen, SUBRAMANIAN, Suvinay, et al. SCORPIO: 36-Core Shared-Memory Processor Demonstrating Snoopy Coherence on a Mesh Interconnect.

[6] ROS, Alberto, ACACIO, Manuel E., et GARCÍA, José M. A direct coherence protocol for many-core chip multiprocessors. Parallel and Distributed Systems, IEEE Transactions on, 2010, vol. 21, no 12, p. 1779-1792.

[7] YUAN, Fengkai et JI, Zhenzhou. DP&TB: a coherence filtering protocol for many-core chip multiprocessors. The Journal of Supercomputing, 2013, vol. 66, no 1, p. 249-261.

Encadrant :

Quentin Meunier