Quel est le comportement du cache L1/L2 pour les LUT et les semblables?

Question

En supposant une table de conversion de 512 Ko, par exemple, de types doubles 64 bits. De manière générale, comment le processeur met-il en cache la structure dans L1 ou L2? Par exemple: J'accède à l'élément central, essaie-t-il de mettre en cache la totalité de la table ou une partie de celle-ci - disons l'élément central et ensuite n éléments suivants?

Quels types d'algorithmes le processeur utilise-t-il pour déterminer ce qu'il conserve dans le cache L2? Y at-il une certaine stratégie d'anticipation il suit

Note: Je présume que x86, mais je serais intéressé de savoir comment les autres architectures fonctionne PUISSANCE, etc .. SPARC

Answer 1

Cela dépend de la structure de données vous utilisez pour le LUT (table de correspondance?)

Les caches sont à leur meilleur avec les choses qui sont disposées de manière contiguë est la mémoire (par exemple sous forme de tableaux ou std :: vecteurs) plutôt que dispersés. En termes simples, lorsque vous accédez à un emplacement de mémoire, un bloc de RAM (une «ligne de cache» de valeur - 64 octets sur x86) est chargé dans le cache, éventuellement en expulsant certaines données précédemment mises en cache.

Généralement, il existe plusieurs niveaux de cache, formant une hiérarchie. Avec chaque niveau, les temps d'accès augmentent, tout comme la capacité.

Oui, il y a préanalyse, qui est limitée par des algorithmes plutôt simplistes et l'incapacité de franchir les frontières de la page (une page de mémoire est généralement 4 Ko en taille sur x86.)

Je vous suggère de lire What Every Programmer Should Know About Memory. Il a beaucoup de bonnes informations sur le sujet.

Answer 2

Les caches sont généralement formés comme une collection de lignes de cache. La granularité de chaque ligne de cache est alignée sur la taille de la ligne de cache, ainsi, par exemple, un cache avec une ligne de cache de 128 octets aura l'adresse de mise en cache des données alignée sur 128 octets. Les caches d'UC utilisent généralement un mécanisme d'éviction LRU (utilisé le moins récemment, comme pour supprimer la ligne de cache la plus ancienne sur un cache manquant), ainsi qu'un mappage d'une adresse de mémoire à un ensemble particulier de lignes de cache. (Cela entraîne l'une des nombreuses fausses erreurs de partage dans x86 si vous essayez de lire à partir de plusieurs adresses alignées sur une limite de 4k ou 16M.)

Ainsi, lorsque vous avez une erreur de cache, la CPU lit dans un ligne de mémoire cache qui inclut la plage d'adresses manquante. S'il vous arrive de lire une limite de ligne de cache, cela signifie que vous lirez deux lignes de cache.