Arquitectura de Computadores

Tema N° 12: Sistema de Memoria: Cache Eduardo Daniel Cohen – [email protected]

http://www.herrera.unt.edu.ar/arqcom

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

1

En Perspectiva: ¿En dónde estamos ahora? ° Las cinco componentes clásicas un computador: Processor

Input Control Memory Datapath

Output

° Temas a cubrir: • Localidad y Jerarquías de Memoria. • Organización de Memoria: Caché.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

2

Tendencias Tecnológicas

Capacidad

Velocidad

Lógica:

2x en 3 años

2x en 3 años

DRAM:

4x en 3 años

2x en 10 años

Disk:

4x en 3 años

2x en 10 años

DRAM Año 1980 1983 1985 1989 1992 1996 1998 2000 2002 2004 Cache - D. Cohen

Tamaño 64 Kb 256 Kb 1 Mb 4 Mb 16 Mb 64 Mb 128 Mb 256 Mb 512 Mb 1024 Mb

Fila 250 ns 185 ns 135 ns 90 ns 90 ns 60 ns 60 ns 55 ns 50 ns 45 ns

Columna 150 ns 100 ns 40 ns 30 ns 30 ns 12 ns 10 ns 7 ns 5 ns 3 ns

UNT – Arq. de Computadoras - 2014

Precio/Mb $1.500 $ 500 $ 200 $ 50 $ 15 $ 10 $ 4 $ 1 $ 0,25 $ 0,10 3

Importancia de la Jerarquía de Memorias

Brecha CPU-DRAM (latencia)

Performance

1000

CPU

“Ley de Moore”

100

µProc 60%/año (2X/1.5año)

Brecha de Performance CPU-DRAM: (aumenta 50% / año) DRAM DRAM 9%/año. (2X/10 años)

10

1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000

1

Tiempo Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

4

Situación Actual: Microprocesador

° Se basa en Caches para cerrar la brecha. ° Brecha de Performance Microprocesador-DRAM: • Tiempo de un fallo completo de caché en instrucciones ejecutadas: 1st Alpha (7000): 2nd Alpha (8400):

340 ns/5.0 ns = 68 clks x 2 or 266 ns/3.3 ns = 80 clks x 4 or

136 instructions 320 instructions

3rd Alpha (t.b.d.):

180 ns/1.7 ns =108 clks x 6 or

648 instructions

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

5

Impacto en la Performance ° Suponga un CPU que funciona a

Inst M iss (0.5) 16%

• Frecuencia de Reloj = 200 MHz (5 ns por ciclo) • CPI = 1.1 • 50% arith/logic, 30% ld/st, 20% control

° Supongamos que 10% de las operaciones de M tienen una penalidad for fallos = 50 ciclos. CPI

Ideal CPI (1.1) 35%

DataM iss (1.6) 49%

= CPI ideal + paradas promedio por instrucción = 1.1 ciclos +( 0.30 (opsM/ins) x 0.10 (fallos/opsM) x 50 (ciclos/fallos)) = 1.1 ciclos + 1.5 ciclos = 2.6

° 58 % del tiempo del procesador (1,5/2,6) está parado esperando a memoria! ° Un 1% de fallos en accesos a Memoria de Instrucciones adicionaría 0.5 ciclos al CPI!

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

6

Objetivo: Ilusión de una Memoria grande, barata y rápida

° Memorias grandes son lentas, memorias pequeñas son rápidas. ° Memorias rápidas son caras. Memorias lentas son baratas. ° ¿Cómo creamos una memoria que sea grande, barata y rápida (la mayor parte del tiempo)? • Jerarquías. • Paralelismo.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

7

Jerarquías de Memoria en Computadores Modernos ° Objetivo de Diseño: • Presentar al usuario todo su espacio de direccionamiento en la tecnología más barata. • Proveerle acceso a la velocidad de la tecnología más rápida. • Que cada tarea tenga un espacio disjunto y protegido. ¿por qué? Processor Control

Speed (ps): 1s Size (bytes): 100s Cache - D. Cohen

On-Chip Cache

Registers

Datapath

Second Level Cache (SRAM)

Main Memory (DRAM)

10s

100s

Ks

Gs

UNT – Arq. de Computadoras - 2014

Secondary Storage (Disk)

(10s ms) Gs

Tertiary Storage (Disk)

(10s sec) Ts 8

