Modèles et protocoles de cohérence de données

La révolution technologique de ce siècle doit en grande partie son effervescence à l’informatique. Du téléphone intelligent à la voiture autonome en passant par la console de jeux, l’informatique est rendue de plus en plus indispensable dans le quotidien de chacun. Si cette science évolue aussi rapidement dans le marché grand public, elle en fait de même pour des domaines plus critiques tels que la prévision météorologique, la simulation de phénomènes physiques ou encore la manipulation et le traitement de grandes quantités de données.

Les exigences de ces domaines applicatifs ne cessent d’augmenter ce qui nécessite une très grande puissance de calcul et une capacité de stockage importante. La loi de Moore, résultat d’une extrapolation empirique, prévoit une multiplication par deux de la puissance de calcul tous les 18 mois. Elle a été vérifiée pendant plusieurs années grâce à la croissance de la technologie des semi-conducteurs qui a permis de doubler le nombre de transistors sur une même surface de silicium tous les 24 mois au plus tard. Une des métriques utilisées pour la vérification de la loi de Moore est l’augmentation de la fréquence d’horloge qui caractérise la vitesse de traitement des systèmes. Cependant, cette évolution est rapidement limitée, en particulier pour les systèmes autonomes, par la consommation d’énergie et la dissipation thermique qui en découle.

Depuis 2004 la fréquence des processeurs ne peut plus suivre la courbe donnée par la loi de Moore. Il est donc question de chercher des solutions à basse consommation énergétique tout en garantissant les performances de calcul. Les multicœurs sont des systèmes parallèles sur puce qui permettent d’agréger la puissance de calcul de plusieurs cœurs afin d’atteindre de hautes performances. Depuis plus d’une dizaine d’années, les systèmes sur puce suivent une tendance dérivée des multicœurs qui consiste à implémenter plusieurs centaines voire des milliers de cœurs simples à basse fréquence sur une même puce. Ces systèmes sont appelés manycœurs et ils promettent un bon compromis entre la performance du calcul parallèle et le coût énergétique. Parmi les manycœurs disponibles actuellement sur le marché, on peut citer la puce MPPA à 288 cœurs de Kalray, la famille de processeurs GX de Tilera qui atteint 72 cœurs, la puce Xeon Phi d’Intel avec 61 cœurs et la puce Epiphany à 72 cœurs d’Adapteva. Les réseaux de communication sur les manycœurs sont optimisés pour faciliter les échanges entre les nombreux cœurs de la puce. Les connexions courtes et rapides entre les éléments d’un manycœurs forment ce qui est appelé plus communément un NoC (en anglais Network on Chip). L’utilisation de la mémoire dans ce genre de systèmes est basée sur une approche hiérarchique répartie où chaque niveau de mémoire représente un coût et une capacité différents. Cette approche est largement utilisée dans des systèmes à plus large échelle tels que les grilles de calculateurs. En dépit des capacités physiques que peut offrir une architecture manycœurs, l’exploitation de la puissance de calcul disponible n’est pas toujours triviale. Du point de vue de l’utilisateur, la programmation des systèmes hautement parallèles peut être très complexe. Elle nécessite une gestion efficace de tous les aspects concurrentiels du calcul parallèle, notamment les conflits d’accès à la mémoire. Nous nous intéressons dans ces travaux particulièrement aux problèmes de la cohérence des données dans les architectures massivement parallèles. Pour des raisons de passage à l’échelle, chacun des cœurs du système a au moins un niveau de cache privé garantissant un accès physique direct aux copies locales des données.

Des multicœurs vers les manycœurs

Les systèmes intégrés sur puce connaissent une très forte croissance, si ce n’est la plus rapide dans le marché des ordinateurs. Ils couvrent une large partie des applications grands publics (ex. électroménager, consoles de jeux, téléphonies, automobiles). Ils sont également présents dans des domaines plus pointus tels que l’accélération des calculs scientifiques (ex. prévisions météorologiques, simulations physiques, analyse financière) et pour le contôle de certains systèmes complexes (ex. industrie avionique et sousmarine).

Comparés aux ordinateurs de bureau et aux systèmes de serveurs, les système embarqués offrent un plus large éventail de puissances de calculs et de consommations énergétiques. Le marché des systèmes embarqués propose une offre qui va des petits processeurs 8-bit et 16-bit qui coûtent moins d’un euro et du microprocesseur 32-bit capable de traiter 500 MIPS qui coûte quelques dizaines d’euros aux systèmes d’une grande puissance de calcul capables d’exécuter des billions d’instructions par seconde et dont le coût est de l’ordre de centaines (Tilera Gx [Ram11a]) voire milliers (Intel XeonPhi 7100 [Chr14], Kalray MPPA-256 [dDAB+13]) d’euros.

