Organización de computadores
Sistema de memoria Almacenamiento de datos e instrucciones durante ejecución de
programas Desempeño del sistema de memoria es vital en desempeño del
computador como un todo Ejecución de cualquier instrucción accesa memoria de
instrucciones Instrucciones load y store accesan memoria de datos
Control
SecciónDatos
Memoria
ProcesadorEntrada
Salida
Desempeño de CPU vs. DRAM
Per
form
ance
µProc60%/yr.(2X/1.5yr)
DRAM9%/año.(2X/10 años)1
10
100
100019
8019
81
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
DRAM
CPU19
82
Procesador-MemoriaGap Desempeño:(crece 50% / año)
“Moore’s Law”
¡Mejorar sólo desempeño de CPU es insuficiente!
Jerarquía de memoria Requerimiento: gran cantidad de memoria, rápido acceso
Entregar cantidad de memoria permitida por tecnología más barata Proveer velocidad de acceso permitida por tecnología más rápida
Principio de funcionamiento Jerarquía de almacenamiento de creciente tamaño y tiempo de
acceso Niveles más rápido de la jerarquía contienen copia del subconjunto de
datos más utilizados de los niveles de mayor tamaño
Control
Datapath
MemoriaSecundaria
(Disco)
Procesador
Reg
istros
MemoriaPrincipal(DRAM)
Cach
e L2
Dato
s, Inst.
~1 ~10,000,000Velocidad (ciclos): ~1-5 ~100
~100- 1000 40-400GTamaño (bytes): ~32K ~512M-4G
Cach
e L1
Inst
Cach
e L1
Dato
s
~5-12
~32K
Objetivos de jerarquía de memoria
Mantener cerca de procesador información que se necesita ahora y en el futuro cercano Memoria más cerca del procesador es más
rápida y cara Consecuencia, ser selectivo en tal información
Tecnologías en jerarquía de memoria Más cerca de procesador, memorias cache
SRAM Más lejos, memoria principal DRAM Discos magnéticos: almacenamiento de archivos
Principio de localidad
Localidad temporal Ejemplo: instrucción en lazo iterativo se lee varias veces,
variables se reutilizan Mantener los datos referenciados más recientemente cerca del
procesador Localidad espacial
Ejemplo: Leer instrucción N, luego N+1, luego N+2, etc., elementos de un vector. Programa en general secuencial
Mover bloques de datos contiguos a los niveles superiores de la jerarquía de memoria. Arreglos
Address Space0 2^n - 1
Probabilityof reference
Tecnología de memoria
Flip-flopsElementos individualesEscritura sincronizada por relojBanco de registros
SRAM (RAM estática)Organizada como arreglo unidimensionalRápido acceso, costosa: 6 transistores/bitMemorias cache
DRAM (RAM dinámica)Dinámica: necesita ser refrescada periódicamente (8 ms)Organizada como arreglo bidimensional: filas ycolumnasAcceso lento, densa: 1 transistor/bitMemoria principal
Costo/velocidad: SRAM/DRAM ~ 8-16
RAM: Random Access Memory(memoria de acceso aleatorio)
velocidadcosto ydensidad
Terminología
Hit (acierto): dato presente en bloque de nivel superior (blk X) Hit rate (tasa de acierto): fracción de accesos a memoria
encontrados en nivel superior Hit time (tiempo de acierto): tiempo de acceso al nivel superior
tiempo de acceso memoria + tiempo determinación de acierto Miss (fallo): data debe traerse de un bloque de nivel
inferior (blk Y) Miss rate (tasa de fallo): 1 – (Hit rate) Miss penalty (penalidad de fallo): tiempo para reemplazar el
bloque en nivel superior + tiempo para entregar dato al procesador
Tiempo de acierto << penalidad de fallo
Memorias cache
Primer nivel en la jerarquía de memoria Accesada en ciclo fetch y lectura/escritura de datos Nivel 1 (L1) en mismo chip del procesador Máquinas contemporáneas: L2 (on-chip) y L3 (off-chip)
Tiempo de acceso compatible con velocidad del procesador 1-2 ciclos Pequeña y rápida SRAM
Objetivo Mantener el conjunto de datos e instrucciones más utilizado
por el programa en el cache
AMD Opteron
L1 I-TLB, D-TLB: 32+8 entradas, asociativoL2 I-TLB, D-TLB: 512 entradas, 4-way
L1 I-cache, D-cache: 64KB, 2-wayL2 cache unificada: 1MB, 16-way
Pentium 4L2
IC
DC
L2 cache unificada: 512K, 8-wayL1 I-cache: Trace cacheL1 D-cache: 8KB
Para más info: www.inf.udec.cl/~chernand/arquitectura/links/Pentium4.pdf
Trace Cache
Execution Trace CacheAdvanced L1 instruction cache removes decoder pipeline latency, and caches "decoded" instructions, thus improving efficiency and hit rate to cached instructions. L1 cache supplies up to 12K decoded instructions into the processor pipeline.
Dual Core Processor
Para mayor informaciónwww.inf.udec.cl/~chernand/arquitectura/links/IntelCoreDuo.pdf
Algunas preguntas-Alternativas de diseño Cuándo se trae contenido de memoria a cache? Cómo sabemos si está en cache?
Identificación del bloque
Dónde lo ponemos en cache?
Ubicación del bloque Qué ocurre si cache está llena y queremos traer algo
nuevo?
Reemplazo del bloque O qué ocurre si queremos traer algo nuevo y el
lugar donde queremos ponerlo ya está ocupado? estrategia de escritura
Algunas respuestas
Cuándo se trae contenido de memoria a cache? Por demanda, la primera vez que tenemos un fallo por
dirección. Prefetch. Por adelantado antes que sea usado pero con
alta probabilidad que se use en el futuro próximo Dónde lo ponemos en cache?
Depende de la organización del cache Cómo sabemos está en cache?
Cada entrada en cache contiene su nombre o tag Qué ocurre si cache está llena y queremos traer algo
nuevo? Entrada actual en cache se reemplaza por nueva de
acuerdo a algún criterio
Principio de funcionamiento Secuencia de acceso a memoria
Procesador genera dirección efectiva del dato Dato se busca primero en memoria cache Si dato se encuentra en el cache (acierto), se entrega al procesador Si dato no se encuentra en el cache (fallo), se busca en el siguiente
nivel de la jerarquía de memoria (ej. DRAM) Aprovechar localidad temporal
Si dato no se encuentra en el cache, traerlo al cache desde DRAM Porque es probable que se vuelva a direccionar pronto
Aprovechar localidad espacial En vez de traer palabra referenciada, traer un bloque de varias
palabras Porque es probable que se direccione pronto palabra cercana Accesos aleatorios a DRAM son lentos, pero acceso a direcciones
consecutivas es más rápido Ej. Bloques de 64 bytes: referencia palabra en dirección 24, traer
datos en direcciones 0-63. Referencia a palabra en dirección 96, traer datos en direcciones 64-127
Uso básico de caches Cuando se va a buscar instrucción, primero ver si
está en cache Si es un acierto, traer instrucción de cache a IR Si no está (fallo), ir al próximo nivel en la jerarquía de
memoria, hasta encontrarlo Cuando se ejecuta un load, primero ver si dato está
en cache Si es un acierto, leer dato de cache a registro destino Si es un fallo, ir al próximo nivel en jerarquía de memoria
hasta encontrarlo Cuando se ejecuta store, hay varias posibilidades
Al final se escribe en memoria en jerarquía de memoria Diferentes estrategias (Write through y Write back)
Acceso a cache para un load o búsqueda (fetch) de una instrucción
Cache es mucho más pequeña que memoria principal No todas las direcciones de memoria principal tiene una
correspondiente en cache Cuando una referencia a memoria es generada?
cuando CPU genera una dirección Se busca en cache, si ubicación de memoria está
mapeada en cache, tenemos un acierto. Contenido de ubicación en cache es retornado a CPU
Si no está en cache, tenemos un fallo y se busca en siguiente nivel de jerarquía de memoria
CPU
dirección
Cache
Memoria
Principal
Como sabemos donde
Buscar?
Como sabemos si hay
Acierto?
Memoria principal sólo se accesa si hay
fallo
acierto
fallo
Acceso a cache
Algunas preguntas-Alternativas de diseño Cómo sabemos si está en cache?
Identificación del bloque
Dónde lo ponemos en cache?
Ubicación del bloque Qué ocurre si cache está llena y queremos traer algo
nuevo?
Reemplazo del bloque O qué ocurre si queremos traer algo nuevo y el
lugar donde queremos ponerlo ya está ocupado? estrategia de escritura
Organización de cache genérica
dirección
direccióndireccióndireccióndirección
dirección
datadatadatadata
data
Dirección o tag
Generada por CPU
Si dirección (tag) generada por CPU = dirección (tag) de una entrada cache, tenemos un acierto en cache; el data en entrada cache es buena
Entrada en cache o bloque cache o linea cache
Identificación del bloque La ubicación de memoria puede
ser mapeada: A una única entrada, organización cache
es mapeada directa (direct mapped) en cualquier lugar del cache,
organización cache es completamente asociativa (full associative)
A una de varias entradas en cache, organización es asociativa por conjunto (set-associative)
Cache con Mapeo Directo
data
data
data
datadata
datatagtagtagtag
tag
tag
Tag indice d
Si tag (gen por dirección) = tag(entrada apuntada por índice en cache) y bit válido es on, tenemos acierto
d corresponde a número de bytes en el bloque
indice corresponde a número de bloques en cache
tag es lo que resta de direción
Estos campos tienen el mismo tamaño
Validez?
Identificación del bloque I Cache de traducción directa (direct-mapped) Para cache de 2N bytes, bloques de 2M bytes 2(N-M) bloques (líneas)
M bits inferiores son desplazamiento en el bloque (N-M) bits siguientes son índice en el cache (32-N) bits superiores de dirección son el “tag”,
Bloque se busca en la línea indicada por el índice Simple y rápida, pero tasa de fallos alta por conflictos
Ej. dirección: 0x34500010
N = 8 M = 4 Tag: 24 bitsÍndice: 4 bits
Ej: 0x1 Ej: 0x0
0
1
2
3
:
DatosByte 0
:
Ej: 0x345000
0x34500
Bit Validez
:
15
Byte 1Byte 15 :
Byte 16Byte 17Byte 31 :Byte 240Byte 255 :
Tag
Índice
0331
Tag Desplazamiento
7Dirección de bloque 48
Ejemplo: Cache de traducción directa
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x0000121
0x003A541
0x003A541
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x00001112
1 bit 24 bits
Despl.ÍndiceTag4424 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
Ejemplo: Cache de traducción directa
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x0000121
0x003A541
0x003A541
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x00001112
1 bit 24 bits
Despl.ÍndiceTag4424 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x003A5400
¡Acierto!
Ejemplo: Cache de traducción directa
Cache de 16 bloques, líneas de 16 bytes, direcciones de 24 bits
0x0000121
0x003A541
0x003A541
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x00001112
1 bit 24 bits
Despl.ÍndiceTag4424 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x003A5401
¡Acierto!
Ejemplo: Cache de traducción directa
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x0000121
0x003A541
0x003A541
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x00001112
1 bit 24 bits
Despl.ÍndiceTag4424 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x003A5410
¡Acierto!
Ejemplo: Cache de traducción directa
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x0000121
0x003A541
0x003A541
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x00001112
1 bit 24 bits
Despl.ÍndiceTag4424 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x00001256
¡Acierto!
Ejemplo: Cache de traducción directa
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x0000121
0x003A541
0x003A541
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x00001112
1 bit 24 bits
Despl.ÍndiceTag4424 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x00001112
¡Fallo!
Cómo verificar acierto
Para caches directamente mapeadas Verificar sólo campo tag de la única
posible entrada
Mapeo más restrictivo Una ubicación de bloque de memoria
sólo puede ser mapeado en un único lugar en el cache
Ejemplo: cache de acceso directo
Para cache tamaño 2N
(32-N) bits superiores de dirección son el “cache tag”, (N-M) bits siguientes son índice en el cache
M bits inferiores con desplazamiento en el bloque (tamaño 2M)
Bloque también llamado “línea” Ante un fallo, traer la línea completa del
siguiente nivel de memoria
Ejemplo: Cache con acceso directo
Cache Index
0
1
2
3
:
Cache DataByte 0
0731
:
Cache Tag Example: 0x3450
Ex: 0x01
0x3450
Stored as partof the cache “state”
Valid Bit
:255
Byte 1Byte 255 :
Byte 256Byte 257Byte 511 :
Byte 65026Byte 65535 :
Cache Tag
Byte Select
Ex: 0x00
15Block address
Dirección: 0x34500100N = 16=> 64K M = 8 =>256BTag: 16 bitsÍndice: 8 bits
Cache completamente asociativo Mapeo más general
Un bloque de dirección de memoria puede ser mapeado en cualquier parte del cache
Ningún cache de tamaño considerable es implementado de esta manera, pero es el comúnmente usado para el mapeo de páginas virtuales a físicas (disco, memoria principal) en pequeñas TLBs (ver más adelante)
Identificación del bloque II
Cache completamente asociativo (fully associative) Para cache de 2N bytes, bloques de 2M bytes 2(N-M) bloques
(líneas) M bits inferiores son desplazamiento en el bloque (32-M) bits superiores de dirección son el “tag”,
Bloque se busca en todas las líneas simultáneamente Menor tasa de fallos por conflictos, pero más compleja y lenta
Ej. dirección: 0x34500100
N = 8M = 4 Tag: 28 bits
:
Datos
Byte 0
0331
:
Tag
V
:
Byte 1Byte 15 :
Byte 16Byte 17Byte 31 :
Tag
Desplazamiento
Ej: 0x0
=
=
=
=
=
Ej: 0x345001
4
01
15
Cache asociativo
No hay índice Cualquier bloque de memoria puede
almacenarse en cualquier línea del cache Tag se compara con todas las líneas del
cache en paralelo N líneas N comparadores (alto costo) Por definición fallos de conflicto = 0
Ejemplo: Cache asociativo
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits 0x00001111
0x00001251
0x003A5411
0x003A5401
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 28 bits
Despl.Tag428 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
Ejemplo: Cache asociativo
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x00001111
0x00001251
0x003A5411
0x003A5401
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 28 bits
Despl.Tag428 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x003A5400
¡Acierto!
Ejemplo: Cache asociativo
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x00001111
0x00001251
0x003A5411
0x003A5401
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 28 bits
Despl.Tag428 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x003A5401
¡Acierto!
Ejemplo: Cache asociativo
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x00001111
0x00001251
0x003A5411
0x003A5401
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 28 bits
Despl.Tag428 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x003A5410
¡Acierto!
Ejemplo: Cache asociativo
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x00001111
0x00001251
0x003A5411
0x003A5401
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 28 bits
Despl.Tag428 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x00001256
¡Acierto!
Ejemplo: Cache asociativo
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x00001111
0x00001251
0x003A5411
0x003A5401
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 28 bits
Despl.Tag428 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x00001112 ¡Acierto!
Ejemplo: Cache asociativo
Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits
0x00001111
0x00001251
0x003A5411
0x003A5401
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 28 bits
Despl.Tag428 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
0x002C0510 ¡Fallo!
Cómo verificar acierto
Completamente asociativa Verificar todos los tags para ver si hay
alguno con la dirección generada por ALU
Muy cara, se tiene que realizar todas las comparaciones en paralelo
Normalmente no existen para caches de propósito general
Identificación del bloque III Cache asociativo por conjuntos (set-associative) Para cache de 2N bytes, bloques de 2M bytes 2(N-M) bloques (líneas)
Asociatividad 2K-way conjuntos de 2K líneas, 2(N-M-K) conjuntos M bits inferiores son desplazamiento en el bloque (N-M-K) bits siguientes son índice del conjunto (32-N+K) bits superiores de dirección son el “tag”,
Bloque se busca en todos las líneas del conjunto indicado por el índice Baja tasa de fallos por conflicto, más sencillo que cache asociativo
Ej. dirección: 0x34500100
N = 8M = 4 K = 1 (2-way)Tag: 25 bits
DatosTagV
:: :
Cache Data Tag V
: ::
Mux 01Sel1 Sel0
Dato
Tag Dir=
OR
Hit
Ej: 0x1 Ej: 0x0Ej: 0x345000 | 0b
Índice
0331
Tag Desplazamiento
6 47
Tag Dir=
Cache asociativo por set (conjunto) Mapeo menos restrictivo
Bloques en cache son agrupados en conjuntos y una ubicación de bloque de memoria se mapea en conjunto. Dentro del conjunto, el bloque de memoria puede ser puesto en cualquier parte. Asociativos de 2 (2-way set-associative), 4 , 8 y 16 se han implementado
Mapeo directo = 1-way set-associative Completamente asociativo con m
entradas es un m-way set-associative
Cache asociativo por conjuntos
Combinación de asociativo y directo Asociativo por conjuntos de N vías: N líneas por
índice en el cache Equivalente a N caches directos en paralelo
Ejemplo: cache asociativo por conjuntos de dos vías Índice selecciona un conjunto (set) Los dos tags se comparan en paralelo Si hay un acierto, seleccionar dato dentro del
conjunto
Cache asociativa por conjuntos
Cache Data
Cache Block 0
Cache TagValid
:: :
Cache Data
Cache Block 0
Cache Tag Valid
: ::
Cache Index
Mux 01Sel1 Sel0
Cache Block
CompareAdr Tag
Compare
OR
Hit
Ejemplo: Cache asociativo por conjuntos
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 25 bits
Despl.Tag425
16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
Ind.3
0x000012 | 0b1
0x003A54 | 0b1
0x003A54 | 0b1
0x000011 | 0b1
V Tag Datos1 bit 25 bits 16 bytes
Línea 0 Línea 1
Ejemplo: Cache asociativo por conjuntos
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 25 bits
Despl.Tag425
16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
Ind.3
0x000012 | 0b1
0x003A54 | 0b1
0x003A54 | 0b1
0x000011 | 0b1
V Tag Datos1 bit 25 bits 16 bytes
0x003A54|0b00¡Acierto! Línea 0 Línea 1
Ejemplo: Cache asociativo por conjuntos
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 25 bits
Despl.Tag425
16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
Ind.3
0x000012 | 0b1
0x003A54 | 0b1
0x003A54 | 0b1
0x000011 | 0b1
V Tag Datos1 bit 25 bits 16 bytes
0x003A54|0b01¡Acierto! Línea 0 Línea 1
Ejemplo: Cache asociativo por conjuntos
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 25 bits
Despl.Tag425
16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
Ind.3
0x000012 | 0b1
0x003A54 | 0b1
0x003A54 | 0b1
0x000011 | 0b1
V Tag Datos1 bit 25 bits 16 bytes
0x003A54|0b11¡Acierto! Línea 0 Línea 1
Ejemplo: Cache asociativo por conjuntos
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 25 bits
Despl.Tag425
16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
Ind.3
0x000012 | 0b1
0x003A54 | 0b1
0x003A54 | 0b1
0x000011 | 0b1
V Tag Datos1 bit 25 bits 16 bytes
0x000012|0b56¡Acierto! Línea 0 Línea 1
Ejemplo: Cache asociativo por conjuntos
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 25 bits
Despl.Tag425
16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
Ind.3
0x000012 | 0b1
0x003A54 | 0b1
0x003A54 | 0b1
0x000011 | 0b1
V Tag Datos1 bit 25 bits 16 bytes
0x000011|0b12¡Acierto! Línea 0 Línea 1
Ejemplo: Cache asociativo por conjuntos
Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits
V Tag Datos
Traza de direcciones
0x003A54000x003A54010x003A54100x000012560x000011120x002C0510
1 bit 25 bits
Despl.Tag425
16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
Ind.3
0x000012 | 0b1
0x003A54 | 0b1
0x003A54 | 0b1
0x000011 | 0b1
V Tag Datos1 bit 25 bits 16 bytes
0x002C05|0b10¡Fallo! Línea 0 Línea 1
Cómo verificar acierto
Para caches asociativas por set Verificar campo tag del conjunto (set) de
posibles entradas
Clasificación de fallos
Obligatorios (compulsory) Fallo por primer acceso al bloque Insignificantes en programas grandes con buena localidad
Capacidad (capacity) Tamaño del cache insuficiente para datos utilizados por programa
Conflicto (conflict) Dos bloques compiten por el mismo lugar en el cache (mismo índice) Cero para cache completamente asociativo, máximo para cache
directo
Coherencia (coherence) Elemento externo modifica memoria principal Necesario invalidar copia almacenada en el cache
Algunas preguntas-Alternativas de diseño Cómo sabemos si está en cache?
Identificación del bloque
Dónde lo ponemos en cache?
Ubicación del bloque Qué ocurre si cache está llena y queremos traer algo
nuevo?
Reemplazo del bloque Qué ocurre si queremos traer algo nuevo y el
lugar donde queremos ponerlo ya está ocupado? estrategia de escritura
Ubicación del bloque I Cache de traducción directa
Sólo en línea identificada por índice en dirección
V Tag Datos
Dirección
0x00001256
1 bit 24 bitsDespl.ÍndiceTag4424
16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
Ubicación del bloque II Cache completamente asociativo
En cualquier línea
V Tag Datos
Dirección
0x00001256
1 bit 24 bits 16 bytes
0x0
0x1
0x2
0x3
0x4
0x5
0x6
0x7
0x8
0x9
0xA
0xB
0xC
0xD
0xE
0xF
Despl.Tag428
Ubicación del bloque III Cache asociativo por conjuntos
Sólo en conjunto indicado por índice En cualquier línea dentro del conjunto
Despl.Tag427
Ind.3
Dirección
0x00001256 0x000012|0b56
0x0
V Tag Datos1 bit 27 bits 16 bytes
Conjunto 0 Conjunto 1
0x1
0x2
0x3
0x4
0x5
0x6
0x7
V Tag Datos1 bit 27 bits 16 bytes
Comparación
Cache asociativo por conjuntos de N vías vs. directo N comparadores vs. 1 Retardo de MUX adicional Obtiene dato después de determinar acierto/fallo En cache directo, datos disponibles antes de determinar
acierto/fallo Posible asumir acierto y corregir en caso de fallo
Cache asociativo por conjuntos de N vías vs. Asociativo N comparadores vs. M (M = #líneas/N; M >> N)
Alternativas de diseño a costo constante
Mapeo DirectoAsociativo por conjuntoDe N vias Asociativo completo
Fallo obligado
Tamaño Cache
Fallo por capacidad
Fallo por coherencia
Grande Mediano Pequeño
Mismo Mismo Mismo
Fallo por conflicto Alto Mediano Cero
Bajo Mediano Alto
Mismo Mismo Mismo
Tiempo de acierto aumenta con tamaño y asociatividad
Desempeño del cache
Tiempo promedio de acceso a memoria (average memory access time: AMAT) = (tasa acierto L1 x tiempo de acierto L1)+ (tasa fallo L1 x penalidad fallo L1)
Ej. L1 directoTasa de acierto L1 = 90%Tiempo de acierto L1 = 1 cicloTransferencia bloque DRAM a L1: 250 ciclos
AMAT = 0.90*1 + 0.10*250 = 25.9 ciclos
Desempeño del cache
Ej. 2Tasa de acierto L2 = 99%Tiempo de acierto L2: 10 ciclosTransferencia bloque DRAM a L2: 250 ciclos
Tiempo fallo(L1) = AMAT(L2) = 0.99 * 10 + 0.01 * 250 = 12.4 ciclosAMAT = 0.90 * 1 + 0.10 * 12.4 = 2.14 ciclos
Ej. 3 Repetir para L1 asociativo por conjuntos (Tasa acierto = 97%, tiempo acierto = 2 ciclos)
Sin L2: AMAT = 0.97*2 + 0.03*250 = 9.44 ciclosCon L2: AMAT = 0.97*2 + 0.03*12.4 = 2.312 ciclos
Recommended