David Madore's WebLog: Comment les processeurs se partagent la mémoire

Ça fait partie de ces questions dont je me suis souvent dit un jour, j'essaierai de comprendre ça : comment, sur les ordinateurs modernes — dont le moindre PC a maintenant deux ou quatre cœurs travaillant en parallèle —, l'accès à la mémoire est-il présenté aux processeurs ? Quelle est la sémantique des opérations ?

La vision idéale, ce serait de croire que quand un processeur écrit une donnée en mémoire, cette donnée peut instantanément être lue par tous les processeurs (lui-même comme les autres) : autrement dit, si un processeur écrit une valeur v à l'emplacement x à l'instant t et qu'un autre processeur, à un instant t′>t, lit la valeur à cet emplacement x, alors c'est bien v qui sera lue (sauf si une autre écriture a eu lieu entre temps, bien sûr) — c'est la vision bien rassurante d'un monde totalement ordonné par le temps, et on appelle ça le modèle de cohérence stricte (ou strict, parce que c'est peut-être le modèle qui l'est). En réalité, le temps, on ne sait pas vraiment ce que c'est, l'exécution d'une instruction par un processeur est quelque chose qui est étalée sur un long intervalle, donc ça n'a pas vraiment de sens, mais on peut au moins proposer une vision abstraite de la même chose, le modèle de cohérence séquentielle (Lamport, 1979) : la mémoire est dite séquentiellement cohérente par rapport à un système multiprocesseur lorsqu'il existe une façon d'ordonner totalement les instructions exécutées par tous les processeurs de façon cohérente avec l'ordre d'exécution (l'ordre de programme) sur chaque processeur séparément, et de façon que chaque lecture en mémoire (par n'importe quel processeur) renvoie le résultat de la plus récente écriture — pour cet ordre total — qui y a été faite (par n'importe quel processeur, le même ou un autre). Autrement dit, la cohérence séquentielle signifie qu'on peut s'imaginer que les instructions exécutées par les différents processeurs s'exécutent dans un certain ordre global (elles ne sont jamais exactement simultanées, bien sûr), et tout se passe comme si les accès à la mémoire étaient faits par rapport à cette sérialisation. Si on n'a jamais réfléchi à la question, ça peut paraître tellement évident qu'on n'y pense même pas.

Par exemple, si un processeur écrit successivement 1 dans des emplacements mémoire x et y qui valaient initialement 0 (je noterai ça [x]←1; [y]←1) et qu'un autre processeur, pendant ce temps, lit l'emplacement y dans un registre r₁ (je noterai ça r1←[y]) et y trouve la valeur 1, alors nécessairement s'il lit ensuite l'emplacement x il trouvera la valeur 1, n'est-ce pas ? N'est-ce pas ? Cela semble presque évident : quelqu'un écrit x puis y dans cet ordre, et qu'un d'autre arrive à un moment où la valeur de y a été écrite, donc forcément celle de x a dû l'être aussi. Dans le modèle de cohérence séquentielle, ce raisonnement est juste : ([x]←1; [y]←1 | r1←[y]; r2←[x]) — si la barre verticale | indique une exécution en parallèle par deux processeurs en partant d'une mémoire initialisée à zéro — ne peut jamais produire le résultat r1=1, r2=0 (alors que les cas de figure r1=0, r2=0 et r1=1, r2=1 et r1=0, r2=1 sont possibles selon que les lectures ont lieu respectivement complètement avant, complètement après, ou quelque part entre les deux, par rapport aux écritures).

Pourtant, dans un vrai système, les chose ne sont pas forcément aussi simples : les accès de chaque processeur à la mémoire peuvent être réordonnés (et même si c'est fait de façon qui, sur chaque processeur, ne modifie pas sa sémantique locale — c'est-à-dire, si on ne réordonne deux accès à la même cellule que si ce sont deux lectures, cela change la façon dont les autres processeurs verront se dérouler les événements), des données peuvent être rendues visibles plus ou moins vite à d'autres processeurs à cause du fait qu'elles sont détenues par une ligne de cache locale, etc. Certains de ces phénomènes sont rendus invisibles au niveau sémantique, c'est-à-dire que le programme ne peut pas s'apercevoir qu'ils se produisent : on espère en tout cas que c'est le cas sur un système à un seul processeur (on peut réordonner lectures et écritures, mais doit maintenir l'illusion qu'elles se déroulent exactement dans l'ordre où elles sont programmées). Mais sur un système multiprocesseur, on va vraiment pouvoir exhiber des problèmes, où par problèmes j'entends des différences de comportement par rapport au modèle de cohérence séquentielle.

Un exemple de problème concevable est celui que je viens de donner : [x]←1; [y]←1 | 1←[y]; 0←[x] (cette fois je ne note pas les registres, car on se moque bien de ce qu'ils sont, donc j'écris juste 1←[y] pour dire que le processeur a lu 1 depuis y), autrement dit, qu'un processeur écrive dans des emplacements mémoire x et y dans cet ordre, et qu'un autre voie la valeur écrite dans y alors qu'il ne voit pas encore la valeur écrite dans x ; ceci peut effectivement se produire sur certaines familles de processeurs : par exemple, il est réellement possible sur les PowerPC, les Alpha et les Itanium, et il est autorisé par certains des modèles mémoires des Sparc (PSO et RMO, même si le modèle obligatoire, TSO, n'admet pas ce comportement). Sur le modèle des Intel x86, ([x]←1; [y]←1 | 1←[y]; 0←[x]) est garanti ne pas se produire — le modèle Intel est assez strict et relativement proche de la cohérence séquentielle ; mais même sur ce modèle, des problèmes différents peuvent se produire : par exemple, ([x]←1; 0←[y] | [y]←1; 0←[x]) est possible sur n'importe quel système multiprocesseur moderne (ou même pas moderne), et il contredit également la séquentialité (si le premier processeur voit 0 dans y, avec la cohérence séquentielle ça implique que l'écriture de 1 dans y par l'autre processeur n'a pas été faite, donc la lecture de x par lui doit être aussi postérieure, et elle doit nécessairement renvoyer 1 et pas 0).

