jerarquias de memoria -...

Preview:

Citation preview

JERARQUÍAS DE MEMORIA

Organización de Computadoras

Facultad de Ingeniería Universidad de Buenos Aires

14/05/2010 Jerarquías de Memoria 1

Universidad de Buenos Aires2010

Introducción

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

2

La Brecha CPU-Memoria

1000

10000

100000

Des

emp

eño

CPU

55% por año

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

3

1

10

100

1000

1980 1985 1990 1995 2000 2005

Año

Des

emp

eñ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•

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

4

• Localidad temporal

La Memoria Local o Memoria Cache

CPUMemoria

PrincipalCPU CacheMemoria

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

5

CPU PrincipalCPU CacheMemoria

Principal

Funcionamiento Básico

.

Bloques

.. .

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

6

CPU Cache

Memoria

Principal

Transferencia

de Bloques

Transferencia

de Palabras

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

7

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

8

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

5

6

7

Memoria

Cache por

Correspondencia Directa

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

9

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 {

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

10

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

11

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

12

Políticas de reemplazo

� LRU� FIFO� RANDOM� RANDOM� Basadas en Distancias de Pila LRU� Óptima (Belady 1963)

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

13

Que pasa en una escritura?

� Write Through� Write Back

Alocación: -Write Allocate-Write No-Allocate

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

14

Cache Performance

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

15

Ecuación de desempeño de CPUcon Memoria cache

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

16

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

17

Reduccion de Penalidad de missCaches multinivel

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

18

Reduccion de Penalidad de missCritical Word First, Early Restart

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

19

Reduccion de Penalidad de miss

� Prioridad a Lecturas sobre las escrituras� Merging Write buffers� Caches de VíctimasCaches de Víctimas

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

20

Reducción de la Tasa Miss

Causas de los misses en memoria cache?Causas de los misses en memoria cache?

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

21

Herramientas de Modelado y Análisis

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

22

Una Clasificación para los Desaciertos en Memoria Cache

� Modelo de las “Tres C” • A favor:

• Tipos conceptuales• Obligatorios

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

23

• Obligatorios• Capacidad• Conflicto

• Muy difundidos

• En contra• Da resultados incorrectos• No clasifica individualmente

Otro Modelo: de las Tres C Determinístico “D3C”

• Obligatorios• Capacidad• Conflicto

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

24

Definición operacional:

BDConflicto

BDCapacidad

computablenoDosObligatori

>

:

:

:

C

Desaciertos dela cache bajoestudio

Desaciertos de lacache totalmente

asociativa(Capacidad 3C)

Desaciertos de la cache totalmente asociativa infinita

(Obligatorios)

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

25

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•

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

26

• Memoria Cache• Lazos: componente importante en la mayoría de

las aplicaciones.

El Modelo del Lazo Simple

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

27

Memoria

Lazo

El Modelo del Lazo Simple

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

28

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

29

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• α=(L-C)/L

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

30

• α=(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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

31

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

32

M−1

M

B−1

B

M

B

�M

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

33

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

34

-2

0

2

4

DM DM + V DM DM + V DM DM + V

Mis

s

TotalConfCap.

3C D3C

Benchmark Su2cor, cache DM de 8 Kbytes y cache de víctimas de128 bytes (4 bloques de 32 bytes)

Metodología Experimental

� Simulaciones manejadas por trazas� Benchmarks SPEC95

• SPECint95:• compress, go, gcc, m88ksim, li, perl, ijpeg, vortex

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

35

• 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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

36

0

0.5

1

1.5

2

2.5

3

1 2 4 8 16 32 64 128 256 512 1024 2048

Asociatividad

Mis

s

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

Mis

s

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

Mis

s

Oblig Oblig+Cap Total Oblig+Cap(3C)

8Kb

16Kb

32Kb64Kb

SPECint SPECfp

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

37

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

Mis

s

Oblig Oblig+Cap Total Oblig+Cap(3C)

8Kb

16Kb

32Kb64Kb

Cache de Datos

02468

1012141618

1 2 4 8 16 32 64 128 256 512 1024 2048

Asociatividad

Mis

s

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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

38

02468

10

8192 16384 32768 65536

Mis

s

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.

Reducción de la Tasa Miss

� Bloques más grandes

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

40

Reducción de Ciclos de stall en cache via paralelismo

� Caches no bloqueantes� Hardware prefetching� Software prefetching� Software prefetching

• Programa• CompiladorOpciones

Buffer prefetchingCache prefetching

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

41

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).

Optimización de Memoria #1:Lectura Adelantada (prefetching)

� Especula con los accesos futuros a datos e instrucciones.� Se implementa a nivel de hardware o software.� Suficiente un prefetch por bloque de la caché.

Lectura Adelantada (cont.)

� Útil en bucles con patrones de acceso simples (aplicaciones científicas).

� En lenguaje C, es posible realizar una lectura adelantada mediante __builtin_prefetch(), si la arquitectura lo soporta.arquitectura lo soporta.

Desde MIPS IV, se soporta prefetching mediante la

instrucción pref

Lectura Adelantada (cont.)

� ¿Con cuánta anticipación debe leerse un bloque desde memoria principal a caché?

� Si se hace cerca del instante de uso, podría ser tarde.� Conviene aplicarlo con mayor anticipación.� Conviene aplicarlo con mayor anticipación.� Deberá considerarse:

• Cuántos tiempo insume el prefetch.• Cuántos tiempo insume una iteración del bucle.

� Por ejemplo:

TP

TI = 1/3 TP

TP = Tiempo prefetch

TI = Tiempo iteración

Lectura Adelantada (cont.)

� Se debe generar un pipeline para que el bucle no deba esperar.

x[24] … x[31]x[16] …x[23]

x[8] …x[15]

x[0] …x[7]

PROCESAx[0] … x[7]

PROCESAx[8] … x[15]

PROCESAx[16] … x[23]

PROCESAx[24] … x[31] …

x[32] … x[39]

x[40] … x[47]

Distancia d = 3

En general � d = TP / TI

Lectura Adelantada (cont.)24

Agregar una estructura condicional (if..else) o desenrollar el bucle, para no ejecutar el prefetch en todas las iteraciones.

FACTOR DE DESENROLLADO

IGUAL A LA CANT. DE ELEMENTOS POR

BLOQUE DE CACHÉ

Optimización de Memoria #2:Reemplazo de Elem. de Arreglos

� Pocos compiladores intentan mantener los elementos de un arreglo en registros, entre iteraciones sucesivas.

� Reemplazar el elemento de una arreglo por una variable temporal, para que pueda mantenerse en un registro.

Optimización de Memoria #3:Intercambio de Bucles

� Según el lenguaje, un arreglo multidimensional podría almacenarse en memoria, ordenado por filas o por columnas.

Orden por filas(row-major order)

Orden por columnas(column-major order)

Intercambio de Bucles (cont.)

� Se busca acceder al arreglo en pasos unitarios (unit stride).

� Esto permite aprovechar A(1,1)

A(1,2)

A(1,1)

A(2,1)

Orden por filas(row-major order)

Orden por columnas(column-major order)

� Esto permite aprovechar la localidad espacial en la memoria caché de datos.

A(1,3)

A(1,4)

A(2,1)

A(2,2)

A(2,3)

A(2,4)

...

A(3,1)

A(4,1)

A(1,2)

A(2,2)

A(3,2)

A(4,2)

...

Intercambio de Bucles (cont.)

� C/C++, Java, Pascal utilizan row-major order.� Fortran y versiones viejas de BASIC, utilizan

column-major order.� Por lo tanto, deben intercambiarse los bucles, de ser � Por lo tanto, deben intercambiarse los bucles, de ser

necesario:

Intercambio de Bucles (cont.)

Usando row-major order:

Desaciertos de escritura en la matriz (1 cada 8 escrituras)

Intercambio de Bucles (cont.)

Usando column-major order:

Desaciertos de escritura en la matriz (8 cada 8 escrituras)

Optimización de Memoria #4:Operación en Bloques

� Permite decrementar la cantidad de desaciertos de

capacidad cuando se opera con arreglos grandes.� Mejora la localidad temporal (mantiene en la

caché, datos que se usarán en el corto plazo).caché, datos que se usarán en el corto plazo).

