advertisement

Memoria I

71 %
29 %
advertisement
Information about Memoria I

Published on August 5, 2007

Author: stefanosalvatori

Source: slideshare.net

advertisement

Sistemas de Memoria Cecilia Hernández

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ón Datos Memoria Procesador Entrada Salida

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

Desempeño de CPU vs. DRAM Performance ¡Mejorar sólo desempeño de CPU es insuficiente! µProc 60%/yr. (2X/1.5yr) DRAM 9%/año. (2X/10 años) 1 10 100 1000 1980 1981 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 DRAM CPU 1982 Procesador-Memoria Gap Desempeño: (crece 50% / año) “ Moore’s Law”

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 Memoria Secundaria (Disco) Procesador Registros Memoria Principal (DRAM) Cache L2 Datos, Inst. ~1 ~10,000,000 Velocidad (ciclos): ~1-5 ~100 ~100- 1000 40-400G Tamaño (bytes): ~32K ~512M-4G Cache L1 Inst Cache L1 Datos ~5-12 ~32K

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

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

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 Space 0 2^n - 1 Probability of reference

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

Tecnología de memoria Flip-flops Elementos individuales Escritura sincronizada por reloj Banco de registros SRAM (RAM estática) Organizada como arreglo unidimensional Rápido acceso, costosa: 6 transistores/bit Memorias cache DRAM (RAM dinámica) Dinámica: necesita ser refrescada periódicamente (8 ms) Organizada como arreglo bidimensional: filas ycolumnas Acceso lento, densa: 1 transistor/bit Memoria principal Costo/velocidad: SRAM/DRAM ~ 8-16 RAM: Random Access Memory (memoria de acceso aleatorio) velocidad costo y densidad

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

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

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, asociativo L2 I-TLB, D-TLB: 512 entradas, 4-way L1 I-cache, D-cache: 64KB, 2-way L2 cache unificada: 1MB, 16-way

Pentium 4 L2 IC DC L2 cache unificada: 512K, 8-way L1 I-cache: Trace cache L1 D-cache: 8KB Para más info: www.inf.udec.cl/~chernand/arquitectura/links/Pentium4.pdf

Trace Cache Execution Trace Cache Advanced L1 instruction cache removes decoder pipeline latency, and caches &quot;decoded&quot; instructions, thus improving efficiency and hit rate to cached instructions. L1 cache supplies up to 12K decoded instructions into the processor pipeline.

Execution Trace Cache Advanced L1 instruction cache removes decoder pipeline latency, and caches &quot;decoded&quot; 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ón www.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? U bicació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

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?

U bicació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

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

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)

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

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? U bicació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

Cómo sabemos si está en cache?

Identificación del bloque

Dónde lo ponemos en cache?

U bicació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ón dirección dirección dirección dirección data data data data 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 )

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 data data data tag tag tag tag 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 2 N bytes, bloques de 2 M 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 : Datos Byte 0 : Ej: 0x345000 0x34500 Bit Validez : 15 Byte 1 Byte 15 : Byte 16 Byte 17 Byte 31 : Byte 240 Byte 255 : Tag Índice 0 3 31 Tag Desplazamiento 7 Dirección de bloque 4 8

Cache de traducción directa (direct-mapped)

Para cache de 2 N bytes, bloques de 2 M 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

Ejemplo: Cache de traducción directa Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 1 bit 24 bits 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x000012 1 0x003A54 1 0x003A54 1 Despl. Índice Tag 4 4 24

Ejemplo: Cache de traducción directa Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 1 bit 24 bits 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x003A54 0 0 ¡Acierto! 0x000012 1 0x003A54 1 0x003A54 1 Despl. Índice Tag 4 4 24

Ejemplo: Cache de traducción directa Cache de 16 bloques, líneas de 16 bytes, direcciones de 24 bits V Tag Datos Traza de direcciones 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 1 bit 24 bits 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x003A54 0 1 ¡Acierto! 0x000012 1 0x003A54 1 0x003A54 1 Despl. Índice Tag 4 4 24

