PDF de programación - Tema 6: Memoria Caché

Estructura de Computadores, Facultad de Informática, UCM, Curso 11-12



Tema 6: Memoria Caché.

Objetivos:


Introducir la terminología y los principios básicos de funcionamiento de la memoria caché,
resaltando la localidad referencial de los programas que explican su elevado rendimiento.

 Analizar las alternativas de diseño que determinan el comportamiento de una caché,
resaltando la función de correspondencia, las políticas de búsqueda y sustitución de
bloques, y el mantenimiento de la coherencia con memoria principal en las escrituras.

 Estudiar los factores que más influencia tienen en el rendimiento de una caché junto a las

alternativas de diseño hardware y software que permiten optimizar dichos factores.

 Analizar el sistema de memoria caché de algunos procesadores, especialmente el del ARM.

Contenido:

1. Principios básicos de funcionamiento de la memoria caché

2. Elementos de diseño.

3. Factores que determinan el rendimiento de la memoria caché.

4. Ejemplos de sistemas de memoria caché.

La velocidad de la memoria se ha distanciado progresivamente de la velocidad de los
procesadores. En la figura siguiente se muestran las gráficas de la evolución experimentada por el
rendimiento de las CPUs y las memoria DRAM (soporte de la memoria principal de los
computadores actuales) en los últimos años. Las curvas muestran que el rendimiento de la CPU
aumentó un 35% anual desde 1980 hasta 1987; y un 55% anual a partir de ese año. En cambio la
memoria ha mantenido un crecimiento sostenido del 7% anual desde 1980 hasta la fecha. Esto
significa que si se mantiene la tendencia, el diferencial de rendimiento no sólo se mantendrá sino
que aumentará en el futuro. Para equilibrar esta diferencia se viene utilizando una solución
arquitectónica: la memoria caché

100.000

10.000

1000

100

10

0.1

55%

Diferencia
progresiva

35%

7%

1980 1987 2000

Evolución de la mejora de rendimiento de la CPU y memoria DRAM

64 KB (DRAM)



CPU

Memoria
(DRAM)



1

Estructura de Computadores, Facultad de Informática, UCM, Curso 11-12


La memoria caché es una memoria pequeña y rápida que se interpone entre la CPU y la
memoria principal para que el conjunto opere a mayor velocidad. Para ello es necesario mantener
en la caché aquellas zonas de la memoria principal con mayor probabilidad de ser referenciadas.
Esto es posible gracias a la propiedad de localidad de referencia de los programas.

1.1. Localidad de referencia: temporal y espacial
Los programas manifiestan una propiedad que se explota en el diseño del sistema de gestión
de memoria de los computadores en general y de la memoria caché en particular, la localidad de
referencias: los programas tienden a reutilizar los datos e instrucciones que utilizaron
recientemente. Una regla empírica que se suele cumplir en la mayoría de los programas revela que
gastan el 90% de su tiempo de ejecución sobre sólo el 10% de su código. Una consecuencia de la
localidad de referencia es que se puede predecir con razonable precisión las instrucciones y datos
que el programa utilizará en el futuro cercano a partir del conocimiento de los accesos a memoria
realizados en el pasado reciente. La localidad de referencia se manifiesta en una doble dimensión:
temporal y espacial.

Localidad temporal: las palabras de memoria accedidas recientemente tienen una alta
probabilidad de volver a ser accedidas en el futuro cercano. La localidad temporal de los programas
viene motivada principalmente por la existencia de bucles.

Localidad espacial: las palabras próximas en el espacio de memoria a las recientemente
referenciadas tienen una alta probabilidad de ser también referenciadas en el futuro cercano. Es
decir, que las palabras próximas en memoria tienden a ser referenciadas juntas en el tiempo. La
localidad espacial viene motivada fundamentalmente por la linealidad de los programas
(secuenciamiento lineal de las instrucciones) y el acceso a las estructuras de datos regulares.

CPU

Memoria cache

(Mc)

Memmoria principal

Mp

palabras

bloques (líneas)

Para implementar el mecanismo de actualización de la caché con los datos con mayor
probabilidad de ser refernciados se divide la memoria principal en bloques de un número de bytes
(4,8,16 etc.) y la caché en marcos de bloque o líneas de igual tamaño. El bloque será, pues, la
unidad de intercambio de información entre la memoria principal y la caché, mientras que entre la
caché y la CPU sigue siendo la palabra. El directorio contiene la información de qué bloques de Mp
se encuentran ubicados en Mc



2



Estructura de Computadores, Facultad de Informática, UCM, Curso 11-12



n

Dirección
de memoria
0
1
2



direccion



2n -1



Mp

Directorio

Mc

Bloque 0



Bloque 1



Bloque 2n/K -1

