Organización del Computador 1 Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires

26 de Octubre de 2010

Clase Práctica Memoria Caché

¿Qué es la memoria caché? En el sentido general, un caché es un espacio de almacenamiento de velocidad alta donde se guarda una copia de una parte de los datos que se encuentran en un segundo medio de almacenamiento de velocidad más reducida. En caso que nos interesa, el caché de un CPU, se trata de una memoria de muy alta velocidad que por lo general se encuentra integrada en el chip del CPU y guarda una parte de los datos de la memoria RAM para permitir acceder a ellos más rápidamente. La palabra proviene del francés “cache” (pronunciado cash) que significa “escondite”. Los cachés funcionan siempre en el contexto de una jerarquía de memoria, es decir, una organización de los dispositivos de almacenamiento en la que existen velocidades y capacidades distintas. Así, solo tiene sentido utilizar dispositivos más rápidos como caché de otros más lentos. En la figura se observa una comparación del tiempo necesario para acceder a un dato en memoria desde el CPU según el dispositivo en que se encuentra alojado. Las cachés L1, L2 y L3 que se encuentran en un procesador moderno se organizan en una estructura jerárquica: una caché L3 guarda datos de la RAM, una L2 guarda datos de la L3, una L1 guarda datos de la L2 y a su vez el CPU solo accede a datos que se encuentran en la caché L1. Antes de accederlos, será necesario cargar todos

Tiempo de Acceso (ns) 120 100 80 60 40 20 0 Registro

L1

L2

L3

RAM

los niveles de caché. Como se observa en el gráfico, si el tiempo para acceder a un registro es de un ciclo de reloj, un acceso a memoria RAM tiene un costo inmenso y el tiempo de espera requerido por esta operación no puede ser utilizado para hacer cómputos: es un desperdicio importante de potencia computacional. Las cachés funcionan por lo general bajo la hipótesis de localidad de referencia de varios tipos, en particular: • localidad espacial: si se utiliza un dato en memoria en un instante dado, es muy probable que en los instantes siguientes se utilice algún dato en una dirección cercana • localidad temporal: si se utiliza un dato en memoria en un instante dado, es muy probable que en los instantes siguientes se vuelva a utilizar

Características La característica primordial de una memoria caché es su función de mapeo. Esta función establece una o varias posiciones de caché en las que puede almacenarse una copia de una posición de RAM dada. Dado que el tamaño de la caché es siempre muy inferior al de la RAM, dicha función nunca puede ser inyectiva: necesariamente varias posiciones de la RAM serán almacenadas en la misma posición de la caché (aunque no simultáneamente!). Por esta razón, será necesario que al almacenar un dato en caché, se etiquete la posición de la caché indicando el origen (la posición en RAM) correspondiente al dato en cuestión. Esta etiqueta se denomina tag, y permite identificar cual de las múltiples posiciones de memoria que van a parar a una línea dada de la caché se encuentra allí en un momento determinado. Las memorias caché se organizan y operan (cargan y descargan) en líneas, a diferencia de una memoria convencional que se opera de a palabras. A su vez, dentro de cada línea, cada unidad direccionable tiene un índice dentro de la misma. Tags

Palabras por línea

Líneas

0 Índices

1

2

3

Tipos de caché Si bien puede diseñarse una función de mapeo de cualquier característica, en la materia nos interesaremos en una familia particular que es la más utilizada en la práctica. Este tipo de función de mapeo se llama “asociativa por conjuntos de N vías” y divide a las líneas de caché en conjuntos de N líneas. Así, si tuviéramos una caché asociativa por conjuntos de 2 vías, las 2 primeras líneas de la caché conformarían el conjunto 0, las 2 segundas el conjunto 1, y así sucesivamente. La función de mapeo se construye entonces de la siguiente forma: Dirección de memoria

tag

set (o “line”)

index