Ejemplo: Cache de traducción directa Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 1 bit 24 bits 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x003A54 1 0 ¡Acierto! 0x000012 1 0x003A54 1 0x003A54 1 Despl. Índice Tag 4 4 24

Ejemplo: Cache de traducción directa Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 1 bit 24 bits 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x000012 5 6 ¡Acierto! 0x000012 1 0x003A54 1 0x003A54 1 Despl. Índice Tag 4 4 24

Ejemplo: Cache de traducción directa Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 1 bit 24 bits 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x000011 1 2 ¡Fallo! 0x000012 1 0x003A54 1 0x003A54 1 Despl. Índice Tag 4 4 24

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

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 2 N (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 2 M ) Bloque también llamado “línea” Ante un fallo, traer la línea completa del siguiente nivel de memoria

Para cache tamaño 2 N

(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 2 M )

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 Data Byte 0 0 7 31 : Cache Tag Example: 0x3450 Ex: 0x01 0x3450 Stored as part of the cache “state” Valid Bit : 255 Byte 1 Byte 255 : Byte 256 Byte 257 Byte 511 : Byte 65026 Byte 65535 : Cache Tag Byte Select Ex: 0x00 15 Block address Dirección: 0x34500100 N = 16=> 64K M = 8 =>256B Tag: 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)

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 2 N bytes, bloques de 2 M 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 = 8 M = 4 Tag: 28 bits : Datos Byte 0 0 3 31 : Tag V : Byte 1 Byte 15 : Byte 16 Byte 17 Byte 31 : Tag Desplazamiento Ej: 0x0 = = = = = Ej: 0x345001 4 0 1 15

Cache completamente asociativo (fully associative)

Para cache de 2 N bytes, bloques de 2 M 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

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

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 V Tag Datos Traza de direcciones 0x003A540 0 0x003A540 1 0x003A541 0 0x0000125 6 0x0000111 2 0x002C051 0 1 bit 28 bits Despl. Tag 4 28 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x0000111 1 0x0000125 1 0x003A541 1 0x003A540 1

Ejemplo: Cache asociativo Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A540 0 0x003A540 1 0x003A541 0 0x0000125 6 0x0000111 2 0x002C051 0 1 bit 28 bits Despl. Tag 4 28 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x003A540 0 ¡Acierto! 0x0000111 1 0x0000125 1 0x003A541 1 0x003A540 1

Ejemplo: Cache asociativo Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A540 0 0x003A540 1 0x003A541 0 0x0000125 6 0x0000111 2 0x002C051 0 1 bit 28 bits Despl. Tag 4 28 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x003A540 1 ¡Acierto! 0x0000111 1 0x0000125 1 0x003A541 1 0x003A540 1

Ejemplo: Cache asociativo Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A540 0 0x003A540 1 0x003A541 0 0x0000125 6 0x0000111 2 0x002C051 0 1 bit 28 bits Despl. Tag 4 28 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x003A541 0 ¡Acierto! 0x0000111 1 0x0000125 1 0x003A541 1 0x003A540 1

Ejemplo: Cache asociativo Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A540 0 0x003A540 1 0x003A541 0 0x0000125 6 0x0000111 2 0x002C051 0 1 bit 28 bits Despl. Tag 4 28 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x0000125 6 ¡Acierto! 0x0000111 1 0x0000125 1 0x003A541 1 0x003A540 1

Ejemplo: Cache asociativo Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A540 0 0x003A540 1 0x003A541 0 0x0000125 6 0x0000111 2 0x002C051 0 1 bit 28 bits Despl. Tag 4 28 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x0000111 2 ¡Acierto! 0x0000111 1 0x0000125 1 0x003A541 1 0x003A540 1

Ejemplo: Cache asociativo Cache de 16 bloques, líneas de 16 bytes, direcciones de 32 bits V Tag Datos Traza de direcciones 0x003A540 0 0x003A540 1 0x003A541 0 0x0000125 6 0x0000111 2 0x002C051 0 1 bit 28 bits Despl. Tag 4 28 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x002C051 0 ¡Fallo! 0x0000111 1 0x0000125 1 0x003A541 1 0x003A540 1

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

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 2 N bytes, bloques de 2 M bytes  2 (N-M) bloques (líneas) Asociatividad 2 K -way  conjuntos de 2 K 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 = 8 M = 4 K = 1 (2-way) Tag: 25 bits Datos Tag V : : : Cache Data Tag V : : : Mux 0 1 Sel1 Sel0 Dato Tag Dir = OR Hit Ej: 0x1 Ej: 0x0 Ej: 0x345000 | 0b Índice 0 3 31 Tag Desplazamiento 6 4 7 Tag Dir =