¿Cómo Funciona la Jerarquía? ° Principio de Localidad: • Un programa accede a una pequeña porción del espacio de direcciones en cualquier momento dado de tiempo. Probabilidad De Referencia

0

Espacio direcciones2^n - 1

¿Qué es espacio de direcciones? Conjunto de Trabajo: Conjunto de direcciones de Memoria accedidas en un período fijo de tiempo, o ventana de tiempo. La localidad espacial y la temporal aseguran que el contenido del Conjunto de Trabajo cambie lentamente durante el tiempo de ejecución. EL CONJUNTO DE TRABAJO DEBE ESTAR EN LA MEMORIA RÁPIDA.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

9

¿Cómo Funciona la Jerarquía de Memorias? ° Localidad Temporal (localidad en el tiempo): => Si accedo a un ítem, es probable que se lo acceda nuevamente pronto. => Mantener a los ítems que hayamos accedido más recientemente cerca del procesador.

° Localidad Espacial (localidad en el espacio): => Si se accede a un ítem, es probable que se acceda a ítems vecinos pronto. => Mover bloques que consisten en palabras de direcciones contiguas, a los niveles superiores. Al CPU

Memoria de Nivel Superior

Memoria de Nivel Inferior

Blk X

Del CPU

Cache - D. Cohen

Blk Y

UNT – Arq. de Computadoras - 2014

10

Jerarquía de Memorias: Terminología Al CPU

Mem. Nivel Superior

Mem. Nivel Inferior

Blk X

Del CPU

Blk Y

° Acierto (Hit): El dato está en algún bloque del nivel superior (ejemplo: Block X) • Hit Rate: Fracción de accesos a Memoria que se encuentran en el nivel superior. • Hit Time: Tiempo para acceder al nivel superior, que consiste en: RAM access time + tiempo para determinar si hubo acierto o fallo.

° Fallo (Miss): El dato debe ser ubicado en un nivel inferior y llevado al nivel superior (ejemplo: Block Y) • Miss Rate = 1 - (Hit Rate) • Penalidad del Fallo: Tiempo para reemplazar un bloque completo en el nivel superior.

° Hit Time menos chips => más difícil de tener bancos. • Crecimiento bits/chip DRAM : 50%-60% por año.

° Mejoras Tecnológicas: • Fast Page. A la salida de la DRAM se pone una SRAM capaz de almacenar una fila completa. Se accede a esta fila a la velocidad de una SRAM. • SDRAM – Syncronic DRAM. Se pasa la dirección inicial y la longitud de la secuencia de accesos y la memoria comienza a enviarlos al procesador a un ritmo dado por la señal de clock. El tiempo de acceso es menor que una EDO. Adentro hay bancos en interleaving. • DDR SDRAM – el ritmo es el doble del clock, envía con el flanco positivo y negativo, por eso se llama Dual Data Rate. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

16

Costo de Cerrar la Brecha Procesador-Memoria

Procesador

% Area

%Transistors

(~costo)

(~consumo)

• Alpha 21164

37%

77%

• StrongArm SA110

61%

94%

• Pentium Pro

64%

88%

- 2 dados por paquete: (CPU+L1) + L2

° Los Caches no tienen un valor por sí mismos, solo sirven para cerrar la brecha CPU-M.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

17

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

18

Cómo se Diseña Sistemas de Memoria Carga de trabajo típicas con Programas Benchmarks

CPU Series de Referencia: , ,,, . . . op: i-fetch, read, write

Memoria $ MEM

Cache - D. Cohen

Optimizar la organización de memoria para Minimizar el tiempo promedio de acceso Para cargas de trabajo típicas

UNT – Arq. de Computadoras - 2014

19

4 Cuestiones Básicas en Jerarquía de Memorias

1. ¿Donde poner un bloque en el Cache? (Ubicación de Bloques) 2. ¿Como encontrar un bloque en el Cache? (Identificación de Bloques)

3. ¿Qué bloque reemplazar en caso de fallos? (Reemplazo de Bloques) 4. ¿Qué se hace en caso de escritura? (Estrategia de Escritura) °

Preguntas 1 y 2. •

Cache - D. Cohen

Debe haber una forma de “mapear” M a Cache.

UNT – Arq. de Computadoras - 2014

20

Lo más simple: Cache de mapeo directo. Memory Address 0 1 2 3 4 5 6 7 8 9 A B C D E F Cache - D. Cohen

Memory

4 Byte Direct Mapped Cache Cache Index 0 1 2 3