Évolution des circuits intégrés vers les manycœurs

Le microprocesseur Intel 4004 est l’un des tous premiers fabriqués par Intel en 1971. Il s’agit d’un calculateur intégrant 2300 transistors MOS et cadencé à une fréquence ne dépassant pas les 740 kHz. Le développement qu’a connu le marché des processeurs par la suite, doit son essor à l’augmentation de la densité des transistors intégrés et à la diminution de la surface de gravure. Gordon Moore (l’un des fondateurs d’Intel) a constaté que la complexité des semiconducteurs doublait tous les deux ans à coût constant depuis leur apparition en 1959. Il prévoyait la continuité de cette croissance exponentielle sur les années à venir. Cette extrapolation empirique est connue depuis 1965 sous le nom de la loi de Moore. En 1975, quatre ans plus tard, la loi de Moore a fait l’objet d’une réévaluation. Elle postule que le nombre de transistors sur une puce en silicium va doubler tous les ans. Bien qu’il ne s’agit pas d’une loi physique, la loi de Moore a été vérifiée jusqu’en 2001, la densité des transistors doublait tous les 18 mois. En conséquence, les ordinateurs sont devenus moins coûteux, moins encombrant et surtout plus puissants. Plusieurs versions inspirées de la loi de Moore ont été diffusées. La version sur la fréquence d’horloge qui semblait suivre la même évolution n’est plus vérifiée depuis 2004. Il est actuellement de plus en plus difficile d’augmenter la fréquence pour des raisons liées à la dissipation thermique et à la consommation énergétique. Si récemment la densité des transistors augmente chaque année de 35%, en quadruplant à peu près tous les 4 ans, l’évolution au niveau de la taille de la puce reste moins prédictible mais plus lente (de 10% à 20% par an). En conséquences, le nombre de transistors sur puce augmente de 40% à 55% par an (i.e. doublement tous les 18 à 24 mois) [HP12]. Cette tendance est touchée sur le marché par des processeurs parallèles, appelés multicœurs, regroupant plusieurs unités de calcul simples et à basse fréquence, Cette approche permet de mieux gérer la dissipation thermique, directement liée à la fréquence d’horloge, tout en garantissant une grande puissance de calcul. Face à la demande du marché, cette tendance continue à attirer les fondeurs en leur permettant d’améliorer les performances des systèmes sans augmenter leur prix. Une nouvelle génération de systèmes sur puce massivement parallèles voit le jour : les manycœurs [Cor11]. Les architectures manycœurs promettent une grande capacité de calcul à basse consommation énergétique grâce à l’intégration de plusieurs dizaines (voir plusieurs centaines) de cœurs simples sur la même puce. Ce type d’architectures repose sur une organisation mémoire (cache hiérarchique) et une structure de communication (réseau sur puce) optimisées pour accélérer les traitements parallèles sur la puce. Les deux sections suivantes décrivent les tendances technologiques au niveaux des réseaux de communication et de la mémoire.

Technologies des réseaux de communication sur puce

Dans les systèmes sur puce à un grand nombre d’unités de calcul, il est important d’avoir une meilleure communication entre elles. La conception d’un système de communication sur puce est contrainte par la surface de la puce et le coût de développement ce qui limite ses performances. Le passage à l’échelle dans ce genre de réseaux, objectif majeur des systèmes sur puce, dépend fortement des performances en latence et en bande passante. Ce dernier est caractérisé par la structure de connexion entre les cœurs (i.e. topologie) et par le système de communication associé (ex. routage, arbitrage). Les réseaux sur puce, dits NoC (correspondant à Network-on-Chip), est un type particulier de réseaux dédié à la connexion entre les unités de calcul et les périphériques du systèmes (ex. registres, mémoires caches) au sein d’une microarchitecture. Ils sont conçus pour connecter efficacement plusieurs dizaines à plusieurs centaines de nœuds à une distance de l’ordre de quelques centimètres. Parmi les NoCs existants sur le marché actuellement, nous retrouvons le NoC d’Intel Teraflops [VHR+07] reliant 80 cœurs simples ; celui d’Intel Single-Chip Cloud Computer(SCCC) [DBMO11] regroupant 48 cœurs de l’architecture IA-32 ; et le réseau de la gamme Tilera TILE-Gx [Ram11b] connectant jusqu’à 200 cœurs (2013). Ces NoC atteignent des bandes passantes de 256 GBps pour les puces d’Intel et 200 GBps pour le processeur Tilera Tile-Gx. Une topologie de NoC permet d’établir un lien de communication entre n’importe quels deux points distants du système, soit de façon directe (connexion physique directe) ou à travers des points intermédiaires (point-à-point). Elle est constituée de l’ensemble des liens physiques, des commutateurs et des nœuds d’une architecture. De très nombreuses topologies plus ou moins complexes ont été proposées pour les différents types de systèmes. La complexité d’une topologie est dûe essentiellement au nombre de liens physique qu’elle engendre, ce qui reflète son coût, et à la distance maximale (en nombre de pas réseau) entre deux éléments distants dans le système.

