Escuela de Ingeniería de Sistemas Departamento de...
Transcript of Escuela de Ingeniería de Sistemas Departamento de...
Universidad de Los Andes
Escuela de Ingeniería de Sistemas
Departamento de Computación
Arquitectura de Computadores
Semestre B-2010 Ícaro Alzuru C.
Clase 19
AGENDA
• 2do Avance de Proyecto: 17/12/2010 (Por
correo electrónico: [email protected])
• 3er Examen Parcial: 08/12/2010
• Jerarquía de memoria.
Razonamiento inicial
• Lo ideal sería poder contar con una gran cantidad
de memoria que fuese tan rápida como el
procesador.
• Pero….Tecnología Tiempo de acceso (ns) $ por GB (2008)
SRAM 0,5 – 2,5 2.000 – 5.000
DRAM 50 – 70 20 – 75
Disco Magnético 5.000.000 – 20.000.000 0,2 – 2,0
CPU
Control
Camino de datos
Memoria
Dispositivos
Entrada
Salida
Procesador – MemoriaDesface de rendimiento
1
10
100
1000
10000
1980
1982
1984
1986
1988
1990
1992
1994
1996
1998
2000
2002
2004
Año
Re
nd
imie
nto
“Ley de Moore”
µProc
55%/Año
(2X/1.5 Año)
DRAM
7%/Año
(2X/10 Anual)
Diferencia
rendimiento
CPU - Memoria
(Crece 50%/Año)
La “Pared de la memoria”
• El desface entre la velocidad del CPU
y la DRAM continúa creciendo
0,01
0,1
1
10
100
1000
VAX/1980 PPro/1996 2010+
Core
Memory
Cic
los p
or
instr
ucció
n
Cic
los p
or
acceso a
DR
AM
Jerarquía de Memoria(Otras motivaciones)
• Realidad: Las memoria grandes son lentas y las memorias rápidas son pequeñas
• ¿Cómo crear una memoria (algo) que parezca ser grande, barato y rápido (La mayoría de las veces)?
• “LEYES” de Localidad:– Localidad temporal (tiempo). Si se referencia un
elemento tenderá a ser referenciado pronto.
– Localidad espacial (espacio). Si se referencia un elemento, los elementos cercanos a él tenderán a ser referenciados pronto.
D
red
Ejemplos de jerarquías de
memoria
disco
RAM
cache
CPU
disco
RAM
Cache L2
I
CPU
Jerarquías de Memoria(Características)
• Reacción natural al principio de localidad y a los costos de la tecnología• Organizada en varios niveles (cada uno más pequeño, más caro y más rápido que el anterior)• Todos los datos de un nivel superior se encuentran también en el nivel inferior• Explotar que: 10% del código se ejecuta durante el 90% del tiempo• La memoria Cache es una memoria escondida: El programador no sabe ni necesita saber que existe. ¿Y en la ISA?
Jerarquías de Memoria(Características)
Distancia
creciente desde
el procesador,
en tiempo de
acceso
L1$
L2$
Memoria Principal
Memoria Secundaria
Procesador
(Relativo) Tamaño de la memoria a cada nivel
Inclusivo– Lo que
está en la L1 es un
subconjunto de lo
que está en la L2,
que es un
subconjunto de los
que está en la MP
(subconjunto de los
que está en MS)
4-8 bytes (Palabra)
1 a 4 bloques
1,024+ bytes (Sector de disco = Página)
8-32 bytes (Bloque o
línea)
Cache
L2
(SRAM)
Jerarquía de memorias típica
Control
Datapath
Memoria
Secundaria
(Disco)
Componentes On-Chip
RegF
ile
Memoria
Principal
(DRAM)
Data
Cache
Instr
Cache
ITLB
DT
LB
DRAM
Velo. (%Ciclos): ½’s 1’s 10’s 100’s 1,000’s
Tamaño (bytes): 100’s K’s 10K’s M’s G’s a T’s
Costo: Mayor Menor
Sacando ventaja del principio de localidad
Se puede presentar al usuario tanta memoria como la que está
disponible en la tecnología más barata
Y la velocidad ofrecida por la tecnología más rápida
Terminología básica (1)
Acierto (hit) : Sucede cuando se busca un bloque de datos en
una memoria y sí es escontrado.
Tiempo de hit (hit time): Tiempo empleado para recuperar un
dato desde memoria (Incluye el tiempo para saber si es un
acierto o un fallo)
Fallo (miss) : Ocurre cuando se busca un bloque de datos y este
no se encuentra en la memoria.
Penalización por fallo (miss penalty) : Tiempo necesario para buscar
el bloque en el nivel inferior, más el tiempo de sustituirlo, más el tiempo
necesario para proporcionar este bloque al dispositivo que lo solicito
(generalmente la CPU).
hit time << miss penalty (¡100s instrucciones!)
Terminología básica (2)
Frecuencia o tasa de aciertos (hit rate) : Fracción de accesos a
memoria que resultan en aciertos o hits (Bloques encontrados).
Frecuencia de fallos (miss rate): (1 - frecuencia de aciertos)
Fracción de accesos a memoria que resultan en fallos o misses
(Bloques no encontrados).
Penalización por fallo (Incluye):Tiempo de acceso : Tiempo necesario para acceder a la primera palabra de un bloque en un fallo (Relacionado con la latencia del nivel más bajo)Tiempo de transferencia : Tiempo para transferir las restantes palabras del bloque. (Relacionado con el ancho de banda entre las
memoria de nivel más bajo y más alto).
Impacto del rendimiento de la
memoria
• Suponer que un procesador ejecuta
– CPI (Ideal) = 1.1
– 50% arit/logic, 30% ld/st, 20% control
Y que 10% de las operaciones a datos en memoria,
fallan con una penalización por falla de 50 ciclos
• CPI = CPI Ideal + Detención promedio por instrucción
= 1.1(Ciclo) + (0.3(OpsDatMem/Instr) x
0.1(fallo/OpMemDat) x 50 (ciclo/fallo))
= 1.1 Ciclos + 1.5 Ciclos = 2.6
Por ende, 58% del tiempo el CPU está detenido,
esperando a la memoria
• Un 1% más de rata de fallas añade un 0.5 más a los CPI
Ideal CPI;
1,1
DataMiss;
1,5
InstrMiss;
0,5
Tecnologías de Memorias
• Las cache usan SRAM por
su velocidad y compatibilidad
– Baja densidad (6 transistores),
alto voltaje, cara, rápida
– Estática: El contenido no se
degrada o pierde (hasta que se
apaga la máquina)
• La Memoria Principal utiliza DRAM por el tamaño (densidad)
– Alta densidad (1 transistor), bajo consumo, barata, lenta
– Dinámica: Requiere ser “refrescada” regularmente (~ cada 8 ms)
• 1% a 2% de los ciclos activos de la DRAM
– Direcciones divididas en 2 mitades (fila y columna)
• RAS (Row Access Strobe): Decodificador del disparador de fila
• CAS (Column Access Strobe): Selector del disparador de columna
Dout[15-0]SRAM
2M x 16
Din[15-0]
Dirección
Chip select
Output enable
Write enable
16
16
21
Métricas del Rendimiento de
Memoria
• Latencia: Tiempo de acceso a una palabra
– Tiempo de acceso: Tiempo entre la solicitud y la disponibilidad
de la data (o escritura)
– Tiempo de acceso (lectura) típico para SRAMs en 2004 era de
2 a 4ns para las memorias más rápidas y de 8 a 20ns para las
memorias más grandes
• Ancho de banda: Cuántos datos desde la memoria se
le pueden proveer al procesador, por unidad de tiempo
– Ancho del canal de datos * frecuencia a la cual puede ser
utilizado
Memoria Cache
• Cache: Lugar seguro donde esconder o
almacenar cosas.
• Utilizadas por primera vez a principios de
los años 60.
• Hoy en día; cualquier computador de
propósito general, desde servidores a
procesadores encajados de baja potencia,
incluyen memorias caches.
Tipos de Cache(Según ubicación de datos e instrucciones)
• Tipo Princeton:– Es cuando una cache almacena tanto datos como
instrucciones
• Tipos Harvard:– Las instrucciones y los datos son guardados en
caches separadas
– Término alusivo a la Mark I fabricada en Harvard
– Permite que el procesador extraiga al mismo tiempo datos e instrucciones
Ubicación de un bloque1.- ¿Dónde se coloca un bloque en la Cache?
Mapeo Directo(La organización más sencilla)
• La localidad 0 de la cache puede ser ocupada por las direcciones de memoria 0, 4, 8, etc… cualquiera cuyos 2 LSB sean 00
• ¿Cuál deberíamos colocar en la Cache?
• ¿Cómo podemos averiguar cuál está ocupando la Cache?
Búsqueda de un bloque2.- ¿Cómo saber si un bloque está en la Cache?
• Index: Indica el conjunto (Set) de Tags a tomar en cuenta
• Tag: Dirección del bloque
• Offset: Dirección del dato deseado dentro del bloque
• Por lo general, se agrega un bit de validez al tag para saber si contiene una dirección válida o no
• Los tags candidatos o posibles, se revisan en paralelo (por cuestiones de velocidad)
• ¿Cuántos bits tendría Index si se tratase una memoria 4-way associative?
Reemplazo de un bloque3.- ¿Qué bloque reemplazar si ocurre un Miss en la Cache?
• Si es mapeo directo: No hay problema
• Estrategias posibles:
– Least Recently Used (LRU): El bloque que fue utilizado
hace más tiempo
– Aleatorio: Selección al azar de qué bloque sobreescribir
– First In, First Out (FIFO): Debido a que LRU es difícil
de calcular, se determina el bloque más viejo (el que
lleva más tiempo) de la cache.
Escritura de un bloque4.- ¿Qué ocurre al escribir un bloque en la Cache?
• Las escrituras de datos en Cache no son tan frecuentes (28%) como las lecturas.
• La escritura de un bloque comienza después de que chequeamos que ocurrió un miss.
• Alternativas:– Write through: Se escribe el bloque en la Cache y en la memoria
de menor nivel.
– Write back: Se escribe el bloque sólo en la Cache. El bloque se actualiza en las memorias de nivel inferior sólo si el bloque se va a sobreescribir.
• En Write back se requiere marcar que un bloque ha sido escrito, para saber que hay que actualizarlo en los niveles inferiores. Para ello, se utiliza un bit (dirty bit).
• Write back consume menos ancho de banda de memoria y es más rápido
• Write through es más sencillo de implementar
La Cache en el Pipeline
Estrategias para mejorar la relación
hits - misses
Los fallos pueden ocurrir porque:
1. Obligatorios: El primer acceso a un bloque (Cold-start miss o First-reference miss)
2. Por capacidad: La cache no puede albergar a todos los bloques necesarios para ejecutar un programa.
3. Conflicto: Debido a la estrategia de ubicación de los bloques en la cache, ocurre que un bloque se alterna entre ser descartado y ser requerido (Conflict miss)
Estrategias para mejorar la relación
hits - misses
1. Aumentar el tamaño del bloque
Se reducen los cold-start misses
Se incrementan los fallos por capacidad
(Caben menos bloques)
Estrategias para mejorar la relación
hits - misses
2. Aumentar el tamaño de la cache
Se reducen los fallos por capacidad
Mayor latencia y consumo: Es una cache de
mayor tamaño
Estrategias para mejorar la relación
hits - misses
3. Aumentar la asociatividad (El tamaño de
los conjuntos)
Se reducen los fallos por capacidad
Cache más cara y aumenta el tiempo de hit
Estrategias para mejorar la relación
hits - misses
4. Aumentar los niveles de Cache
La Cache L1 debería ser lo suficientemente
pequeña para ir a la velocidad del CPU
La Cache L2 debería ser lo más grande que se
pueda (Sin penalizar mucho la velocidad) para
minimizar los misses
5. Dar prioridad a la lectura sobre la escritura
Utilizar buffers de escritura
Se complican los accesos a memoria y aumenta el
costo