° El lugar 0 solo puede ser ocupado por: • Datos en direcciones de MP 0, 4, 8, ... etc. • En general: cualquier lugar de memoria cuyos 2 LSB de la dirección son ceros. • Address => índice del caché

° ¿Cuál de ellos pondríamos en el caché?

° ¿Cómo podemos saber cuál de ellos está en el caché? UNT – Arq. de Computadoras - 2014

21

Rótulo e Indice de Cache ° Sean 32 bits para direccionar Memoria (bytes): • Para un caché de mapeo directo de 2N: -

Indice del cache: Los N menos significativos para direccionarlo. Rótulo del Cache (Tag): Los (32 - N) MSB de la dirección de memoria.

-

Sistema Octal: 0x50. ¿Para qué es el bit de Validez?

31

N

Cache Tag

Valid Bit

Example: 0x50

Stored as part of the cache “state”

0x50

:

Cache Index 2 N Bytes Direct Mapped Cache Byte 0 Byte 1 Byte 2 Byte 3

: UNT – Arq. de Computadoras - 2014

0 1 2 3

: Byte 2**N -1

Cache - D. Cohen

0 Ex: 0x03

2 N- 1 22

Ejemplo de Acceso al Caché V

Comienzo

Tag

Data 3 Access 000 01 (HIT)

1 Access 000 01 (miss)

000 010

M [00001] M [01010]

000 010

M [00001] M [01010]

Miss Handling: Write Tag & Set V Load Data

000

M [00001]

2 Access 010 10 (miss)

4 Access 010 10 (HIT)

Load Data

° Triste Realidad:

Write Tag & Set V

000 010

M [00001] M [01010]

• Muchos fallos al comienzo: Fallos Compulsivos -

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

(Fallos de arranque en frío) 23

Bloque del Cache

° Nuestro ejemplo previo era “extremo”: • Cache de mapeo directo de 4 bytes: Block Size = 1 Byte • Aprovechaba la localidad temporal: Si un dato es accedido, tenderá a ser accedido nuevamente pronto. • No aprovechaba la localidad espacial: Si se accede a un dato, los datos vecinos serán accedidos pronto.

° Localidad espacial: conviene traer un bloque “grande” de bytes “vecinos” en lugar de un único byte. ° Cache Block: Conjunto de palabras que están en un mismo rótulo. Valid

Cache - D. Cohen

Cache Tag

Direct Mapped Cache Data Bloque 0 Bloque 1 Bloque 2 Bloque 3

UNT – Arq. de Computadoras - 2014

24

Ej: Cache de Mapeo Directo de 1 KB con Bloques de 32 B ° Para un Cache de 2n Bytes: • Los (32 - n) bits más significativos conforman el Cache Tag (rótulo) • Los m LSBits seleccionan el byte en el bloque (tamaño bloque=2 m). • Los n-m bits siguientes (índice) seleccionan el bloque.

Valid Bit

Example: 0x50

Cache Tag 0x50

:

Cache Data Byte 31 Byte 63

Byte 1 Byte 0 0 Byte 33 Byte 32 1 2 3

:

: Byte 1023

Cache - D. Cohen

4 0 Byte Select Ex: 0x00

UNT – Arq. de Computadoras - 2014

:

Cache Tag

9 Cache Index Ex: 0x01

: :

31

Byte 992 31 25

Tamaño del Bloque - Compromiso Average Access Miss Time Rate No explota localidad espacial Increased Miss Penalty Pocos bloques & Miss Rate compromete Localidad temporal

Miss Penalty

Block Size Block Size

Block Size

° Bloques más grandes aprovechan mejor la localidad espacial, pero: • Bloques más grandes implican una penalidad de falla mayor:

- Toma más tiempo traerlo de MP. • Habrá muy pocos bloques en el caché, generará fallos en los saltos

° El tiempo promedio de Acceso: • = Hit Time + Miss Penalty x Miss Rate Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

26

Otro Ejemplo Extremo: Bloque Unico Valid Bit

Cache Tag

Cache Data Byte 3 Byte 2 Byte 1 Byte 0 0

° Tamaño Cache = 4 bytes

Tamaño Bloque = 4 bytes

• Una única entrada en el caché.

° Si un ítem es accedido, va a ser accedido pronto de nuevo • ¡Pero es improbable que sea accedido inmediatamente! • El próximo acceso seguramente generará un fallo:

-

