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 ont alors vu le jour pour rendre l'usage de plusieurs processeurs plus adéquat.
Une première solution consiste à placer plusieurs processeurs sur la même carte mère, ce qui donne un ordinateur multi-processeurs. Au lieu de dupliquer des ordinateurs, on duplique simplement les 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.
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 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. 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 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.
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 entraîner 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.
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 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 voire 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œurs 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.
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 de comparaison 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 cache 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. C'est un avantage, mais cela 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 coeur, 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.
Le partage des caches adapté à une hiérarchie de caches.
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 L3 est presque tout le temps un cache partagé, tandis que le L1 n'est jamais partagé ! 
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 le cache L3, 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, voire partagé entre plusieurs coeurs mais pas à tous. En effet, 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.
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.
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.
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.
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 protocoles de cohérence des caches : généralités.
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 ?
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.
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.
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 :
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".
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. 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.
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 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.
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 :
On peut aussi citer le protocole MOESI, un protocole MESI auquel on a jouté l'état O.
L'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 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.
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").
Les instructions atomiques.
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 :
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.
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.
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.
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. À 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.
Le "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. 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.
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.
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, différents modèles de consistance mémoire. Ceux-ci sont décrits dans le tableau ci-dessous.
Les "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 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.
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.
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 :
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 :
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).