Así, los bits menos significativos denotan el índice, los siguientes el número de conjunto y los restantes el tag. La cantidad de bits de cada campo corresponde a la cantidad de valores posibles que pueden adoptar según las cantidades propias de la caché (como se observa en la figura anterior). Además, es de destacar que al cargarse la caché de a líneas, cuando se cargue una línea desde memoria, un bloque contiguo de RAM ocupará una línea en caché. Por esta razón, no es necesario tener un tag para cada posición dentro de cada línea de caché, sino que es suficiente con uno por línea: todas las posiciones cargadas en una línea en un momento dado comparten el mismo tag (los bits más significativos de su dirección). Una memoria caché asociativa por conjuntos de 1 vía se denomina “de mapeo directo”, mientras que si un único conjunto contiene a todas las líneas de la caché, se denomina “asociativa” a secas o “completamente asociativa”.

Operatoria de la caché Al realizarse un acceso a memoria, la computadora busca en primer lugar si dicha posición se encuentra en caché. Para esto, evalúa la función de mapeo y obtiene un número de conjunto que corresponde a esa línea. Enseguida, accede a caché y busca el conjunto correspondiente, lo cual puede terminar de una de dos maneras: • Si alguna de las líneas del conjunto comparte el tag con la dirección que se intentó acceder, entonces el valor buscado se encuentra en caché y se puede devolver al CPU. Esta situación se denomina hit. • Si ninguna de las líneas del conjunto comparte el tag con la dirección que se intentó acceder, entonces el valor buscado no se encuentra en caché. Esta situación se denomina miss. En este caso, la computadora accede a memoria y busca la dirección pedida, cargándola en caché junto con el resto de las posiciones contiguas (se llena completamente la línea de caché). En caso de que todas las líneas del conjunto estuvieran ya ocupadas, se desalojará alguna según la política de desalojo establecida. A continuación se devuelve el valor pedido al CPU. El hit rate es la tasa de hits por sobre la cantidad de accesos totales a memoria. Se calcula como HR = hits / (hits + misses). El miss rate es análogo a éste, cambiando el numerador.

Caché de escritura Además de las políticas detalladas antes, que se refieren a como se comporta el controlador de caché al momento de producirse una lectura, es necesario considerar también qué ocurre con las escrituras. Básicamente, frente a una escritura, deben considerarse dos aspectos del funcionamiento del controlador. En primer lugar, frente a una escritura, ¿debe cargarse la línea correspondiente de la caché? • En una caché write-allocate (asignación en escritura), cuando el CPU desea hacer una escritura a memoria, el controlador de caché carga la línea correspondiente. • En una caché write-no-allocate, (¿a que no adivinan?), no. En segunda instancia, si cuando se desea escribir a memoria, la posición involucrada se encuentra almacenada en caché1, ¿qué hace el controlador? • En una caché write-through (escritura inmediata), el controlador escribe los cambios tanto en la caché como en la memoria inmediatamente. • En una caché write-back (escritura demorada), el controlador escribe los cambios a caché pero no realiza la correspondiente escritura en memoria hasta tanto no se desaloje la línea en cuestión. Por lo general, las cachés write-back utilizan la política write-allocate. Esto se debe a que la caché write-back opera a partir de la suposición de que es probable que se produzcan múltiples escrituras en una misma posición, y por lo tanto resulta beneficioso esperar a que se completen todas antes de acceder a memoria para efectivizarlas. Por otro lado, las cachés write-through utilizan habitualmente la política write-no-allocate, puesto que no perciben ningún beneficio en tener la línea cargada a futuro (siempre accederán a memoria para realizar eventuales futuras escrituras).

Políticas de desalojo Por último, las memorias caché con nivel de asociatividad mayor a uno comparten la característica de que una posición de memoria puede ocupar más de una posición en la memoria caché. Por lo tanto, de encontrarse llenos todos los espacios posibles que puede ocupar una posición de memoria que ingresa a caché, será necesario decidir cual de las alternativas será desalojada. Dicha decisión se toma según una política, entre las que se incluyen: • LFU (Least Frequently Used, menos frecuentemente usada), que como su nombre lo indica desalojará la línea que haya sido usada con menor frecuencia desde que fue cargada. A su vez, el cálculo de la frecuencia puede hacerse de diversas maneras que dependerán de la implementación del controlador de caché. • LRU (Least Recently Used, menos recientemente usada) que desalojará la línea que, entre las alternativas, haya sido usada por última vez hace más tiempo. • FIFO (First In First Out, el primero que entra sale primero) Para la implementación de estas políticas muchas veces es necesario espacio adicional en la caché (por ejemplo, para contabilizar la cantidad de veces que se usó una línea), que por lo general se ubica junto con la información de tag. 1 En una caché write-allocate esto ocurre siempre, porque siempre se carga la línea correspondiente!