Se cargan datos continuamente en el caché, pero solo para ser descartados antes de usarse nuevamente.

-

La peor pesadilla del diseñador: Efecto Ping Pong.

° Fallos por Conflicto son fallos causados por: • Lugares diferentes en MP que se mapean al mismo lugar en CACHE. Cache - D. Cohen

Solución 1: aumentar el tamaño del cache. Solución 2: cache asociativo – próxima diapositiva. UNT – Arq. de Computadoras - 2014

27

Cache Completamente Asociativo. Cache Tag (27 bits long)

Valid Bit Cache Data Byte 31 Byte 1 Byte 0 Byte 63 Byte 33 Byte 32

: :

Cache Tag X X 27

Byte Select Ex: 0x01

X X

X

:

:

:

° Implementación • No hay índice del cache. Un bloque se puede ubicar en cualquier parte. • Comparar los rótulos de todos los datos del cache en paralelo. • Ejemplo: para un caché de N bloques necesitamos N comparadores de 27 bits.

° No hay fallos por conflictos. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

28

Ventajas y Desventajas del Cache Asociativo Ventaja • Es el más flexible: cualquier bloque de MP puede ponerse en cualquier parte del cache. • No hay fallos por conflictos. Desventajas

• Mucha Memoria para Rótulos (tags más anchos). • Mucho Hw para búsqueda asociativa en todo el cache simultáneamente.

• Hit Time mayor que Cache de Mapeo Directo. ¿Se podrán combinar las ventajas de los dos: Asociativo y Directo?

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

29

Caché Asociativo por conjuntos ° Asociativo de N vías: N entradas para cada índice. • N cachés de mapeo directo operan en paralelo.

° Ejemplo: Cache asociativo de 2 vías. • Cache Index selecciona un “conjunto” del cache • Los dos tags en el conjunto se comparan en paralelo • Se selecciona el dato según el resultado de la comparación. Valid

Cache Tag

:

:

Adr Tag

Compare

Cache Index Cache Data Cache Data Cache Block 0 Cache Block 0

:

:

Sel 1 1

Mux

0 Sel 0

Cache Tag

Valid

:

:

Compare

OR Hit Cache - D. Cohen

Cache Block

UNT – Arq. de Computadoras - 2014

30

Desventaja del Cache Asociativo por Conjuntos ° Caché Asociativo de N-Vías versus Cache de mapeo directo.

• N comparadores Vs. 1 • Retardo adicional del MUX para datos. • El dato llega DESPUES de la decisión HIT/MISS y la selección de la vía

° En el cache de mapeo Directo, el bloque está disponible ANTES del Hit/Miss:

• Es posible suponer un HIT y continuar, se puede reponer si es un MISS

Valid

Cache Tag

:

:

Adr Tag

Compare

Cache Index Cache Data Cache Data Cache Block 0 Cache Block 0

:

:

Sel 1 1

Mux

0 Sel 0

Cache Tag

Valid

:

:

Compare

OR

Hit Cache - D. Cohen

Cache Block

UNT – Arq. de Computadoras - 2014

31

Principales Motivos de Fallos de Cache (Las 3 “C”)

° Compulsivos (inicio “en frío” o cambio a nuevo proceso:primer acceso a un Dato o Instrucción). • Gracias a la localidad de referencia su proporción es muy baja. • Mejora si se agranda el bloque – loc espacial. • Pero a costa de una mayor penalidad, menor localidad temporal

° Conflictos (colisiones): • Múltiples direcciones de Memoria que se mapean al mismo lugar en el cache.

• Solución 1: incrementar tamaño del cache (a costa de Hit Time). • Solución 2: incrementar asociatividad (a costa de Hit Time).

° Capacidad: • El cache no puede contener todos los bloques del programa. • Solución: incrementar la dimensión del cache (a costa Hit Time, Energía y $$$)

° Invalidez: otros procesos (ej: I/O) actualizan MP • Veremos más adelante. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

32

Quiz: Fuentes de Fallos en Cache

Direct Mapped

N-way Set Associative

Fully Associative

Tamaño del Cache: Alto, medio, bajo? Fallos Compulsivos

Fallos de Conflictos Fallos de Capacidad Fallos de Invalidez

Selección: Cero, Bajo, Medio, Alto, igual

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

33

Quiz: Fuentes de Fallos en Cache

Direct Mapped

N-way Set Associative

Fully Associative

Tamaño del Cache: Alto, medio, bajo?

Alto