Comme on le voit par mes deux exemples précédents, il y a un certain nombre de sortes de problèmes différentes. Dans un espoir de les classifier, on peut imposer des garanties pour éviter les problèmes, c'est-à-dire, des règles qui spécifient la façon dont, essentiellement, les processeurs voient chacun les écritures des autres : ce sont les modèles de cohérence mémoire, plus ou moins stricts (i.e., proches de la cohérence séquentielle). Et c'est là que ça devient compliqué, et un peu confus dans mon esprit : parce que toutes sortes de modèles de cohérence ont été définis dans la littérature, avec malheureusement des notations ou des approches très différentes et, pire, parfois un même terme qui recouvre des notions différentes selon l'auteur (ce qui donne des affirmations en apparence contradictoires[#]) — on ne s'y retrouve pas du tout.

Je peux quand même essayer de décrire ce que j'ai compris (attention, ce qui suit devient ultra-technique). Il s'agit, donc, de modèles qui offrent des garanties intermédiaires entre la cohérence séquentielle (la plus forte) et la cohérence locale (Bataller & Bernabéu, 1997), très faible. Cette cohérence locale demande seulement que chaque processeur voie ses propres écritures se dérouler dans l'ordre où il les a exécutées, les écritures faites par les autres processeurs pouvant intervenir, de son point de vue, dans n'importe quel ordre (a priori variable selon le processeur observateur q et le processeur écrivant p ; notez quand même qu'on n'autorise pas à une écriture par un processeur p d'être vue plusieurs fois par un autre processeur q, donc ce n'est toujours pas la notion la plus faible imaginable) : si on veut, on peut s'imaginer que chaque processeur a une copie locale de la mémoire, sur laquelle il effectue immédiatement ses opérations, et quand il fait une écriture il la signale aux autres processeurs pour qu'elle soit aussi exécutée dans leur copie de la mémoire, mais ce message peut prendre un temps quelconque à arriver à chaque autre processeur, les messages peuvent se croiser, ils peuvent arriver dans des ordres différents pour un processeur et pour un autre, etc. : essentiellement rien n'est garanti (si ce n'est qu'il n'y a aura pas de duplication des messages).

