Organización del Computador I Verano

Jerarquía de MemoriaBasado en el capítulo 7 del libro de Patterson y Hennessy

Verano 2004 Profesora Borensztejn

Memoria

• Los registros y los bancos de registros se utilizan para la construcción de memorias pequeñas.

• Las memorias mas grandes se realizan mediante:– SRAM: Static Random Access Memory– DRAM: Dynamic Random Access Memory

SRAM• Se llaman de acceso aleatorio porque el tiempo de acceso

para acceder cualquier dato es fijo.

• Cada celda de memoria SRAM es básicamente como el biestable D que estudiamos en clases pasadas.

SRAM

32K x 88

8

15Dirección

D entradaD salida

CS OEWE

• 3 líneas de control

• WE: Write Enable

• CS: Chip Select

• OE: Output Enable

• 15 líneas de dirección

• 8 líneas de datos de entrada

• 8 líneas de datos de salida

SRAM• Para iniciar un acceso de lectura o escritura, la señal CS debe estar activa.• Para realizar una lectura:

– debe activarse la señal OE, que es útil cuando se conectan varios chips de memoria, y sirve para determinar cual de ellos accede al bus.

– El tiempo de acceso de lectura de una memoria SRAM es el tiempo desde que se activa OE, y las líneas de dirección son válidas, hasta que el dato está presente en las salidas. Suele ser del orden de los 5nseg.

SRAM

32K x 88

8

15Dirección

D entradaD salida

CS OEWE • Para realizar una escritura– debe activarse la señal WE durante

un tiempo mínimo, y el dato y su dirección deben estar disponibles durante un tiempo antes (setup time) y mantenerse durante un tiempo posterior (hold time) a la activacion de la señal WE

– El tiempo para completar una escritura se especifica como una combinación del setup time, hold time y la duración de la señal WE.

SRAM• Si bien se construyen con biestables D, igual que los

registros, para seleccionar la salida no se usa un multiplexor. Seria demasiado grande! (multiplexor de 32K a 1!)

• Se realizan mediante una línea de salida compartida entre varias celdas de memoria. Cada celda tiene su salida implementada con un buffer tri-estado:

Selección 1

Selección 3

Selección 2

Selección 0

Dato 3

Dato 2

Dato 1

Dato 0

Entrada

Entrada

Entrada

Entrada

Salida

Salida

Salida

Salida

Salida

Permiso

Permiso

Permiso

Permiso

0

1

2

3

Permiso

DC Q

Permiso

DC Q

Permiso

DC Q

Permiso

DC Q

Permiso

DC Q

Permiso

DC Q

Permiso

DC Q

Permiso

DC Q

D entrada(1) D entrada(0)

D salida(1) D salida(0)

WE

Dirección

SRAM de 4x2

DRAM• En las DRAM el valor almacenado se mantiene como una

carga en un capacitor.

• El transistor permite acceder al valor almacenado en el capacitor.

Word line

Pass transistor

Capacitor

Bit line

• Para escribir:

• Cuando la señal de línea de palabra está activada, el transistor se abre conectando el capacitor con la línea de bit.

• Si el valor de la línea es 1, el capacitor se carga.

• Si el valor de la línea es 0, se descarga.

DRAM

Word line

Pass transistor

Capacitor

Bit line

• Para leer: • Se carga la línea de bit con un valor medio entre el voltaje alto

y bajo

• Se activa la línea de palabra, abriendo el transistor.

• La carga del capacitor se mueve hacia la línea de bit, provocando un cambio en ella.

• Se mide el cambio y se detecta si era un cero o un uno dependiendo de hacia donde se movió el voltaje en la línea de bit.

• La lectura es destructiva! Se descargó el capacitor volver a escribirlo.

DRAMrow

decoder

rowaddress

Column Selector & I/O Circuits Column

Address

data

RAM Cell Array

word (row) select

bit (data) lines

– Selecciona un bit

Cada intersección representa un bit

DRAM• Direccionamiento de dos niveles: primero se le da la dirección de fila y luego

la de columna.– La dirección de fila activa la línea de palabra y todas las columnas se almacenan en

un conjunto de cerrojos.– La dirección de columna selecciona el bit.

• El tiempo de acceso es mas grande que en las SRAM, del orden de 5 a 10 veces mas.

• Además, los capacitores pierden carga y es necesario refrescar los contenidos.• Ocupa menos área por bit que la SRAM• Es mas barata.

DRAM

256K x 8

8

9Dirección D entrada

D salidaCAS

OEWE

RAS

Jerarquía de Memoria• Los usuarios quieren una memoria