Medio

Bajo

Fallos Compulsivos

Igual

Igual

Igual

Fallos de Conflictos

Alto

Medio

Cero

Baja

Media

Alta

Igual

Igual

Igual

Fallos de Capacidad Fallos de Invalidez

Selección: Cero, Bajo, Medio, Alto, igual

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

34

Impacto en el Tiempo de Ejecución PC

I -Cache Cache Hit Time: Aumenta con el tamaño de cache Aumenta con asociatividad

miss

IR IRex

A

B

invalid

IRm

R D Cache

Tiempo Promedio de Acceso = Hit Time + Miss Rate x Miss Penalty

IRwb

T

Miss

tiempo ejecuc = CI x T x (CPI ideal + paradas de Mem/Instrucción)

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

35

4 Cuestiones Básicas en Jerarquía de Memorias

1. ¿Donde poner un bloque en el nivel superior? (Ubicación de Bloques) 2. ¿Como encontrar un bloque en el nivel superior? (Identificación de Bloques)

3. ¿Qué bloque reemplazar en caso de fallos? (Reemplazo de Bloques) 4. ¿Qué se hace en caso de escritura? (Estrategia de Escritura)

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

36

1. ¿Donde se ubica un Bloque? ° Ejemplo: Cache de 8 Bloques, ubicar block 12. • Lo marcado en Verde son posibles lugares para la ubicación • Mapeo Directo: 12 Mod 8 = 4 • Mapeo por Conjuntos 12 Mod (N° líneas=4) = 0 0 1 2 3 4 5 6 7

Asociativo

Cache - D. Cohen

0 1 2 3 4 5 6 7

Mapeo Directo

UNT – Arq. de Computadoras - 2014

0 1 2 3

Asociativo por Conjuntos 4 Conjuntos 2 Vías 37

2. ¿Cómo se encuentra a un bloque?

° Rótulo e Indice en cada Bloque. ° El aumento de la asociatividad achica el índice y expande el Rótulo.

Indice

Rótulo

Desplazamiento

Dirección del Bloque

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

38

3. ¿Qué bloque reemplazar en caso de fallos? ° Para Mapeo Directo es fácil.

° Caché Asociativo o Asociativo por Conjuntos: • Cualquiera al azar (Random). • El menos usado próximamente – imposible: no somos adivinos. • El menos usado recientemente = LRU (Least Recently Used)

° Estadísticas de Fallos: Asociatividad Tamaño 16 KB 64 KB 256 KB

Cache - D. Cohen

2 Vías 4 Vías 8 Vías LRU Random LRU Random LRU Random 5.2% 5.7% 4.7% 5.3% 4.4% 5.0% 1.9% 2.0% 1.5% 1.7% 1.4% 1.5% 1.15% 1.17% 1.13% 1.13% 1.12% 1.12%

UNT – Arq. de Computadoras - 2014

39

4. ¿Qué se hace en caso de escritura? ° La lectura es más fácil de manejar que la escritura: • Es más fácil diseñar un cache de Instrucciones que uno de datos.

° Escritura en Cache: • ¿Cómo mantenemos el Cache y MP consistentes?

° Dos Alternativas: • Write Back: escribir solo en el cache. Cuando el bloque se reemplace, entonces se escribe todo el bloque en MP. • Se necesita un “bit de ensuciado” para cada bloque del cache. -

Reduce fuertemente el ancho de banda requerido para MP. El control puede ser complejo.

• Write Through: Escribir simultáneamente en Caché y MP. - ¿Cómo es posible? ¿No era MP muy lenta para esto?

° Ventajas y Desventajas • WT: Menor penalidad cuando se reemplaza el bloque. • WB: Menos Ancho de Banda para MP. Varios Writes  1 Write. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

40

Buffer de Escritura para escritura “a través”.

Processor

Cache

DRAM

Write Buffer

° Se necesita un buffer de escritura entre Cache y MP • CPU: escribe datos en Cache y Write Buffer. • Controlador de Mem: escribe contenido del Buffer en MP.

° El Buffer no es otra cosa que un FIFO: • Número típico de entradas: 4

• Anda bien si: frecuencia escritura 1 / DRAM write cycle • Si esta condición subsiste por períodos largos de tiempo (reloj del CPU muy rápido y/o muchas escrituras muy seguidas): - El Buffer va a saturarse, sin importar cuan grande sea. -

El ciclo equivalente del CPU tiende al ciclo de escritura de DRAM

