Cohérence de la mémoire et cohérence du cache

16

Est-il vrai que la cohérence séquentielle est une propriété plus forte que la cohérence du cache?

Selon

Sorin, Daniel J; Hill, Mark D; Wood, David A: Une introduction à la cohérence de la mémoire et à la cohérence du cache , Morgan et Claypool, 2011

la cohérence séquentielle peut être décrite comme (non formellement):

Le modèle de mémoire de cohérence séquentielle spécifie que le système doit apparaître pour exécuter toutes les charges des threads et les stocker dans tous les emplacements de mémoire dans un ordre total qui respecte l'ordre des programmes de chaque thread. Chaque chargement obtient la valeur du magasin le plus récent de cette commande totale.

En d'autres termes, le système est séquentiellement cohérent, si on donne des événements de mémoire (charges et magasins) de chaque thread, nous pouvons ordonner tous ces événements de telle sorte que: 1) pour chaque thread, l'ordre de ses événements soit préservé, et 2) l'ordre global soit série (toute charge renvoie la dernière valeur stockée).

Maintenant, ils continuent et décrivent la cohérence:

Une définition de la cohérence qui est analogue à la définition de la cohérence séquentielle est qu'un système cohérent doit apparaître pour exécuter toutes les charges des threads et les stocker dans un seul emplacement de mémoire dans un ordre total qui respecte l'ordre des programmes de chaque thread.

En d'autres termes, le système est cohérent, si on donne des événements de mémoire de chaque thread pour chaque emplacement, nous pouvons ordonner des événements pour cet emplacement, tels que: 1) pour chaque thread, l'ordre de ses événements vers cet emplacement est préservé, et 2) pour chaque l'emplacement de la commande est en série.

Enfin, ils soulignent la différence:

Cette définition met en évidence une distinction importante entre cohérence et cohérence : la cohérence est spécifiée sur une base d'emplacement par mémoire, tandis que la cohérence est spécifiée par rapport à tous les emplacements de mémoire.

Il semble donc que la différence est que pour les systèmes cohérents, nous avons besoin d'un ordre total sur tous les événements pour chaque emplacement (donc l'ordre entre les événements pour un emplacement particulier), tandis que pour les systèmes cohérents, l'ordre total devrait être défini sur tous les événements (et donc le la commande est également entre les événements pour différents endroits)?

Est-ce à dire que la cohérence est moins stricte que la cohérence? (ce qui semble amusant!) Y a-t-il des traces cohérentes mais pas cohérentes?

Ayrat
la source
2
Notez que nous n'aimons pas les questions du formulaire "veuillez vérifier ma réponse!". Pouvez-vous ajouter une question plus spécifique? Où pensez-vous que votre écart pourrait être?
Raphael
@ Raphael, tu as raison, et ce n'était pas très bon quand j'écrivais la question. Mais que faire si je ne trouvais pas de réponse sur Internet (sauf de vagues affirmations comme «la cohérence parle d'un bit, ce qui est différent de la cohérence qui parle de tous les bits»), et j'ai donc essayé de trouver une réponse, et quand cela semble pour trouver qu'il n'était pas sûr que ce soit correct. Aurais-je dû poser une question louche? Ou ne répondez pas à la question? :)
Ayrat
@Ayrat J'ai lu la dernière partie de votre question comme une réponse que vous souhaitez vérifier. Si tel est le cas, il devrait y avoir un doute (sinon, pourquoi demander?) Que vous devriez identifier pour les lecteurs. Peut-être que j'ai mal lu?
Raphael
@Raphael 'la dernière partie veut être vérifiée' - oui. 'pourquoi demander?' - le sujet est nouveau et je n'étais pas sûr que la conclusion soit correcte. Je vais essayer d'éviter ce genre de questions à l'avenir et probablement trouver quelqu'un autour pour le vérifier.)
Ayrat

Réponses:

9

Comme vous l'avez souligné, la cohérence est une propriété d'un emplacement de mémoire individuel tandis que la cohérence fait référence à l'ordre d'accès à tous les emplacements de mémoire. La cohérence séquentielle est une propriété strictement plus forte que la cohérence. C'est-à-dire: chaque système qui est séquentiellement cohérent l'est également à chaque emplacement de mémoire. L'inverse n'est pas vrai, une mémoire cohérente à chaque emplacement n'est pas nécessairement séquentielle. En fait, il existe de nombreux multiprocesseurs cohérents en cache où le modèle de mémoire n'est que faiblement cohérent (il existe des cas où différents processeurs observent que les accès à différents emplacements se produisent dans des ordres différents.)

La preuve de la cohérence séquentielle implique la cohérence:

XX

XyX0y0XyXyyX

Cela peut conduire à des résultats surprenants. Par exemple

initially A=B=0
process 1               process 2
store A := 1            load B (gets 1)
store B := 1            load A (gets 0) 

Cette trace est cohérente:

  • A l'ordre est le suivant : proc2 loads A(gets 0),proc1 stores A:=1
  • B l'ordre est le suivant : proc1 stores B:=1,proc2 loads B(gets 1)

Mais ce n'est pas cohérent! Puisque if proc2 load Brenvoie 1, alors proc1 store A := 1déjà arrivé et proc2 load Adevrait également retourner 1.

Logique errante
la source