M2 - Archi3

Cohérence de Cache dans un Système Multiprocesseur

Exercice 1

On considère le code C suivant, qui multiplie par deux les éléments d'un tableau partagé :

// N = 4096 / NB_THREADS

int tab[4096] = { ... }; // Initialisation du tableau
int curr_elem = 0;
int lock = 0;

void process_elem() {
   lock_acquire(&lock);
   tab[curr_elem] *= 2; // instruction (a)
   curr_elem++;
   lock_release(&lock);
}


void process() {
   int i;
   for (i = 0; i < N; i++) {
      process_elem();
   }
}

a - Donner le code assembleur Mips du corps de la fonction process_elem

On s'intéresse au cas où la fonction process_elem est exécutée par 2 processeurs de manière concurrente (N = 2048). On considère par ailleurs les protocoles de cohérence suivants : Write-Through Invalidate (WTI), Write-Through Write-Update (WTU), Write-Back MESI (WB).

Hypothèses :

• Les lignes de cache font 4 mots, et le cache est direct-mapped
• La tableau tab est aligné sur une frontière de ligne de cache
• Le cache est assez grand pour contenir tout le tableau tab et la ligne contenant la variable curr_elem (il n'y a pas de collisions)
• On ignore dans les questions suivantes les accès à la variable lock (on considère qu'ils sont toujours non cachés)
• On ne considère pas la cohérence entre le cache L2 et le niveau supérieur (on suppose par exemple qu'il y a un unique cache L2 et on ne s'intéresse pas à ses miss)

On suppose, pour les 2 questions suivantes, que le processeur 0 effectue d'abord 2048 itérations, puis que le processeur 1 effectue 2048 itérations.

Ci-dessous sont représentés, pour le protocole WTI, les états des lignes de cache et des entrées du directory contenant les variables tab et curr_elem, après l'exécution de l'instruction (a) durant la première itération du processeur 1 :

Cache 0

Etat	mot 0	mot 1	mot 2	mot 3
Valide	tab[0]	tab[1]	tab[2]	tab[3]
Valide	...	...	...	...
Valide	tab[2044]	tab[2045]	tab[2046]	tab[2047]
Valide	curr_elem	...	...	...

Cache 1

Etat	mot 0	mot 1	mot 2	mot 3
Valide	tab[2048]	tab[2049]	tab[2050]	tab[2051]
Valide	curr_elem	...	...	...

Directory

Etat	TAG	Copies
Valide	&tab[0]	0
Valide	...	0
Valide	&tab[2044]	0
Valide	&tab[2048]	1
Valide	curr_elem	0, 1

b - Faire de même pour les protocoles WTU et WB.

c - Donner pour chacun des 3 protocoles, le nombre et la nature des miss (miss, miss dirty, miss clean) et des requêtes de cohérence (invalidation, invalidation RO, write-back) pour les 2 processeurs. Donner en plus pour les protocoles WTI et WTU le nombre d'écritures propagées en mémoire.

On suppose maintenant que les processeurs 0 et 1 effectuent leurs itérations de manière alternative (proc 0, puis proc 1, puis proc 0, etc.).

d - Dessiner, pour les 3 protocoles, le contenu des caches et du directory après le traitement de 4 éléments (2 itérations de chaque processeur)

e - Donner pour chacun des 3 protocoles, le nombre et la nature des miss et des requêtes de cohérence. Donner en plus pour les protocoles WTI et WTU le nombre d'écritures propagées en mémoire.

Remarque : il est recommandé d'expliquer le déroulement d'une itération, accès par accès, notamment pour le WB