Fonctionnement d'un ordinateur/Architectures multiprocesseurs et multicœurs
Pour réellement tirer parti du parallélisme de taches, rien ne vaut l'utilisation de plusieurs processeurs et/ou de plusieurs ordinateurs, qui exécutent chacun un ou plusieurs programmes dans leur coin. Si utiliser plusieurs ordinateurs connectés par un réseau local est une solution simple et facile à implémenter, elle est cependant assez onéreuse et demande des logiciels adaptés qui permettent de profiter d'une telle architecture matérielle. D'autres solutions multiprocesseurs ont alors vu le jour pour rendre l'usage de plusieurs processeurs plus adéquat.
Les différents types de multiprocesseur/multicoeurs
[modifier | modifier le wikicode]La première implémentation du multiprocesseur consiste à placer plusieurs processeurs sur la même carte mère, ce qui donne un ordinateur multi-processeurs. Cette méthode marchait bien mais n'était pas des plus pratique, surtout que l'utilisation de plusieurs processeurs en même temps n'était de plus pas vraiment démocratisé à cette époque. Les logiciels et les systèmes d'exploitation grand public n'étaient pas adaptés pour, la demande pour des ordinateurs multiprocesseurs était limitée à quelques professionnels et ne justifiait pas un investissement majeure dans ces technologies.
Au niveau matériel, il fallait une carte mère adaptée, qui n'était pas facilement disponible et coûtait généralement plus cher que les cartes mères à un seul processeur. Sans compter qu'il valait mieux avoir une mémoire RAM rapide et des processeurs dotés de beaucoup de mémoire cache, ce qui coûtait encore plus cher. Au final, le gain était assez faible en terme de performance, peu de logiciels grand public profitaient de l'usage de plusieurs processeurs, la technologie est restée confidentielle.
Les processeurs multicoeurs
[modifier | modifier le wikicode]Puis, avec les progrès en matière de miniaturisation des processeurs, les fabricants ont eu l'idée d'utiliser les transistors qu'ils avaient pour fabriquer des processeurs multicœurs, un terme que vous avez peut-être déjà entendu sans vraiment ce qu'il signifiait réellement. Les processeurs multicœurs peuvent être vus comme un regroupement de plusieurs processeurs sur la même puce de silicium.
Pour être plus précis, ils contiennent plusieurs cœurs, chaque cœur pouvant exécuter un programme tout seul. Chaque cœur dispose de toute la machinerie électronique pour exécuter un programme, que ce soit un séquenceur d'instruction, des registres, une unité de calcul. Par contre, certains circuits d'un processeur ne sont présents qu'en un seul exemplaire dans un processeur multicœurs, comme les circuits de communication avec la mémoire ou les circuits d’interfaçage avec la carte mère. Suivant le nombre de cœurs présents dans notre processeur, celui-ci sera appelé un processeur double-cœur (deux cœurs), quadruple-cœur (4 cœurs), octuple-cœur (8 cœurs), etc. Ces processeurs sont devenus la norme dans les ordinateurs grand public et les logiciels et systèmes d'exploitation se sont adaptés.
Dans ce qui suit, nous utiliserons le terme cœurs pour désigner soit les cœurs d'un processeur multicœurs, soit les différents processeurs d'un ordinateur multiprocesseur. Tout le contenu de ce chapitre vaut aussi bien pour les systèmes multicœurs que multiprocesseur. Les différences entre les deux sont mineures, les deux font face aux mêmes problèmes, les mêmes solutions peuvent s'appliquer sur les deux types de systèmes.
Le multiprocesseur/multicoeurs symétrique ou asymétrique
[modifier | modifier le wikicode]Dans la grosse majorité des cas, les cœurs d'un processeur multicœurs sont tous identiques. Mais ce n'est certainement pas une obligation et on peut très bien mettre plusieurs cœurs assez différents sur la même puce. On peut par exemple utiliser un cœur principal avec des cœurs plus spécialisés autour. Il faut ainsi distinguer le multicœurs symétrique, dans lequel on place des processeurs identiques sur la même puce de silicium, du multicœurs asymétrique où les cœurs ne sont pas identiques.
Un exemple est celui du processeur CELL de la console de jeu PS3. Il intègre un cœur principal POWER PC v5 et 8 coeurs qui servent de processeurs auxiliaires. Le processeur principal est appelé le PPE et les processeurs auxiliaires sont les SPE. Les SPE sont reliés à une mémoire locale (local store) de 256 kibioctets qui communique avec le processeur principal via un bus spécial. Les SPE communiquent avec la RAM principale via des contrôleurs DMA. Les SPE possèdent des instructions permettant de commander leur contrôleur DMA et c'est le seul moyen qu'ils ont pour récupérer des informations depuis la mémoire. Et c'est au programmeur de gérer tout ça ! C'est le processeur principal qui va envoyer aux SPE les programmes qu'ils doivent exécuter. Il délègue des calculs aux SPE en écrivant dans le local store du SPE et en lui ordonnant l’exécution du programme qu'il vient d'écrire.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Schema_Cell.png/440px-Schema_Cell.png)
Les architectures à cœurs conjoints
[modifier | modifier le wikicode]Sur certains processeurs multicœurs, certains circuits sont partagés entre plusieurs cœurs. Cette technique consistant à ne pas dupliquer certains circuits et à en partager certains s'appelle le cluster multithreading, ou encore les architectures à cœurs conjoints (Conjoined Core Architectures). Typiquement, les mémoires caches et l'unité de calcul flottantes peuvent être partagées sans trop de problèmes, les unités SIMD qu'on verra dans quelques chapitres sont aussi dans ce cas.
Elle est notamment utilisée sur les processeurs FX-8150 et FX-8120 d'AMD, et les autres processeurs basés sur l'architecture Bulldozer. Sur ces processeurs, tous les cœurs se partagent l'unité de calcul sur les nombres flottants. Le partage de circuits permet d'éviter de dupliquer trop de circuits et donc d'économiser des transistors. Le problème est que ce partage est source de dépendances structurelles, ce qui peut entraîner des pertes de performances.
Les interruptions inter-processeurs
[modifier | modifier le wikicode]Les différents cœurs sont gérés par le système d'exploitation de l'ordinateur, avec l'aide d'interruptions inter-processeurs, des interruptions déclenchées sur un cœur et exécutées sur un autre, éventuellement par tous les autres pour certaines interruptions spécifiques. Pour générer des interruptions inter-processeur, le contrôleur d'interruption doit pouvoir rediriger des interruptions déclenchées par un processeur vers un autre.
L'exemple de la console de jeu Néo-géo
[modifier | modifier le wikicode]Un exemple d'implémentation très simple est celui de la console Néo-géo, qui contenait deux processeurs. Le premier est un Motorola 68000 qui sert de processeur principal, l'autre est un Z80 qui sert de processeur dédié à l'audio. Le Z80 commande un synthétiseur sonore, et est relié à sa propre mémoire, distincte de la mémoire principale. Le MC68000 est le processeur principal et a une relation maitre-esclave avec le Z80 : le MC68000 envoie des interruptions au Z80, mais la communication ne va pas dans l'autre sens.
Les deux processeurs communiquent via l'intermédiaire d'un IO arbiter chip, un circuit sur la carte mère connecté ua bus, qui gère les interruptions inter-processeur. Il contient un registre de 8 bits, dans lequel le MC68000 peut écrire dedans à sa guise, le registre étant adressable par le processeur. Les valeurs écrites dans ce registre sont des numéros d'interruption, qui indiquent quelle routine d'interruption exécuter. Lorsque le MC68000 écrit une valeur dedans, cela déclenche l’exécution automatique d'une interruption sur le Z80. Le code de 8 bits est envoyé au processeur Z80, en parallèle de l'interruption.
Il est possible de voir ce IO arbiter chip comme un contrôleur d'interruptions spécialisé dans les interruptions inter-processeur.
L'exemple du X86
[modifier | modifier le wikicode]Les anciens PC incorporaient sur leur carte mère un contrôleur d'interruption créé par Intel, le 8259A, qui ne gérait pas les interruptions inter-processeurs. Les cartes mères multiprocesseurs devaient incorporer un contrôleur spécial en complément. De nos jours, chaque cœur x86 possède son propre contrôleur d’interruption, le local APIC, qui gère les interruptions en provenance ou arrivant vers ce processeur. On trouve aussi un IO-APIC, qui gère les interruptions en provenance des périphériques et de les redistribuer vers les APIC locaux. L'IO-APIC gère aussi les interruptions inter-processeurs en faisant passer les interruptions d'un local APIC vers un autre. Tous les APIC locaux et l'IO-APIC sont reliés ensembles par un bus APIC spécialisé, par lequel ils vont pouvoir communiquer et s'échanger des demandes d'interruptions.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/19/Contr%C3%B4leurs_d%27interrptions_sur_syst%C3%A8mes_x86_multicoeurs.png/330px-Contr%C3%B4leurs_d%27interrptions_sur_syst%C3%A8mes_x86_multicoeurs.png)
On peut préciser le processeur de destination en configurant certains registres du IO-APIC, afin que celui-ci redirige la demande d'interruption d'un local APIC vers celui sélectionné. Cela se fait avec l'aide d'un registre de 64 bits nommé l'Interrupt Command Register. Pour simplifier le mécanisme complet, chaque processeur se voit attribuer un Id au démarrage qui permet de l'identifier (en fait, cet Id est attribué au local APIC de chaque processeur). Certains bits de ce registre permettent de préciser quel est le type de transfert : doit-on envoyer l'interruption au processeur émetteur, à tous les autres processeurs, à un processeur particulier. Dans le dernier cas, certains bits du registre permettent de préciser l'Id du processeur qui va devoir recevoir l'interruption. À charge de l'APIC de faire ce qu'il faut en fonction du contenu de ce registre.
Le partage des caches
[modifier | modifier le wikicode]Quand on conçoit un processeur multicœur, il ne faut pas oublier ce qui arrive à la pièce maîtresse de tout processeur actuel : le cache ! Pour le moment nous allons oublier le fait que les processeurs ont une hiérarchie de caches, avec des caches L1, L2, L3 et autres. Nous allons partir du principe qu'un processeur simple cœur a un seul cache, et voir comment adapter le cache à la présence de plusieurs cœurs. Nous allons rapidement lever cette hypothèse, pour étudier le cas où un processeur multicœur a une hiérarchie de caches, mais seulement après avoir vu le cas le plus simple à un seul cache.
Le partage des caches sans hiérarchie de caches : caches dédiés et partagés
[modifier | modifier le wikicode]Avec un seul niveau de cache, sans hiérarchie, deux solutions sont possibles. La première consiste à garder un seul cache, et de le partager entre les cœurs. L'autre solution est de dupliquer le cache et d'utiliser un cache par cœur. Les deux solutions sont appelées différemment. On parle de caches dédiés si chaque cœur possède son propre cache, et de cache partagé avec un cache partagé entre tous les cœurs. Ces deux méthodes ont des inconvénients et des avantages.
![]() |
![]() |
Le premier point sur lequel comparer caches dédiés et partagés est celui de la capacité du cache. La quantité de mémoire cache que l'on peut placer dans un processeur est limitée, car le cache prend beaucoup de place, près de la moitié des circuits du processeur. Aussi, un processeur incorpore une certaine quantité de mémoire cache, qu'il faut répartir entre un ou plusieurs caches. Les caches dédiés et partagés ne donnent pas le même résultat. D'un côté, le cache partagé fait que toute la mémoire cache est dédiée au cache partagé, qui est très gros. De l'autre, on doit répartir la capacité du cache entre plusieurs caches séparés, individuellement plus petits. En conséquence, on a le choix entre un petit cache pour chaque processeur ou un gros cache partagé.
Le choix entre les deux n'est pas simple, mais doit tenir compte du fait que les programmes exécutés sur les cœurs n'ont pas les mêmes besoins. Certains programmes sont plus gourmands et demandent beaucoup de cache, alors que d'autres utilisent peu la mémoire cache. Avec un cache dédié, tous les programmes ont accès à la même quantité de cache, car les caches des différents cœurs sont de la même taille. Les caches dédiés étant assez petits, les programmes plus gourmands devront se débrouiller avec un petit cache, alors que les autres programmes auront du cache en trop. A l'opposé, un cache partagé répartit le cache de manière optimale : un programme gourmand peut utiliser autant de cache qu'il veut, laissant juste ce qu'il faut aux programmes moins gourmands. le cache peut être répartit plus facilement selon les besoins des différents programmes.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/43/Cache_partag%C3%A9_contre_cache_d%C3%A9di%C3%A9.png/550px-Cache_partag%C3%A9_contre_cache_d%C3%A9di%C3%A9.png)
Un autre avantage des caches partagés est quand plusieurs cœurs accèdent aux même données. C'est un cas très courant, souvent lié à l'usage de mémoire partagé ou de threads. Avec des caches dédiés, chaque cœur a une copie des données partagées. Mais avec un cache partagé, il n'y a qu'une seule copie de chaque donnée, ce qui utilise moins de mémoire cache. Imaginons que l'on sait 8 caches dédiés de 8 Kibioctets, soit 64 kibioctets au total, comparé à un cache partagé de même capacité totale. Les doublons dans les caches dédiés réduiront la capacité mémoire utile, effective, comparé à un cache partagé. S'il y a 1 Kibioctet de mémoire partagé, 8 kibioctets seront utilisés pour stocker ces données en doublons, seulement 1 kibioctet sur un cache partagé.
Mais le partage du cache peut se transformer en inconvénient si les programmes entrent en compétition pour le cache, que ce soit pour y placer des données ou pour les accès mémoire. Deux programmes peuvent vouloir accéder au cache en même temps, voire carrément se marcher sur les pieds. La résolution des conflits d'accès au cache est résolu soit en prenant un cache multiport, avec un port dédié par cœur, soit par des mécanismes d'arbitrages avec des circuits dédiés.
Le revers de la médaille tient au temps de latence. Plus un cache est gros, plus il est lent. En conséquence, des caches dédiés seront plus rapides qu'un gros cache partagé plus lent. De plus, la cohérence des caches est plus simple sur les caches partagés, comme on le verra plus loin dans ce chapitre.
Les caches partagés centralisés et distribués
[modifier | modifier le wikicode]Un point important est que quand on parle de cache partagé ou de cache dédié, on ne parle que de la manière dont les cœurs peuvent accéder au cache, pas de la manière dont le caches est réellement localisé sur la puce. En théorie, qui dit plusieurs caches dédiés signifie que l'on a vraiment plusieurs caches séparés sur la puce. Et chaque cache dédié est proche du cœur qui lui est attribué. Et pour les caches partagés unique, une portion de la puce de silicium contient le cache, que cette portion est un énorme bloc de transistors. Il est généralement placé au milieu de la puce ou sur un côté, histoire de facilement le connecter à tous les cœurs.
Mais pour les caches séparés, ce n'est pas toujours le cas. Avoir un cache énorme poserait des problèmes sur les architectures avec beaucoup de cœurs. En réalité, le cache est souvent découpé en plusieurs banques, reliées à un contrôleur du cache par un système d'interconnexion assez complexe. Les banques sont physiquement séparées, et il arrive qu'elles soient placées proche d'un cœur chacune. L'organisation des banques ressemble beaucoup à l'organisation des caches dédiés, avec une banque étant l'équivalent d'un cache dédié. La différence est que les cœurs peuvent lire et écrire dans toutes les banques, grâce au système d'interconnexion et au contrôleur de cache.
La différence entre les deux solutions pour les caches partagés porte le nom de cache centralisés versus distribués. Un gros cache unique sur la puce est un cache centralisé, et c'est généralement un cache partagé. Mais un cache composé de plusieurs banques dispersées sur la puce est un cache distribué, qui peut être aussi bien dédié que partagé.
Le partage des caches adapté à une hiérarchie de caches
[modifier | modifier le wikicode]Dans la réalité, un processeur multicœur ne contient pas qu'un seul cache. Les processeurs actuels ont une organisation hybride, dans laquelle certains caches sont partagés et pas d'autres. Le cache L1 n'est jamais partagé, car ce cache doit avoir une latence très faible, ce qui augmente les temps d'accès. Partager le cache L1 serait parfaitement possible, mais rendrait celui-ci trop lent pour sa tâche. Pour les autres caches, tout dépend du processeur.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ec/Dual_Core_Generic.svg/220px-Dual_Core_Generic.svg.png)
Les premiers processeurs multicœurs commerciaux utilisaient deux niveaux de cache : des caches L1 dédiés et un cache L2 partagé. Il fallait relier le cache L2 partagé aux nombreux caches L1, ce qui était fait par un système assez complexe d'interconnexions. Le cache de niveau L2 était souvent simple port, car les caches L1 se chargent de filtrer les accès aux caches de niveau inférieurs. Par contre, il faut maintenir la cohérence des caches, comme on le verra plus bas.
De nos jours, les processeurs ont ajouté des caches L3 et même L4, de grande capacité. Le partage des caches s'est alors complexifié. Pour le cache L3 et le cache L4, il est systématiquement partagé, car son rôle est d'être un cache lent mais gros, ce qui colle parfaitement à ce qu'on attend d'un cache partagé. Le cas du cache L2 est un peu à part. Pour le cache L2, cela dépend des architectures : il est partagé sur certains processeurs, dédié sur d'autres. Mais dans le cas le plus courant, il y a plusieurs caches L2 qui sont chacun partagés entre plusieurs cœurs mais pas à tous. En effet, on peut limiter le partage du cache à quelques cœurs particuliers pour des raisons de performances.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fc/Partage_des_caches_sur_un_processeur_multicoeurs.png/440px-Partage_des_caches_sur_un_processeur_multicoeurs.png)
La cohérence des caches
[modifier | modifier le wikicode]Les caches dédiés ont un problème, que je vais introduire par un exemple. Prenons deux processeurs qui ont chacun une copie d'une donnée dans leur cache. Si un processeur modifie sa copie de la donnée, l'autre ne sera pas mise à jour. L'autre processeur manipule donc une donnée périmée : il n'y a pas cohérence des caches, sous-entendu cohérence entre contenu du cache et de la RAM.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Coh%C3%A9rence_des_caches.png/440px-Coh%C3%A9rence_des_caches.png)
Les caches partagés entre tous les cœurs ne posent aucun problème de cohérence car, avec eux, la donnée n'est présente qu'une seule fois dans tout le cache. Vous remarquerez que sur le schéma, la mémoire RAM contient encore une autre version de la donnée (du moins, si on utilise un cache Write Back). Mais cela ne pose pas de problème car les processeurs ne peuvent pas accéder à la donnée en RAM, mais seulement à la donnée dans le cache.
![](http://upload.wikimedia.org/wikipedia/commons/c/ce/Shared_cache_coherency.png)
Pour les caches partagés entre plusieurs cœurs, mais pas avec tous les cœurs, comme le cache L2, le problème est intermédiaire. Prenons le cas d'un processeur avec deux caches L2, partagés entre 4 cœurs (deux cœurs par cache L2). La cohérence des caches n'est pas conservée entre les 4 cœurs, mais elle est conservé entre les deux cœurs qui partagent un même cache. On est donc dans un cas intermédiaire entre les caches dédiés et les caches totalement partagés.
Dans ce cours, ce n'est pas la première fois que l'on fait face à un problème de cohérence des caches. Les transferts DMA peuvent poser des problèmes de cohérence des caches, par exemple. Pareil pour les TLBs : modifier la table des pages entraine une différence entre le contenu de la TLB et la table des pages en RAM. Le problème des architectures multicoeurs n'en est qu'un exemple. Le processeur fait face à un problème de cohérence de ses caches dès qu'un tier peut écrire dans la RAM, peu importe que le tier soit un autre processeur, un périphérique intégrant un controleur DMA, ou quoique ce soit d'autre.
Le seul problème est que les solutions des situations précédentes ne peuvent pas s'appliquer ici. Avec la TLB, on invalidait le contenu de la TLB quand les circonstances l'exigaient. Avec les transferts DMA, on interdisait la mise en cache pour certains intervalles d'adresse utilisés pour ces transferts DMA. Ici, ces solutions ne sont clairement pas possible. Les problèmes de cohérence des caches des architectures multicoeurs/multiprocesseurs surviennent dans une situation bien précise : deux processus partagent une même zone de mémoire. Interdire de mettre en cache cette zone de mémoire détruirait les performances et annulerait les gains liés au parallèlisme. Pariel pour l'invalidation des caches : ceux-ci seraient remis à zéro à chaque écriture dans la mémoire partagée, ce qui serait trop complexe à mettre en oeuvre et détruirait les performances au-delà du raisonnable.
En guise de solution alternative plus performante, les ingénieurs ont inventé de quoi détecter les données périmées et les mettre à jour :, formalisés dans des protocoles de cohérence des caches. Il existe beaucoup de protocoles de cohérence des caches et nous ne les verrons pas tous dans ce chapitre. Tout protocole de cohérence des caches doit répondre ce problème : comment les autres caches sont-ils au courant qu'ils ont une donnée périmée ?
Les protocoles de cohérence des caches : généralités
[modifier | modifier le wikicode]On voit donc que la cohérence des caches n'est pas automatiquement maintenue pour les caches qui ne sont pas partagés entre tous les cœurs. Pour corriger ce problème, les ingénieurs ont inventé de quoi détecter les données périmées et les mettre à jour : des protocoles de cohérence des caches. Il existe beaucoup de protocoles de cohérence des caches et nous ne les verrons pas tous dans ce chapitre. Tout protocole de cohérence des caches doit répondre ce problème : comment les autres caches sont-ils au courant qu'ils ont une donnée périmée ?
Les différents types de protocoles de cohérence des caches
[modifier | modifier le wikicode]Il existe différents protocoles de cohérence des caches, qui visent à assurer automatiquement une cohérence des caches. Les architectures distribuées et les architectures à mémoire partagée n'utilisent pas les mêmes protocoles. On verra dans quelques chapitres que les architectures distribuées utilisent des protocoles de cohérence des caches à base de répertoires, qui ne sont pas utilisés sur les architectures à mémoire partagée. D'autres architectures multicœurs utilisent d'autres modèles de cohérence. Un cas assez particulier est celui des GPU, les processeurs intégrés sur les cartes graphiques. N'importe quelle carte graphique moderne contient un ou plusieurs processeurs multicœurs de haute performance, et dispose a ce titre d'un mécanisme de cohérence des caches. Mais celui-ci est très particulier, du fait que les cartes graphiques sont conçues pour le parallélisme de données, comme on le verra plus tard.
Sur les architectures à mémoire partagée, ces protocole utilisent la technique dite de l’espionnage du bus. Son nom trahit l'idée qui se cache derrière cette technique : les caches interceptent les écritures sur le bus, qu'elles proviennent ou non des autres processeurs. S'il n'y a pas de bus mémoire partagé entre les caches, le principe reste le même : les caches sont interconnectés entre eux et échangent des informations pour maintenir la cohérence. Concrètement, quand un cœur/processeur écrit une donnée dans un cache dédié/partiellement partagé, les autres processeurs reçoivent aussi l'écriture. Pour chaque écriture interceptée, ils vérifient si l'écriture modifie une donnée dans leur cache. Rien de plus simple pour cela : ils accèdent à leur cache avec l'adresse où écrire, et vérifie si l'adresse matche une ligne de cache. Si ce n'est pas le cas, c'est que le cache n'a pas de copie de la donnée modifiée, et il n'y a rien à faire. Dans le cas contraire, le cache contient une copie périmée de la donnée modifiée et le cache doit agir.
La première action du cache est de marquer la ligne de cache fautive comme étant invalide. Avec ces protocoles, chaque ligne de cache contient des bits qui indique si la donnée contenue est à jour ou périmée. Typiquement, on trouve un dirty bit par ligne de cache, qui indique si la donnée est invalide ou non, et qui est vérifié lors de chaque lecture. Tout accès à une ligne de cache invalide entrainera un défaut de cache et la donnée sera chargée depuis la RAM et/ou depuis un autre cache. Cela garantit que la copie périmée n'est pas utilisée.
Il faut aussi remplacer la copie périmée par une copie valide, la plus récente. Dans ce cas, on fait face à deux choix : mettre à jour la ligne de cache immédiatement, ou la mettre à jour au prochain accès.
- Avec la mise à jour sur écriture, les caches sont mis à jour automatiquement le plus tôt possible, avant même toute tentative de lecture de la donnée périmée.
- Avec l'invalidation sur écriture, toute écriture invalide les versions de la donnée dans les autres caches. Ces versions seront mises à jour quand le processeur les lira : il détecta que la ligne de cache a été invalidée et la mettra à jour si besoin.
Les caches d'instruction et les TLB ne sont pas concernées par la cohérence des caches
[modifier | modifier le wikicode]Tout ce qui a été dit précédemment ne vaut que pour les caches de données. Les caches d'instruction et les TLB ne sont pas gardées cohérentes. La raison principale est une question de performance. Les caches d'instruction et les TLBs sont quasiment en lecture seule, à savoir qu'on écrit très rarement dedans. Il est rare de modifier à la volée le code machine d'un programme, très rare. Modifier le contenu d'une table des pages est aussi assez peu fréquent, surtout d'une manière qui invalide le contenu d'une TLB. Cela arrive quand une page change de place, pas plus. Ne pas garder ces caches cohérents permet de gagner grandement en performances et d'économiser des circuits.
Pour les TLB, d'autres contraintes techniques font que de tels caches ne peuvent pas facilement être rendus cohérents. Les TLBs ne savent pas à quelle adresse se situe leur contenu. Elles associent des numéros de page logique à des numéros de page physique, la correspondance en question fait partie de la table des pages en RAM et se trouve à une adresse physique précise, mais sa position est inconnue de la TLB. Incorporer cette adresse physique dans la TLB ne résout pas tous les problèmes. Il faudrait accéder à toute la TLB à chaque accès mémoire pour implémenter la cohérence des caches, ce qui se marie mal avec des TLB associatives par voie. Les techniques pour résoudre ce problème n'en valent pas la peine, et le système de mémoire virtuelle dispose de techniques pour invalider le contenu de la TLB quand c'est nécessaire.
Les protocoles sans nouveaux états
[modifier | modifier le wikicode]Pour commencer, nous allons voir le protocole de cohérence des caches le plus simple : le protocole SI. Il ne fonctionne qu'avec des caches Write-trough, où toute donnée écrite dans le cache est écrite en même temps dans la RAM et dans les niveaux de caches inférieurs s'ils existent. Le contenu de la mémoire est donc toujours à jour, mais ce n'est pas le cas pour les caches des autres processeurs.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Coh%C3%A9rence_des_caches_write-through.png/550px-Coh%C3%A9rence_des_caches_write-through.png)
Seuls deux états suffisent pour décrire l'état d'une ligne de cache : Shared, qui indique que la ligne de cache est cohérente et Invalid, qui indique que la donnée est périmée. On obtient le protocole de cohérence des caches le plus simple qui soit : le protocole SI. Voici décrit en image le fonctionnement de ce protocole :
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Diagramme_d%27%C3%A9tat_du_protocole_SI.png/440px-Diagramme_d%27%C3%A9tat_du_protocole_SI.png)
Les protocoles à état Shared
[modifier | modifier le wikicode]La cohérence des caches est très simple quand on a des caches write-trough, mais ces derniers sont à l'origine de beaucoup d'écritures en mémoire qui saturent le bus. Aussi, on a inventé les caches Write-back, où le contenu de la mémoire n'est pas cohérent avec le contenu du cache. Si on écrit dans la mémoire cache, le contenu de la mémoire RAM n'est pas mis à jour. On doit attendre que la donnée sorte du cache pour l'enregistrer en mémoire ou dans les niveaux de caches inférieurs (s'ils existent), ce qui évite de nombreuses écritures mémoires inutiles.
Divers protocoles de cohérence des caches existent pour les caches Write Back. Le plus simple d'entre eux est le protocole MSI. Ce protocole scinde l'état Shared en deux sous-états : Modified et Shared. L'état Invalid ne change pas et correspond toujours au cas où la donnée présente dans le cache est périmée. L'état Shared change et correspond maintenant à une donnée à jour, présente dans plusieurs caches. L'état Modified correspond à une donnée à jour, mais dont les copies des autres caches sont périmées. Avec ce protocole, un processeur peut lire des lignes de caches dans l'état Modified ou Shared sans problème, mais toute tentative de lecture d'une ligne Invalid demande de récupérer la version à jour dans la mémoire. Pour l'écriture, rien de plus simple : toute écriture est possible et place la ligne de cache dans l'état Modified.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b8/Diagramme_d%27%C3%A9tat_informel_du_protocole_MSI.png/440px-Diagramme_d%27%C3%A9tat_informel_du_protocole_MSI.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/86/Modified-Shared-Invalid_Protokoll.png/440px-Modified-Shared-Invalid_Protokoll.png)
Les protocoles à état Exclusif
[modifier | modifier le wikicode]Le protocole MSI n'est pas parfait. Si un seul cache possède une donnée, on aura prévenu les autres caches pour rien en cas d'écriture. Et les communications sur le bus ne sont pas gratuites. Pour régler ce problème, on peut scindr l'état Shared en deux états : Exclusive si les autres processeurs ne possèdent pas de copie de la donnée, Shared sinon. Grâce à cette distinction, on peut éviter l'envoi de messages aux autres caches pour la modification d'une donnée en état Exclusive : on sait que les autres caches ne possèdent pas de copie de la donnée. Le protocole MESI ainsi créé est identique au protocole MSI, avec quelques ajouts. Par exemple, si une donnée est chargée depuis la mémoire pour la première fois dans un cache, elle passe soit en Exclusive (les autres caches ne contenaient pas la donnée), soit en Shared (les autres caches en possèdent une copie). Une donnée marquée Exclusive peut devenir Shared si la donnée est chargée dans le cache d'un autre processeur.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/MESI_State_Transaction_Diagram.svg/440px-MESI_State_Transaction_Diagram.svg.png)
Comment le processeur fait-il pour savoir si les autres caches ont une copie de la donnée ? Pour cela, il faut ajouter un fil Shared sur le bus, qui sert à dire si un autre cache a une copie de la donnée. Lors de chaque lecture, l'adresse à lire sera envoyée à tous les caches, qui vérifieront s'ils possèdent une copie de la donnée. Une fois le résultat connu, chaque cache fournit un bit qui indique s'il a une copie de la donnée. Le bit Shared est obtenu en effectuant un OU logique entre toutes les versions du bit envoyé par les caches.
Le protocole à état Owned
[modifier | modifier le wikicode]Les protocoles MESI et MSI ne permettent pas de transférer des données entre caches sans passer par la mémoire. Si le processeur demande la copie valide d'une donnée, tous les caches ayant la bonne version de la donnée répondent en même temps et la donnée est envoyée en plusieurs exemplaires ! Pour éviter ce problème, on doit rajouter un état supplémentaire : l'état Owned. Si un processeur écrit dans son cache, il mettra sa donnée en Owned, mais les autres caches passeront leur donnée en version Modified, voire Shared une fois la mémoire mise à jour. Ainsi, un seul processeur pourra avoir une donnée dans l'état Owned et c'est lui qui est chargé de répondre aux demandes de mise à jour.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4d/MOSI_Processor_Transactions.png/220px-MOSI_Processor_Transactions.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/98/MOSI_Bus_Transactions.png/220px-MOSI_Bus_Transactions.png)
Divers protocoles de cohérences des caches utilisent cet état Owned. Le premier d’entre eux est le protocole MOSI, une variante du MESI où l'état exclusif est remplacé par l'état O. Lors d'une lecture, le cache vérifie si la lecture envoyée sur le bus correspond à une de ses données. Mais cette vérification va prendre du temps, et le processeur va devoir attendre un certain temps. Si au bout d'un certain temps, aucun cache n'a répondu, le processeur postule qu'aucun cache n'a la donnée demandée et va lire la donnée en mémoire. Ce temps est parfois fixé une fois pour toute lors de la création des processeurs, mais il peut aussi être variable, qui est géré comme suit :
- pour savoir si un cache contient une copie de la donnée demandée, chaque cache devra répondre en fournissant un bit ;
- quand le cache a terminé la vérification, il envoie un 1 sur une sortie spécifique, et un 0 sinon ;
- un ET logique est effectué entre tous les bits fournis par les différents caches, et le résultat final indique si tous les caches ont effectué leur vérification.
On peut aussi citer le protocole MOESI, un protocole MESI auquel on a jouté l'état O.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b9/MOESI_State_Transaction_Diagram.svg/440px-MOESI_State_Transaction_Diagram.svg.png)
L'atomicité
[modifier | modifier le wikicode]Afin de gérer le partage de la mémoire sans problèmes, chaque processeur doit définir un modèle mémoire, un ensemble de restrictions et de contraintes qui garantissent que les instructions ne puissent pas être interrompues (ou donnent l'impression de ne pas l'être) : c'est la propriété d'atomicité. Un thread doit utiliser plusieurs instructions successives sur la donnée pour pouvoir en faire ce qu'il veut, et cela peut poser des problèmes si les instructions peuvent être interrompues par une exception ou tout autre chose. Par exemple, il est possible qu'une lecture démarre avant que la précédente soit terminée. De même, rien n’empêche une lecture de finir avant l'écriture précédente et renvoyer la valeur d'avant l'écriture.
Prenons un exemple, avec un entier utilisé par plusieurs threads, chaque thread s’exécutant sur un processeur x86. Chaque thread veut l'incrémenter. Seul problème, l'incrémentation n'est pas effectuée en une seule instruction sur les processeurs x86. Il faut en effet lire la donnée, l'augmenter de 1, puis l'écrire. Ce qui fait que l'on peut se retrouver dans la situation illustrée ci-dessous, où un processeur n'a pas eu le temps de finir son incrémentation qu'un autre en a démarré une nouvelle.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Illustration_du_r%C3%A9sultat_de_deux_op%C3%A9rations_concurrentes_sur_la_m%C3%AAme_variable.png/440px-Illustration_du_r%C3%A9sultat_de_deux_op%C3%A9rations_concurrentes_sur_la_m%C3%AAme_variable.png)
Pour avoir le bon résultat il y a une seule et unique solution : le processeur qui accède à la donnée doit avoir un accès exclusif à la donnée partagée. Sans cela, l'autre processeur ira lire une version de la donnée pas encore modifiée par le premier processeur. Dans notre exemple, un seul thread doit pouvoir manipuler notre compteur à la fois. Et bien sûr, cette réponse se généralise à presque toutes les autres situations impliquant une donnée partagée. On doit donc définir ce qu'on appelle une section critique : un morceau de temps durant lequel un thread aura un accès exclusif à une donnée partagée, avec la certitude qu'aucun autre thread ne peut modifier la donnée partagée durant ce temps. Autant prévenir tout de suite, créer de telles sections critiques se base sur des mécanismes mêlant le matériel et le logiciel. Il existe deux grandes solutions, qui peuvent être soit codées sous la forme de programmes, soit implantées directement dans le silicium de nos processeurs.
L'exclusion mutuelle permet à un thread de réserver la donnée partagée. Un thread qui veut manipuler une donnée réserve celle-ci, et la libère une fois qu'il en a fini avec elle. Si la donnée est réservée, tous les autres threads attendent leur tour. Pour mettre en œuvre cette réservation/dé-réservation, on ajoute un compteur à la donnée partagée, qui indique si la donnée partagée est libre ou déjà réservée. Dans le cas le plus simple, ce compteur vaudra 0 si la donnée est réservée, et 1 si elle est libre. Ce compteur ce qu'on appelle un verrou d'exclusion mutuelle, aussi appelé mutex (raccourci du terme anglais mutual exclusion).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Mutex.png/550px-Mutex.png)
Les instructions atomiques
[modifier | modifier le wikicode]Dans le cas précédent, la vérification et modification du compteur ne peut pas être interrompue, sous peine de problèmes. On peut reprendre l'exemple du dessus pour l'illustrer. Si notre compteur est à 0, et que deux threads veulent lire et modifier ce compteur simultanément, il est possible que les deux threads lisent le compteur en même temps : ils liront alors un zéro, et essayeront alors de se réserver la donnée simultanément. Bref, retour à la case départ...
Idéalement, il faudrait que lecture et écriture se fassent en une seule fois. Pour régler ce problème, certains processeurs fournissent des instructions spécialisées, in-interruptibles, capables d'effectuer cette modification du compteur en une seule fois. Elles peuvent lire le compteur, décider si on peut le modifier, et écrire la bonne valeur sans être dérangé par un autre processeur qui viendrait s'inviter dans la mémoire sans autorisation ! Par exemple, sur les processeurs x86, la vérification/modification du compteur vue plus haut peut se faire avec l'instruction test and set. D'autres instructions atomiques similaires existent pour résoudre ce genre de problèmes. Leur rôle est toujours d'implémenter des verrous d'exclusion mutuelle plus ou moins sophistiqués, comme des sémaphores, des verrous (Locks), etc. Généralement, un programmeur n'a pas à manipuler des instructions atomiques lui-même, mais manipule des abstractions basées sur ces instructions atomiques, fournies par des bibliothèques ou son langage de programmation. Ces instructions in-interruptibles sont appelées des instructions atomiques. De plus, elles empêchent tout accès mémoire tant qu'elles ne sont pas terminées. De telles instructions garantissent que les écritures et lectures s’exécutent l'une après l'autre. Voici la plupart de ces instructions atomiques les plus connues :
Instruction | Description |
---|---|
Compare And Swap | Cette instruction va lire une donnée en mémoire, va comparer celle-ci à l'opérande de notre instruction (une donnée fournie par l'instruction), et va écrire un résultat en mémoire si ces deux valeurs sont différentes. Ce fameux résultat est fourni par l'instruction, ou est stocké dans un registre du processeur. |
Fetch And Add | Cette instruction charge la valeur de notre compteur depuis la mémoire, l'incrémente, et écrit sa valeur en une seule fois. Elle permet de réaliser ce qu'on appelle des sémaphores. Elle permet aussi d'implémenter des compteurs concurrents. |
XCHG | Cette instruction peut échanger le contenu d'un registre et d'un morceau de mémoire de façon atomique. Elle est notoirement utilisée sur les processeurs x86 de nos PC, qui implémentent cette instruction. |
Lors de l’exécution de l'instruction atomique, aucun processeur ne peut aller manipuler la mémoire. L'instruction atomique réserve l'accès au bus en configurant un bit du bus mémoire, ou par d'autres mécanismes de synchronisation entre processeurs. Le cout de ce blocage de la mémoire est assez lourd, ce qui rend les instructions atomiques assez lentes. Mais on peut optimiser le cas où la donnée est dans le cache. Dans ce cas, pas besoin de bloquer la mémoire. Le processeur a juste à écrire dans la mémoire cache, et les mécanismes de cohérence des caches se contenteront de mettre à jour la donnée de façon atomique automatiquement. Le coût des instructions atomiques est alors fortement amorti.
Les instructions LL/SC
[modifier | modifier le wikicode]Une autre technique de synchronisation est basée sur les instructions Load-Link et Store-Conditional. L'instruction Load-Link lit une donnée depuis la mémoire de façon atomique. L'instruction Store-Conditional écrit une donnée chargée avec Load-Link, mais uniquement à condition que la copie en mémoire n'aie pas été modifiée entre temps. Si ce n'est pas le cas, Store-conditional échoue. Pour indiquer un échec, il y a plusieurs solutions : soit elle met un bit du registre d'état à 1, soit elle écrit une valeur de retour dans un registre. Sur certains processeurs, l’exécution d'interruptions ou d'exceptions matérielles après un Load-Link fait échouer un Store-conditional ultérieur.
Implémenter ces deux instructions est assez simple, et peut se faire en utilisant les techniques de bus-snopping vues dans le chapitre sur la cohérence des caches. Pour implémenter l'instruction SC, il suffit de mémoriser si la donnée lue par l'instruction LL a été invalidée depuis la dernière instruction LL. Pour cela, on utilise un registre qui mémorise l'adresse lue par l'instruction LL, à laquelle on ajoute un bit d'invalidation qui dit si cette adresse a été invalidée. L'instruction LL va initialiser le registre d'adresse avec l'adresse lue, et le bit est mis à zéro. Une écriture a lieu sur le bus, des circuits vérifient si l'adresse écrite est identique à celle contenue dans le registre d'adresse et mettent à jour le bit d'invalidation. L'instruction SC doit vérifier ce bit avant d'autoriser l'écriture.
La mémoire Transactionnelle Matérielle
[modifier | modifier le wikicode]La mémoire transactionnelle permet de rendre atomiques des morceaux de programmes complets, que l'on appelle des transactions. Pendant qu'une transaction s’exécute, tout se passe comme si la transaction ne modifiait pas de données et restait plus ou moins "invisible" des autres processeurs. Dans le cas où la donnée partagée n'a pas été modifiée par un autre processeur durant l’exécution d'une transaction, celle-ci peut alors écrire son résultat en mémoire. Mais dans le cas contraire, la transaction échoue et doit reprendre depuis le début : les changements effectués par la transaction ne seront pas pris en compte.
Il existe plusieurs manières d'implémenter la mémoire transactionnelle matérielle. La plus simple n'utilise pas le cache et se contente de mettre en attente les écritures dans la Store Queue, la Load-Store Queue ou autre. Lors d'une transaction, les écritures ne sont pas propagées dans les mémoires caches, mais restent dans le pipeline, dans le processeur. A la fin de la transaction, le processeur vérifie s'il n'y a pas eu de conflits et si la transaction est validée. Si c'est le cas, les écritures sont propagées dans le cache. Si ce n'est pas le cas, la Store Queue/Load-Store Queue est vidée et on annule les changements effectués par la transaction (ROB ou autre méthode capable de gérer les interruptions précises). La technique en question porte le nom de gated store buffer, elle a été implémentée la première fois sur les processeurs Transmetta Crusoe et Efficeon.
Mais d'autres implémentations ne se limitent pas à la Store Queue, mais peuvent déborder sur le cache. Avec ces techniques, les écritures se font dans le cache, mais le processeur dispose d'un moyen de les annuler. La cohérence des caches est temporairement mise en pause pendant une transaction, mais est rallumée à la fin d'une transaction. Au du moins, un mécanisme similaire permet de détecter les violations d'intégrité, à savoir qu'un processeur a écrit dans une donnée partagée. Ces solutions ajoutent deux circuits.
Premièrement, le processeur doit mémoriser l'ensemble des adresses modifiées lors d'une transaction, et ce pour chaque transaction. Il gère donc une liste d'adresse pour chaque transaction. Lorsqu'une transaction se termine, cette liste est utilisée pour vérifier si il y a une erreur, et aussi pour invalider les lignes de cache modifiées par la transaction si celle-ci échoue. Deux solutions à cela : un write buffer de grande taille, ou une mémoire FIFO contenant une liste des adresses/lignes de cache modifiées. Si la mémoire FIFO déborde, la transaction est annulée ou du moins mise en attente.
Deuxièmement, le cache est modifié. Pour chaque ligne de cache, des bits pour savoir si la ligne a été lue ou écrite par un cœur. Si un conflit est détectée pour une ligne de cache, elle est marquée comme invalide pour le protocole de cohérence des caches, et l'invalidation est propagée aux autres cœurs grâce à la liste d'adresse précédente. Les lignes de cache marquées comme lues ou écrites doivent rester dans le cache et sont ignorées par l'algorithme de remplacement des lignes de cache.
![](http://upload.wikimedia.org/wikipedia/commons/3/35/Hardware_Transaction.png)
L'implémentation la plus simple utilise un cache dédié aux transactions : le cache transactionnel. À cela, il faut ajouter des instructions pour manipuler le cache transactionnel. Les données dans le cache transactionnel utilisent un protocole légèrement différent des autres caches, avec des états et des transitions en plus. Les autres méthodes préfèrent réutiliser les mémoires caches déjà présentes dans le processeur en guise de cache transactionnel.
Une autre implémentation utilise le cache L1 en lieu et place d'un cache spécialisé. Les écritures dans le cache L1 ne sont pas prises en compte par la cohérence des caches. Chaque coeur modifie son propre cache L1 de son côté, les écritures dans le cache ne sont pas propagées tant que la transaction ne termine pas correctement. A la fin d'une transaction, le protocole de cohérence des caches est rallumé, les écritures se propagent, et on peut alors détecter si une donnée a été modifiée par plusieurs coeurs. Si la transaction foire, les données modifiées par la transaction sont marquées Invalid par les mécanismes de cohérence des caches, elles sont donc relues depuis la mémoire RAM ou les niveaux de cache inférieurs.
Une autre solution, utilisée sur le processeur Blue gene d'IBM, consiste à avoir plusieurs exemplaires d'une donnée dans le cache, chacun venant d'un processeur/cœur différent. Si un seul processeur a manipulé la donnée partagée, celle-ci ne sera présente qu'en une seule version dans les caches des autres processeurs. Mais si la transaction échoue, alors cela veut dire que plusieurs processeurs ont modifié cette donnée : plusieurs versions d'une même donnée différente sera présente dans le cache
Ces techniques ont un défaut : la quantité de données manipulées par la transaction est limitée à la taille du cache. Pour éviter ce petit problème, certains chercheurs travaillent sur une mémoire transactionnelle capable de gérer des transactions de taille arbitraires. Ces techniques mémorisent les données modifiées par la transaction en mémoire RAM, dans des enregistrements que l'on appelle des logs.
Le speculative Lock Elision
[modifier | modifier le wikicode]Les instructions atomiques sont lentes, sans compter qu'elles sont utilisées de façon pessimistes : l'atomicité est garantie même si aucun autre thread n'accède à la donnée lue/écrite. Aussi, pour accélérer l'exécution des instructions atomiques, des chercheurs se sont penchés sur ce problème de réservations inutiles et ont trouvé une solution assez sympathique, basée sur la mémoire transactionnelle. L'idée est de transformer les instructions atomiques qui réservent une donnée en instructions permettant de démarrer des transactions. Bien évidemment, les instructions atomiques qui libèrent la donnée partagée marquent la fin de la transaction. Ce mécanisme tente donc transformer les instructions atomiques en transaction une première fois, puis revient à la normale en cas d'échec. Il s'appelle le Speculative Lock Elision.
Ainsi, on n’exécute pas l'instruction atomique permettant d'effectuer une réservation, et on la transforme en une simple instruction de lecture de la donnée partagée. Une fois cela fait, on commence à exécuter la suite du programme en faisant en sorte que les autres processeurs ne voient pas les modifications effectuées sur nos données partagées. Puis, vient le moment de libérer la donnée partagée via une autre instruction atomique. À ce moment, si aucun autre thread n'a écrit dans notre donnée partagée, tout ira pour le mieux : on pourra rendre permanents les changements effectués. Par contre, si jamais un autre thread se permet d'aller écrire dans notre donnée partagée, on doit annuler les changements faits. À la suite de l'échec de cette exécution optimiste, cette transaction cachée, le processeur reprendre son exécution au début de notre fausse transaction, et va exécuter son programme normalement : le processeur effectuera alors de vraies instructions atomiques.
Il arrive parfois que le premier essai échoue lamentablement : si un autre thread a beaucoup de chance de manipuler une donnée partagée en même temps qu'un autre, le premier essai a de fortes chances de planter. Pour plus d'efficacité, certains processeurs cherchent à éviter ce genre de situation en estimant la probabilité que le premier essai (la transaction) échoue. Pour cela, ils incorporent un circuit permettant d'évaluer les chances que le premier essai marche en tant que transaction : le Transaction Predictor. Une fois cette situation connue, le processeur décide ou non d’exécuter ce premier essai en tant que transaction.
L'exemple avec le x86
[modifier | modifier le wikicode]Dans cette section, nous allons étudier les premiers processeurs grand public qui ont supporté la mémoire transactionnelle matérielle : les processeurs Intel basés sur l’architecture Haswell, sortis aux alentours de mars 2013. Sur ces processeurs, deux modes sont disponibles pour la mémoire transactionnelle matérielle : le mode TSX, et le mode HLE.
Le mode TSX fournit quelques instructions supplémentaires pour gérer la mémoire transactionnelle matérielle. On trouve ainsi trois nouvelles instructions : XBEGIN, XEND et XABORT. XBEGIN démarre une transaction, dans le sens où toutes les instructions placées après elles sont dans une transaction. L'instruction XBEGIN fournit une adresse qui pointe sur un morceau de code permettant de gérer l'échec de la transaction. En cas d'échec de la transaction, le processeur va reprendre automatiquement son exécution à cette adresse. Si on a de quoi marquer le début d'une transaction, il faut aussi indiquer sa fin avec l'instruction XEND. XABORT, quant à elle, stoppe l’exécution d'une transaction, si jamais le programme détecte un problème lors de l’exécution de la transaction. Lors de la fin d'une transaction, le processeur reprend à l'adresse indiquée par XBEGIN, et remet le processeur dans l'état d'avant le début de la transaction. Les registres modifiés par la transaction sont remis dans leur état initial, à une exception prêt : EAX. Celui-ci sert à stocker un code d'erreur qui indique les raisons de l'échec d'une transaction.
Les processeurs Haswell supportent aussi le Speculative Lock Elision. Les instructions atomiques peuvent être transformée en transaction à une condition : qu'on leur rajoute un préfixe. Le préfixe d'une instruction x86, correspond à un octet optionnel, placé au début de l'instruction. Il donne des indications au processeur, qui permettent de modifier le comportement de l'instruction. Le préfixe LOCK rend certaines instructions atomiques, REPNZE répéte certaines instructions tant qu'une condition est requise, etc. Le fait est que certains préfixes n'ont pas de signification pour certaines instructions. Autrefois, les préfixes sans signification étaient totalement ignorés par le processeur. Pour supporter le Lock Elision, ces préfixes sans significations sont réutilisés pour indiquer qu'une instruction atomique doit subir la Lock Elision. De plus, deux "nouveaux" préfixes font leur apparition : XAQUIRE qui sert à indiquer que notre instruction atomique doit être tentée en tant que transaction ; et XRELEASE qui dit que la transaction spéculative est terminée. Ainsi, un programme peut être conçu pour utiliser la Lock Elision, tout en fonctionnant sur des processeurs plus anciens, qui ne la supportent pas ! Belle tentative de garder la rétrocompatibilité.
La consistance mémoire
[modifier | modifier le wikicode]On a vu dans les chapitres précédents que les processeurs modernes modifient l'ordre des accès mémoire pour gagner en efficacité. Avec plusieurs processeurs, chaque processeur fait cela chacun dans son coin sans se préoccuper des autres. Les opérations d'écriture peuvent être mises dans le désordre du point de vue des autres processeurs, et les lectures effectuées par les autres processeurs peuvent alors renvoyer de vielles données.
Un exemple classique est celui de deux cœurs qui partagent le même cache ou la même mémoire, mais qui utilisent chacun un tampon d'écriture (store buffer). Imaginons que le premier cœur effectue une écriture, puis une lecture. L'écriture sera exécutée en écrivant dans le tampon d'écriture, l'écriture dans le cache aura lieu plus tard. La lecture est effectuée en lisant directement dans le cache. Pour le premier processeur, l'écriture s'est réalisée avant la lecture, car pour lui, la fin de l'écriture signifie écrire dans le tampon d'écriture. Mais pour le second cœur, l'ordre s'est inversé : il voit la lecture dans le cache, puis l'écriture dans le cache. La raison est qu'il n'a pas connaissance du contenu du tampon d'écriture de l'autre cœur.
Pour que les accès mémoires dans le désordre ne posent pas de problèmes, il existe différentes solutions, différents modèles de consistance mémoire. Ceux-ci sont décrits dans le tableau ci-dessous.
Modèle de consistance | Description |
---|---|
Consistance séquentielle | Aucune réorganisation de l'ordre des instructions n'est possible. Tout se passe comme si les instructions de chaque programme s'effectuaient dans l'ordre imposé par celui-ci, et que les lectures ou écritures des différents processeurs étaient exécutées les unes après les autres. Ce modèle de consistance interdit de nombreux cas de réorganisation parfaitement légaux, même avec plusieurs processeurs. |
Total Store Ordering | Un processeur peut immédiatement réutiliser une donnée qu'il vient d'écrire dans son cache. Tout se passe donc comme si l'écriture en question n'était pas in-interruptible : on peut lire la donnée écrite avant que toutes les versions de la donnée soient mises à jour. C'est ce qui était fait dans les protocoles de cohérence des caches qu'on a vus précédemment : le statut modified n’empêchait pas les lectures de la donnée. |
Partial Store Ordering | Permet des écritures simultanées, ainsi que des réorganisations de l'ordre des écritures qui portent sur des données différentes. Ainsi, on peut démarrer une nouvelle écriture avant que les écritures précédentes ne soient terminées. La seule condition pour éviter les catastrophes est que ces écritures manipulent des données différentes, placées à des endroits différents de la mémoire. |
No Store Ordering | Toutes les réorganisations possibles entre lectures et écritures sont autorisées, tant qu'elles se font sur des données différentes. On peut parfaitement démarrer une lecture pendant que d'autres sont en attente ou en cours. |
Les fences et barrières mémoires
[modifier | modifier le wikicode]Les processeurs à type No Store Ordering garantissent que les accès à des données partagées se déroulent correctement avec des instructions appelées barrières mémoires ou Fences. Ce sont des instructions qui forcent le processeur à terminer toutes les écritures et/ou lectures qui la précède. Certains processeurs possèdent une barrière mémoire pour les lectures et une autre pour les écritures. D'autres processeurs utilisent un nombre de barrières mémoires plus élevé, dont des barrières mémoires dédiées à des cas particuliers.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Fences.png/440px-Fences.png)
Un compilateur peut placer les barrières mémoires au bon endroit, avec un peu d'aide du programmeur. Certains langages de programmation permettent d'indiquer au compilateur qu'une donnée doit toujours être lue depuis la mémoire RAM, via le mot-clé volatile. C'est très utile pour préciser que cette donnée est potentiellement partagée par plusieurs processeurs ou manipulable par des périphériques. Les compilateurs peuvent placer des barrières mémoires lors des lectures ou écritures sur ces variables, mais ce n'est pas une obligation. Il arrive aussi que le programmeur doive manipuler explicitement des barrières mémoires. Utiliser l'assembleur est alors une possibilité, mais qui est rarement exploitée, pour des raisons de portabilité. Pour limiter la casse, certains systèmes d'exploitations ou compilateurs peuvent aussi fournir des barrières mémoires explicites, encapsulées dans des bibliothèques ou cachées dans certaines fonctions.
L'exemple du modèle mémoire x86
[modifier | modifier le wikicode]Après avoir vu la théorie, passons maintenant à la pratique. Dans cette partie, on va voir les modèles de consistances utilisés sur les processeurs x86, ceux qu'on retrouve dans nos PC actuels. Le modèle de consistance des processeurs x86 a varié au cours de l'existence de l'architecture : un vulgaire 486DX n'a pas le même modèle de consistance qu'un Core 2 duo, par exemple. Quoi qu’il en soit, les modèles de consistance des processeurs x86 ont toujours étés assez forts, avec pas mal de restrictions. Si on compare aux autres processeurs, le x86 est assez strict. Bref, le premier modèle de consistance utilisé sur les processeurs x86 est apparu sur les premiers processeurs x86 et est resté en place sur tous les processeurs de marque Pentium. Ce modèle est assez simple : hormis une exception, tout doit se passer comme si le processeur accédait à la mémoire dans l'ordre des opérations de notre programme. Cette exception concerne les lectures : dans certains cas, on peut les exécuter avant certaines écritures, sous réserve que les conditions suivantes soient respectées :
- ces écritures doivent se faire dans la mémoire cache ;
- la lecture doit se faire dans la mémoire ;
- nos écritures doivent aller écrire à des adresses différentes de l'adresse accédée en lecture ;
- aucune transaction avec un périphérique ne doit être en cours.
Sur les processeurs à partir du Pentium 4, les choses changent. Le Pentium 4 est en effet le premier processeur à implémenter des techniques permettant d’exécuter plusieurs processus en parallèle. Ce processeur est en effet le premier à utiliser l'Hyperthreading. En conséquence, le modèle de consistance a du être assoupli pour éviter de perdre bêtement en performance. Voici un résumé de ce modèle de consistance :
- une lecture ne peut pas être déplacée avant ou après une autre lecture ;
- une écriture ne peut pas être déplacée avant une lecture ;
- à part pour quelques exceptions, l'ordre des écritures dans la mémoire ne change pas : une écriture dans la mémoire ne peut pas être déplacée avant ou après une autre écriture ;
- on ne peut pas déplacer une écriture ou une lecture avant ou après une instruction atomique, ainsi que quelques instructions supplémentaires (celles qui accèdent aux périphériques ou aux entrées-sorties, notamment) ;
- des lectures peuvent être déplacées avant des écritures, si ces écritures et la lecture ne se font pas au même endroit, à la même adresse.
Dans cette liste, j'ai mentionné le fait que les écritures en mémoire peuvent changer dans certains cas exceptionnels. Ces cas exceptionnels sont les écritures effectuées par les instructions de gestion de tableaux et de chaînes de caractères, ainsi que certaines instructions SSE. Ces instructions SSE sont les instructions qui permettent d'écrire des données sans passer par le cache, mentionnées il y a quelques chapitres. Ce sont donc les instructions MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, MOVNTPD. Mais ce ne sont pas les seules : le x86 possède quelques instructions permettant de travailler directement sur des chaines de caractères ou des tableaux : ce sont les instructions REPMOVSD, REPSCACB, et bien d'autres encore. Eh bien sachez que les écritures effectuées dans ces instructions peuvent se faire dans un désordre complet (ou presque).