jerarquias de memoria - materias.fi.uba.armaterias.fi.uba.ar/6620/clases/clase4.pdf · Uso de la Clasificación D3C para el Modelo del Lazo Simple Obligatorios Capacidad Conflicto

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?


3

La Brecha CPU-Memoria

1000

10000

100000

Desempeño

CPU

55% por año


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

•


5

• Localidad temporal

La Memoria Local o Memoria Cache

CPUMemoria

PrincipalCPU CacheMemoria


6

CPU PrincipalCPU CacheMemoria

Principal

Estructura Básica de una Jerarquía de Memoria


7


Caches L1 L2 L3


8

Principal

Secundaria



9

Funcionamiento Básico

.

Bloques

.. .


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.


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


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


13

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

5

6

7

Memoria

Cache por





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 {


Asociativa por Conjuntos


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 {


16

Contenido de la Memoria Cache

10110xxxxNúmero

de Bloqueen RAM


17

11010xxxx 10000xxxx

00011xxxx 10010xxxx


18


19

Políticas de reemplazo

� LRU

� FIFO

� RANDOM� RANDOM

� Basadas en Distancias de Pila LRU

� Óptima (Belady 1963)


20

Que pasa en una escritura?

� Políticas de escritura• Write Through

• Write Back

� Miss de escritura, dos casos:• Write Allocate

• Write No-Allocate


21

Ecuación de desempeño de CPUcon Memoria cache


22

Otra Medida de Desempeño

Tiempo Promedio de Acceso a 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


24

Reduccion de Penalidad de MissCaches Multinivel


25

Reduccion de Penalidad de missCritical Word First, Early Restart


26

Reduccion de Penalidad de miss

� Prioridad a Lecturas sobre las escrituras

� Merging Write buffers

� Caches de VíctimasCaches de Víctimas


27

Reducción de la Tasa Miss

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


28

Herramientas de Modelado y Análisis


29

Una Clasificación para los Desaciertos en Memoria Cache

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

• Tipos conceptuales• Obligatorios


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


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


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


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


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

Miss


8Kb

16Kb

32Kb64Kb

SPECint SPECfp


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


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


� Caches más grandes y más asociativas

10

Cache de Datos, SPECint95


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


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)


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

•


38

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

las aplicaciones.



39

Memoria

Lazo



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


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.


� Definiciones• L tamaño del lazo

• C tamaño de la memoria cache

•


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


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


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


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


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)


� Bloques más grandes


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


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


50

Redución del tiempo de hit

� Evitar traducción de páginas

� Cache pipeline

� Trace Caches (intel p4)� Trace Caches (intel p4)


51

Mejorar el ancho de banda de la memoria principal.


52

Intercalado


53

Tecnología DRAM


54


55

DRAM Convencional


56

DRAM de Modo Página Rápido


57

DRAM de Modo Página Rápido(EDO)


58

RAM Sincrónica (SDRAM)


59

Evolución DRAM sincrónica

� SDRAM

� DDR

� DDR2� DDR2

� DDR3

� DDR4, 5, etc (video)


60

Memoria Virtual


61

Memoria Virtual

Antecedentes

� Overlays

� Registro cerco


62

Memoria Virtual Páginada


63

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


64

Comparación parámetrosMemoria Virual–Memoria Cache


65

Mapeo de las Páginas Virtuales

Totalmente


66

TotalmenteAsociativo

Proceso de traducción


67

Solo es necesariotraducir el númerode página

El offset seconcatena

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


68

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


69


70

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


71

CPU TLB

MEMORIA

TLB


72

TLB. Ejemplo


73

Miss en TLB (MIPS)


74

Caches direccionadas pordirecciones físicas


75

CPU TLBMEMORIA

CACHE

TLB y CACHE


76

Index Virtual – Tag Físico


77

Caches direccionadas pordirecciones virtuales


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


79

Paginado vs Segmentado

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


80

Paginado vs Segmentado


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


82

FIN


83

Documents

jerarquias de memoria - materias.fi.uba.armaterias.fi.uba.ar/6620/clases/clase4.pdf · Uso de la Clasificación D3C para el Modelo del Lazo Simple Obligatorios Capacidad Conflicto