ISI374 – Arquitectura de Computadores
Clase 21: Jerarquía de memoria Pt.3
Departamento de Ingeniería de Sistemas
Universidad de Antioquia
2010-1
2
Resumen
Estimación del rendimiento de la cache
 Tiempo medio de acceso a memoria
 Caches asociativas
 Políticas de reemplazo
 Modelo de las tres C’s
 Caches multinivel
ISI374 - Arquitectura de Computadores (2010-1)

3
Estimación del rendimiento de la cache

Componentes del tiempo de CPU
ISI374 - Arquitectura de Computadores (2010-1)

Ciclos de ejecución del programa
»
Asumiendo que el tiempo de acierto en la cache hace parte de ellos
Ciclos de espera por el sistema de memoria
 Debidos principalmente a fallos de cache

CPU Time = (CPU execution clock cycles + Memory-stall clock cycles)
× Clock cycle time

Los ciclos de parada de memoria se estiman como la suma de los ciclos de
parada asociados con lecturas y escrituras:
Read-stall cycles = reads/program × read miss rate × read miss penalty
 Write-stall cycles = (writes/program × write miss rate × write miss penalty) +
write buffer stalls


De manera muy simplificada tenemos:

Memory-stall cycles = memory accesses/program × miss rate × miss penalty
4
Impacto del rendimiento de la cache
ISI374 - Arquitectura de Computadores (2010-1)

La penalización relativa de la cache se incrementa a medida que se incrementa el
rendimiento del procesador (mayor frecuencia de reloj y/o menor CPI)


Es poco probable que la memoria mejore tanto como puede hacerlo el tiempo de ciclo del
procesador. Cuando se calcula CPIstall, la penalización de fallo de cache se estima en
términos de ciclos de reloj del procesador necesarios para tratar el fallo
Entre menor sea el CPIideal, mayor será el impacto de las paradas
Ejemplo:
 Procesador con CPIideal = 2 (no hay paradas de memoria), penalización de fallo = 100
ciclos, 36% de instrucciones load/store y tasa de fallos en D$ e I$ de 4% y 2%,
respectivamente
Memory-stall cycles = Instruction-stall_cycles + Data-stall_cycles
Memory-stall cycles = (I × 2% × 100) + (I × 36% × 4% × 100 ) = 3.44 × I
CPIstall = 2 + 3.44 = 5.44 (el rendimiento con la cache perfecta es 5.44/2 = 2.72 veces mejor)
Qué pasa si el rendimiento del procesador se incrementa de manera que el CPIideal se
reduce a 1?
 Qué sucede si se dobla la frecuencia del procesador (doblando la penalización del
fallo)?

5
Tiempo medio de acceso a memoria
Hasta ahora, asumimos que el tiempo de acierto no influye en el rendimiento
de la cache
 Una cache de mayor tamaño tendrá un tiempo de acceso mayor
 En pipelines profundos, un incremento en el tiempo de acierto probablemente
obligará a agregar una nueva etapa
 En algún punto, el incremento en el tiempo de acierto para una cache de
mayor tamaño predominará sobre lo ganado en tasa de aciertos, degradando
el rendimiento
ISI374 - Arquitectura de Computadores (2010-1)


Average Memory Access Time (AMAT): tiempo medio de acceso a memoria
considerando tanto los aciertos como los fallos
AMAT = Hit time + Miss rate × Miss penalty

Ej: Cuál es el AMAT para un procesador con un tiempo de ciclo de reloj de 20
ns, una penalización de fallo de 50 ciclos de reloj, una tasa de aciertos del 98%
por instrucción y un tiempo de acierto de 1 ciclo de reloj?
6
Técnicas para mejorar el rendimiento de la cache
ISI374 - Arquitectura de Computadores (2010-1)

Tiempo medio de acceso a memoria (Average memory access time, AMAT)
AMAT = Hit time + Miss rate × Miss penalty
Dos técnicas para mejorar el rendimiento de la cache se enfocan en reducir:

Miss rate


Reduciendo la probabilidad de que dos bloques diferentes de memoria compitan
por la misma ubicación en la cache (Asociatividad)
Miss penalty

Agregar un nivel adicional a la jerarquía (Caches multinivel)
7
ISI374 - Arquitectura de Computadores (2010-1)
Caches asociativas

¿En qué lugar se puede ubicar un bloque en la cache?