° Alternativas de Solución: • Cambiar a “Write Back”.

• Instalar un cache de segundo nivel L2. L2 debe usar “Write Back”

Processor

Cache

L2 Cache

DRAM

Write Buffer

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

42

Política de Fallo en Escrituras ° Si se trata de escribir un dato de 16-bits en la dirección 0x0 y resulta un fallo: • ¿Traemos todo el bloque a la Cache (Byte 2, 3, ... 31)? Si: “Write Allocate” No: “Write Not Allocate”

Valid Bit

Example: 0x00

Cache Tag 0x00

:

Cache Data Byte 31 Byte 63

Byte 1 Byte 0 0 Byte 33 Byte 32 1 2 3

:

: Byte 1023

Cache - D. Cohen

4 0 Byte Select Ex: 0x00

UNT – Arq. de Computadoras - 2014

:

Cache Tag

9 Cache Index Ex: 0x00

: :

31

Byte 992 31 43

Ejemplo: El Cache del Pentium Pro • El Pentium Pro tenía 2 caches on-chip — uno para instrucciones y otro para datos. Además tiene un caché de Nivel 2 de 256K. • La dirección efectiva en el Pentium es de 32 bits. • Cada cache es asociativo por conjunto, de 2 vías. • Cada cache tiene un tamaño de 8 K = 213 bytes • Tamaño del Bloque: 32 = 25 bytes. • Hay 2 bloques por línea (26 bytes), 1 bloque por vía, y por lo tanto 213/26 = 27 = 128 líneas o conjuntos. • Esto deja 32 - 5 - 7 = 20 bits para el campo Rótulo: Rótulo

Índice (línea)

20

7

Byte 5

0

31

Esta “aritmética de cache” es importante y hay que manejarla perfectamente L2 único para Instrucciones y Datos. L1 trabaja con Write Back – Early Start. L2 “encapsulado en chip” – mejora tiempo de acceso y disminuye pins. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

44

Ejemplo: Cache del PowerPC 601 (McIntosh) Set of 8

Tag memory

Cache memory

Sector 0

Line 0

Sector 1

Address tag 64 sets 8 words 88 wowrodrsds 8 8ww orodrsds 8 word s

8 words 88 wowrodrsds 8ww orodrsds 64bybtyetse8 s 8wo 6 4 r ds 64 bytes 64 bytes 64 bytes 64 bytes

20 bits Line 63

Physical address:

Tag

Line (set) #

20

6

Byte

6

• El PPC 601 tenía un cache unificado para instrucciones y datos. • Tamaño: 32KB, organizado como 64 x 8 vías- asociativo por conjuntos, con bloks de 16 palabras de 4 bytes c/u organizadas como 2 sectores independientes de 8-palabras (por conveniencia en el proceso de actualización) • Una línea de cache se actualiza en dos operaciones de 1 T, de 1 sector c/u. • Normalmente trabaja por write-back, pero write through puede seleccionarse vía Sw. El cache puede ser deshabilitado también vía SW. • LRU para reemplazo, al igual que Pentium. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

45

Pentium IV ° Algunas versiones avanzadas incluyen L3 on chip

° Xeon: L3 de 1 Mb. P4 Extreme Edition 2 Mb. ° L1 en AMD Opteron • 64 Kb para Datos y 64 Kb para instrucciones

• Asociativo por conjuntos de 2 vías. • Tamaño de Block: 64 bytes. • Write Back. • LRU.

° L2 en AMD Opteron • 1 Mb – unificados Datos e Instrucciones. • Asociativo por conjuntos de 16 vías. • Write Back. • LRU aproximado. • Tamaño Block 64 bytes. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

46

Mejora de la Performance del Cache – 3 Opciones Tiempo Ejecución = IC x T x (CPI ideal + paros de Memoria/Inst.) Tiempo promedio de acceso a Memoria =

Hit Time + (Tasa de Fallos x Penalidad por Fallo)

1. Reducir la tasa de fallos. 2. Reducir la penalidad por fallos. 3. Reducir el tiempo de acierto en el cache.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

47

Tasa de Fallos Absoluta – 3 C - (SPEC92)

Tasa de Fallos

0.14

1-vía

Conflicto (lo que no es verde)

0.12 2-vías

0.1 4-vías 0.08 8-vías

0.06

Capacidad (asociativa pura)

0.04

0.02

128

Tamaño de Cache (KB)

64

32

