jerarquias de memoria - materias.fi.uba.armaterias.fi.uba.ar/6620/clases/clase4.pdf · Uso de la...

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