rápida e infinita.

• Las tres tecnologías de fabricación de memoria varían en precio y tiempo de acceso:

– Tiempo de Acceso:

• SRAM: 5-25 nseg

• DRAM: 60-120 nseg

• Disco magnético: 10-20 millones nseg.

– Precios:

• SRAM: $100-$250 por Mbyte

• DRAM: $5-$10 por Mbyte

• Disco magnético: $0,10-$0,20

CPU

Level n

Level 2

Level 1

Levels in thememory hierarchy

Increasing distance from the CPU in

access time

Size of the memory at each level

Darle la máxima capacidad con la tecnología mas barata al mismo tiempo que se le proporciona acceso a la velocidad mas rápida

Localidad

• Es el principio que hace que la jerarquía de memoria sea una buena idea– Si un dato es referenciado:

• Localidad temporal: volverá a ser referenciado pronto• Localidad espacial: datos cercanos al actual serán inmediatamente

referenciados

• La localidad es una característica de los programas y de sus datos! – El código.....suele tener mucha localidad espacial y/o temporal. – Los datos que referencia dicho código.....depende del programa

Jerarquía de Memoria

• La jerarquía de memoria puede estar compuesta por varios niveles:– Las transferencias de información se dan entre niveles

adyacentes– La unidad mínima de información que se transfiere

entre dos niveles (el inferior y el superior) se llama bloque.

– Hit (Acierto): el dato buscado está en el nivel superior– Miss (Fallo): el dato buscado NO está en el nivel

superior.

Jerarquía de Memoria

Control

Datapath

SecondaryStorage(Disk)

Processor

Registers

MainMemory(DRAM)

SecondLevelCache

(SRAM)

On

-Ch

ipC

ache

1 10,000,000s (10s ms)

Speed (ns): 10s 100s

100sGs

Size (bytes): Ks Ms

Memoria caché Memoria virtual

Memorias Cachés

• Ideado por Wilkes, 1960. Las llamó memorias esclavas.• Actualmente se implementan con SRAM.• Principio de operación:

– La CPU pide un dato– El dato se busca en la caché

• Si no está (Miss)– El dato se trae a la memoria caché y se entrega a la CPU

• Si está (Hit)– El dato se entrega a la CPU

• Dos preguntas:– ¿Como se sabe si el dato está o no en la caché?– Y si está, ¿como se localiza?

• ¿Donde se ubica un dato? En una posición única de la caché.

• ¿Como se asigna esa posición única? En relación con la dirección del dato en memoria.

• Supongamos que el dato constituye un bloque

Caché de Mapeo Directo

Dirección del bloque en caché =(dirección del bloque en memoria) módulo (número de bloques de la caché)

• Si el número de bloques en caché es una potencia de 2, la operación módulo es simplemente quedarse con los log2 bits de menor peso de la dirección.

Caché de Mapeo Directo

00001 00101 01001 01101 10001 10101 11001 11101

000

Cache

Memory

001

01

001

11

001

011

101

11

• Si cada bloque de la caché puede contener los datos de unas cuantas direcciones de memoria ¿Como se sabe si los datos que están en la caché son los deseados?

• Es decir, ¿como se sabe si hay hit o miss? Añadiendo a la caché un conjunto de etiquetas (tags) que contienen la información necesaria para identificar a un dato en la caché:

Caché de Mapeo Directo

tag = (dirección del bloque en memoria) div (número de bloques de la caché)

• El tag está formado por los bits altos de la dirección del dato en memoria que NO se usan para indexar a la memoria caché.

Caché de Mapeo DirectoAddress (showing bit positions)

20 10

Byteoffset

Valid Tag DataIndex

0

1

2

1021

1022

1023

Tag

Index

Hit Data

20 32

31 30 13 12 11 2 1 0

• Caché de 1024 palabras (de 32 bits)

• Se direcciona con los bits A2..A11.

• El tag está compuesto por los bits A12..A31

• Los bits A0 y A1 sólo interesan para seleccionar el byte dentro de la palabra (bloque).

•Un bit de validez se agrega para saber si la entrada es válida

Caché de Mapeo Directo

• La caché almacena tanto datos como tags.• Calcular el tamaño de una caché de mapeo

directo sabiendo que:• Las direcciones son de 32 bits• Los bloques son de 4 bytes• La caché tiene 2n bloques

