JERARQUÍAS DE MEMORIA
Organización de Computadoras
Facultad de Ingeniería Universidad de Buenos Aires
10/09/2017 Jerarquías de Memoria 1
Universidad de Buenos Aires
Introducción
Grande y rápida:
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
2
Grande y rápida:
Explotando la
Jeraquía de Memoria
Que significan todos estosParámetros?
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
3
La Brecha CPU-Memoria
1000
10000
100000
Desempeño
CPU
55% por año
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
4
1
10
100
1000
1980 1985 1990 1995 2000 2005
Año
Desempeño
CPU
Memoria35% por año
7% por año
El Principio de Localidad para las Referencias a Memoria
� Los programas referencian la memoria localmente• Localidad espacial
•
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
5
• Localidad temporal
La Memoria Local o Memoria Cache
CPUMemoria
PrincipalCPU CacheMemoria
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
6
CPU PrincipalCPU CacheMemoria
Principal
Estructura Básica de una Jerarquía de Memoria
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
7
Estructura Básica de una Jerarquía de Memoria
Caches L1 L2 L3
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
8
Principal
Secundaria
Estructura Básica de una Jerarquía de Memoria
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
9
Funcionamiento Básico
.
Bloques
.. .
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
10
CPU Cache
Memoria
Principal
Transferencia
de Bloques
Transferencia
de Palabras
Funcionamiento Básico
� La Memoria Cache contiene copias de los bloques de memoria principal.
� Hit: lo buscado por la CPU está en � Hit: lo buscado por la CPU está en cache. Si no está es Miss y se produce una penalidad.
� Trabaja sobre demanda.
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
11
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
0
1
2
3
4
Bloque
Nro.
Bloque
Nro.
...
.
Organizaciones Básicas:
Totalmente Asociativa
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
12
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
5
6
7
Memoria
Cache
Totalmente Asociativa
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
0
1
2
3
4
Bloque
Nro.
Bloque
Nro.Organizaciones Básicas:
Correspondencia Directa
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
13
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
5
6
7
Memoria
Cache por
Correspondencia Directa
Organizaciones Básicas:
Correspondencia Directa
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
14
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
0
1
2
3
4
Bloque
Nro.
Conjunto
Nro.
0 {
1 {
2 {
Organizaciones Básicas:
Asociativa por Conjuntos
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
15
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
5
6
7
Memoria
Cache Asociativa
por Conjuntos
2 {
3 {
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
16
Contenido de la Memoria Cache
10110xxxxNúmero
de Bloqueen RAM
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
17
11010xxxx 10000xxxx
00011xxxx 10010xxxx
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
18
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
19
Políticas de reemplazo
� LRU
� FIFO
� RANDOM� RANDOM
� Basadas en Distancias de Pila LRU
� Óptima (Belady 1963)
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
20
Que pasa en una escritura?
� Políticas de escritura• Write Through
• Write Back
� Miss de escritura, dos casos:• Write Allocate
• Write No-Allocate
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
21
Ecuación de desempeño de CPUcon Memoria cache
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
22
Otra Medida de Desempeño
Tiempo Promedio de Acceso a Memoria:
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
23
Optimizaciones para mejorar el desempeño en sistemas con memoria cache
� Reducir la Penalidad de miss
� Reducir el Miss Rate
� Reducir el tiempo de Hit
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
24
Reduccion de Penalidad de MissCaches Multinivel
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
25
Reduccion de Penalidad de missCritical Word First, Early Restart
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
26
Reduccion de Penalidad de miss
� Prioridad a Lecturas sobre las escrituras
� Merging Write buffers
� Caches de VíctimasCaches de Víctimas
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
27
Reducción de la Tasa Miss
Causas de los misses en memoria cache?Causas de los misses en memoria cache?
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
28
Herramientas de Modelado y Análisis
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
29
Una Clasificación para los Desaciertos en Memoria Cache
� Modelo de las “Tres C” • A favor:
• Tipos conceptuales• Obligatorios
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
30
• Obligatorios• Capacidad• Conflicto
• Muy difundidos
• En contra• A veces da resultados incorrectos• No clasifica individualmente
Metodología Experimental
� Simulaciones manejadas por trazas� Benchmarks SPEC95
• SPECint95:• compress, go, gcc, m88ksim, li, perl, ijpeg, vortex
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
31
• compress, go, gcc, m88ksim, li, perl, ijpeg, vortex• SPECfp95
• applu, apsi, turb3d, su2cor, hydro2d, swim, tomcatv, wave5, mgrid, fppp.
� Trazas• Herramienta: ATOM• Formato: ASF• Logitud: 700 a 1200 millones de instrucciones
Benchmarks SPECint95
Cache de Instrucciones
3
3.5
4
4.5
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
32
0
0.5
1
1.5
2
2.5
3
1 2 4 8 16 32 64 128 256 512 1024 2048
Asociatividad
Miss
Oblig Oblig+Cap Total Oblig+Cap(3C)
8Kb
16Kb
32Kb64Kb
Cache de Instrucciones
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
1 2 4 8 16 32 64 128 256 512 1024 2048
Asociatividad
Miss
Oblig Oblig+Cap Total Oblig+Cap(3C)
8Kb
16Kb
32Kb64Kb
Cache de Instrucciones
0
0,5
1
1,5
2
2,5
1 2 4 8 16 32 64 128 256 512 1024 2048
Asociatividad
Miss
Oblig Oblig+Cap Total Oblig+Cap(3C)
8Kb
16Kb
32Kb64Kb
SPECint SPECfp
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
33
Cache de Datos
0
1
2
3
4
5
6
7
8
9
1 2 4 8 16 32 64 128 256 512 1024 2048
Asociatividad
Miss
Oblig Oblig+Cap Total Oblig+Cap(3C)
8Kb
16Kb
32Kb64Kb
Cache de Datos
02
468
1012
141618
1 2 4 8 16 32 64 128 256 512 1024 2048
Asociatividad
Miss
Obig Obig+Cap Total Obig+Cap(3C)
8Kb16Kb 32Kb
64Kb
SPECint SPECfp
Reducción de la Tasa Miss
� Caches más grandes y más asociativas
10
Cache de Datos, SPECint95
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
34
02468
10
8192 16384 32768 65536
Miss
Tamaño (Bytes)
DM
2W
4W
SW
FA
Reducción de la tasa de miss.Asociatividad mas alta.
� La organización de correspondencia directa sufre de thrashing.
� El esquema asociativo por conjunto lo reduce o elimina.
Otro Modelo: de las Tres C Determinístico “D3C”
• Obligatorios
• Capacidad
• Conflicto
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
36
Definición operacional, se basa en las distancias de pila LRU D:
BDConflicto
BDCapacidad
computablenoDosObligatori
≤
>
→
:
:
:
Con B como la cantidad de bloques en la memoria cache
C
Desaciertos dela cache bajoestudio
Desaciertos de lacache totalmente
asociativa(Capacidad 3C)
Desaciertos de la cache totalmente asociativa infinita
(Obligatorios)
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
37
BU
A
C
Total de referenciasa memoria
Capacidad D3C Conflicto D3C
ABConflicto
CBACapacidad
CosObligatori
¬=
¬=
=
.
..
El Modelo del Lazo Simple
� Aplicaciones con desempeño pobre bajo LRU• Memoria Virtual
•
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
38
• Memoria Cache• Lazos: componente importante en la mayoría de
las aplicaciones.
El Modelo del Lazo Simple
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
39
Memoria
Lazo
El Modelo del Lazo Simple
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
40
Memoria
CacheLazo
Uso de la Clasificación D3C para el Modelo del Lazo Simple
Obligatorios Capacidad Conflicto Total
3C 0 1 -0,4 0,6
D3C 0 0,6 0 0,6
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
41
D3C 0 0,6 0 0,6
Cache LRU asociativa por conjuntos de grado 2, lazo 20% más grande que la memoria cache.
El Modelo del Lazo Simple
� Definiciones• L tamaño del lazo
• C tamaño de la memoria cache
•
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
42
•α=(L-C)/L
� Organizaciones analizadas• Todas las asociatividades
• Políticas de reemplazo LRU/FIFO, Random, Óptima y No Reemplazo
Relación de Desaciertos para el Modelo del Lazo Simple
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
43
Uso de la Clasificación D3C para el Modelo de las Referencias a Memoria al Azar
M
B−1B
−1
Obligatorios Capacidad Conflicto Total
3C 0 0
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
44
M−1
M
B−1
−
−
−
B
M
N
B
NM
B
M 1
3C 0 0
D3C 0 ≠0M
B−1
Uso de la Clasificación D3C para el Caso de la Anomalía de Belady
B = 3 Obligatorios Capacidad Conflicto Total
3C 5 5 -1 9
D3C 5 4 0 9
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
45
B = 4 Obligatorios Capacidad Conflicto Total
3C 5 3 3 10
D3C 5 3 2 10
Secuencia: 0,1,2,3,0,1,4,0,1,2,3,4, cache totalmente asociativa FIFO
Uso de la Clasificación D3C en la Cache de Víctimas
6
8
10
Total
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
46
-2
0
2
4
DM DM + V DM DM + V DM DM + V
Miss
Total
Conf
Cap.
3C D3C
Benchmark Su2cor, cache DM de 8 Kbytes y cache de víctimas de128 bytes (4 bloques de 32 bytes)
Reducción de la Tasa Miss
� Bloques más grandes
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
47
Reducción de Ciclos de stall en cache via paralelismo
� Caches no bloqueantes
� Hardware prefetching
� Software prefetching� Software prefetching• Programa
• Compilador
Opciones
Buffer prefetching
Cache prefetching
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
48
Redución de la tasa de miss. Optimizaciones del Software
� Lectura adelantada (prefetching) de datos e instrucciones.
� Reemplazo de elementos de arreglos por escalares.� Intercambio de bucles.� Operación en bloques (blocking algorithms).� Rellenado de arreglos (array padding).� Reducción de solapamiento (aliasing).
Redución del tiempo de hit
� Caches más pequeñas y más simples
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
50
Redución del tiempo de hit
� Evitar traducción de páginas
� Cache pipeline
� Trace Caches (intel p4)� Trace Caches (intel p4)
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
51
Mejorar el ancho de banda de la memoria principal.
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
52
Intercalado
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
53
Tecnología DRAM
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
54
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
55
DRAM Convencional
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
56
DRAM de Modo Página Rápido
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
57
DRAM de Modo Página Rápido(EDO)
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
58
RAM Sincrónica (SDRAM)
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
59
Evolución DRAM sincrónica
� SDRAM
� DDR
� DDR2� DDR2
� DDR3
� DDR4, 5, etc (video)
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
60
Memoria Virtual
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
61
Memoria Virtual
Antecedentes
� Overlays
� Registro cerco
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
62
Memoria Virtual Páginada
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
63
Memoria Virtual Páginada: tamañosde los espacios virtual y físico
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
64
Comparación parámetrosMemoria Virual–Memoria Cache
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
65
Mapeo de las Páginas Virtuales
Totalmente
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
66
TotalmenteAsociativo
Proceso de traducción
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
67
Solo es necesariotraducir el númerode página
El offset seconcatena
Traducción: tabla de Traducciónde páginas.
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
68
Páginas se alojan en memoriafísica o disco.
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
69
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
70
Técnicas de traducción rápida: TLB (Translation Lookaside Buffer) o cache de traducción de páginas.
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
71
CPU TLB
MEMORIA
TLB
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
72
TLB. Ejemplo
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
73
Miss en TLB (MIPS)
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
74
Caches direccionadas pordirecciones físicas
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
75
CPU TLBMEMORIA
CACHE
TLB y CACHE
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
76
Index Virtual – Tag Físico
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
77
Caches direccionadas pordirecciones virtuales
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
78
CPU TLBMEMORIA
CACHE
Memoria Virtual Segmentada
� Bloques de tamaño variable: segmentos
� Dos palabras por dirección:• Número de segmento.
•• Número de segmento.
• Offset dentro del segmento
� Visible a la arquitectura de programación
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
79
Paginado vs Segmentado
Segmentado: bloques de tamaño variable Dos palabras porDirección: nro segmentoy offset
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
80
Paginado vs Segmentado
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
81
Memoria Virtual
Programa
puede superar
la memoria
fisica
Protección Compartir Direcciones
Virtuales
Overlays xOverlays x
RegistroCerco
x x
Memoria V. Páginada
x x x x
Memoria V. Segmentada
x x x x
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
82
FIN
10/09/2017 Modelización y Simulación de Jerarquías de Memoria
83