Cohérence et synchronisation du cache

Dans ce chapitre, nous discuterons des protocoles de cohérence du cache pour faire face aux problèmes d'incohérence multicache.

Le problème de cohérence du cache

Dans un système multiprocesseur, une incohérence des données peut se produire entre des niveaux adjacents ou au sein du même niveau de la hiérarchie de mémoire. Par exemple, le cache et la mémoire principale peuvent avoir des copies incohérentes du même objet.

Comme plusieurs processeurs fonctionnent en parallèle, et indépendamment plusieurs caches peuvent posséder différentes copies du même bloc de mémoire, cela crée cache coherence problem. Cache coherence schemes aider à éviter ce problème en maintenant un état uniforme pour chaque bloc de données mis en cache.

Soit X un élément de données partagées qui a été référencé par deux processeurs, P1 et P2. Au début, trois copies de X sont cohérentes. Si le processeur P1 écrit une nouvelle donnée X1 dans le cache, en utilisantwrite-through policy, la même copie sera immédiatement écrite dans la mémoire partagée. Dans ce cas, une incohérence se produit entre la mémoire cache et la mémoire principale. Lorsqu'unwrite-back policy est utilisé, la mémoire principale sera mise à jour lorsque les données modifiées dans le cache sont remplacées ou invalides.

En général, il existe trois sources de problème d'incohérence -

• Partage de données inscriptibles
• Migration de processus
• Activité d'E / S

Protocoles de bus Snoopy

Les protocoles Snoopy assurent la cohérence des données entre la mémoire cache et la mémoire partagée via un système de mémoire basé sur le bus. Write-invalidate et write-update les politiques sont utilisées pour maintenir la cohérence du cache.

Dans ce cas, nous avons trois processeurs P1, P2 et P3 ayant une copie cohérente de l'élément de données «X» dans leur mémoire cache locale et dans la mémoire partagée (Figure-a). Le processeur P1 écrit X1 dans sa mémoire cache en utilisantwrite-invalidate protocol. Ainsi, toutes les autres copies sont invalidées via le bus. Il est noté «I» (Figure-b). Les blocs invalides sont également appelésdirty, c'est-à-dire qu'ils ne doivent pas être utilisés. lewrite-update protocolmet à jour toutes les copies de cache via le bus. En utilisantwrite back cache, la copie mémoire est également mise à jour (Figure-c).

Événements et actions de cache

Les événements et actions suivants se produisent lors de l'exécution des commandes d'accès à la mémoire et d'invalidation -

• Read-miss- Lorsqu'un processeur veut lire un bloc et qu'il ne se trouve pas dans le cache, une lecture manquée se produit. Cela initie unbus-readopération. S'il n'y a pas de copie sale, la mémoire principale qui a une copie cohérente fournit une copie à la mémoire cache demandeuse. Si une copie sale existe dans une mémoire cache distante, ce cache restreindra la mémoire principale et enverra une copie à la mémoire cache demandeuse. Dans les deux cas, la copie du cache entrera dans l'état valide après un échec de lecture.

• Write-hit - Si la copie est sale ou reservedstate, l'écriture se fait localement et le nouvel état est sale. Si le nouvel état est valide, la commande d’invalidation d’écriture est diffusée à tous les caches, annulant leurs copies. Lorsque la mémoire partagée est écrite, l'état résultant est réservé après cette première écriture.

• Write-miss- Si un processeur ne parvient pas à écrire dans la mémoire cache locale, la copie doit provenir soit de la mémoire principale, soit d'une mémoire cache distante avec un bloc sale. Cela se fait en envoyant unread-invalidatecommande, qui invalidera toutes les copies de cache. Ensuite, la copie locale est mise à jour avec l'état sale.

• Read-hit - La lecture-hit est toujours effectuée dans la mémoire cache locale sans provoquer de transition d'état ni utiliser le bus snoopy pour l'invalidation.

• Block replacement- Lorsqu'une copie est sale, elle doit être réécrite dans la mémoire principale par la méthode de remplacement de bloc. Cependant, lorsque la copie est dans un état valide ou réservé ou invalide, aucun remplacement n'aura lieu.

Protocoles basés sur l'annuaire

En utilisant un réseau à plusieurs étages pour construire un grand multiprocesseur avec des centaines de processeurs, les protocoles de cache snoopy doivent être modifiés pour s'adapter aux capacités du réseau. La diffusion étant très coûteuse à réaliser dans un réseau à plusieurs étages, les commandes de cohérence ne sont envoyées qu'aux caches qui conservent une copie du bloc. C'est la raison du développement de protocoles basés sur des répertoires pour les multiprocesseurs connectés au réseau.

Dans un système de protocoles basé sur un répertoire, les données à partager sont placées dans un répertoire commun qui maintient la cohérence entre les caches. Ici, le répertoire agit comme un filtre où les processeurs demandent l'autorisation de charger une entrée de la mémoire primaire vers sa mémoire cache. Si une entrée est modifiée, le répertoire la met à jour ou invalide les autres caches avec cette entrée.

Mécanismes de synchronisation matérielle

La synchronisation est une forme particulière de communication où, au lieu du contrôle des données, des informations sont échangées entre des processus communicants résidant dans le même processeur ou dans des processeurs différents.

