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

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
mAucun résumé des modifications
mAucun résumé des modifications
Ligne 1 : Ligne 1 :
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 facile à implémenter, elle est cependant assez onéreuse.
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 autre solution consiste à placer plusieurs processeurs sur la même carte mère, ce qui permet de réduire les couts. 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 coutait 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 coutait 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.
Une première solution consiste à placer plusieurs processeurs sur la même carte mère, ce qui permet de réduire les couts. 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 coutait 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 coutait 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-coeur (deux cœurs), quadruple-coeur (4 cœurs), octuple-coeur (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.
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-coeur (deux cœurs), quadruple-coeur (4 cœurs), octuple-coeur (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.

Version du 16 novembre 2021 à 20:05

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 permet de réduire les couts. 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 coutait 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 coutait 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-coeur (deux cœurs), quadruple-coeur (4 cœurs), octuple-coeur (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.

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

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.

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.

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

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

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.

MOESI State Transaction Diagram

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 processuer n'a pas eu le temps de finir son incrémentation qu'un autre en a démarré une nouvelle.

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 pas encore modifiée par lepremier 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.

Mutex.

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 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 cout 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. 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.

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

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 Haswall 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.

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

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.

Fences.

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 :

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