m marcos de bloque o líneas
2n palabras
K palabras/bloque
M = 2n/K bloques >> m

Marco de
Bloque 0



Marco de
Bloque m -1



El funcionamiento de la memoria caché se puede resumir en el diagrama de flujo de la
siguiente figura. En él se describe el proceso de traducción de la dirección física procedente de la
CPU (en el supuesto que el procesador no disponga de memoria virtual o esté desactivado) en el
dato ubicado en la posición de memoria determinada por dicha dirección:

Mc <-- CPU(DF)

Recibe la

Dirección Física
(DF) de la CPU

¿ DF bloque
en la cache?

no

(fallo)

Acceso a Mp para obtener
el bloque que contiene DF

si (acierto)

Leer el contenido de DF

y llevarlo a la CPU

CPU <-- <DF>

Asignar un marco de la
cache al bloque de Mp

Mc <-- Mp(bloque)

Cargar el bloque de

Mp en el marco

asignado de la cahe

Llevar el contenido
de la DF a la CPU

1.2. Tasa de aciertos y tasa de fallos:
Cuando una dirección se presenta en el sistema caché pueden ocurrir dos cosas:



 Acierto de caché (hit): el contenido de la dirección se encuentre en un bloque ubicado en

una línea de la caché.

 Fallo de caché (miss): el contenido de la dirección no se encuentre en ningún bloque

ubicado en alguna línea de la caché.

Si en la ejecución de un programa se realizan Nr referencias a memoria, de las que Na son

aciertos caché y Nf fallos caché, se definen los siguientes valores:



3

Estructura de Computadores, Facultad de Informática, UCM, Curso 11-12


 Tasa de aciertos:
 Tasa de fallos:
Evidentemente se cumple:



Ta = Na/ Nr
Tf = Nf/ Nr
Ta = 1 - Tf

2. Elementos de diseño.

A la hora de diseñar un sistema de memoria caché hay que elegir entre una serie de

alternativas para cada uno de los siguientes elementos de diseño:

 Función de correspondencia: determina las posibles líneas de la caché (marcos de bloque)
en las que se puede ubicar un determinado bloque de la memoria principal que ha sido
referenciado por el programa y hay que llevarlo a memoria caché.

 Algoritmo de sustitución: determina el bloque que hay que desubicar de una línea de la

caché cuando ésta está llena y hay que ubicar un nuevo bloque.

 Política de escritura: determina la forma de mantener la coherencia entre memoria caché y

memoria principal cuando se realizan modificaciones (escrituras)

 Política de búsqueda de bloques: determina la causa que desencadena la llevada de un

bloque a la caché (normalmente un fallo en la referencia)

 Cachés independientes para datos e instrucciones: frente a cachés unificadas.
2.1. Función de correspondencia
Existen tres funciones de correspondencia para definir la posible ubicación de un bloque de
memoria principal (Mp) en la memoria caché (Mc): directa, asociativa y asociativa por conjuntos.
En el primer caso un bloque de Mp sólo puede ubicarse en una línea de la caché, aquella que
coincide con el bloque cuando superponemos Mc sobre Mp respetando fronteras de Mc, es decir,
sobre espacios de Mp que son múltiplos del tamaño de Mc. En la correspondencia asociativa un
bloque puede ubicarse en cualquier línea de Mc. Finalmente, la correspondencia asociativa por
conjuntos es un compromiso entre las dos anteriores.

Mp

Mc

Mc

Mc

B0
B1
B2
B3
B4
B5
B6
B7

B0
B1
B2
B3
B4
B5
B6
B7

C0
C1
C2
C3

Directa Asociativa Asociativa por conjuntos

2.1.1. Correspondencia directa



En la correspondencia directa el bloque Bj de Mp se puede ubicar sólo en el marco de bloque
o línea MBi que cumple la siguiente relación i = j mod m, donde m es el número total de líneas que
tiene la caché. En la tabla siguiente se especifica el conjunto de bloques que se pueden ubicar en
una línea de Mc:



4

Estructura de Computadores, Facultad de Informática, UCM, Curso 11-12



Bloques de Mp
0, m, 2m, ... , 2s-1m
1, m+1, 2m+1,..., 2s-1m+1
......
m-1, 2m-1, 3m-1,..., 2sm-1

Marcos de bloque de Mc
0
1
...
m-1

Interpretación de una dirección física en correspondencia directa:

s

bloque

etiqueta marco de bloque palabra

s-r r w



2w palabras/bloque
2s bloques de Mp
2r marcos de bloque en Mc (2r = m)
2s-r veces contiene Mp a Mc
Los s - r bits de la etiqueta diferenciarán a cada uno de los bloques de Mp que pueden
ubicarse en el mismo marco de bloque de Mc. El directorio caché en correspondencia directa
contendrá un registro de s - r bits por cada m