Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 11
Types de communications, topologies de connexion, SIMD, MIMD
Année 2002-2003

Suite N°4...

11.7 QUESTIONS DE COHÉRENCE

11.7.1 La question

L'écriture de programmes corrects et efficaces pour les systèmes à mémoire commune nécessite, au delà la partie proprement algorithmique d'application, de spécifier la sémantique des mémoires, grossièrement leur comportement. Comme il s'agit au fond de cohérence, on la nomme modèle de cohérence.

Deux exemples de comportement :

L'emploi d'un tampon d'écriture.

On utilise un tampon de stockage intermédiaire des résultats à écrire en mémoire pour éviter l'attente de l'écriture. La cohérence exige la vérification de la présence de la donnée dans la tampon pour chaque lecture. C'est relativement facile dans un monoprocesseur mais pas dans un multiprocesseur.

Les imbrications.

Avec deux processeurs seulement et un bus unique, l'ordre de prise de commande du bus peut induire des délais différents.
Soient deux processus P1 et P2, P1 écrit A puis B, P2 lit A puis B.
La séquence réelle peut être :
P1 écrit A,
P2 fait les deux lectures, il lit donc une version de B qui n'est pas à jour.

Cette imbrication non maîtrisée est encore plus probable pour des mémoires gérées en mode EDO qui réservent le bus.

L'emploi de caches propres à chaque processeur rend la situation plus complexe car la même donnée peut être en plusieurs endroits et en plusieurs états. Considérons la séquence d'évènements qui suit où A et B sont deux processeurs et x une variable.

A lit x, causant une défaut de cache, x = 45 est chargé dabs son cache.
B lit x, causant une défaut de cache, x = 45 est chargé dabs son cache.
A écrit 12 dans la variable x sans mettre à jour la mémoire.
B lit x de façon réussie dans son cache, il obtient la valeur 45.
A vide x de son cache, il écrit 12 en mémoire.
B lit x de façon réussie dans son cache, il obtient toujours la valeur 45.

La définition de Lamport [LAM79] utilise la référence au modèle séquentiel. Elle dit explicitement ce que le modèle de Neumann contient implicitement. Elle est très proche de la cohérence intuitive.
 

Un multiprocesseur possède la cohérence séquentielle si : le résultat de toute exécution est le même que si les opérations de tous les processeurs avaient été faites dans un ordre total; les opérations dans chaque processeurs sont faites dans l'ordre où elles sont dans le programme.

Il s'agit bien d'une définition et non d'une prescription opératoire. Selon la façon dont elle est obtenue, elle peut interdire certaines optimisations et réduire d'autant l'intérêt du multiprocesseur. C'est pourquoi beaucoup de multiprocesseurs l'appliquent sous une forme atténuée qui rend la situation encore moins simple.

Les effets

Le modèle de cohérence, intermédiaire entre le programmeur et le système, a trois effets :

• sur la programmation en ce que le programmeur doit en tenir compte pour établir que son programme est correct;
• sur les performances du système en ce qu'il détermine en partie les possibilités d'optimisation;
• sur la portabilité des programmes dans la mesure où les modèles diffèrent d'une machine à une autre et que à modèle différent, programme différent.

• le maintien de l'ordre du programme par rapport aux opérations des processeurs;
• le maintien d'un ordre unique entre les groupes d'opérations des différents processeurs.

• à mettre la mémoire au centre du dispositif;
• à connecter à la mémoire chaque processeur successivement de telle sorte que les processus qu'ils portent s'exécutent
• entre eux dans l'ordre où ils ont été prévus;
• chacun dans son ordre interne.

Comment obtenir cette cohérence, il existe plusieurs modèles.

Le modèle le plus contraignant consiste en ce que :

• l'opération d'écriture en mémoire doit être faite et achevée avant de faire l'opération qui suit dans l'ordre du programme;
• une écriture est considérée comme faite après réception d'un accusé venant de la mémoire;
• l'écriture est considérée comme achevée après réception des accusés de tous les autres caches en réponse au signal qui invalide toutes les autres copies du même item;
• une valeur n'est lue qu'après la fin des invalidations et des mises à jour;
• dans les systèmes à caches les écritures sont ordonnées de telle sorte que les écritures en un même lieu sont vues dans le même ordre par tous les processeurs;
• l'emploi de registres de stockage temporaire est particulièrement surveillé. L'idéal serait de n'employer qu'un seul accumulateur.