16

8

4

2

1

0

Compulsiva • Compulsiva: prácticamente 0. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

48

1. Reducir Fallos mediante aumento en el tamaño del Bloque

Miss Rate

25%

Tamaño Cache

20%

1K 4K

15%

16K 10% 64K 5%

256K

256

128

64

32

16

0%

Block Size (bytes) Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

49

2. Reducción de Fallos Mediante mayor Asociatividad ° Cuidado: ¡El tiempo de ejecución es lo que cuenta! • TMAM: Tiempo Medio de Acceso a Memoria. • ¿Aumentará el TMAM con la asociatividad? • Hill [1988] estudió el hit-time para 2-vías Vs. 1-vía: Caché Externo se incrementa en 10%, Vías adicionales en 2%

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

50

Ejemplo: Tiempo Medio de Acceso a Mem vs. Fallos

° Suponga TH = 1.10 para 2 vías, 1,12 para 4 vías, 1,14 para 8 vías Vs. TH=1 para Mapeo directo. Cache Size (KB) 1 2 4 8 16 32 64 128

1-way 2.33 1.98 1.72 1.46 1.29 1.20 1.14 1.10

Associativity TMAM 2-way 4-way 2.15 2.07 1.86 1.76 1.67 1.61 1.48 1.47 1.32 1.32 1.24 1.25 1.20 1.21 1.17 1.18

8-way 2.01 1.68 1.53 1.43 1.32 1.27 1.23 1.20

(Rojo: T Medio de Acceso a Memoria no se mejora con más asociatividad). Hay un límite a la asociatividad. ¿Por qué? Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

51

3. Reducción de Fallos con más Capacidad

° Poner Cachés más grandes: • Mejora fallos por Capacidad. (+) • Es más caro $$$. (-) • Consume más energía. (-) • Aumenta tiempo de acierto. (-)

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

52

4. Reducción de Fallos mediante un caché “Víctima” ° ¿Cómo combinar un buen tiempo de acierto en mapeo directo y evitar fallos por conflicto?

TAGS

DATA

° Agregar un buffer “Víctima” para poner los datos que se descartan del cache.

° Cuando el dato no está en Cache, se busca en el Víctima y si se encuentra se “intercambian” ° Jouppi [1990]: un cache víctima de 4 entradas elimina 20% a 95% de los conflictos en un cache de datos de mapeo directo de 4 KB.

Tag and Comparator

One Cache line of Data

Tag and Comparator

One Cache line of Data

Tag and Comparator

One Cache line of Data

Tag and Comparator

One Cache line of Data To Next Lower Level In Hierarchy

° Se usó en CPUs ALPHA, máquinas HP. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

53

5. Reducción de Fallos mediante Pre-Búsqueda por Hw ° Ej: Instruction Prefetching • Alpha 21064 buscaba 2 bloques en caso de fallo. • El block extra se pone en un “buffer de pendientes” • Si hay un fallo se chequea también el buffer de pendientes.

° Trabaja tambien con bloque de datos: • Jouppi [1990] 1 buffer de pendientes resolvió 25% de los fallos de un cache de 4KB; 4 buffers tomaron 43%

° La pre-búsqueda supone que existe ancho de banda extra para MP que puede usarse sin penalidad adicional.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

54

6. Reducción de Fallos mediante Pre-búsqueda por Sw

° Pre-Búsqueda de Datos • El compilador analiza referencias futuras y provee instrucciones especiales de pre-búsqueda en el programa. • Estas instrucciones cargan el cache en paralelo (mientras no es accedido o bien cache con varios bancos independientes). • Puede ser: cargar datos en registros (Itanium loads). • O también: pre-búsqueda en Cache: Cargar en Cache. (MIPS IV, PowerPC, SPARC v. 9)

° Instrucciones de Pre-Búsqueda toman tiempo • ¿costo de pre-búsqueda < ahorro en menos fallos? • La pregunta vale cuando la pre-búsqueda es especulativa.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

55

7. Reducción de Fallos por Optimización del Compilador ° McFarling [1989] redujo las fallas de cache en 75% en un cache de mapeo directo de 8KB, blocks de 4 Bytes por Software ° Instrucciones • Reordenar los procedimientos en memoria para reducir los fallos por conflictos.