Operación en Bloques (cont.)

� Ejemplo: multiplicación de matrices.� Elevada cantidad de desaciertos.� Para una caché 2WSA 2-KB con bloques de 32

bytes, multiplicar dos matrices de 64x64 bytes, multiplicar dos matrices de 64x64 enteros, produce una tasa de desaciertos del 11,3%

Operación en Bloques (cont.)

� Solución: operar en bloques pequeños.� Se reducen los accesos conflictivos, ya que los bloques

pequeños pueden ser mantenidos en la caché.

Operación en Bloques (cont.)

2WSA 2-KB (bloque de 32 bytes)

Optimización de Memoria #5:Rellenado de Arreglos (padding)

� Suma de matrices.

C(0,0)

C(0,1)

C(0,2)

0x00000080

0x00000084

0x00000088

...C

(64 bytes)

A(0,0)

A(0,1)

A(0,2)

...

B(0,0)

B(0,1)

B(0,2)

...

0x00000000

0x00000004

0x00000008

0x00000040

0x00000044

0x00000048

A(64 bytes)

B(64 bytes)

Rellenado de Arreglos (cont.)

Memoria caché DM64 bytes8 bytes por línea

THRASHING

Rellenado de Arreglos (cont.)

Memoria caché DM64 bytes8 bytes por línea