L'ordre d'exécution du programme. On distingue différentes façons de procéder relatives à l'ordre entre une écriture et une lecture suivante, entre deux écritures, et enfin entre une lecture et les lectures ou écritures suivantes. Dans tous les cas, bien sur ces opérations portent sur des adresses différentes.

L'atomicité de l'écriture. Les distinctions sont fondées sur la manière dont le modèle autorise une lecture avant que toutes les autres copies aient été soit invalidées soit modifiées, c'est-à-dire avant que l'écriture soit visible de tous les autres processeurs.

En résumé, on peut avoir trois niveaux de cohérence :

• le niveau haut, les opérations d'écriture sont visibles dans le même ordre par tous les processeurs. Les écritures simultanées sont interdites. Les performances diminuées;
• le niveau moyen, l'ordre des écritures d'un processeur est visible de façon identique par tous les autres processeurs. L'ordre des écritures peut être différent selon le processeur qui écrit. Des incohérences peuvent apparaître à l'exécution;
• le niveau faible, seuls les accès à un même emplacement de mémoire sont ordonnés. La lecture d'un emplacement de mémoire fournit ainsi la valeur la plus récemment écrite. Les écritures à des emplacements différents peuvent apparaître selon des ordres différents à des processeurs distincts. Il n'y a plus de synchronisation entre les différents processeurs.

11.7.2 Les solutions et les moyens

Quel que soit le modèle de mémoire, les mémoires et les caches propres aux autres processeurs doivent être à jour. En pratique cela signifie que :

• toute écriture sera visible avec plus ou moins de retard et suppose que l'écriture et la lecture peuvent être séparées dans le temps;
• les écritures successives d'un même item sont vues dans l'ordre où elles ont été émises et seule la dernière écriture est disponible.

Il faut :

• connaître l'existence et l'emplacement des copies;
• décider du processeur qui seul a le droit d'écriture à un moment donné.

• Supprimer ou rendre inutilisable l'ancienne valeur dans chaque cache où elle se trouve, c'est l'invalidation sur écriture. Si un processeur qui l'avait en cache en fait une lecture, il y aura échec et perte d'efficacité. Attention : ceci ne vaut que pour des caches. On n'invalide pas les contenus de mémoires locales non communes. Cette politique est aussi nommée protocole de Berkeley.
• Remplacer la valeur ancienne par la nouvelle partout où elle figure, on la nomme diffusion des écritures, ce peut être fait dans les caches, c'est fait dans les mémoires locales.

• l'hétérogénéité des supports : caches et mémoire;
• l'empilement des supports en plusieurs niveaux de caches;
• l'hétérogénéité des unités de données accessibles : pages en mémoire, blocs différents d'un cache à un autre
• si la taille du bloc est petite, le nombre des échanges sera grand;
• si la taille du bloc est grande, le volume des échanges unitaires sera grand et l'on pourra observer un effet de ping-pong (thrashing) par invalidation : Soient deux processeurs A et B et leurs caches C(A) et C(B). Une ligne de cache L est présente dans C(A) et dans C(B). Elle contient au moins deux données x et y. A écrit x, ce qui invalide L dans C(B), B écrit y, il y a rechargement de L dans C(B) et invalidation de L dans C(A);