Cache de emplazamiento directo (Direct-mapped cache):


Un bloque puede ocupar sólo un lugar en la cache
Completamente asociativa (Fully associative)
Un bloque puede ocupar cualquier entrada en la cache
 Para encontrar un bloque es necesario buscar en todas las entradas (en paralelo)
 Requiere un comparador por cada entrada (muy costoso)


Asociativa por conjuntos de n-vías (n-way set associative)
Cada conjunto posee n bloques (vías)
 Cada bloque en memoria se mapea a un único conjunto de la cache, pero el
bloque se puede ubicar en cualquiera de las n vías de ese conjunto

»
Número de conjunto en cache = (Dirección del bloque) mod (# conjuntos en la cache)
Todas las vías en un conjunto se buscan a la vez
 n comparadores (menos costoso)

8
Gama de asociatividad
Cuatro configuraciones diferentes para una cache con 8 bloques
 El tamaño de la cache (en bloques) es igual al número de conjuntos por el
grado de asociatividad
ISI374 - Arquitectura de Computadores (2010-1)


La ventaja de incrementar la asociatividad es que normalmente reduce la tasa
de fallos
9
ISI374 - Arquitectura de Computadores (2010-1)
Ejemplo de asociatividad

Comparación de memorias cache con tamaño de 4 bloques y 1 palabra/bloque
 Direct-mapped, 2-way set associative, fully associative
 Secuencia de acceso a bloques: 0, 8, 0, 6, 8 (direcciones de bloque)

Direct-mapped
Block
address
0
8
0
6
8
Cache
index
Hit/miss
0
Cache content after access
1
2
3
10
ISI374 - Arquitectura de Computadores (2010-1)
Ejemplo de asociatividad

Comparación de memorias cache con tamaño de 4 bloques y 1 palabra/bloque
 Direct-mapped, 2-way set associative, fully associative
 Secuencia de acceso a bloques: 0, 8, 0, 6, 8 (direcciones de bloque)

Direct-mapped
Block
address
0
8
0
6
8
Cache
index
0
0
0
2
0
Hit/miss
miss
miss
miss
miss
miss
Cache content after access
0
1
2
Mem[0]
Mem[8]
Mem[0]
Mem[0]
Mem[6]
Mem[8]
Mem[6]
3
11
ISI374 - Arquitectura de Computadores (2010-1)
Ejemplo de asociatividad

Comparación de memorias cache con tamaño de 4 bloques y 1 palabra/bloque
 Direct-mapped, 2-way set associative, fully associative
 Secuencia de acceso a bloques: 0, 8, 0, 6, 8 (direcciones de bloque)

2-way associative
Block
address
0
8
0
6
8
Cache
set
Hit/miss
Cache content after access
Set 0
Set 1
12
ISI374 - Arquitectura de Computadores (2010-1)
Ejemplo de asociatividad

Comparación de memorias cache con tamaño de 4 bloques y 1 palabra/bloque
 Direct-mapped, 2-way set associative, fully associative
 Secuencia de acceso a bloques: 0, 8, 0, 6, 8 (direcciones de bloque)

2-way associative
Block
address
0
8
0
6
8
Cache
set
0
0
0
0
0
Hit/miss
miss
miss
hit
miss
miss
Cache content after access
Set 0
Set 1
Mem[0]
Mem[0] Mem[8]
Mem[0] Mem[8]
Mem[0] Mem[6]
Mem[8] Mem[6]
13
ISI374 - Arquitectura de Computadores (2010-1)
Ejemplo de asociatividad

Comparación de memorias cache con tamaño de 4 bloques y 1 palabra/bloque
 Direct-mapped, 2-way set associative, fully associative
 Secuencia de acceso a bloques: 0, 8, 0, 6, 8 (direcciones de bloque)

Fully associative
Block
address
0
8
0
6
8
Hit/miss
Cache content after access
14
ISI374 - Arquitectura de Computadores (2010-1)
Ejemplo de asociatividad

Comparación de memorias cache con tamaño de 4 bloques y 1 palabra/bloque
 Direct-mapped, 2-way set associative, fully associative
 Secuencia de acceso a bloques: 0, 8, 0, 6, 8 (direcciones de bloque)

Fully associative
Block
address
0
8
0
6
8
Hit/miss
miss
miss
hit
miss
hit
Cache content after access
Mem[0]
Mem[0]
Mem[0]
Mem[0]
Mem[0]
Mem[8]
Mem[8]
Mem[8]
Mem[8]
Mem[6]
Mem[6]
15
Ejemplo de asociatividad
Para la secuencia de referencias, tres fallos es lo mejor que se puede lograr
(porque sólo se accede a tres direcciones de bloque diferentes)
 Si la cache fuera de 8 bloques, la cache asociativa de dos vías no tendría
reemplazos
ISI374 - Arquitectura de Computadores (2010-1)



El número de fallos sería el mismo que el de la cache completamente asociativa
De la misma manera, si la cache tuviera 16 bloques, las tres configuraciones
previas de cache tendrían el mismo número de fallos
Compruébelo usted mismo!

Conclusión:
El cambio observado en la tasa de fallos demuestra que el tamaño de la cache
y la asociatividad no son independientes a la hora de determinar el
rendimiento de la cache
16
¿Cuánta asociatividad?

Incrementar la asociatividad reduce la tasa de fallos
ISI374 - Arquitectura de Computadores (2010-1)


Aunque el retorno es cada vez menor a medida que la asociatividad crece
Simulación de un sistema con D-cache de 64KB, bloque de 16 palabras
(SPEC2000)
1-way (Direct-mapped):
 2-way:
 4-way:
 8-way:

10.3%
8.6%
8.3%
8.1%
17
Organización de una cache asociativa por conjuntos
Asociativa por conjuntos de 4 vías
 Bloque de una palabra. 4 bloques por conjunto. 256 conjuntos
ISI374 - Arquitectura de Computadores (2010-1)

18
Beneficios de las caches asociativas por conjuntos
ISI374 - Arquitectura de Computadores (2010-1)

La elección de una cache de emplazamiento directo o una cache asociativa
por conjuntos depende de la relación entre el costo de un fallo y el costo de la
implementación, tanto en tiempo como en hardware
Mayor asociatividad significa mayor complejidad del hardware
 Una cache con gran asociatividad tendrá una menor tasa de fallos

»
Menor posibilidad de conflicto entre dos direcciones que mapeen al mismo conjunto
19
Políticas de reemplazo
ISI374 - Arquitectura de Computadores (2010-1)

Cuando ocurre un fallo, cómo se define el bloque a reemplazar?
Política de reemplazo
Emplazamiento directo (Direct-mapped): no hay elección
 Asociativa por conjuntos

Varios bloques son candidatos a reemplazarse en cada conjunto (en la cache
completamente asociativa, todos los bloques son candidatos)
 Preferiblemente se reemplaza la entrada no válida, si hay alguna
 De otra manera, elegir entre las entradas del conjunto siguiendo algún criterio


Least-recently used (LRU)
»

Elegir el bloque que más tiempo ha estado sin ser referenciado
 Simple para 2 vías, manejable para 4 vías, muy compleja más allá de este punto
Random
»
»
El bloque se elige aleatoriamente
Entrega aproximadamente el mismo rendimiento que LRU cuando el tamaño de la
cache y la asociatividad son altas
20
ISI374 - Arquitectura de Computadores (2010-1)
Políticas de reemplazo: LRU vs. Random

Fallos de cache de datos por cada 1000 instrucciones para comparar las
políticas LRU y Random (SPEC2000)

16 bytes/block
Associativity
2-way
4-way
8-way
Cache size
LRU
Random
LRU
Random
LRU
Random
16 KB
114.1
117.3
111.7
115.1
109.0
111.8
64 KB
103.4
104.3
102.4
102.3
99.7
100.5
256 KB
92.2
92.1
92.1
92.5
92.1
92.1
21
ISI374 - Arquitectura de Computadores (2010-1)
Modelo de las tres

Modelo de la memoria cache para comprender el origen de los fallos en una
jerarquía de memoria y cómo son afectados estos fallos por cambios
introducidos en ella

Compulsory misses
Fallos causados por el primer acceso al bloque: hay que llevar el bloque a la cache
(cold-start misses)
 Inevitables, incluso con cache de tamaño infinito


Capacity misses
Fallos causados cuando la cache (aún siendo completamente asociativa) no puede
contener todos los bloques necesarios durante la ejecución de un programa
 Ocurren cuando los bloques son reemplazados y luego traídos otra vez a la cache


Conflict misses

Fallos que ocurren en las caches de emplazamiento directo y asociativas por
conjuntos cuando varios bloques compiten por el mismo conjunto (y que se
eliminarían usando una cache completamente asociativa del mismo tamaño)
(collision misses)
22
Modelo de las tres C’s
ISI374 - Arquitectura de Computadores (2010-1)

SPEC2000 integer and FP benchmarks
Conflict
Conflicto:
- Competencia por el
mismo bloque de
cache
- Se reducen
incrementando
asociatividad
Capacidad:
Depende del tamaño
de la cache
Compulsory: 0.006%
23
Caches multinivel
Para reducir la brecha entre la frecuencia de reloj del procesador y el enorme
tiempo necesario para acceder a la DRAM, muchos procesadores poseen
niveles adicionales de cache
 El objetivo es reducir la penalización del fallo
ISI374 - Arquitectura de Computadores (2010-1)


Cache primaria (L-1) unida a la CPU


Pequeña pero veloz
El segundo nivel de cache (L-2) es accedido cuando hay un fallo en la cache
primaria
Más grande, más lenta, pero aún más veloz que memoria principal
 Si hay un acierto en L-2, la penalización del fallo de L-1 será el tiempo de acceso a
L-2 (que será mucho menor que el tiempo de acceso a memoria principal)

La memoria principal atiende los fallos de la cache L-2
 Algunos sistemas high-end incluyen una cache L-3

AMD Phenom II X4 920 Deneb: L-1: 512 KB /
L-2: 2048 KB / L-3: 6144 KB (USD$236)
 Intel Core i7-975 XE Bloomfield: L-1: 256KB /
L-2: 1024KB / L-3: 8192KB (~USD$1000)

24
Ejemplo caches multinivel

Dado:
CPU con CPI base = 1, frecuencia de reloj = 4GHz (periodo = 0.25ns)
 Tiempo de acceso a memoria principal (incluye tratamiento del fallo) = 100ns
 Tasa de fallos/instrucción (Cache primaria) = 2%
ISI374 - Arquitectura de Computadores (2010-1)


Solamente con cache primaria

Penalización de fallo respecto a memoria principal
= 100ns/(0.25ns/ciclo) = 400 ciclos

CPI efectivo = CPI base + Ciclos de parada de memoria por instrucción
CPI efectivo = 1 + 0.02 × 400 = 9
25
Ejemplo caches multinivel (cont.)

Ahora con cache L-2 que tiene estas características:
Tiempo de acceso = 5ns
 Tamaño suficiente para tener una tasa de fallos respecto a memoria principal de
0.5%
ISI374 - Arquitectura de Computadores (2010-1)


Fallo en cache primaria con acierto en L-2


Penalización = 5ns/(0.25ns/ciclo) = 20 ciclos
Fallo en L-2 que obliga acceso a memoria principal:

Penalización = 100ns/(0.25ns/ciclo) = 400 ciclos
CPI total = 1 + Paradas L-1 por instrucción + Paradas L-2 por instrucción
 CPI total = 1 + 0.02 × 20 + 0.005 × 400 = 3.4


Relación de rendimiento= 9/3.4 = 2.6

El procesador con una cache L-2 es 2.6 veces más rápido
26
Consideraciones sobre caches multinivel

Cache primaria
ISI374 - Arquitectura de Computadores (2010-1)


Su objetivo principal es reducir el tiempo de acierto (y así soportar un tiempo de
ciclo más reducido)
Segundo nivel de cache (L-2)
Se enfoca en reducir la tasa de fallos para reducir la penalización de los accesos
tan lentos a memoria principal
 El tiempo de acierto de L-2 es menos importante (afecta la penalización de fallo de
L-1 pero no su tiempo de acierto)


En comparación con una cache de un solo nivel, en la cache multinivel:
La cache L-1 suele ser más pequeña
 El tamaño de bloque de la cache L-1 suele ser pequeño (para estar acorde con el
menor tamaño de cache y la penalización de fallos reducida)

27
Lecturas recomendadas
Computer organization and architecture. Designing for performance, 6th ed.,
Chapter 4. W. Stallings. Pearson Education
 Computer organization and design. The hardware/software interface, 3rd ed.,
Chapter 7. D. Patterson and J. Hennessy. Morgan Kaufmann Publishers
ISI374 - Arquitectura de Computadores (2010-1)

Descargar

AC20101-c21-18nov2010