À peine plus forte que la cohérence locale, on a la cohérence lente (Hutto & Ahamad, 1990), qui spécifie que, en outre, pour chaque cellule mémoire x donnée et chaque processeur p observé, chaque processeur observateur q voit les écritures vers x par p se dérouler dans l'ordre dans lequel elles ont été programmées par p (en revanche, on ne fait pas d'hypothèse sur l'entrelacement de ces ordres si on fait varier x ou p, ni sur la différence de ces entrelacements si on fait varier q) : dans mon modèle par messages, cela signifie que plusieurs messages d'un même processeur p à un même processeur q et concernant une même cellule x ne peuvent pas se croiser. La cohérence de cache[#2] (Goodman, 1989), est encore un chouïa plus forte que la cohérence lente (et a fortiori que la cohérence locale), et elle exige que pour chaque cellule mémoire x tous les processeurs voient les écritures vers x se dérouler dans le même ordre (ordre qui doit être cohérent avec l'ordre programmé par n'importe quel processeur p qui écrirait sur cette cellule), mais sans faire d'hypothèse sur la façon dont ces ordres s'entrelacent entre cellules différentes. La cohérence PRAM (Lipton & Sandberg, 1988) renforce la cohérence lente de façon à peu près orthogonale à la cohérence de cache en demandant, cette fois, que chaque processeur q voie les écritures vers l'ensemble de la mémoire effectués par chaque processeur p dans l'ordre dans lequel elles ont été programmées par p, mais sans faire d'hypothèse sur la façon dont ces ordres s'entrelacent entre des p différents : là on commence à atteindre des conditions qui ne sont plus vérifiées sur les processeurs réels. La cohérence de processeur au sens de Goodman (Goodman, op. cit.) demande en gros qu'on ait à la fois cohérence de cache et cohérence PRAM, même si on peut faire des petites variations autour de la question selon qu'on demande que les ordres sur les écritures sur les cellules mémoire x et les ordres sur les écritures par les processeurs p doivent ou non s'entrelacer de la même façon sur chaque processeur q — il faut admettre que c'est un peu de l'enculage de mouches. La cohérence causale (Ahamad &al, 1991, cf. par exemple Ahamad &al, 1994), qui renforce la cohérence PRAM mais toujours orthogonalement à la cohérence de cache, est un petit peu fastidieuse à définir, mais elle demande quelque chose de très logique et raisonnable : en gros, si un processeur voit une écriture w en mémoire, alors il voit aussi toute écriture qui la précède causalement (i.e., qui pourrait l'avoir influencée) — c'est-à-dire, essentiellement, toute écriture w′ ayant fixé le résultat d'une lecture r ayant précédé l'écriture w en mémoire (et ainsi de suite par transitivité) ; par exemple, si un processeur fait [x]←1 (écriture w′) et qu'un deuxième lit 1←[x] (lecture r) puis fait [y]←1 (écriture w), alors tout processeur qui observe 1←[y] doit aussi observer 1←[x] (il a vu une conséquence possible w de l'écriture w′:[x]←1, donc il doit voir cette écriture elle-même) ; ceci est programmatiquement utile car cela signifie que si un processeur exécute du code comme if (x==1) y←1 alors les autres processeurs verront une vision cohérente du monde. Je crois que je comprends à peu près ces différents modèles, qui sont d'ailleurs assez bien récapitulés dans Steinke & Nutt, 2004 et dans Kawash, 2000 (disponible ici).

Là où ça devient nettement plus confus (pour moi), c'est que si les modèles dont je viens d'esquisser l'idée définissent les choses en termes de vues des instructions d'un processeur par les autres processeurs, il y en a aussi, qui les définissent en termes de réordonnancement des instructions (et là, même si ce sont des conditions plus ou moins orthogonales, le rapport précis avec les notions précédentes n'est pas clair du tout) : cf. Adve & Gharachorloo, 1995 pour une présentation assez synthétique et plus ou moins claire selon cet ordre d'idées, beaucoup moins théorique que les autres papiers que j'ai cités. Par exemple, on peut définir un ordre partiel sur les opérations d'un programme, qui est l'ordre du programme normal sauf qu'une lecture mémoire qui suit une écriture mémoire à un emplacement différent n'est pas (a priori) comparable à elle (elle le sera quand même si entre les deux il y a une instruction qui force l'ordre par transitivité) ; autrement dit, cet ordre permet d'anticiper une lecture en la faisant passer avant des écritures vers des cellules mémoires différentes. Lorsqu'on peut mettre un ordre total sur toutes les opérations écritures de façon que, pour chaque processeur, il y ait moyen d'intercaler ses opérations de lecture de façon à donner une histoire correcte et compatible avec l'ordre que je viens de définir, on dit qu'on a la contrainte de cohérence TSO au sens de Kohli (Kohli &al, 1993). En clair, on permet de réordonner les instructions de tous les processeurs mais seulement en faisant passer des lectures avant des écritures vers des emplacements différents, et on doit arriver comme ça à une sérialisation. Cette cohérence TSO-Kohli est plus forte que la cohérence de cache (tout simplement car on ne permet pas de réordonner les instructions touchant à la même cellule mémoire), mais incomparable à la fois avec la cohérence de processeur au sens de Goodman, avec la cohérence causale, et avec la cohérence PRAM. La « vraie » cohérence TSO (Sun Microsystems, 1991), elle, permet aussi de réordonner deux lectures (depuis des cellules différentes) à condition que la première soit « domestique », c'est-à-dire qu'elle produit le résultat d'une écriture par le même processeur : concrètement, cela signifie qu'un processeur peut voir les résultats de ses propres écritures avant qu'elles soient visibles par les autres (les explications sont dans Kawash, op. cit., §4.2.2). La cohérence PSO (Sun Microsystems, op. cit.) est encore plus faible et permet aussi de réordonner deux écritures (vers des cellules différentes) ; et la cohérence RMO (Sun Microsystems, 1994) permet de réordonner deux accès quelconques sauf quand c'est indispensable pour préserver la sémantique locale (deux accès à la même cellule dont une au moins est une écriture). Mais ces différents ordres partiels — ou règles de réordonnancement — permettent aussi, j'ai l'impression, plutôt que de chercher une sérialisation complète qui les respecte (c'est-à-dire, finalement, donner une version faible de la cohérence séquentielle), de définir des versions faibles des autres systèmes de cohérence que j'ai définis plus haut (cohérence PRAM / cohérence de processeur, et cohérence causale surtout, car a priori pour la cohérence de cache ça ne devrait rien changer vu qu'on ne permet pas de réordonner des écritures vers une même cellule mémoire). Cela devrait, par exemple, recouvrir la cohérence de processeur au sens DASH (Lenoski &al, 1990), qui est subtilement différente de celle de Goodman évoquée plus haut, mais Ahamad &al, 1993 n'est pas d'accord avec moi, et de toute façon (voir ci-dessous) il y a l'air d'avoir des contradictions gênantes dans la littérature. Je ne sais pas trop quoi penser.

