Cohérence et synchronisation du cache

Dans ce chapitre, nous aborderons les protocoles de cohérence du cache pour faire face aux problèmes d’incohérence du multicache.

Le problème de cohérence du cache

Dans un système multiprocesseur, l’incohérence des données peut se produire entre des niveaux adjacents ou au sein d’un même niveau de la hiérarchie de la 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 un problème de cohérence de cache. Les schémas de cohérence de cache aident à éviter ce problème en maintenant un état uniforme pour chaque bloc de données mis en cache.

Laissons X être 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 utilisant la politique d’écriture directe, la même copie sera écrite immédiatement 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’une politique de réécriture est utilisée, la mémoire principale sera mise à jour lorsque les données modifiées dans le cache sont remplacées ou invalidées.

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

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

Protocoles de bus Snoopy

Les protocoles Snoopy réalisent la cohérence des données entre la mémoire cache et la mémoire partagée par le biais d’un système de mémoire basé sur un bus. Les politiques d’écriture-invalidation et d’écriture-mise à jour 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 utilisant le protocole write-invalidate. Ainsi, toutes les autres copies sont invalidées via le bus. Elle est désignée par ‘I’ (Figure-b). Les blocs invalidés sont aussi appelés dirty, c’est-à-dire qu’ils ne doivent pas être utilisés. Le protocole write-update met à jour toutes les copies du cache via le bus. En utilisant le cache write-back, la copie de mémoire est également mise à jour (Figure-c).

Événements et actions du 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 –

• Lecture manquée – Lorsqu’un processeur veut lire un bloc et qu’il n’est pas dans le cache, une lecture manquée se produit. Cela déclenche une opération de lecture sur le bus. S’il n’existe pas de copie sale, la mémoire principale qui possède une copie cohérente fournit une copie à l’antémémoire requérante. Si une copie corrompue existe dans une antémémoire distante, cette antémémoire va retenir la mémoire principale et envoyer une copie à l’antémémoire requérante. Dans les deux cas, la copie du cache entrera dans l’état valide après un read miss.

• Write-hit – Si la copie est dans un état sale ou réservé, l’écriture est faite localement et le nouvel état est sale. Si le nouvel état est valide, la commande write-invalidate est diffusée à tous les caches, invalidant leurs copies. Lorsque la mémoire partagée est traversée en écriture, l’état résultant est réservé après cette première écriture.

• Write-miss – Si un processeur échoue à é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. Pour ce faire, on envoie une commande read-invalidate, qui invalide toutes les copies de cache. Ensuite, la copie locale est mise à jour avec l’état sale.

• Lecture – La lecture est toujours effectuée dans la mémoire cache locale sans provoquer une transition d’état ou utiliser le bus snoopy pour l’invalidation.

• Remplacement de bloc – 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 soit dans un état valide ou réservé ou invalide, aucun remplacement n’aura lieu.

Protocoles basés sur les répertoires

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 multi-étages, les commandes de cohérence sont envoyées uniquement aux caches qui conservent une copie du bloc. C’est la raison du développement des protocoles à base de répertoire pour les multiprocesseurs connectés au réseau.

Dans un système de protocoles à base de 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 la permission 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 matériels de synchronisation

La synchronisation est une forme spéciale de communication où, au lieu du contrôle des données, l’information est échangée entre les processus communicants résidant dans le même ou différents processeurs.

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 les opérations de lecture, d’écriture ou de lecture-modification-écriture de la mémoire pour mettre en œuvre certaines primitives de synchronisation. Autres que les opérations atomiques de mémoire, certaines interruptions inter-processeurs sont également utilisées à des fins de synchronisation.

Cache Coherency in Shared Memory Machines

Maintenir la cohérence du cache est un problème dans un système multiprocesseur lorsque les processeurs contiennent une 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é 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 en écriture à travers le cache local de P1, la mémoire principale est également mise à jour. Maintenant, lorsque P2 essaie de lire l’élément de données (X), il ne trouve pas X parce que l’élément de données dans le cache de P2 est devenu périmé.

Migration de processus

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

Activité d’E/S

Comme illustré dans 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 dispositif 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 P1) essaie de lire l’élément X, il obtient une copie périmée. Donc, P1 écrit dans l’élément X. Maintenant, si le dispositif d’E/S essaie de transmettre X, il obtient une copie périmée.

Accès uniforme à la mémoire (UMA)

L’architecture d’accès uniforme à la mémoire (UMA) signifie que la mémoire partagée est la même pour tous les processeurs du système. Les classes populaires de machines UMA, qui sont couramment utilisées pour les serveurs (de fichiers), sont les multiprocesseurs dits symétriques (SMP). Dans un SMP, toutes les ressources du système comme la mémoire, les disques, les autres périphériques d’entrée/sortie, etc. sont accessibles par les processeurs de manière uniforme.

Non-Uniform Memory Access (NUMA)

Dans l’architecture NUMA, il y a plusieurs clusters SMP ayant un réseau interne indirect/partagé, qui sont connectés dans un réseau évolutif de passage de messages. Ainsi, l’architecture NUMA est une architecture de mémoire distribuée physiquement partagée logiquement.

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 des caches sont impliqués, la cohérence du cache doit être maintenue. Ainsi, ces systèmes sont également connus sous le nom de CC-NUMA (Cache Coherent NUMA).

Cache Only Memory Architecture (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 à association de jeux. Les blocs de données sont hachés vers un emplacement dans le cache DRAM en fonction de leurs adresses. Les données qui sont extraites à distance sont en fait stockées dans la mémoire principale locale. De plus, les blocs de données n’ont pas d’emplacement fixe de départ, ils peuvent se déplacer librement dans le système.

Les architectures COMA ont le plus souvent un réseau hiérarchique de passage de messages. Un commutateur dans un tel arbre contient un répertoire avec des éléments de données comme sous-arbre. Les données n’ayant pas d’emplacement d’origine, elles doivent être recherchées explicitement. Cela signifie qu’un accès à distance nécessite une traversée le long des commutateurs de l’arbre pour rechercher les données requises dans leurs répertoires. 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 reviennent, le commutateur en envoie de multiples copies vers le bas de son sous-arbre.

COMA versus CC-NUMA

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

• COMA tend à être plus flexible que CC-NUMA parce que COMA supporte de façon transparente la migration et la réplication des données sans le 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 la 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 puisque le réseau d’arbres doit être traversé pour trouver les données.

.