Rellenado de Arreglos (cont.)� Se cambia la forma en que los arreglos son almacenados

en memoria principal.� Reduce los accesos conflictivos.� Disminuye el thrashing y, por consiguiente, la cantidad de � Disminuye el thrashing y, por consiguiente, la cantidad de

desaciertos.� Como desventaja, utiliza mayor cantidad de memoria.

Rellenado de Arreglos (cont.)Sin rellenado:

Desaciertos de escritura en la matriz (8 cada 8 escrituras)

Desaciertos de lectura (8 cada 8 lecturas)

Rellenado de Arreglos (cont.)Con rellenado:

Rellenos

Desaciertos de escritura en la matriz C (1 cada 8 escrituras)

Desaciertos de lectura de matrices A y B (1 cada 8 lecturas)

Algo sobre Valgrind

� Herramienta para profiling y debugging.� Site: http://valgrind.org/� Soporta cualquier lenguaje compilado.

Pública y de código abierto.� Pública y de código abierto.� Aplica la técnica de instrumentación dinámica de código.� Ejemplo de ejecución:

valgrind --tool=<tool> my_prog

Algo sobre Valgrind (cont.)� Cachegrind es el módulo para simulación de memorias

caché.� Junto con la herramineta cg_annotate, es posible

detectar el origen de los desaciertos en caché.$ valgrind --tool=cachegrind --D1=2048,2,32 prueba$ valgrind --tool=cachegrind --D1=2048,2,32 prueba

(genera un archivo cachegrind.out.<pid>)

$ cg_annotate --<pid> prueba.c

IMPORTANTE: no olvidar compilar prueba.c utilizando la opción -g para incluir información de debugging útil para Valgrind).

Redución del tiempo de hit

� Caches más pequeñas y más simples

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

66

Redución del tiempo de hit

� Evitar traducción de páginas� Cache pipeline� Trace Caches (intel p4)� Trace Caches (intel p4)

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

67

Mejorar el ancho de banda de la memoria principal.

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

68

Intercalado

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

69

Tecnología DRAM

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

70

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

71

DRAM Convencional

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

72

DRAM de Modo Página Rápido

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

73

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

74

RAM Sincrónica

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

75

Evolución DRAM sincrónica

� SDRAM� DDR� DDR2� DDR2� DDR3� DDR4, 5, etc (video)

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

76

Memoria Virtual

Programa > memoriafisica

Protección Compartir DireccionesVirtuales

Overlays x

RegistroCerco

x x

Memoria V. Páginada

x x x x

Memoria V. Segmentada

x x x x

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

77

Memoria Virtual Páginada

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

78

Memoria Virtual Páginada: tamañosde los espacios virtual y físico

14/05/2010 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

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

80

Comparación parámetrosMemoria Virual–Memoria Cache

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

81

Paginado vs Segmentado

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

82

Mapeo de las Páginas Virtuales

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

83

Proceso de traducción

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

84

Traducción: tabla de Traducciónde páginas.

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

85

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

86

Páginas se alojan en memoriafísica o disco.

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

87

Técnicas de traducción rápida: TLB (Translation Lookaside Buffer) o cache de traducción de páginas.

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

88

CPU TLB

MEMORIA

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

89

TLB. Ejemplo

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

90

Miss en TLB (MIPS)

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

91

TLB y CACHE

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

92

Index Virtual – Tag Físico

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

93

Caches direccionadas pordirecciones virtuales

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

94

CPU TLBMEMORIA

CACHE

FIN

14/05/2010 Modelización y Simulación de Jerarquías de Memoria

95

FIN

Recommended