Tag= 32 – (n+2) bitsNumero Total de Bits= 2n * (tamaño del bloque +tamaño tag+tamaño validez)Numero Total de Bits= 2n* (32+(32-n-2) +1= 2n * (63-n)

Caché de Mapeo Directo

• ¿Cuantos bits se necesitan para realizar una caché de mapeo directo con 64KB de datos y bloques de una palabra, suponiendo direcciones de 32 bits?• Las direcciones son de 32 bits• Los bloques son de 4 bytes• La caché tiene 214 bloques (64 KB son 16KW)

Numero Total de Bits= 214* (32+(32-14-2) +1= 214 * 49=784Kbits

784Kbits=98KB

•Respuesta: Para implementar una caché de 64KB se necesita almacenar 98KB1,5 veces mas que los datos

Memoria Caché en nuestra máquina

• Para implementar caché reemplazamos las memorias del camino de datos por cachés de datos y de instrucciones

• Un acierto....es fácil de implementar por el control.

• Un fallo: – Parar la CPU: congelar los valores de los registros– Un control separado realiza el acceso a memoria – Una vez que los datos están presentes, se reanuda la

CPU en el ciclo en que se había bloqueado

Memoria Caché en nuestra máquina

• Supongamos un fallo de instrucción– Los contenidos de IR no son válidos– La dirección que provocó el fallo es PC-4 (se puede calcular usando

una UF y guardándolo en los registros de segmentación)– Se accede a la memoria principal– La CPU espera que el acceso esté finalizado, y – Escribe el dato en la caché:

• Se indexa con los bits bajos (menos los 2 de menos peso) • lo que viene de la memoria externa, se escribe en la parte de datos• Lo que sale de la ALU (los bits más altos) en el tag• Poner a válida la entrada

– Reiniciar la ejecución de la instrucción en el primer paso (Fetch)

Un ejemplo: La caché de DECStation 3100

16 14

Byteoffset

Valid Tag DataIndex

0

1

2

Tag

Index

Hit Data

16

0

214-1

32

• Utiliza el MIPS R2000• Caché de 64KB• Memorias cachés

separadas de instrucciones y datos

Un ejemplo: La caché de DECStation 3100

• Lecturas: (a cualquier caché)• Enviar dirección (PC o ALU)

• Si es hit dato presente en las líneas de datos

• Si es miss enviar dirección a memoria principal, esperar los datos y escribirlos en caché

• Escrituras: (a cualquier caché)• Enviar dirección

• Si es hit escribir los datos en caché y en memoria principal (porque sino, quedan incoherentes): escritura a través (write through)

• Si es miss¿para que leer de memoria principal? Escribir los datos y también el tag en caché, escribir en memoria principal.

Un ejemplo: La caché de DECStation 3100

• Problemas con la política de escrituras:

• Se tarda mucho tiempo escribiendo en memoria principal solución: usar buffers de escritura

• Una vez que se escribió en caché y en los buffers, la ejecución puede reanudar.

• Cuando la escritura en memoria finaliza, se libera el buffer: el DECStation tiene un buffer de 4 palabras

• Alternativa a la política write through para lecturas

• Sólo se escribe en memoria principal cuando hay reemplazo de bloque....(hablamos de reemplazos?)

• Reemplazo de Bloque:

• Cuando hay un miss, y se trae el nuevo bloque, y la posición donde este debe ser ubicado está ocupada, se debe desalojar la línea vieja.

• Aprovechar la localidad espacial:

– Aumentando el tamaño del bloque, en caso de fallo se trae no sólo la palabra que produjo el fallo, sino también las subsiguientes.

Caché de Mapeo Directo

Address (showing bit positions)

16 12 Byteoffset

V Tag Data

Hit Data

16 32

4Kentries

16 bits 128 bits

Mux

32 32 32

2

32

Block offsetIndex

Tag

31 16 15 4 32 1 0

• Aprovechar la localidad espacial:– Aumentando el tamaño del bloque, en caso de fallo se trae no sólo la

palabra que produjo el fallo, sino también las subsiguientes.• Que cambia?

– En el caso de write miss, • hay que leer la línea de memoria principal: escribir los datos y el

tag• Luego, realizar la escritura del dato que provocó el miss• Escribir también memoria principal (o en los buffers)

Caché de Mapeo Directo

• Aumentar el tamaño del bloque hace descender la tasa de fallos

• Si los bloques son muy grandes en relación al tamaño total de la caché, entonces habrá mucha competencia por el lugar muchos desalojos antes de poder referenciar las palabras de los bloques.

Rendimiento

1 KB

8 KB

16 KB

64 KB

256 KB

256

40%

35%

30%

25%

20%

15%

10%

5%

0%

Mis

s ra

te

64164

Block size (bytes)

• Miss Rate (tasa de misses)= Número de Misses/Total de Accesos

• Hay más localidad espacial en el código: es más sensible al aumento del tamaño del bloque.

• Podría ser mejor usar cachés separadas y darles a cada una el tamaño de bloque idóneo.

Rendimiento

ProgramBlock size in

wordsInstruction miss rate

Data miss rate

Effective combined miss rate

gcc 1 6.1% 2.1% 5.4%4 2.0% 1.7% 1.9%

spice 1 1.2% 1.3% 1.2%4 0.3% 0.6% 0.4%

Rendimiento

tiempo ejecución = (ciclos ejecución + ciclos bloqueo) tiempo ciclo

ciclos bloqueo = # de instrucciones M tasa de miss penalización del miss

• Modelo Simplificado:

ciclos bloqueo = # de instrucciones tasa de miss/Instrucciones penalización del miss

Rendimiento• Ejemplo: Determinar cuanto más rápida sería una máquina con una caché ideal

respecto a esta:

– Para gcc se asume:

• Tasa de fallos de instrucciones del 2%

• Tasa de fallos de datos del 4%

– CPI =2 sin bloqueos de memoria

– Penalización por fallo=40 ciclos

– Frecuencia de instrucciones del gcc:

• 36% de lecturas/escrituras

ciclos bloqueo debidos a instrucciones= I*2%*40=0.80*I

ciclos bloqueo debidos a datos= I*36%*4%*40=0.56*I

ciclos bloqueo totales= 1.36*I CPI con bloqueos= 2+1.36=3.36

68.12

36.3

**

**

perfecta caché CPU Tiempo

bloqueosin CPU Tiempo

cicloCPII

cicloCPII

perfecta

bloqueo

Rendimiento• Ejemplo: Supongamos que se incrementa el rendimiento de la máquina

del ejemplo anterior doblando la frecuencia de reloj, sin embargo la velocidad de la memoria principal no cambia (muy posible). Es decir, no cambia el tiempo absoluto de tratar un fallo. ¿cuánto más rápida es esta máquina que la anterior, con el mismo porcentaje de fallos?

Nueva penalización por fallos=80 ciclos (el doble de ciclos)

CPI con bloqueos= 2+2,75=4,75

41.1

2

75.436.3

2**

**

rápida CPU Tiempo

lenta CPU Tiempo

cicloCPII

cicloCPII

rápida

lenta

ciclos bloqueo totales= I*2%*80 + I*36%*4%*80 =2,75*I

Rendimiento

• Las penalizaciones relativas a la caché se incrementan cuando la máquina es más rápida.

• Cuanto mas bajo es el CPI, más pronunciado será el efecto del bloqueo

• El sistema de memoria no mejora tan rápidamente como el tiempo de ciclo del procesador una CPU con un reloj más rápido tendrá una penalización por fallo más larga.

Rendimiento• Dos formas de mejorar el rendimiento:

– Reduciendo la tasa de misses– Reduciendo la penalidad por misses

• Una manera de reducir la tasa de misses es aumentando el tamaño del bloque– Sin embargo, esto puede aumentar la penalidad por misses: es el tiempo requerido

para ir a buscar un bloque en el siguiente nivel y cargarlo en la caché.– Este tiempo tiene dos componentes:

• Latencia de la primera palabra• Tiempo de transferencia del resto del bloque: este se incrementa a medida que crece el

tamaño del bloque

– Algunas soluciones para este problema:• Diseño de un sistema de memoria que permita transferir grandes bloques de manera mas

eficiente• Ocultar el tiempo de transferencia reanudando la ejecución tan pronto como sea posible

(cuando ya esté la palabra pedida) sin esperar que todo el bloque haya sido transferido.

Otras formas de reducir los fallos de caché

• Cambiando la manera en que se mapea un bloque en la memoria caché.

• Por ejemplo: – Que un bloque pueda ir a cualquier posición de la caché: mapeo

totalmente asociativo– Reduce los misses por conflicto: aquellos bloques que ya

estaban pero fueron desalojados porque otro bloque lo reemplazó.

– Implementación:• Para buscar un bloque se debe recorrer TODA la cachéun comparador

por cada entrada, para hacer todas las comparaciones en paralelo.• Inconveniente: incremento del costo en hardware.• Solución: cachés con pocos bloques

Compared to direct mapped, give a series of references that:– results in a lower miss ratio using a 2-way set associative cache– results in a higher miss ratio using a 2-way set associative cache

assuming we use the “least recently used” replacement strategy

O bien: buscar un término medio: asociativas por conjuntos

Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data

Eight-way set associative (fully associative)

Tag Data Tag Data Tag Data Tag Data

Four-way set associative

Set

0

1

Tag Data

One-way set associative(direct mapped)

Block

0

7

1

2

3

4

5

6

Tag Data

Two-way set associative

Set

0

1

2

3

Tag Data

Asociativa por conjuntos

• Dentro de cada conjunto (set), la asignación de entradas es totalmente asociativa.

• Los conjuntos son de n-vias: es decir, el bloque se asigna en cualquiera de las n vías del conjunto

• La asignación de un bloque a un conjunto es por mapeo directo.

ImplementaciónAddress

22 8

V TagIndex

01

2

253254255

Data V Tag Data V Tag Data V Tag Data

3222

4-to-1 multiplexor

Hit Data

123891011123031 0

Asociatividad en Cachés• Ejemplo: Se tienen 3 cachés pequeñas, cada una consistente en cuatro

bloques de una palabra. Una es totalmente asociativa, la segunda es asociativa de 2 vías por conjunto, y la tercera es de mapeo directo. Encontrar el número de fallos para cada organización de la caché para la siguiente secuencia de direcciones de bloque: 0,8,0,6,8.

• Mapeo Directo:

• Dirección Dirección de Bloque en Caché

0 0 módulo 4=0

8 8 módulo 4=0

6 6 módulo 4=2

• Fallos: los cinco son fallos.

Asociatividad en Cachés• Totalmente Asociativa:

• Hay cuatro bloques, y cualquier bloque de memoria puede estar en cualquier bloque.

• 0 fallo,8 fallo,0 acierto,6 fallo,8 acierto

• Asociativa por dos conjuntos de 2 vías:

• Dirección Dirección de Bloque en Caché

0 0 módulo 2=0

8 8 módulo 2=0

6 6 módulo 2=0

• 0 fallo, 8 fallo, 0 acierto, 6 fallo (desplaza al 8), 8 fallo

Rendimiento

0%

3%

6%

9%

12%

15%

Eight-wayFour-wayTwo-wayOne-way

1 KB

2 KB

4 KB

8 KB

Mis

s ra

te

Associativity 16 KB

32 KB

64 KB

128 KB

• La asociatividad aumenta el rendimiento, es decir, disminuye la tasa de fallos, pero aumenta el tiempo del acierto (circuitería). El mayor beneficio se obtiene al pasar de una de mapeo directo a una asociativa de 2 vías.

Algoritmos de reemplazo

• ¿Que bloque tiene que ser reemplazado?– Es una pregunta para las cachés asociativas. En las

totalmente asociativas, cualquier bloque es el candidato, en las asocaitivas de n-vías alguno de los n.

– Algoritmos:• Aleatorio

• LRU (least recently used): es costoso para mas de 4 vías se usa un aproximado.

• El algoritmo de reemplazo para cachés se realiza mediante hardware, por eso debe ser sencillo

Una alternativa para disminuir la penalización por fallo

• Cachés Multinivel: agregar un segundo nivel de caché– La caché primaria (nivel 1) está en el mismo chip que

el procesador.– Se implementa con memoria SRAM otro nivel de

memoria entre la principal y el nivel 1.– Si no está en L1, es probable que esté en L2, y el

tiempo de acceso a L2 es menor que el tiempo de acceso a memoria principal.

Cachés MultinivelEjemplo:

– Sea una CPU con un reloj de 500 Mhz, un CPI de 1.0, una tasa de fallos del 5% y 200ns de acceso a DRAM.

– Le agregamos una caché de nivel 2 con 20ns de tiempo de acceso y una tasa de fallos a memoria principal del 2%

– Cuanto mas rápida es la máquina con los dos niveles de caché?

CON UN NIVEL DE CACHÉ

Penalización por fallos a MP, en ciclos: 200 nseg/(2nseg/ciclo)=100 ciclos

CPI con bloqueos por memoria= 1 + 5%*100=6

CON DOS NIVELES DE CACHÉ

Penalización por fallos a L2, en ciclos: 20 nseg/(2nseg/ciclo)=10 ciclos

Penalización por fallos a MP en ciclos: 10 ciclos + 100 ciclos=110 ciclos

CPI con bloqueos por memoria= 1 + bloqueos del nivel 1 + bloqueos del nivel 2

CPI total= 1 + 0,05 (10 ciclos * 0,98 + 110 ciclos*0,02)=1,6

Organización del Computador I Verano

Rendimiento (2 de 3) Basado en el capítulo 2 del libro de Patterson y Hennessy

Verano 2004 Profesora Borensztejn

FIN Jerarquía de Memoria