Les systèmes multiprocesseurs utilisent des mécanismes matériels pour mettre en œuvre des opérations de synchronisation de bas niveau. La plupart des multiprocesseurs ont des mécanismes matériels pour imposer des opérations atomiques telles que des opérations de lecture de mémoire, d'écriture ou de lecture-modification-écriture pour implémenter certaines primitives de synchronisation. Outre les opérations de mémoire atomique, certaines interruptions interprocesseurs sont également utilisées à des fins de synchronisation.

Cohérence du cache dans les machines à mémoire partagée

Le maintien de la cohérence du cache est un problème dans un système multiprocesseur lorsque les processeurs contiennent de la mémoire cache locale. L'incohérence des données entre les différents caches se produit facilement dans ce système.

Les principaux domaines de préoccupation sont:

• Partage de données inscriptibles
• Migration de processus
• Activité d'E / S

Partage de données inscriptibles

Lorsque deux processeurs (P1 et P2) ont le même élément de données (X) dans leurs caches locaux et qu'un processus (P1) écrit dans l'élément de données (X), comme les caches sont le cache local en écriture de P1, la mémoire principale est également mis à jour. Maintenant, lorsque P2 essaie de lire l'élément de données (X), il ne trouve pas X car l'élément de données dans le cache de P2 est devenu obsolète.

Migration de processus

Dans la première étape, le cache de P1 a l'élément de données X, tandis que P2 n'a rien. Un processus sur P2 écrit d'abord sur X puis migre vers P1. Maintenant, le processus commence à lire l'élément de données X, mais comme le processeur P1 a des données obsolètes, le processus ne peut pas les lire. Ainsi, un processus sur P1 écrit dans l'élément de données X puis migre vers P2. Après la migration, un processus sur P2 commence à lire l'élément de données X mais il trouve une version obsolète de X dans la mémoire principale.

Activité d'E / S

Comme illustré sur la figure, un périphérique d'E / S est ajouté au bus dans une architecture multiprocesseur à deux processeurs. Au début, les deux caches contiennent l'élément de données X. Lorsque le périphérique d'E / S reçoit un nouvel élément X, il stocke le nouvel élément directement dans la mémoire principale. Maintenant, lorsque P1 ou P2 (supposons que P1) essaie de lire l'élément X, il obtient une copie obsolète. Ainsi, P1 écrit dans l'élément X. Maintenant, si le périphérique d'E / S tente de transmettre X, il obtient une copie obsolète.

Accès mémoire uniforme (UMA)

L'architecture UMA (Uniform Memory Access) signifie que la mémoire partagée est la même pour tous les processeurs du système. Les classes populaires de machines UMA, couramment utilisées pour les serveurs (de fichiers), sont les multiprocesseurs symétriques (SMP). Dans un SMP, toutes les ressources système telles que la mémoire, les disques, les autres périphériques d'E / S, etc. sont accessibles par les processeurs de manière uniforme.

Accès mémoire non uniforme (NUMA)

Dans l'architecture NUMA, il existe plusieurs clusters SMP ayant un réseau interne indirect / partagé, qui sont connectés dans un réseau de transmission de messages évolutif. Ainsi, l'architecture NUMA est une architecture de mémoire distribuée physiquement partagée de manière logique.

Dans une machine NUMA, le contrôleur de cache d'un processeur détermine si une référence mémoire est locale à la mémoire du SMP ou si elle est distante. Pour réduire le nombre d'accès à la mémoire distante, les architectures NUMA appliquent généralement des processeurs de mise en cache qui peuvent mettre en cache les données distantes. Mais lorsque les caches sont impliqués, la cohérence du cache doit être maintenue. Donc, ces systèmes sont également connus sous le nom de CC-NUMA (Cache Coherent NUMA).

Architecture de mémoire cache uniquement (COMA)

Les machines COMA sont similaires aux machines NUMA, à la seule différence que les mémoires principales des machines COMA agissent comme des caches à mappage direct ou à ensembles associatifs. Les blocs de données sont hachés vers un emplacement dans le cache DRAM en fonction de leurs adresses. Les données récupérées à distance sont en fait stockées dans la mémoire principale locale. De plus, les blocs de données n'ont pas de domicile fixe, ils peuvent se déplacer librement dans tout le système.

Les architectures COMA ont pour la plupart un réseau de transmission de messages hiérarchique. Un commutateur dans un tel arbre contient un répertoire avec des éléments de données comme sous-arborescence. Étant donné que les données n'ont pas d'emplacement d'origine, elles doivent être explicitement recherchées. Cela signifie qu'un accès distant nécessite un parcours le long des commutateurs dans l'arborescence pour rechercher dans leurs répertoires les données requises. Ainsi, si un commutateur du réseau reçoit plusieurs demandes de son sous-arbre pour les mêmes données, il les combine en une seule demande qui est envoyée au parent du commutateur. Lorsque les données demandées sont renvoyées, le commutateur en envoie plusieurs copies dans son sous-arbre.

COMA contre CC-NUMA

Voici les différences entre COMA et CC-NUMA.

• COMA a tendance à être plus flexible que CC-NUMA car COMA prend en charge de manière transparente la migration et la réplication des données sans avoir besoin du système d'exploitation.

• Les machines COMA sont coûteuses et complexes à construire car elles nécessitent un matériel de gestion de mémoire non standard et le protocole de cohérence est plus difficile à mettre en œuvre.

• Les accès à distance dans COMA sont souvent plus lents que ceux dans CC-NUMA car le réseau arborescent doit être traversé pour trouver les données.