Cache asociativo por conjuntos (set-associative)

Para cache de 2 N bytes, bloques de 2 M bytes  2 (N-M) bloques (líneas)

Asociatividad 2 K -way  conjuntos de 2 K 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

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

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

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 Tag Valid : : : Cache Index Mux 0 1 Sel1 Sel0 Cache Block Compare Adr Tag OR Hit Cache Data Cache Block 0 Cache Tag Valid : : : Compare

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 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 0x002C05 1 0 1 bit 25 bits Despl. Tag 4 25 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 Ind. 3 V Tag Datos 1 bit 25 bits 16 bytes Línea 0 Línea 1 0x000012 | 0b 1 0x003A54 | 0b 1 0x003A54 | 0b 1 0x000011 | 0b 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 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 0x002C05 1 0 1 bit 25 bits Despl. Tag 4 25 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 Ind. 3 V Tag Datos 1 bit 25 bits 16 bytes 0x003A54|0b 0 0 ¡Acierto! Línea 0 Línea 1 0x000012 | 0b 1 0x003A54 | 0b 1 0x003A54 | 0b 1 0x000011 | 0b 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 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 0x002C05 1 0 1 bit 25 bits Despl. Tag 4 25 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 Ind. 3 V Tag Datos 1 bit 25 bits 16 bytes 0x003A54|0b 0 1 ¡Acierto! Línea 0 Línea 1 0x000012 | 0b 1 0x003A54 | 0b 1 0x003A54 | 0b 1 0x000011 | 0b 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 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 0x002C05 1 0 1 bit 25 bits Despl. Tag 4 25 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 Ind. 3 V Tag Datos 1 bit 25 bits 16 bytes 0x003A54|0b 1 1 ¡Acierto! Línea 0 Línea 1 0x000012 | 0b 1 0x003A54 | 0b 1 0x003A54 | 0b 1 0x000011 | 0b 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 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 0x002C05 1 0 1 bit 25 bits Despl. Tag 4 25 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 Ind. 3 V Tag Datos 1 bit 25 bits 16 bytes 0x000012|0b 5 6 ¡Acierto! Línea 0 Línea 1 0x000012 | 0b 1 0x003A54 | 0b 1 0x003A54 | 0b 1 0x000011 | 0b 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 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 0x002C05 1 0 1 bit 25 bits Despl. Tag 4 25 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 Ind. 3 V Tag Datos 1 bit 25 bits 16 bytes 0x000011|0b 1 2 ¡Acierto! Línea 0 Línea 1 0x000012 | 0b 1 0x003A54 | 0b 1 0x003A54 | 0b 1 0x000011 | 0b 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 0x003A54 0 0 0x003A54 0 1 0x003A54 1 0 0x000012 5 6 0x000011 1 2 0x002C05 1 0 1 bit 25 bits Despl. Tag 4 25 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 Ind. 3 V Tag Datos 1 bit 25 bits 16 bytes 0x002C05|0b 1 0 ¡Fallo! Línea 0 Línea 1 0x000012 | 0b 1 0x003A54 | 0b 1 0x003A54 | 0b 1 0x000011 | 0b 1

Cómo verificar acierto Para caches asociativas por set Verificar campo tag del conjunto (set) de posibles entradas

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

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? U bicació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

Cómo sabemos si está en cache?

Identificación del bloque

Dónde lo ponemos en cache?

U bicació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 0x000012 5 6 1 bit 24 bits 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF Despl. Índice Tag 4 4 24

Cache de traducción directa

Sólo en línea identificada por índice en dirección

Ubicación del bloque II Cache completamente asociativo En cualquier línea V Tag Datos Dirección 0x0000125 6 1 bit 24 bits 16 bytes 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF Despl. Tag 4 28