Ejercicio 1 Se dispone de una máquina con direcciones de 32 bits direccionando a byte, con palabras de 16 bits. La cache del CPU tiene 32KB utilizables (sin contar las posiciones reservadas para tags), en líneas de 8 bytes. Se desea utilizar una estrategia de correspondencia directa. 1. Indique la cantidad de bits de los campos tag, line e index. 2. Repita la tarea para una caché asociativa por conjuntos de 2 vías, otra asociativa por conjuntos de 8 vías y por último una caché totalmente asociativa. 3. Simule la siguiente secuencia de lecturas, indicando el estado de la caché, hits, misses, y el hit rate de toda la ejecución. Accesos: 0x70040, 0x70042, 0x70044, 0x70046, 0x70048, 0x8803c,  0x8803e, 0x88040, 0x70044, 0xb803f

Solución 1. Cada línea de caché tiene 8 bytes, por lo tanto serán necesarios 3 bits para el índice dentro de cada línea. Si hay 32 KB de caché en líneas de 8 bytes, esto resulta en 4096 líneas de caché. En una caché de correspondencia directa (es decir, asociativa por conjuntos de una vía) cada conjunto tiene una única línea. Tenemos por lo tanto 4096 conjuntos posibles que pueden distinguirse con 12 bits de set. Los 17 bits restantes se asignarán al tag. 2. Las soluciones son las siguientes, siguiendo la misma lógica del punto 1: Estrategia

Tag

Set

Index

Mapeo directo

17

12

3

Asociativa por conjuntos de 2 vías

18

11

3

Asociativa por conjuntos de 8 vías

21

9

3

Completamente asociativa

29

0

3

3. Para realizar este ejercicio debe simplemente decodificarse cada dirección a los valores de tag, set e index y simularse la ejecución, teniendo siempre presente el estado de la caché. En la columna caché se registra el estado de la caché al final de cada acceso a memoria, con el formato { línea: tag }. Dirección

Tag

Line

Index Res

Caché

Nota

0x70040

14

8

0

Miss

{8: 14}

0x70042

14

8

2

Hit

{8: 14}

0x70044

14

8

4

Hit

{8: 14}

0x70046

14

8

6

Hit

{8: 14}

0x70048

14

9

0

Miss

{8:14, 9: 14}

0x8803c

17

7

4

Miss

{8:14, 9: 14, 7: 17}

0x8803e

17

7

6

Hit

{8:14, 9: 14, 7: 17}

0x88040

17

8

0

Miss

{8: 17, 9: 14, 7: 17}

Desalojo

0x70044

14

8

4

Miss

{8: 14, 8: 14, 7: 17}

Desalojo

0xb803f

23

7

7

Miss

{8: 23, 8: 14, 7: 23}

Acceso desalineado

Un acceso desalineado es una situación especial que se da cuando se realiza un acceso a memoria en una posición cuya palabra sobrepasa el límite de la línea de caché. En este caso, para satisfacer el último pedido de lectura desde caché, será necesario cargar dos líneas de caché en vez de una. Esto tiene graves ramificaciones de performance, y si bien lo contabilizamos como un único miss, su costo es en general superior al de un miss convencional. El hit rate es HR = hits / (hits + misses) = 4 / (4 + 6) = 4/10 = 0.4 = 40 %