Et encore ! Tout ce fourbi ne concerne que les modèles de cohérence à mémoire pure, où les seules instructions sont des accès, en lecture ou en écriture, à la mémoire (et en plus, je considère la mémoire comme un tableau de cellules atomiques : je ne parle pas de la question des accès non alignés, par exemple). Dans les modèles hybrides, il y a, en outre, des instructions de synchronisation, qui permettent d'obtenir des contraintes de cohérence additionnelles que le modèle de base (pur) ne promet pas, ce qui est indispensable si ce modèle de base est trop faible. Hélas, ces instructions sont assez variées et il n'est pas évident de comparer les modèles différents. En pratique, cependant, les processeurs utilisent généralement le modèle des barrières mémoire : dans la description des modèles de cohérence en termes de réordonnancement, la barrière mémoire offre la garantie que les instructions qui la précèdent ne seront pas réordonnées avec celles qui la suivent (éventuellement en se limitant aux instructions d'un certain type : le Sparc (en modèle RMO), par exemple, fournit quinze types de barrières mémoire pour offrir toutes les combinaisons de protection de réordonnancement des lectures avant contre lectures après la barrière, lectures avant contre écritures après, écritures avant contre lectures après, et écritures avant contre écritures après ; l'Alpha ne fournit qu'une barrière générale et une barrière en écriture ; l'Itanium fournit des annotations d'acquisition/libération qui indiquent, plutôt, dans quel sens on peut réordonner par rapport à ces instructions annotées (et aussi une barrière mémoire équivalente à une acquisition+libération). Les détails dépendent au plus haut point du modèle hybride utilisé.

Pour essayer de m'éclaircir les idées, au moins pour les modèles purs (i.e., sans aucune synchronisation), j'ai essayé de dresser un tableau de certains problèmes pouvant apparaître, et de quels modèles purs les autorisent : dans tout ce qui suit, toutes les cellules mémoire valent initialement 0, les lettres indiquent évidemment des cellules différentes, la barre indique la séparation entre processeurs différents (et il n'y a pas d'autre processeur qui tourne sur les cellules concernées), et les points-virgules indiquent l'ordre de programme sur un processeur. Un point (•) dans le tableau indique que la trace d'exécution figurant au début de la ligne est possible (i.e., que le « problème » peut survenir) dans le modèle décrit par la colonne.

	Ktso	Stso	Spso	Srmo	Prda	Caus	Proc	Pram	Cach	Lent	Locl	Ix86
`[x]←1 \| 1←[x]; 0←[x]`				•
`[x]←1; [x]←2 \| 2←[x]; 1←[x]`				•							•
`[x]←1; [y]←1 \| 1←[y]; 0←[x]`			•	•					•	•	•
`[x]←1; [y]←2; [x]←2 \| [y]←1; 0←[x]; 2←[x]; 1←[y]`	•	•	•	•	•				•	•	•	???
`1←[x]; [y]←1 \| 1←[y]; [x]←1`				•	•		•	•	•	•	•
`[x]←1 \| 1←[x]; [y]←1 \| 1←[y]; 0←[x]`				•	•		•	•	•	•	•
`[x]←1; 2←[x] \| [x]←2; 1←[x]`						•		•		•	•
`[x]←1 \| [y]←1 \| 1←[x]; 0←[y] \| 1←[y]; 0←[x]`				•	•	•	•	•	•	•	•
`[x]←1; [y]←2; 1←[y] \| [y]←1; [x]←2; 1←[x]`			•	•	•	•		•	•	•	•
`[x]←1; [z]←1; 0←[y] \| [y]←1; [z]←2; 0←[x]`	•	•	•	•	•	•		•	•	•	•	•
`[x]←1; 1←[x]; 0←[y] \| [y]←1; 1←[y]; 0←[x]`		•	•	•	•	•	•	•	•	•	•	•
`[x]←1; 0←[y] \| [y]←1; 0←[x]`	•	•	•	•	•	•	•	•	•	•	•	•
`[x]←1; [y]←2; 1←[x] \| 1←[x]; [x]←2; [y]←1; 2←[y]`	•	•	•	•	•	•		•	•	•	•	•
`[x]←1; [y]←2; 2←[y]; 1←[x] \| 1←[x]; [x]←2; [y]←1; 2←[y]`		•	•	•	•	•		•	•	•	•	•?

Sigles : Séqn = cohérence séquentielle ; Ktso = cohérence TSO au sens de Kohli ; Stso = cohérence (Sparc) TSO ; Spso = cohérence (Sparc) PSO ; Srmo = cohérence (Sparc) RMO ; Prda = cohérence de processeur au sens DASH (telle que je la comprends dans, par exemple, Adve & Gharachorloo, 1995 : ceci contredit explicitement Ahamad &al, 1990) ; Caus = cohérence causale ; Proc = cohérence de processeur au sens de Goodman ; Pram = cohérence PRAM ; Cach = cohérence de cache ; Lent = cohérence lente ; Locl = cohérence locale ; Ix86 = comportement du Intel x86.

Je n'ai pas mis les cohérences au sens PowerPC, Alpha et Itanium dans le tableau, car pour autant que je les comprends elles doivent coïncider avec la cohérence Sparc RMO (colonne Srmo du tableau) en l'absence de barrières mémoires : par exemple, dans la ligne ([x]←1 | [y]←1 | 1←[x]; 0←[y] | 1←[y]; 0←[x]), le comportement est indiqué comme possible sur Srmo, mais c'est car le modèle permet la permutation des deux lectures — si on place une barrière lecture-contre-lecture entre toutes les instructions de lecture (à l'emplacement des points-virgules, donc), le comportement devient impossible sur Sparc où les écritures sont atomiquement visible aux autres processeurs, alors qu'il reste, je crois, possible sur PowerPC où un processeur peut lire en avance les écritures d'un autre processeur.

[#] Exemple d'incohérence : Ahamad &al, 1990 explique que la cohérence de processeur, que ce soit au sens de Goodman ou au sens DASH, implique la cohérence PRAM ; Kohli &al, 1993 est d'accord avec ce fait, et ajoute, en outre, que la cohérence TSO implique la cohérence de processeur (et donc la cohérence PRAM), ce que Adve & Gharachorloo, 1995 a également l'air de penser ; or Kawash, 2000 non seulement explique que la cohérence TSO au sens du papier de Kohli ci-dessus n'est pas la vraie cohérence TSO, mais par ailleurs donne un contre-exemple incontestable (computation 11, page 71) vérifiant la cohérence TSO dans les deux sens (la « vraie » et celle de Kohli) mais pas la cohérence PRAM. Contradiction : l'informatique disparaît dans un pouf de logique !

[#2] En anglais on peut dire coherence tout seul, parce que le mot que je traduis par cohérence en français est consistency.