jerarquias de memoria - materias.fi.uba.armaterias.fi.uba.ar/6620/clases/jerarquias_de_memoria.pdf · Reemplazar el elemento de una arreglo por una variable temporal, para que pueda

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


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•


4

• Localidad temporal

La Memoria Local o Memoria Cache

CPUMemoria

PrincipalCPU CacheMemoria


5

CPU PrincipalCPU CacheMemoria

Principal

Funcionamiento Básico

.

Bloques

.. .


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


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


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


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 {


10


11


12

Políticas de reemplazo

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


13

Que pasa en una escritura?

� Write Through� Write Back

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


14

Cache Performance


15

Ecuación de desempeño de CPUcon Memoria cache


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


17

Reduccion de Penalidad de missCaches multinivel


18

Reduccion de Penalidad de missCritical Word First, Early Restart


19

Reduccion de Penalidad de miss

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


20

Reducción de la Tasa Miss

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


21

Herramientas de Modelado y Análisis


22

Una Clasificación para los Desaciertos en Memoria Cache

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

• Tipos conceptuales• Obligatorios


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


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)


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•


26

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

las aplicaciones.



27

Memoria

Lazo



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


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.


� Definiciones• L tamaño del lazo• C tamaño de la memoria cache• α=(L-C)/L


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


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


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


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


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


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


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


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


8Kb

16Kb

32Kb64Kb


0

0,5

1

1,5

2

2,5

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

Asociatividad

Mis

s


8Kb

16Kb

32Kb64Kb

SPECint SPECfp


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


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


� Caches más grandes y más asociativas

10

Cache de Datos, SPECint95


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.


� Bloques más grandes


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


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


� ¿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


� 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[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)

...


� 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:


Usando row-major order:

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


Usando column-major order:


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%


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

pequeños pueden ser mantenidos en la caché.


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


66

Redución del tiempo de hit

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


67

Mejorar el ancho de banda de la memoria principal.


68

Intercalado


69

Tecnología DRAM


70


71

DRAM Convencional


72

DRAM de Modo Página Rápido


73


74

RAM Sincrónica


75

Evolución DRAM sincrónica

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


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


77

Memoria Virtual Páginada


78

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


79

Paginado vs Segmentado

Segmentado: bloques de tamaño variable Dos palabras porDirección: nro segmentoy offset


80

Comparación parámetrosMemoria Virual–Memoria Cache


81

Paginado vs Segmentado


82

Mapeo de las Páginas Virtuales


83

Proceso de traducción


84

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


85


86

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


87

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


88

CPU TLB

MEMORIA


89

TLB. Ejemplo


90

Miss en TLB (MIPS)


91

TLB y CACHE


92

Index Virtual – Tag Físico


93

Caches direccionadas pordirecciones virtuales


94

CPU TLBMEMORIA

CACHE

FIN


95

FIN

Documents

jerarquias de memoria - materias.fi.uba.armaterias.fi.uba.ar/6620/clases/jerarquias_de_memoria.pdf · Reemplazar el elemento de una arreglo por una variable temporal, para que pueda