Download - Memoria Caché
ARQUITECTURA DEL COMPUTADOR
Ing. Electrónico Alex Jiménez
Memoria Caché
SISTEMA DE MEMORIA
Memorias Caché Memoria caché:
Primer nivel (también corresponde al segundo) de la jerarquía de memoria Memoria caché es accesada por CPU durante los ciclos de búsqueda de
instrucción y durante los accesos a memoria de datos El tiempo de acceso a la caché debe ser compatible con velocidad del
procesador. es decir, velocidad debe ser alta (la memoria debe ser simple y pequeña)
Caché unificada: caché único para datos e instrucciones. Caché separada: un caché para datos y otro para instrucciones. Caché multinivel: más de un nivel de caché
CPU
Cach
é I
nstr
.
Cach
é D
ato
s
Bco.Regs
Cach
éL.
II
RA
M
Memorias Caché
Terminología Bloque: unidad mínima de transferencia entre caché y memoria.
corresponde a un conjunto de Wds contiguas en memoria Hit: acción de solicitar un dato y éste se encuentra en caché Miss: acción de solicitar un dato y éste no se encuentra en caché Tasa acierto (tH): tasa de referencias memoria que producen hits Tasa desacierto: tM =1 – fH Tiempo de acierto (TH): tiempo empleado en leer un dato del
caché Penalidad de desacierto (TM): tiempo empleado en direccionar la
memoria principal (o el siguiente nivel de caché), obtener el dato y trasferirlo a CPU y simultáneamente a caché
Tiempo de acceso promedio a memoria (TAcceso): promedio ponderado por sus respectivas tasas, entre tiempo de acierto y la penalidad de desacierto
TAcceso= tA TH + (1- tA) TM
Memorias Caché
Forma de operar de una caché1. Dirección D generada por el
procesador es comparada con datos almacenados en los bloques del caché
2. Si el dato D está presente, el procesador lo lee del caché
3. Si dato está ausente, se transfiere desde la memoria principal o desde el siguiente nivel jerárquico hacia el caché1. Se asigna la ubicación del
bloque B en el caché2. Si es necesario, se reemplaza
uno de los datos presentes en el caché
3. Paralelamente se entrega el dato D al procesador
Dir
ecció
n D
desd
e C
PU
¿Está en cachébloque B quecontiene a D?
No
Sí Accesar memoria (o
L.I I ) y leer bloque Bque contiene a D
Asignar la ubicacióndel bloque B en caché
AlmacenarB en caché
Leer Ddesde B
Leer Ddesde B
Memorias Caché Impacto de los desaciertos en el desempeño
La ejecución de las instrucciones debe detenerse durante el acceso y transferencia del bloque faltante.
con esto, el CPI efectivo aumenta Pueden usarse técnicas para reducir en parte el impacto del
desacierto, ejecutar instrucciones siguientes, no esperar la transferencia de
todo el bloque desde la memoria, etc.
Parámetro Valor típico
Tamaño bloque 4 a128 [By]
Tiempo acierto 1 a 4 [ciclos]
Penalidad desacierto (Tpo. acceso/Tpo. transferencia)
8 a 32 [ciclos](6 a 10 / 2 a 22) [ciclos]
Tasa desacierto 0.01 a 0.2
Tamaño caché 1 K a 2 M [By]
Memorias Caché
Interna Externa
CPU L. I instr L. I datos L. II L. II
Alpha 21264 64 KBy 64 KBy 8 MBy
AMD Athlon 64 KBy 64 KBy 256 KBy
HPPA 8600 512 KBy 1024 KBy
IBM Power3II 32 KBy 64 KBy 8 MBy
Pentium III 16 KBy 16 KBy 256 KBy
Pentium 4 12 KBy 8 KBy 256 KBy
MIPS R12000 32 KBy 32 KBy 8 MBy
Sun Ultra-II 16 KBy 16 KBy 8 MBy
Sun Ultra III 32 KBy 64 KBy 8 MBy
Memorias Caché
Ejemplo: si el CPI ideal de un programa es 4, la penalización de desacierto es de 12 ciclos y el 33% de las instrucciones son tipo load/store. ¿Cuál es el CPI real del programa si la tasa de falla de instrucciones es de 5% y la de datos es de 10%?
Solución:CPIideal = CPIL/S,ideal = CPIOtras,ideal
CPIL/S,real = CPIL/S,ideal + tM,Instr TM+ tM,Datos TM
CPIOtras,real= CPIOtras,ideal + tM,Instr TM
CPIProg,real = fOtras CPIOtras,real + fL/S CPIL/S,real
Memorias Caché
Caché
2C By
Bloque2B By
Memoria
Principal
2M By
Transferencia sóloen caso de miss
2C-B Bloques 2M-B BloquesBy Individuales
Memorias Caché
Aspectos básicos de memoria caché Tamaños asociados
bloque: SizeB= 2B [By] caché: SizeC= 2C [By] 2C-B = c [bloques] memoria principal: SizeM=2M [By] 2C-M = m [bloques] B < C < M utilizar bloques como unidad de medida de datos
Tipos de miss en caché obligatorios: producidos cuando caché está vacío por competencia: bloques de memoria pelean por el un
espacio en caché por capacidad: producidos al llenar caché datos inválidos: producidos cuando en el caché existen
datos pero provienen de otro programa
Memorias Caché
Aspectos de diseño de memorias caché Algoritmo de búsqueda dentro del caché Algoritmo de ubicación en el caché
al traer un dato hacia caché: ¿dónde dejarlo? necesario pues C<M
Algoritmo de reemplazo de datos como C<M caché se llena una vez llena caché: ¿cuál bloque reemplazar?
Algoritmo de escritura ¿actualizar los datos entre memorias inmediatamente
o al producirse un reemplazo? recordar que accesar memoria principal es lento
Memorias Caché
Algoritmo de búsqueda dentro del caché ¿Cómo reconocer a cuál de los bloques de memoria
corresponde el i-ésimo bloque del caché? 2M-B bloques de memoria competirán por los 2C-B bloques del caché múltiples opciones no basta con almacenar sólo el dato, se necesita de una marca que
identifique al i-ésimo bloque del caché Tag: identificador de bloque de memoria en el caché
la diferencia entre los bloques de memoria la hace dirección de bloque
correspondiente a los (M-B) b MSB de dirección de memoria [By] ¡esta cantidad de b puede disminuirse!
b adicionales: necesarios para la coherencia de los datos dirty: indica que el bloque del caché fue modificado y debe
escribirse en memoria validez: el dato presente en el bloque es válido y no corresponde a
basura
Memorias Caché
Ejemplo: bloques de 16 By, memoria 16 MBy, caché 64 By Mem[0xFF1018]=123
Tag = 0xFF101 Dato = 123
Mem[0xFFAA11]=Hola Tag = 0xFFAA1 Dato = Hola
Mem[0x0000AA]=10 Tag = 0x0000A Dato = 10
0xFF101-10
0x0000A-10
0xFFAA1-10
XXXXX-00
123
10
HolaDato...
Hola
123
10
2C-B Bloques 2M-B Bloques
Tag b adicionales
Memorias Caché
Algoritmo de ubicación en el caché Al llevar un dato al caché, ¿en cuál de los
posibles bloques del caché se ubica? ¿cualquier parte? ¿en una única ubicación bien
definida? ¿en cualquier parte dentro de una cierta cantidad bien definida?
Objetivos del caché: minimizar la competencia realizar el mínimo de transferencias mapear una dirección de memoria en alguna posición
del cachéM={0,1,2…,2M-1}, C={0,1,2…,2C-1}Map: M V
Memorias Caché
Algoritmo de ubicación en el caché Mapeo directo
un bloque de memoria se ubica en un único bloque del caché
Mapeo completamente asociativo un bloque de memoria se ubica en cualquier bloque
del caché Mapeo asociativo por conjuntos de w-vías
un bloque de memoria se ubica en cualquiera de los bloques que contiene un único conjunto
caché está formado por s=2S conjuntos, cada uno con w=2W de bloques (llamados también vías), donde:c = w * s
Memorias Caché
Algoritmos de ubicación: mapeo directo Ubicación Caché={ int(SizeM/SizeB) } mod c Ventajas: económico, acceso rápido Desventaja: mayor tasa de desaciertos por competencia por bloques
Caché
Memoria
Memorias Caché Algoritmos de ubicación: completamente asociativo
Posición Caché = rand(c) Ventaja: menor tasa de desaciertos por competencia por bloque Desventajas: más caro, acceso más lento
Caché
Memoria
Memorias Caché Algoritmos de ubicación: asociativo por conjuntos w-vías
Posición Caché = { int(SizeM/SizeB) } mod s Ventaja: más económico que caché completamente asociativo, pero
más caro que caché directo Desventaja: dato disponible después de etapa de comparación y
multiplexión
Caché
Memoria
Memorias Caché
Algoritmo de ubicación en el caché El Tag del algoritmo de búsqueda se ve modificado
dependiendo del tipo de algoritmo de ubicación utilizado Mapeo directo
los bits correspondientes a la ubicación del bloque en el caché son idénticos a los de la ubicación en memoria
Tag puede reducirse a (M-C) b Mapeo completamente asociativo
Tag se mantiene pues no existe relación entre direcciones Mapeo asociativo por conjuntos de w-vías
los bits de ubicación a nivel de conjunto son los mismos Tag se reduce a (M-C-S) b
Memorias CachéDir. Mem [By] :0x FF 1234Dir. Mem [By] :1111 1111 0001 0010 0011 0100Dir. Mem [bloques]:1111 1111 0001 0010 0011Dir. Mem [bloques]:1111 1111 0001 0010 00 (M.D.)Dir. Mem [bloques]:1111 1111 0001 0010 0011 (C.A.)Dir. Mem [bloques]:1111 1111 0001 0010 001 (A.C.)
M
C
M-C C-B B
M-C C-B B
M-C C-S-B S B
M.D.
C.A.
A.C.
D.C.
D.M.
Memorias Caché
Algoritmo de reemplazo de bloques Al llevar un a caché y necesita producirse un
reemplazo, ¿por cuál de los posibles bloques del caché se reemplaza?
¿por cualquiera?, ¿por uno en particular?, ¿por cualquiera dentro de un grupo bien definido?
Algoritmos de reemplazo típicos: Random: el candidato a reemplazo es cualquier
bloque FIFO: el bloque que primero entró al caché es el
elegido a salir LRU: el bloque que ha sido accesado hace más
tiempo es el candidato a salir LFU (NRU): el bloque que ha sido accesado una
menor cantidad de veces es el candidato a salir
Memorias Caché
Algoritmo de reemplazo de bloques El algoritmo de reemplazo a utilizar
dependiendo del tipo de algoritmo de ubicación utilizado
Mapeo directo como existe una única ubicación posible el algoritmo
de reemplazo está implícito Mapeo completamente asociativo
cualquier bloque del caché es candidato a reemplazo algoritmos utilizables: random, FIFO, LRU, LFU
Mapeo asociativo por conjuntos de w-vías cualquier bloque dentro del i-ésimo conjunto del
caché es candidato a reemplazo algoritmos utilizables: random, FIFO, LRU, LFU
Memorias Caché
Algoritmo de escritura ¿Cuándo actualizar los datos entre las memorias?
¿inmediatamente o al producirse un reemplazo? dependiendo de cuando se escriba existirá coherencia o no
entre caché y memoria recordar que accesar memoria principal es lento
Escritura sincrónica (Write through) el bloque se escribe en el caché y en memoria principal se utiliza un buffer de escritura para mejorar desempeño no necesita ser escrito en memoria principal al ser
reemplazado Escritura asincrónica (Write back)
se escribe solamente en el caché el bloque se actualiza en memoria principal sólo cuando es
reemplazado se necesita un b adicional para indicar que el bloque fue
modificado (dirty)
Memorias Caché Tamaño del bloque
Un tamaño de bloque grande permite utilizar mejor la localidad espacial
Un tamaño de bloque grande tiene una mayor penalidad de desacierto pues es más costoso traer el bloque
Un tamaño de bloque grande generará pocos bloques en el caché, lo que aumentará la tasa de fallo
muchos fallos por competencia Se debe llegar a un compromiso
Pen
Des
acie
rto
TB
Tas
a Fa
llos
Explota localidad espacial
Poco bloques comprometen localidadtemporal
TBTpo
Acc
Med
io
Alta tasay penalidadde fallos
TB
Memorias Caché
Mapeo directo
Full asociativa
Asociativa w-vías
Tamaño caché Grande Chico Medio
M. Obligatorio Igual Igual Igual
M. Conflicto Alta Cero Media
M. Capacidad Baja Alta Media
M. Validez Igual Igual Igual
Memorias Caché
Organización de memoria para soporte de caché La finalidad del caché es reducir el tiempo de acceso
promedioTAcceso= tA TH + (1- tA) TM
aumentar la tasa de acierto (tA) reducir el tiempo de aceso al caché (TH) reducir la penalidad de un desacierto (TM) existen diversas técnicas para esto: políticas de R/W, uso
de TLB, nivel de asociatividad, etc. Además, es necesario aumentar la velocidad de
transferencia de bloques entre memoria y caché organizar la memoria y caché para obtener mejor
desempeño concepto de ancho de banda de memoria (BW)
Memorias Caché
Organización de memoria para soporte de caché Memorias de una
palabra de ancho requiere varios
accesos a memoria memoria requiere
ser muy rápida es una solución cara BW bajo
Caché
MemoriaPrincipal
Memorias Caché
Organización de memoria para soporte de caché Memorias de varias
palabras de ancho ancho de palabra
mayor bus ancho permite
transferir bloque completo en un acceso
costo alto BW alto
Caché
MemoriaPrincipal
Memorias Caché
Organización de memoria para soporte de caché Memorias
entrelazadas memoria ancha bus de ancho normal lectura simultánea a
las memorias acceso segmentado
para la transferencia BW promedio
Caché
MemoriaPrincipal
MemoriaPrincipal
MemoriaPrincipal
MemoriaPrincipal
Memorias Caché
¿Y esto de las memorias caché sirve para algo útil? Ejemplo: procesamiento
de imágenes se debe procesar los
datos píxel a píxel en el tiempo
se dispone de lk imágenes
cada i,j-ésimo píxel es independiente de sus vecinos
k-ésimo bloque
lk
k-ésimo bloque
lk
Memorias Caché