Ejercicio 2 Se desea dotar a la máquina ORGA1 de una caché asociativa por conjuntos de 2 vías con un tamaño total de 2KB a razón de 4 palabras por línea. La política de desalojo elegida es FIFO. 1. Indique la cantidad de bits de los campos tag, line e index. 2. Contabilice los accesos a memoria. ¿Cual será el hit rate en la ejecución de este programa? MOV R2, 0 MOV R3, 0x1D55 MOV R4, 0x3755 MOV R5, 0x0757 ADD R2, [R3] ADD R2, [R4] ADD R2, [R5] ADD R2, [R5+1] ADD R2, [R3+1] ADD R2, [R4+1]

3. Si se considera que un acceso a memoria insume 50 ciclos y un acceso a caché solo 1, indique cuantos ciclos se ahorran al implementar esta memoria caché. 4. ¿Como mejoraría el programa para aprovechar mejor la caché de la computadora? Solución 1. Cada línea de caché tiene 4 palabras por línea, o sea 8 bytes. Sin embargo, como en este caso la unidad direccionable es la palabra, serán suficientes 2 bits de index. Con 2 KB de memoria caché a razón de 8 bytes por línea, tendremos 256 líneas, que agruparemos en 128 conjuntos de 2 vías. Por lo tanto, utilizaremos 7 bits de set. Finalmente, los 7 bits restantes estarán destinados al tag. 2. Para contabilizar los accesos a memoria de un programa en ensamblador, es necesario primero convertirlo a una secuencia de lecturas de memoria realizando la decodificación de instrucciones. Es importante no olvidar que el fetch de instrucciones y operandos también consta de accesos a memoria! A continuación, simularemos la ejecución.

Instrucción

Accesos

Tag Set Index

Res

Caché

MOV R2, 0

0x0

0

0

0

Miss

0: 0

0x1

0

0

1

Hit

Idem

0x2

0

0

2

Hit

Idem

0x3

0

0

3

Hit

Idem

0x4

0

1

0

Miss

0: 0, 1: 0

0x5

0

1

1

Hit

Idem

0x6

0

1

2

Hit

Idem

0x7

0

1

3

Hit

Idem

0x8

0

2

0

Miss

0: 0, 1: 0, 2: 0

0x1D55

14

85

1

Miss

0: 0, 1: 0, 2: 0, 85: 14

0x9

0

2

1

Hit

Idem

0x3755

27

85

1

Miss

0: 0, 1: 0, 2: 0, 85: 14 y 27

0xA

0

2

2

Hit

Idem

0x0757

3

85

3

Miss

0: 0, 1: 0, 2: 0, 85: 3 y 27

0xB

0

2

3

Hit

Idem

0xC

0

3

0

Miss

0: 0, 1: 0, 2: 0, 85: 3 y 27, 3: 0

0x0758

3

86

0

Miss

0: 0, 1: 0, 2: 0, 85: 3 y 27, 3: 0, 86: 3

0xD

0

3

1

Hit

Idem

0xE

0

3

2

Hit

Idem

0x1D56

14

85

2

Miss

0: 0, 1: 0, 2: 0, 85: 3 y 14, 3: 0, 86: 3

0xF

0

3

3

Hit

Idem

0x10

0

4

0

Miss

0: 0, 1: 0, 2: 0, 85: 3 y 14, 3: 0, 86: 3, 4: 0

0x3756

27

85

2

Miss

0: 0, 1: 0, 2: 0, 85: 3 y 27, 3: 0, 86: 3, 4: 0

MOV R3, 0x1D55

MOV R4, 0x3755

MOV R5, 0x0757

ADD R2, [R3]

ADD R2, [R4]

ADD R2, [R5]

ADD R2, [R5+1]

ADD R2, [R3+1]

ADD R2, [R4+1]

Nota

Entra

Desalojo

Desalojo

Desalojo

El hit rate de esta ejecución es HR = hits / (hits + misses) = 12 / (12 + 11) = 12/23 = 0.521 = 52.1 % 3. En cada hit se ahorran 49 ciclos de reloj, puesto que el acceso cuesta un ciclo en lugar de 50. Dado que hubo 12 hits, se ahorraron 12 * 49 = 588 ciclos de reloj. 4. Se podría aumentar el nivel de asociatividad a 4, o bien (sin cambiar el CPU) se podrían reordenar los accesos a memoria de la suma para maximizar los hits.