La mémoire cache

Correspondance directe

Voici un exemple d’exercice :

Ligne	Init	18	27	3
0	30
1	7
2	0
3	9
4	0
5	0

Pour la correspondance directe il faut pour chaque colonne, le modulo du nombre de lignes.

Dans l’exemple ici, la première colonne est 18 et il y a 6 lignes. On fait donc $18\mathrm{mod}6$ ce qui donne 0. On met donc 18 dans la ligne 0. Ainsi de suite pour les autres.

Ligne	Init	18	27	3
0	30	18
1	7
2	0
3	9		27	3
4	0
5	0

Enfin on complète le tableau en recopiant à chaque fois la case de gauche.

Ligne	Init	18	27	3
0	30	18	18	18
1	7	7	7	7
2	0	0	0	0
3	9	9	27	3
4	0	0	0	0
5	0	0	0	0

Complètement associative avec remplacement circulaire

Schéma honteusement subtilisé à Melisa

Celui ci est un peu plus subtile que le précédent, pour chaque colonne il faut :

1. Vérifier si le nombre est déjà dans la colonne précédente, si oui, on recopie juste la colonne
2. Sinon, pour le premier remplacement, il faut mettre le nombre à la première ligne qui est à 0
3. A chaque remplacement (et pas colonne), on va placer le nombre sur la ligne juste en dessous
4. On complète le reste des cases par les cases de la colonne précédente (comme précédemment)

Associative par ensemble avec remplacement circulaire

Ici, c’est un mélange des deux précédents, ici il y a plusieurs sets, et chaque set a 2 lignes. Pour faire ceci, pour chaque colonne :

1. Faire le modulo de la colonne par le nombre de sets (exemple avec le premier : $22\mathrm{mod}4=2$, donc il faudra écrire 22 dans le set 2)
2. Si il y a une ligne vide (0 ou -) parmis le set en question on place le nombre là (exemple avec le premier : la deuxième ligne du set 2 est -, c’est donc là que l’on place notre nombre)
3. Sinon, si le nombre est déjà inscrit dans le set, on réécrit juste la colonne
4. Sinon, on écrit le nombre à la ligne opposée à celle du dernier remplacement (exemple: le nombre 21 a été placé en bas du set 1, 25 (le remplacement suivant) est donc placé en haut).