master-segfault

Project maintained by tshikaboom Hosted on GitHub Pages — Theme by mattgraham

Coherence de cache

1. Introduction

Après les protocoles Write-Through et Write-Back

2. Types et dégrés de liberté des protocles de cohérence

  1. Write-Through ou Write-Back

  2. Allocation sur écriture ou non (suite a un miss write). Ces deux points ne sont pas propres a la cohérence.

  3. Espionnage (snoop) ou répertoire (directory)
    • Espionnage: les caches (L1) “voient” passer les requêtes et se mettent a jour tout seuls (Utilisé en général sur le bus)
    • Avec répertoire, un ou plusieurs composants matériels centralisent les informations relatives au copies. (nombres et numéro du cache L1 qui ont une copie + état de la ligne)
    • Utilisé en général sur un NoC (Network On Chip) ou un crossbar
    • Pas nécessairement le cas (ex: scorpio)
  4. Invalidation ou mise à jour: lorsque le controleur du L2 reçoit une écriture sur une ligne qui contient des copies, doit-il envisager des mises à jour avec la nouvelle valeur ou simplement invalider ces copies?
    • Avantage des mises a jour: évite des futurs miss potentiels
    • Avantage des invalidations: évite de générer plein de requêtes de mise a jour (update) vers des copies qui ne sont pas utilisées

En pratique, toutes les combinaisons ne pas possibles/pertinentes.

Exemple:

Note: les protocoles peuvent être plus compliqués que ça, par exemple hierarchiques, hybrides,..

Dans la suite on ne s’interessera qu’aux protocoles à base de directory

Résumé des caractéristiques des protocoles WT et WB.

Write-Through

Write-Back

Schémas des états d’une ligne de cache L1

WTI Non Allocate

WTI non Allocate Schema

WB MSI (Allocate)

WB MSI (Allocate) Schema

WB MESI

WB MESI Schema

3. Specification des protocoles

3.1. Définitions

3.1.2. Spécification de haut-niveau d’un protocole WTI

Cache L1

	Si réception d'une requête d'invalidation:
		Invalider la ligne (si présente)
		Répondre à la requète d'invalidation
	Sinon si reception d'une requête du processeur:
		Si Read:
			Si Hit:
				Repondre au processeur
			Si Miss:
				Envoyer une requiète de type miss vers le L2
				Attendre la réponse puis séléctionner une ligne victime et la remplacer
			          avec la ligne reçue
				Répondre au processeur (ou retour en IDLE)
		Si Write:
			Si Hit:
				Mettre a jour le cache
			Envoyer l'écriture vers la mémoire (la mettre dans le write-buffer)
			Répondre au processeur

Cache L2

	Recevoir une requête d'un cache L1
		Si Read:
			Ajouter le cache L1 à la liste des caches ayant une copie
			Envoyer une réponse avec la ligne
		Si Write:
			Pour chaque L1 ayant une copie: Invalidation (requête)
			Attendre que toutes les réponses soient obtenues
			Mettre a jour la ligne
			Répondre au cache L1

Update (WTU)

Cache L1

	Si réception d'une requête d'update:
		Mettre a jour la ligne
		Répondre à la requète d'invalidation
	Sinon si reception d'une requête du processeur:
		Si Read:
			Si Hit:
				Repondre au processeur
			Si Miss:
				Envoyer une requiète de type miss vers le L2
				Attendre la réponse puis séléctionner une ligne victime et la remplacer
        avec la ligne reçue
				Répondre au processeur (ou retour en IDLE)
		Si Write:
			Si Hit:
				Mettre a jour le cache
			Envoyer l'écriture vers la mémoire (la mettre dans le write-buffer)
			Répondre au processeur

Cache L2

	Recevoir une requête d'un cache L1
		Si Read
			Ajouter le cache L1 à la liste des caches ayant une copie
			Envoyer une réponse avec la ligne
		Si Write
			Pour chaque L1 ayant une copie (sauf l'emetteur): update (requête)
			Attendre que toutes les réponses soient obtenues
			Mettre a jour la ligne
			Répondre au cache L1

3.1.3. Spécification de haut niveau d’un protocole WB-MESI

Une ligne de cache L1 peut être dans 4 états:

Au niveau du L2, liste des copies pour chaque ligne + état S ou E/M (ou I)

Types de requête

Requêtes pour la cohérence

N° a b
1. WTI WA WTI WNA
2. WTI WNA WTU WNA
3. WTU WNA WB MESI
4. WB MESI WB MSI
N°1
	a > b (Non propre a la cohérence)
		W(X)
		R(X)
			Pas vraiment de cas, sauf si l'allocation est en préchargement (
        pas bloquant)
	b > a
		W(X)
		W(X+LINE_SIZE)
		W(X+2*LINE_SIZE)

N°2

a>b P0 | P1 — | — R(X) | || R(X) W(X)| W(X)| W(X)| W(X)|

b>a P0 | P1 | commentaire — | — | — R(X) | || R(X+4)| Mot dans la même ligne de cache que X || W(X+4) R(X)| W(X)| ||R(X+4)| ||W(X+4)| R(X)||inval W(X)|| 1 miss/R & 1 inval/W & 1 update/W

N°3

a>b Pour chaque R et pour chaque W, 4x latence L1->L2 ou L2->L1.

b>a P0 | P1 — | — R(X) | || R(X+4) W(X)| W(X)| W(X)| W(X)|

N°4

a>b P0|P1 —|— R(X)| W(X)|

b>a P0|P1 —|— R(X)| ||W(X)|

Exercice 1

a.

#prologue
addiu $29, $29, -29

#corps
la $4, lock
jal lock_acquire
nop
la $8,curr_elem
lw $9, 0($8)
sll $10,$9,2
la $11,table
addu $11,$11,$10
lw $12,0($11)
sll $12,$12,1
sw $12, 0($11)
addiu $9,$9,1
sw $9,0($8)
la $4, lock_acquire
jal lock_release
nop

#epilogue
$29,$29,4
jr $31

b.

Directory Etat TAG Copies
E/M &tab[0] 0
… … …
E/M &tab[2044] 0
E/M &tab[2048] 1
     
S curr_elem 0,1

c. Pour l’execution complète