Direct-mapped cache ?

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

C'est utilisé dans quel contexte ? C'est pas lié à la machine ou à du code machine ?


Ou est-ce une simple hash map ?

C'est possible que aç soit une hash map, je ne sais pas. En gros, le papier assemble plusieurs triangles en une structure de type SoA pour tirer parti des instructions SSE. Or ils indiquent que cet assemblage étant assez coûteux, 32 structures de ce type sont mis en cache pour pouvoir être récupérés rapidement ensuite, via un direct-mapped cache. Suis-je clair ou tu as besoin du papier ?

Citation:

---

Envoyé par Bakura

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:

---

1 2 3 4 5

setcache(adresse,valeur) { int position = F(adresse); cache[position].valeur = valeur; cache[position].tag = Tag(adresse); }

---

Code:

---

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; }

---

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 ?

Citation:

---

Envoyé par Bakura

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

---

? :koi:

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.

Ok. En gros ceci :

Code:

---

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 ?

Citation:

---

Envoyé par Bakura

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

Ok merci :).