« Fonctionnement d'un ordinateur/Architectures multiprocesseurs et multicœurs » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
Ligne 89 : Ligne 89 :


[[File:Diagramme d'état informel du protocole MSI.png|centre|vignette|upright=2|Diagramme d'état informel du protocole MSI.]]
[[File:Diagramme d'état informel du protocole MSI.png|centre|vignette|upright=2|Diagramme d'état informel du protocole MSI.]]

[[File:Modified-Shared-Invalid Protokoll.png|centre|vignette|upright=2|Diagramme du protocole MESI. Les abréviations PrRd et PrWr correspondent à des accès mémoire initiés par le processeur associé au cache, respectivement aux lectures et écritures. Les abréviations BusRd et BusRdx et Flush correspondent aux lectures, lectures exclusives ou écritures initiées par d'autres processeurs sur la ligne de cache.]]


===Les protocoles à état Exclusif===
===Les protocoles à état Exclusif===

Version du 10 novembre 2020 à 22:00

Rien ne vaut l'utilisation de plusieurs processeurs pour réellement tirer parti du parallélisme de taches. Les premières tentatives consistaient à relier plusieurs ordinateurs via un réseau local, ou à les placer sur la même carte mère. De nos jours, il est possible de placer plusieurs processeurs sur la même puce : on obtient un processeur multicœur (chaque processeur s’appelle un cœur). Suivant le nombre de cœurs présents dans notre processeur, celui-ci sera appelé un processeur double-coeur (deux cœurs), quadruple-coeur (4 cœurs), octuple-coeur (8 cœurs), etc.

Les différents types de multicœurs

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 processeurs 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, par exemple. Cela s'appelle du multicœurs asymétrique, qui est à opposer au multicœurs symétrique dans lequel on place des processeurs identiques sur la même puce de silicium.

Le multicœurs asymétrique

Le processeur CELL de la console de jeu PS3 est un bon exemple de multicœurs asymétrique. Il intégre un cœur principal POWER PC version 5, qu'on retrouvait autrefois dans les Mac, et 8 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.

Le cluster multithreading

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. 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 entrainer des pertes de performances.

Les interruptions inter-processeurs

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. 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 du X86

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.

Contrôleurs d’interruptions sur systèmes x86 multicœurs.

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

Quand on conçoit un processeur multicœur, il ne faut pas oublier ce qui arrive à la pièce maitresse de tout processeur actuel : le cache ! Il est possible d'utiliser des caches dédiés, à savoir que chaque cœur possède son propre cache, ou bien de partager un cache entre plusieurs cœurs, ce qui donne un cache partagé. Ces deux méthodes ont des inconvénients et des avantages.

Caches dédiés.
Caches partagés.

Les avantages et inconvénients des caches dédiés/partagés

La quantité de mémoire cache que l'on peut placer dans un processeur est limitée par le nombre de transistors. Et le cache prend beaucoup de place, près de la moitié des circuits du processeur. Le principal défaut des architectures à cache dédiés, à savoir des caches individuellement très petits, vient de là. En conséquence, on peut se demander s'il vaut mieux un petit cache pour chaque processeur ou un gros cache partagé. Alors certes, un gros cache partagé sera plus lent qu'un cache dédié plus petits. Mais les caches partagés ont des avantages à faire valoir.

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 à l'autre programme. Par contre, plusieurs programmes peuvent entrer en compétition pour le cache, que ce soit pour y placer des données ou pour les accès mémoire. De plus, les caches partagés ont un temps d'accès nettement plus élevé.

Cache partagé contre cache dédié

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 architectures hybrides

Partage des caches sur un double cœurs.

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. Généralement, on trouve deux à trois caches dans un processeur (multicœurs ou non) : le L1, le L2, et le L3. Le L2 et le L3 sont souvent partagés, tandis que le L1 n'est jamais partagé ! La raison à cela est que 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. Par contre, rien n’empêche de partager les autres caches, comme le L2 ou le L3 sans trop nuire à leur temps d'accès.

On peut décider de partager un cache entre tous les cœurs, voire limiter ce partage à quelques cœurs particuliers pour des raisons de performances. Ainsi, rien n’empêche pour un processeur quad-core d'avoir deux caches L2, chacun partagés avec deux cœurs, et le cache L3 partagé entre tous les cœurs.

Partage des caches sur un processeur multicœur.

La cohérence des caches

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.

Cohérence des caches

Les caches partagés 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.

Cohérence et caches partagés

On voit donc que la cohérence des caches n'est pas automatiquement maintenue avec les caches dédiés. Pour maintenir cette cohérence des caches, on a 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 ? Pour cela, il existe deux solutions : l'espionnage du bus et l'usage de répertoires.

Certains protocoles utilisent un répertoire, une table de correspondance qui mémorise, pour chaque ligne de cache, toutes les informations nécessaires pour maintenir sa cohérence. Ces protocoles sont surtout utilisés sur les architectures distribuées : ils sont en effet difficiles à implémenter sur les machines à mémoire partagée.

Avec l’espionnage du bus, les caches interceptent les écritures sur le bus (qu'elles proviennent ou non des autres processeurs), afin de mettre à jour la ligne de cache ou de la périmer. Avec ces protocoles, chaque ligne de cache contient des bits qui indique si la donnée contenue est à jour ou périmée. Quand on veut lire une donnée, les circuits chargés de lire dans le cache vérifient ces bits. Si ces bits indiquent que la ligne de cache est périmée, le processeur lit les données depuis la RAM ou les autres caches et la ligne de cache est mise à jour. La mise à jour de ces bits de validité a lieu à chaque écriture (y compris les caches des autres cœurs). Les caches sont interconnectés entre eux et échangent des informations pour maintenir la cohérence. Si un cache contient une donnée partagée, il prévient les autres caches quand la donnée est mise à jour. La mise à jour des données périmées peut être automatique ou basée sur une invalidation. Avec la mise à jour sur écriture, les caches sont mis à jour automatiquement le plus tôt possible, avant même toute tentative de lecture. 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 protocoles sans nouveaux états

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.

Cohérence des caches write-through.

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 :

Diagramme d'état du protocole SI.

Les protocoles à état Shared

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.

Diagramme d'état informel du protocole MSI.

Les protocoles à état Exclusif

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. Ces communications sur le bus ne sont pas gratuites et en faire trop peu ralentir fortement notre ordinateur. Pour régler ce problème, on a scindé l'état Shared en deux états : Exclusive si les autres processeurs ne possèdent pas de copie de la donnée, Shared sinon. Avec cette distinction, on peut éviter l'envoi de messages aux autres caches (ou aux circuits chargés de gérer la cohérence des caches) si on écrit dans une donnée marquée Exclusive : on sait que les autres caches ne possèdent pas de copie de la donnée, alors il ne sert à rien de prévenir inutilement. 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.

Diagramme du protocole MESI. Les abréviations PrRd et PrWr correspondent à des accès mémoire initiés par le processeur associé au cache, respectivement aux lectures et écritures. Les abréviations BusRd et BusRdx et Flush correspondent aux lectures, lectures exclusives ou écritures initiées par d'autres processeurs sur la ligne de cache. Autre description du protocole MESI.

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

Les protocoles MESI et MSI ne permettent pas de transférer des données entre les 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 vont répondre en même temps : 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. 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. Seul le processeur qui possède la donnée en Owned va répondre aux demandes de mise à jour (ceux possédant la donnée Shared ne répondant pas à la demande formulée par le processeur demandeur).

Divers protocoles de cohérences des caches utilisent cet état Owned. Le premier d’entre eux est le protocole MOESI, un protocole MESI auquel on a jouté l'état O.

MOESI State Transaction Diagram

Cependant, celui-ci n'est pas le seul. On peut notamment citer le protocole MOSI, une variante du MESI où l'état exclusif est remplacé par l'état O.

Protocole MOSI, transactions initiées par le processeur associé à la ligne de cache. Protocole MOSI, transactions initiées par les autres processeurs.

Lors d'une lecture, le cache va vérifier 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.

Atomicité

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 : dans certaines situations, 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 entre 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. Et si deux processeurs veulent augmenter simultanément cette donnée, on court à la catastrophe. Chaque thread peut être interrompu à n'importe quel moment par un autre processeur qui voudra modifier sa donnée. Les instructions de nos threads s’exécuteront en série, mais le processeur peut parfaitement être dérangé par un autre processeur entre deux instructions. Dans notre exemple, une telle situation est illustrée ci-dessous. On a donc une valeur de départ de 5, qui est augmentée de 1 deux fois, ce qui donne au final 6.

Illustration du résultat de deux opérations concurrentes sur la même variable.
Illustration du résultat de deux opérations concurrentes sur la même variable.

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 qui n'aura pas encore été modifiée par l'autre processeur. Dans notre exemple, un seul thread doit pouvoir manipuler notre compteur à la fois. Et bien sûr, cette réponse peut, et doit se généraliser à presque toutes les autres situations impliquant une donnée partagée. Chaque thread doit donc avoir un accès exclusif à notre donnée partagée, sans qu'aucun autre thread ne puisse manipuler notre donné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 : notre thread est certain qu'aucun autre thread n'ira modifier la donnée qu'il manipule 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.

Voyons la première de ces solutions : l'exclusion mutuelle. Avec celle-ci, on fait en sorte qu'un thread puisse réserver la donnée partagée. Un thread qui veut manipuler cette donnée va donc attendre qu'elle soit libre pour la réserver afin de l'utiliser, et la libérera une fois qu'il en a fini avec elle. Si la donnée est occupée par un thread, tous les autres threads devront attendre leur tour. Pour mettre en œuvre cette réservation/dé-réservation, on va devoir ajouter 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. Ainsi, un thread qui voudra réserver la donnée va d'abord devoir vérifier si ce nombre est à 1 avant de pouvoir réserver sa donnée. Si c'est le cas, il réservera la donnée en passant ce nombre à 0. Si la donnée est réservée par un autre thread, il devra tout simplement attendre son tour. On a alors créé ce qu'on appelle un verrou d'exclusion mutuelle, aussi appelé mutex.

Mutex
Mutex

Seul problème : cette vérification et modification du compteur pose problème. Celle-ci 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...

Instructions atomiques

Cette vérification et modification du compteur se fait en plusieurs étapes : une lecture du compteur, puis une écriture si le compteur est à la bonne valeur. Il faudrait que cette lecture et l'é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. Ces instructions peuvent ainsi lire ce 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, en permettant d'effectuer une lecture, suivie d'une écriture en une seule fois. Ces instructions permettent ainsi de créer des sémaphores, des Locks, etc. Généralement, un programmeur n'a pas à devoir manipuler des instructions atomiques lui-même, mais ne fait que manipuler 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. L'instruction atomique va réserver l'accès au bus en configurant un bit du bus mémoire, ou par d'autres mécanismes de synchronisation entre processeurs. Si la donnée est dans le cache, 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. 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.

Comme je l'ai dit plus haut, ces instructions empêchent tout autre processeur d'aller lire ou modifier la donnée qu'elles sont en train de modifier. Ainsi, lors de l’exécution de l'instruction atomique, aucun processeur ne peut aller manipuler la mémoire : notre instruction atomique va alors bloquer la mémoire et en réserver l'accès au bus mémoire rien que pour elle. Cela peut se faire en envoyant un signal sur le bus mémoire, ou pas d'autres mécanismes de synchronisation entre processeurs. Quoi qu’il en soit, le cout de ce blocage de la mémoire est assez lourd : cela peut prendre un sacré bout de temps, ce qui fait que nos instructions atomiques sont lentes. Du moins, c'est le cas si la donnée est en mémoire et que le processeur est un peu stupide. En effet, sur certains processeurs, on peut optimiser le tout dans 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 cout des instructions atomiques est alors fortement amorti.

Instructions LL/SC

Une autre technique de synchronisation est basée sur deux instructions : Load-Link et Store-Conditional. L'instruction Load-Link va lire 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.

Mémoire Transactionnelle Matérielle

Pour résoudre les différents problèmes posés par les verrous d'exclusion mutuelle, les chercheurs ont inventé la mémoire transactionnelle. 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 notre donnée et reste 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 rependre depuis le début : les changements effectués par la transaction ne seront pas pris en compte.

Cette mémoire transactionnelle peut être implantée en matériel par diverses techniques. Avec ces techniques, les écritures dans le cache ne sont pas propagées tant que la transaction ne termine pas correctement. Et 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. De plus, les changements effectués par la transaction sur les registres doivent être annulés si celle-ci échoue : on peut sauvegarder une copie des registres du processeur au démarrage de la transaction, ou annuler les changements effectués par la transaction (ROB ou autre méthode capable de gérer les interruptions précises).

Il existe plusieurs manières d'implémenter la mémoire transactionnelle matérielle. La plus simple utilise un cache dédié aux transactions : le cache transactionnel. A 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 solution, utilisée sur le processeur Blue gene d'IBM, consiste à avoir plusieurs exemplaires d'une donnée dans le cache. 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.

Speculative Lock Elision

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. Au lieu de devoir mettre un verrou et de réserver notre donnée juste au cas où, on peut agir d'une façon un peu plus optimiste. Rien n’empêche de transformer nos instructions atomiques servant pour les réservations en instructions permettant de démarrer des transactions. Bien évidemment, les instructions atomiques servant à libérer la donnée partagée vont marquer la fin de notre transaction. Ce mécanisme tente donc de se passer des instructions atomiques en les transformant 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. A 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. A 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, au lieu de les interpréter comme des débuts e transactions.

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 efficacité, certains processeurs cherchent parfois à é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 notre premier 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

Autre exemple, on peut citer les processeurs Intel récents. Je pense notamment aux processeurs basés sur l’architecture Haswell. Au alentour de mars 2013, de nouveaux processeurs Intel sortiront sur le marché : ce seront les premiers processeurs grand public qui supporteront la mémoire transactionnelle matérielle. Attardons-nous un peu sur ces processeurs, et sur l'implémentation de la mémoire transactionnelle matérielle de ces processeurs. Sur ces processeurs, deux modes sont disponibles pour la mémoire transactionnelle matérielle : le mode TSX, et le mode HLE.

Le mode TSX correspond simplement à quelques instructions supplémentaires permettant de gérer la mémoire transactionnelle matérielle. On trouve ainsi trois nouvelles instructions : XBEGIN, XEND et XABORT. XBEGIN sert en quelque sorte de top départ : elle sert à démarrer une transaction. Toutes les instructions placées après elles dans l'ordre du programme seront ainsi dans une transaction. Au cas où la transaction échoue, il est intéressant de laisser le programmeur quoi faire. Pour cela, l'instruction XBEGIN permet au programmeur de spécifier une adresse. Cette adresse permet de pointer sur un morceau de code permettant de gérer l'échec de la transaction. En cas d'échec de la transaction, notre processeur va reprendre automatiquement son exécution à cette adresse. Évidemment, si on a de quoi marquer le début d'une transaction, il faut aussi indiquer sa fin. Pour cela, on utilise l'instruction XEND. XABORT quant à elle, va servir à stopper l’exécution d'une transaction : elle sert à faire planter notre transaction si jamais on s’aperçoit d'un problème lors de l’exécution de notre transaction. Lors de la fin d'une transaction, le processeur va automatiquement reprendre à l'adresse indiquée par XBEGIN, et va remmettre le processeur dans l'état dans lequel il était 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. Cela permet de donner des informations au code de gestion d'échec de transaction, qui peut alors gérer la situation plus finement. HLE

Les processeurs Haswall supportent aussi le Lock Elision. Les instructions atomiques peuvent ainsi supporter l’exécution en tant que transaction à une condition : qu'on leur rajoute un préfixe. Le préfixe, pour les instructions x86, correspond simplement à un octet optionnel, placé au début de notre instruction dans la mémoire. Cet octet servira à donner des indications au processeur, qui permettront de modifier le comportement de notre instruction. Par exemple, les processeurs x86 supportent pas mal d'octets de préfixe : LOCK, qui permet de rendre certaines instructions atomiques, ou REPNZE, qui permet de répéter certaines instructions tant qu'une condition est requise. Le fait est que certains préfixes n'ont pas de signification pour certaines instructions : les placer devant ces instructions n'a alors pas de sens. Autrefois, ils étaient totalement ignorés, et le processeur ne tenait pas compte de ces préfixes sans signification. Pour supporter le Lock Elision, ces préfixes sans significations sont réutilisés histoire de dire au processeur : cette instruction atomique doit subir la Lock Elision et doit être tentée en tant que transaction. 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é.

Consistance mémoire

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. Pour que les accès mémoires dans le désordre ne posent pas de problèmes, il existe différentes solutions.

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.

Fences et barrières mémoires

Les processeurs à type No Store Ordering garantissent que les accès à des données partagées se déroulent correctement avec des instructions que doivent utiliser les compilateurs ou les programmeurs : des Memory Barriers, ou Fences. Ce sont des instructions qui vont forcer le processeur à terminer toutes les écritures et/ou lectures qui la précède. Pour plus d'efficacité, certains processeurs possèdent deux Fences : une pour les lectures, et une autre pour les écritures. Certains processeurs utilisent un nombre de Fences plus élevé, et peuvent ainsi avoir des fences dédiées à des cas particuliers.

Fences
Fences

Le placement des fences dans un programme est géré par un subtil équilibre entre programmeur et compilateur. Généralement, un compilateur peut placer ces Fences 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 Fences 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 Fences. 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 Fences explicites, encapsulées dans des bibliothèques ou cachées dans certaines fonctions.

L'exemple du modèle mémoire x86

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 chaines 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).