Table des matières

Introduction
1 Contexte général de la thèse
1.1 Des multicœurs vers les manycœurs
1.1.1 Évolution des circuits intégrés vers les manycœurs
1.1.2 Technologies des réseaux de communication sur puce
1.1.3 Technologies mémoire
1.1.4 Discussion
1.2 Programmation des systèmes parallèles sur puce
1.2.1 Les niveaux de parallélisme
1.2.2 Classification des modèles de programmation
1.2.3 Discussion
1.3 Modèles et protocoles de cohérence pour les systèmes sur puce
1.3.1 Définition du problème de la cohérence des données
1.3.2 Modèles de cohérence des données
1.3.3 Implémentations : Protocoles et mécanismes de gestion de la cohérence
1.3.4 Discussion
2 Étude des mécanismes de gestion des données pour les systèmes répartis
2.1 Les approches à cache privé et à cache partagé
2.1.1 Cache partagé
2.1.2 Cache privé
2.1.3 Comparaison entre cache privé et partagé
2.2 Approches à caches coopératifs pour les systèmes répartis
2.2.1 L’approche coopérative pour les systèmes de fichiers
2.2.2 L’approche coopérative pour les réseaux sans fils
2.2.3 L’approche coopérative pour les multicœurs
2.3 L’approche coopérative pour les manycœurs
2.3.1 Description du mécanisme de cache élastique
2.3.2 Discussion : limitations du modèle coopératif élastique
2.4 Contribution : le mécanisme de glissement de données pour les manycœurs
2.4.1 Description de l’approche coopérative par glissement de données
2.4.2 Implémentation du protocole de glissement de données
2.4.2.1 Description de l’algorithme de glissement de donnée
2.4.2.2 Implémentation des compteurs d’accès
2.4.2.3 Politique de remplacement
2.4.2.4 Choix du meilleur voisin
2.5 Extension du protocole de glissement à l’aide du modèle physique masseressort
2.5.1 Présentation du modèle physique masse-ressort
2.5.2 Modèle mathématique du masse ressort
2.5.3 Implémentation
2.6 Discussion
3 Étude analytique des protocoles de glissement de données
3.1 Contexte expérimental
3.1.1 Plate-forme de validation
3.1.2 Protocole de cohérence Baseline
3.1.3 Scénarios d’accès mémoire
3.2 Analyse des performances du protocole de glissement
3.2.1 Technique de remplacement des données par priorité dans un voisinage stressé
3.2.2 Évaluation de la technique du choix du meilleur voisin
3.2.3 Analyse des performances par variation du rayon de glissement
3.2.4 Évaluation de l’approche masse-ressort
3.3 Discussion
4 Plate-forme de compilation multi-protocolaire pour les manycœurs
4.1 Les systèmes à mémoire virtuellement partagée
4.1.1 Défis de conception des systèmes à mémoire virtuellement partagée
4.1.2 Techniques d’implémentation d’une mémoire virtuellement partagée
4.1.3 Mémoires virtuellement partagées : l’existant
4.1.4 Discussion
4.2 Architecture de la plate-forme de compilation
4.3 Méthodes d’analyse statique du code
4.3.1 Techniques d’analyse statique
4.3.2 Discussion
4.4 Contribution : modèle d’analyse des accès aux données partagées
4.4.1 Graphe de dépendance étiqueté pour l’analyse des accès aux données partagées
4.4.2 Métriques d’analyse et de décision pour le choix des protocoles de cohérence
4.4.3 Implémentation du modèle d’analyse statique
4.5 Discussion
Conclusion

Télécharger le rapport complet