Skip to main content

La mémoire cache

Correspondance directe

Voici un exemple d'exercice :

LigneInit18273
030
17
20
39
40
50

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 \mod 6$ ce qui donne 0. On met donc 18 dans la ligne 0. Ainsi de suite pour les autres.

LigneInit18273
03018
17
20
39273
40
50

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

LigneInit18273
030181818
17777
20000
399273
40000
50000

Complètement associative avec remplacement circulaire

Schéma 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

Exercice syllabus

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 \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).