° Datos • Intercambio de Lazos: Cambiar el anidado de lazos para que el lazo interno sea el que acceda a datos con más localidad (ej. Una matriz rectangular, sumar 2 a todos los miembros, lazo interno items vecinos). • Bloqueo: Mejorar la localidad espacial accediendo a bloques de datos de manera repetida antes que pasar columnas o filas enteras.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

56

Veamos ahora como reducir la penalidad por fallos. 1. Reducir tasa de fallos,

2. Reducir Penalidad por fallos. 3. Reducir el tiempo de acierto en el Cache.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

57

1. Reducir Penalidad: DRAM / Interface más rápida

° Nuevas Tecnología de DRAMs ° Mejores interfases con el Bus

° Son temas de Permanente Investigación y Mejoras. ° Se podría poner SRAM solamente (CRAY) pero es muy caro… ¿y entonces eliminar el/los caches? ° Seymour Cray – padre de la supercomputación – procesadores http://www.cray.com/About/History.aspx

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

58

2. Penalidad: En fallos Priorizar lecturas sobre escrituras.

° Las Lecturas paran al CPU, ¡escrituras al buffer! ° Write Through: • Escritura mediante buffers puede producir conflictos RAW con lecturas en MP cuando hay fallos. • Si se esperara a que el buffer de escritura esté vacío antes de leer incrementaría el tiempo del fallo (la vieja MIPS 1000 en 50% ) • Chequear los contenidos del buffer de escritura antes de leer; si no hay conflictos, dejar que el acceso a memoria continúe.

° ¿Write Back? • Fallo de Lectura y hay que reemplazar un bloque “sucio”.

• Normal: escribir el bloque en MP, y recién leer el nuevo block. • Mejor: copiar el bloque “sucio” a un buffer de escritura, entonces realizar la lectura, y recién escribir en MP. • CPU para menos porque recomienza no bien se hace la lectura.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

59

3. Penalidad: Recomienzo temprano, primero la palabra crítica

° No esperar a que el bloque completo se cargue para recomenzar el CPU. • Early restart—No bien llegue la palabra solicitada del bloque al cache, que siga el CPU, mientras tanto se termina de cargar en Cache.

• Palabra crítica primero—Leer de Memoria la palabra buscada primero y dejar que continúe el CPU, a continuación se llena el resto de las palabras del bloque en la Cache.

° Util especialmente con bloques grandes,

° Localidad Espacial: se tiende a buscar la siguiente palabra inmediatamente… por lo que no es claro si realmente mejora. block

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

60

4. Reducción de Penalidad: Cache de Segundo Nivel – L2 ° Ecuaciones para L2 TMAM: Tiempo medio de acceso a Memoria

TMAM = Hit TimeL1 + Miss RateL1 x Miss PenaltyL1 Miss PenaltyL1 = Hit TimeL2 + Miss RateL2 x Miss PenaltyL2 TMAM = Hit TimeL1 + Miss RateL1 x (Hit TimeL2 + Miss RateL2 x Miss PenaltyL2)

° Definiciones: • Tasa de Fallo Local — Cantidad de fallos en el cache dividido en el total de accesos a ese cache (Miss rateL2) • Tasa de Fallo Global — Fallos en el sistema de caches dividido en el número total de accesos a memoria generados por el CPU. (Miss RateL1 x Miss RateL2) • L1 toma la “crema” de la localidad, L2 tiene muchos fallos locales. • Lo que importa es la tasa de fallo global resultante, que es la que nos lleva a la gran penalidad en MP.

Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

61

5. Reducir Penalidad: Cache No Bloqueante ° Cache no bloqueante El cache de datos continua sirviendo accesos de otras instrucciones cuando ocurre un fallo. • Funciona con ejecución fuera de orden. • El fallo se procesa en paralelo (requiere caché multi-vía de acceso).

° “Acierto bajo fallo” reduce la penalidad efectiva de un fallo al seguir sirviendo otros accesos. Penalidad solo el tiempo que está efectivamente parado. ° “Acierto bajo múltiples fallos” o “fallo bajo fallo” solapa múltiples fallos sin bloquear la cache de datos, y reduce aún más la penalidad. • Se incrementa significativamente la complejidad del control del cache. • Requiere múltiples vías de accesos en cache. • Pentium Pro permite hasta 4 fallos pendientes. Cache - D. Cohen

UNT – Arq. de Computadoras - 2014

62

En síntesis: Reducción de Penalidad por Fallos

CPUtime IC

CPI

Exe cuti on

Memory accesses Miss rate Miss penalty Instruction

Clock cycle time

° Supone th