Discussion :

[Bakura]

Bonsoir,

J'ai lu plusieurs publications qui parlaient d'un "direct-mapped cache" afin d'optimiser l'accès à des variables souvent utilisées, mais j'ai du mal à comprendre comment ceci est implémenté, d'un point du vue du code. Est-ce implémenté comme un "bête" cache LRU ou MRU, ou est-ce plus compliqué ?

Merci

[pseudocode]

Est-ce implémenté comme un "bête" cache LRU ou MRU, ou est-ce plus compliqué ?

Le "direct-mapped" consiste a avoir une "formule mathematique" pour calculer directement la position dans le cache de n'importe quelle adresse possible.

Bien sur, le cache étant plus petit que l'espace d'adressage, certaines adresses auront la même position dans le cache. Cela implique:

1. en cas de collision, c'est la dernière adresse qui est conservée dans le cache. Il faut donc une formule de calcul qui minimise les collisions, ou alors utiliser des adresses tenant compte de la formule utilisée.

2. il faut une info dans le cache, en plus de la valeur, pour savoir quelle adresse (parmis celles pouvant générer une collision) est stockée actuellement. Cette info est appelée "tag".

Donc cela donne quelque chose comme cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
setcache(adresse,valeur) {
  int position = F(adresse);
  cache[position].valeur =  valeur;
  cache[position].tag =  Tag(adresse);
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
getcache(adresse) {
  int position = F(adresse);
  int tag = Tag(adresse);
  if (cache[position].tag != tag) return null;
  return cache[position].valeur;
}

[Bakura]

Merci de la réponse. Mais j'ai du mal à comprendre comment ça fonctionne concrètement. Imagine que j'ai un tableau de taille fixe de 32 éléments, quelle différence entre cette approche et celle d'accéder directement à un élément du tableau ?

[pseudocode]

quelle différence entre cette approche et celle d'accéder directement à un élément du tableau ?

?

Je ne comprend pas ta question. Le "direct-mapped" accéde directement à un élément du tableau, à la différence d'une méthode type "hash map" dans laquelle on calcule un "hash" puis où l'on parcourt toute la structure du cache pour trouver l'entrée ayant le meme hash.

[Bakura]

Ok. En gros ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
maStructure tab[32];
maStructure s1 = tab[3];

Ceci est donc un direct-mapped cache ? En fait si je comprends ce que tu dis, c'est juste un "bête" tableau, dans lequel on dispose juste d'une fonction pour retrovuer l'indice correspondant ?

[pseudocode]

Ceci est donc un direct-mapped cache ? En fait si je comprends ce que tu dis, c'est juste un "bête" tableau, dans lequel on dispose juste d'une fonction pour retrovuer l'indice correspondant ?

heu... oui, c'est ca : on dispose d'une fonction pour calculer l'indice correspondant.

Cependant, comme je l'ai dit, on ne stocke pas seulement la "valeur" dans le tableau mais également le "tag" pour savoir quelle adresse y est stockée (a cause des collisions dues à la formule de calcul).