• Les implications en volume et en temps qui doivent être maîtrisées. Dans tous les cas, connaître l'existence des copies multiples doit être noté en données (ce qui occupe de l'espace), ces données doivent être lues à chaque écriture (ce qui apporte un délai d'attente) et les mises à jour, invalidation ou pas, doivent être faites (ce qui augmente le trafic).

Il existe divers moyens logiciels attachés au système d'exploitation ou au compilateur, nous n'en parlons pas. Les moyens proprement architecturaux sont le furet et le répertoire.

Le furet dit aussi espion

C'est un dispositif intégré dans chaque contrôleur de cache. On tourne ici le pré requis de connaître les emplacements des copies. Le support de chaque copie pourvoit à l'identification. Le contrôleur du cache dans lequel se produit une transaction qui pourrait produire une incohérence le signale à tous les autres caches. Il y a deux types de telles transactions :

• le défaut de lecture parce qu'il provoquera le chargement d'un bloc;
• l'écriture dans le cache.

• l'invalidation d'un bloc local;
• l'interception d'une écriture en mémoire et la mise à jour de son bloc.

Cette technique est simple à définir, complexe à mettre en œuvre par les ressources matérielles qu'elle nécessite, consommatrice de temps de transport et génératrice de saturation du bus. Le rôle de l'arbitre du bus est important en ce qu'il attribue le bus aux requêtes.

Exemple : dans la machine Firefly de DEC, les informations données par le furet sont utilisées pour une politique mixte, compromis entre la performance et le maintien de la cohérence, dont l'intérêt est de moins utiliser le bus :

. la mise à jour des données non communes est retardée;
. la mise à jour immédiate des données communes est faite par diffusion des écritures.

On trouvera le détail de cet algorithme dans [GRE96].

Le répertoire

On revient au pré requis de connaissance des emplacements des copies. Les indications de présence des copies dans un ou plusieurs emplacements accessibles à tous sont stockées. Ce ou ces emplacements et leur contenu constituent le répertoire.

Le répertoire entretient l'inventaire de la présence et de l'état de toutes les lignes de données dans tous les caches. On peut dire qu'il est un résumé de tous les caches. La diffusion générale est alors inutile. Les mises à jour sont transmises aux seuls caches qui contiennent la donnée en cause. Le gain est double. D'une part le réseau de processeurs peut être hétérogène, d'autre part les volumes échangés sont moindres car la transmission n'est faite que si elle est nécessaire. Toutefois, on ne gagne rien en complexité de matériel car les solutions logicielles sont inefficaces et les réalisations matérielles sont aussi coûteuses que celles de furets. On dispose de plus de latitude pour augmenter le nombre de processeurs mais l'encombrement des accès au répertoire intervient alors.

Mécanisme du répertoire

Une entrée est créée dans le répertoire dès qu'une ligne (bloc en mémoire) est présente dans un cache au moins. Elle contient :

• la référence de la ligne;
• sa présence ou absence dans chaque cache;
• son état : privé, commun, modifié, etc. Cet état est associé à la mémoire, au bloc ou au cache, selon que le répertoire est central ou distribué.

Le répertoire existe sous deux formes :

Le répertoire central et le protocole centralisé.
Le répertoire est unique. Le traitement est long, du fait de l'accès au répertoire et de la lecture éventuelle de la copie dans le cache qui contient la valeur la plus récente. Quand les caches sont groupés en sous ensembles, on utilise parfois des sous répertoires.

Le répertoire distribué
Les données de répertoire sont réparties dans les caches. Chacun contient les informations relatives à ses propres lignes et d'autres informations selon le mécanisme de liaison entre les caches.

11.7.3 Une norme

La norme ANSI/IEEE 1596 définit le protocole d'un répertoire centralisé à liste doublement chaînée (avant et arrière). Chaque entrée a trois pointeurs, un vers l'entrée précédente, un vers l'entrée suivante dans la liste et un vers le dernier processeur cause de modification. Cette technique est bien adaptée à un grand réseau extensible d'interconnexion.

11.7.4 Une pratique

La description des états des lignes a fait l'objet d'un accord implicite quel que soit le protocole de manipulation. Cette description est connu sous l'acronyme MEPI (MESI en anglo-saxon) :

Modifié (modified), la ligne a été modifiée;
Exclusif (exclusive), ce cache contient la seule copie existant de la donnée. La mémoire est valide;
Partagé c'est-à-dire en commun (shared), une copie de cette ligne existe dans au moins un autre cache, la copie en mémoire est invalide;
Invalide (invalid), la ligne dans le cache est invalide.

Exemple de graphe d'état utilisant MEPI :

Deux autres protocoles répandus existent nommés Illinois et Berkeley.

11.7.5 Un avertissement

Le lecteur aura remarqué que dans tous les développements précédents il n'a été question que de mémoire et de caches. Les questions de cohérence portent sur ces éléments. En toute rigueur, les moyens décrits garantissent la cohérence des contenus de ces composants de l'ordinateur.

On se rappelle les trois modèles principaux de fonctionnement selon la classification par opérandes :

• registre à registre;
• registre à mémoire;
• mémoire à mémoire.

Cette situation peut être critique pour les processeurs RISC qui ont un très grand nombre de registres utilisés comme blocs notes pour éviter des lectures et des écritures.