Cache completamente asociativo

En cualquier línea

Ubicación del bloque III Cache asociativo por conjuntos Sólo en conjunto indicado por índice En cualquier línea dentro del conjunto Despl. Tag 4 27 Ind. 3 Dirección 0x000012 5 6 0x000012|0b 5 6 0x0 V Tag Datos 1 bit 27 bits 16 bytes Conjunto 0 Conjunto 1 0x1 0x2 0x3 0x4 0x5 0x6 0x7 V Tag Datos 1 bit 27 bits 16 bytes

Cache asociativo por conjuntos

Sólo en conjunto indicado por índice

En cualquier línea dentro del conjunto

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)

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 Directo Asociativo por conjunto De 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 directo Tasa de acierto L1 = 90% Tiempo de acierto L1 = 1 ciclo Transferencia bloque DRAM a L1: 250 ciclos AMAT = 0.90*1 + 0.10*250 = 25.9 ciclos

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 directo

Tasa de acierto L1 = 90%

Tiempo de acierto L1 = 1 ciclo

Transferencia bloque DRAM a L1: 250 ciclos

AMAT = 0.90*1 + 0.10*250 = 25.9 ciclos

Desempeño del cache Ej. 2 Tasa de acierto L2 = 99% Tiempo de acierto L2: 10 ciclos Transferencia bloque DRAM a L2: 250 ciclos Tiempo fallo(L1) = AMAT(L2) = 0.99 * 10 + 0.01 * 250 = 12.4 ciclos AMAT = 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 ciclos Con L2: AMAT = 0.97*2 + 0.03*12.4 = 2.312 ciclos

Add a comment

Related pages

Das Schwarze Auge: Memoria Test (PC) Von der Sehnsucht ...

Das Schwarze Auge: Memoria Test (PC) Von der Sehnsucht getrieben. Auch Gerons zweites DSA-Abenteuer geht nicht ins Auge: Memoria überzeugt im Test mit ...
Read more

Memoria - Daedalic Entertainment

Memoria. Memoria erzählt die Geschichte von Prinzessin Sadja aus dem fernen Fasar, die einst in die Schlacht gegen die Dämonen in die Gorische Wüste zog.
Read more

Memoria – Wikipedia

Memoria ist. ein Begriff aus der Rhetorik; eine Bezeichnung für das Memorialwesen; Gedächtniskirche für einen Märtyrer oder Heiligen; ein Asteroid ...
Read more

Gedenkseiten & Gedenkportal I QR-Code ... - e-memoria

Gedenkseiten mit QR-Code Plaketten I e-Memoria ist ein Gedenkportal unter werbefreien Gedenkseiten und Trauerseiten mit QR-Code Plaketten aus Edelstahl zur ...
Read more

memoria – Wiktionary

Referenzen und weiterführende Informationen: [1] Lateinischer Wikipedia-Artikel „memoria“ [1–11] Karl Ernst Georges: Ausführliches lateinisch ...
Read more

memoria

memoria blickt auf Erfahrungen im Bankensektor seit 2001, mehr als 10.700 zufriedene Teilnehmer in Seminaren, Trainings & Coachings, etwa 12,7 gefahrene ...
Read more

Memoria - Daedalic Entertainment

Memoria. Memoria tells the tale of princess Sadja of the faraway-land of Fasar, who once ventured into war to fight demons in the Gorian Desert.
Read more

Das Schwarze Auge: Memoria: Pc: Amazon.de: Games

Das Schwarze Auge: Memoria bei Amazon.de - Schneller & Kostenloser Versand ab 29€. Jetzt bestellen!
Read more

memoria24.de: 24 Stunden Pflege und Betreuung | häusliche ...

memoria24 bietet Ihnen 24-Stunden Pflege und Betreuung im eigenen Zuhause. Schnell, preiswert und immer ganz in Ihrer Nähe
Read more

MYMORIA Bestattung zusammenstellen und beauftragen

Bestattung zusammenstellen und online ein Angebot erhalten: Baumbestatttung, Seebestattung, Feuerbestattung, Erdbestattung, Alternative ...
Read more