La fonction de mémorisation - Architecture des Machines et des Systemes Informatiques - page 186

Il faut distinguer la lecture et l'écriture d'un mot. Le principe de fonctionnement
pour la lecture d'un mot est décrit par l'algorithme :
si mot présent
alors charger processeur avec le mot;
sinon
si cache plein
alors charger cache(remplacer);
charger processeur;
sinon
charger cache;
charger processeur;
finsi
Le processeur cherche d'abord si le mot mémoire adressé est dans le cache (mot
présent). Si l'information est présente on parle de succès ( cache hit ). Le cache est de
petite taille et ne contient pas toute l'information de la mémoire centrale : l'informa-
tion peut donc ne pas être dans le cache, on parle alors d'échec ( cache miss ). Dans ce
dernier cas, il faut aller chercher l'information dans la mémoire centrale et placer
celle-ci dans le cache (charger cache) avec éventuellement un remplacement d'infor-
mations actuellement présentes dans le cache puisque le cache est de taille finie
(charger cache (remplacer)). Enfin, le processeur est chargé avec l'information main-
tenant disponible dans le cache.
L'efficacité du cache dépend donc de son taux de succès et donc de la probabilité
de présence dans le cache du mot cherché. Après un échec le cache est chargé avec le
mot manquant, ainsi si ce mot est redemandé ultérieurement, il sera obtenu confor-
mément au temps d'accès du cache (donc plus rapidement que s'il était en mémoire
centrale).
Un programme ne s'exécute pas de manière aléatoire : de nombreuses études
statistiques montrent que lorsqu'une instruction référence une adresse il est très
probable que la référence mémoire qui suit soit dans le voisinage de cette adresse.
En effet les programmes travaillent sur des informations organisées par des structures
de données (exemple les tableaux) qui les placent dans des adresses mémoires très
proches les unes des autres (ces adresses sont contiguës dans le cas des tableaux).
Par ailleurs les instructions d'un programme sont placées dans des mots mémoires
contigus et le flux d'exécution se fait séquentiellement (instruction après instruction)
sauf dans le cas de branchements ou de déroutements.
Ainsi quand une instruction s'exécute, il est très probable que la prochaine instruc-
tion à exécuter soit dans le mot suivant de la mémoire : c'est le principe de localité
spatiale . Ce principe nous conduit à penser que lorsqu'une donnée ou une instruction
doit être chargée dans un cache il serait intéressant de charger également les données
(et/ou instructions) qui sont proches en mémoire. On augmente ainsi la probabilité
que le processeur trouve la prochaine donnée (ou instruction) dans le cache.
Les programmes font beaucoup d'itérations et les données qui y sont traitées sont
très souvent utilisées dans de courts laps de temps (une variable qui pilote une boucle