1
Download ©Mario Medina C. 1
Document related concepts
no text concepts found
Transcript
Sistemas computacionales Procesador Sección de Control Memorias y Cache Sistemas Computacionales Mario Medina C. [email protected] Entrada Memoria Sección de Datos Salida Sistema de memoria z z Almacena datos e instrucciones durante ejecución Incidencia dramática en desempeño del sistema global Ejecución de código accesa memoria de instrucciones Instrucciones movl, pushl, popl accesan memoria de datos Modelo de memoria Jerarquía de memoria Modelo de memoria utilizado hasta ahora z z z Vector lineal de bytes Almacena datos e instrucciones Tiempo de acceso constante a cualquier posición En la práctica, memoria está compuesta por una jerarquía de dispositivos con diferentes z z z capacidades costos tiempos de accesos Jerarquía de memoria Requerimientos z z z Capacidad Tiempo de acceso Costo Entregar gran cantidad de memoria, permitida por tecnología más barata Proveer alta velocidad de acceso, permitido por tecnología más rápida “El tiempo de acceso más rápido posible al costo más barato posible” Jerarquía de memoria Principio de funcionamiento z Jerarquía de almacenamiento de creciente tamaño y tiempo de acceso Mientras más grandes, más lentas z Niveles más rápidos de la jerarquía contienen una copia del subconjunto de datos más utilizados de los niveles de mayor tamaño Principio de inclusión ©Mario Medina C. 1 Principio de inclusión Nivel k: 4 9 14 3 Dispositivo más rápido, pequeño y caro en nivel k almacena un subconjunto de los bloques del nivel k+1 Jerarquía de memoria Registros en la CPU Memoria RAM (Random-Access Memory) z z Los datos se transfieren entre niveles en bloques z RAM estática (Static RAM ó SRAM) RAM dinámica (Dynamic RAM ó DRAM) ROM (Read-Only Memory) Almacenamiento secundario 0 1 2 4 5 6 7 8 9 10 11 12 13 14 15 Nivel k+1: z 3 Dispositivo más grande, barato y Lento del nivel k+1 está dividido en bloques z z Almacenamiento terciario (off-line) z Registros Registros z z z z z z z Almacena un bit en una celda biestable Internos al chip Rápidos (a la velocidad de la CPU) Pocos (Pentium 4 tiene 128) Elementos individuales Escritura sincronizada por reloj Muy alta velocidad y baja densidad Utilizados en banco de registros: múltiples puertas de lectura y escritura z z z Almacena bit como carga en un capacitor z Sólo 1 transistor y 1 capacitor por bit Capacitor necesita ser refrescado ~8ms Sensibles a perturbaciones como luz y ruido Memoria puede ser muy densa z Organizada como matriz de filas y columnas Utilizada para memoria principal y gráfica z Circuito de 6 transistores por bit Consume más energía que DRAM Mantiene el estado del bit mientras tenga energía Memoria más rápida y cara que DRAM Tiempo de acceso cercano a TCPU z Organizada como vector Utilizada en memorias cache Memoria dinámica (DRAM) z Medios magnéticos y/o ópticos Memoria estática (SRAM) z z Medios magnéticos y/o ópticos Memorias Flash Memoria en la nube? Tanto dentro como fuera del chip Memorias cache Memorias intermedias entre la CPU y la memoria RAM principal z Almacenan bloques de las instrucciones y datos más frecuentemente usados Aprovechan el principio de localidad z z Base del diseño de sistemas computacionales Localidad temporal y espacial Algunas utilizan códigos correctores de errores Tiempo de acceso cercano a 10xTCPU ©Mario Medina C. 2 Principio de localidad Probabilidad de referencia Principio de localidad Localidad espacial z 0 Espacio de direcciones 2n - 1 z 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 z z A CPU Desde CPU Ejemplo de localidad espacial int sumaVector(int v[n]) { int i, suma = 0; for (i = 0; i < n; i++){ suma += v[i]; } return suma; } Patrón de acceso secuencial Localidad temporal en suma e i z Cada elemento de v[] es accesado sólo una vez Localidad temporal y espacial en instrucciones Acierto (Hit): dato presente en bloque de nivel superior z Tasa de acierto (Hit rate): fracción de accesos a memoria encontrados en nivel superior Tiempo de acierto (Hit time): tiempo de acceso al nivel superior tiempo de acceso a memoria + tiempo para la determinación del acierto ©Mario Medina C. Nivel k+1 de memoria Bloque X Bloque Y Ejemplo de localidad espacial Localidad temporal en i, j, suma No hay localidad temporal en a[][] z Cada elemento de a[][] es accesado sólo una vez Localidad espacial en a[][] Terminología z Nivel k be memoria int sumaFilas(int a[m][n]) { int i, j, suma = 0; for (i = 0; i < m; i++){ for (j = 0; j < n; j++) { suma += a[i][j]; } } return suma; } Localidad espacial en v[] z Ejemplo: Leer instrucción N, luego N+1, luego N+2, etc., elementos de un vector Mover bloques de datos contiguos a los niveles superiores de la jerarquía de memoria Terminología Fallo (Miss): dato debe traerse de bloque de nivel inferior z z z Tasa de fallas (Miss rate): 1 – (Hit rate) Penalidad de fallo (Miss Penalty): tiempo para reemplazar el bloque en nivel superior + tiempo para entregar dato a CPU Generalmente, se da que Tiempo de acierto << penalidad de fallo 3 Memorias cache Primer nivel en la jerarquía de memoria z z z Accesada en ciclo Fetch y Write Back Típicamente en el mismo chip del procesador Varios niveles: L1, L2, a veces L3 Principio de funcionamiento Secuencia de acceso a memoria z z z Tiempo de acceso compatible con velocidad CPU z z Pequeña y rápida 1-3 ciclos para cache L1 z Objetivo z 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) Mantener el subconjunto de datos más utilizado por el programa dentro del cache Principio de funcionamiento Aprovechar localidad temporal z z 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 z z En vez de traer palabra referenciada, traer un bloque de varias palabras Porque es probable que se direccione pronto palabra cercana Principio de funcionamiento Memorias DRAM organizadas como matrices de bits z Acceso rápido a bits consecutivos de la misma fila Memorias DRAM transfieren datos en bloques o líneas z z Accesos aleatorios a memorias DRAM son lentos Accesos a direcciones consecutivas son rápidos Principio de funcionamiento Alternativas de diseño Memoria RAM típicamente usa bloques de 64 bytes 1. ¿Cómo se encuentra el bloque si éste está en el cache? (identificación del bloque) 2. Al traer un nuevo bloque, ¿dónde almacenar el bloque en el cache? (ubicación del bloque) 3. ¿Qué bloque reemplazar en caso de un fallo? (reemplazo del bloque) 4. ¿Qué pasa al escribir? (estrategia de escritura) z z z Referencia a palabra en dirección 24 trae datos de las direcciones 0-63 Referencia a palabra en dirección 96 trae datos de las direcciones 64-127 Localidad temporal Si ahora se necesita la dirección 96, pronto se la necesitará de nuevo z Localidad espacial Si ahora se necesita la dirección 96, pronto se necesitarán las direcciones 97, 98, 99, etc. ©Mario Medina C. 4 Cache de traducción directa z z Bloque se busca en la línea indicada por el índice Simple y rápida, pero tasa de fallos alta por conflictos Dirección de bloque 31 8 7 Ej: 0x345000 Bit Validez 4 3 Índice Tag Ej: 0x1 Byte 15 Byte 31 0x345000 4 4 Índice Despl. Cache de 16 bloques Líneas de 16 bytes Direcciones de 32 bits 24 bits Tag 0x0 1 0x003A54 0x1 1 0x003A54 16 bytes Datos 0x3 0x4 Traza de direcciones 0x003A5400 0x003A5401 0x003A5410 0x00001256 0x00001112 0x5 1 0x6 0x7 0x8 0x9 0xA Tag 4 4 Índice Despl. Cache de traducción directa 4 Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits Traza de direcciones Acierto! 0x003A5400 0x003A5401 0x003A5410 0x00001256 0x00001112 1 bit V 24 bits Tag 0x0 1 0x003A54 0x1 1 0x003A54 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 1 0x000012 16 bytes Datos 24 Tag 4 4 Índice Despl. Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits Traza de direcciones Acierto! 0x003A5400 0x003A5401 0x003A5410 0x00001256 0x00001112 0xE 0xF ©Mario Medina C. 1 0x003A54 1 0x000012 Datos 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xD 0xE 1 bit V 24 bits Tag 0x0 1 0x003A54 0x1 1 0x003A54 1 0x000012 16 bytes Datos 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0x003A5401 0x1 16 bytes Cache de traducción directa 0xB 0xD 0x003A54 0xF 0xF Despl. 24 bits Tag 1 0xC 0x003A5400 0xE 4 1 bit V 0x0 0xB 0xD Índice 15 0x3 0xC 24 Byte 240 0x2 0xB Tag 1 Cache de traducción directa Traza de direcciones Acierto! 0x003A5400 0x003A5401 0x003A5410 0x00001256 0x00001112 0x000012 0 Byte 16 : : Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits 0x2 Byte 0 Byte 17 3 : 24 1 bit V Byte 1 2 Cache de traducción directa 24 Ej: 0x0 Datos Tag Byte 255 Tag 0 Desplazamiento : z 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” : z Ej. dirección: 0x34500010 N = 8 M = 4 Tag: 24 bits Índice: 4 bits : Cache de traducción directa (direct-mapped) Para cache de 2N bytes Cache de traducción directa 0xC 0x003A5410 0xD 0xE 0xF 5 Cache de traducción directa 4 Despl. Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits 1 bit V 24 bits Tag 0x0 1 0x003A54 0x1 1 0x003A54 16 bytes Datos 0x3 0x4 0x5 1 4 4 Índice Despl. Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits 0x2 Traza de direcciones Acierto! 0x003A5400 0x003A5401 0x003A5410 0x00001256 0x00001112 24 Tag 0x6 0x7 0x8 0x9 0xA Bloque se busca en todas las líneas simultáneamente 0x8 0x9 0xA Cache completamente asociativa 4 Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits 1 bit V Traza de direcciones 0x003A5400 Acierto! 0x003A5401 0x003A5410 0x00001256 0x00001112 0x004E5135 0x003A5400 1 0x003A540 1 0x003A541 0x2 0x4 0x5 0x6 0x7 1 0x0000125 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF ©Mario Medina C. 28 bits Tag 0x1 0x3 0xE 0xF Cache completamente asociativa Ej. dirección: 0x34500100 N=8 M=4 Tag: 28 bits 31 4 3 Tag 1 0x0000111 0 Desplazamiento Ej: 0x0 Ej: 0x345001 V = Datos Byte 15 = Byte 31 Byte 1 Byte 0 Byte 17 Byte 16 1 0 = = : = 0x0 0xD Tag Menor tasa de fallos por conflictos, pero más compleja y lenta Despl. 0x000012 0x7 Conflicto en acceso a línea 1 M bits inferiores son desplazamiento en el bloque (32-M) bits superiores de dirección son el “tag” Tag 1 0x6 0xC Cache completamente asociativo (fully associative) Para cache de 2N bytes, bloques de 2M bytes Æ 2(N-M) bloques (líneas) 28 0x003A54 0x5 0x00001112 0xE Cache completamente asociativa z 1 0xB 0xD 0xF z 0x1 0x4 0xC z 0x003A54 0x3 0xB 0x00001256 24 bits Tag 1 0x2 Traza de direcciones Fallo! 0x003A5400 0x003A5401 0x003A5410 0x00001256 0x00001112 0x000012 16 bytes Datos 1 bit V 0x0 : 4 Índice : 24 Tag Cache de traducción directa : : 15 Cache completamente asociativa 28 4 Tag Despl. 16 bytes Datos 1 bit V Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits Traza de direcciones 0x003A5400 Acierto! 0x003A5401 0x003A5410 0x00001256 0x00001112 0x004E5135 0x003A5401 0x0 28 bits Tag 1 0x003A540 1 0x003A541 1 0x0000125 1 0x0000111 16 bytes Datos 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF 6 Cache completamente asociativa 28 4 Tag Despl. 1 bit V 0x0 Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits 1 28 bits Tag 16 bytes Datos 0x003A540 0x2 1 28 4 Tag Despl. 0x003A541 0x3 0x003A5410 1 0x0000125 0x8 0x9 1 0x0000111 0xB 0xC 0xD 4 Despl. Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits 0x7 28 bits Tag 0xA 1 0x003A540 1 0x003A541 0x2 0xC 0xD 0xE 28 4 Tag Despl. 0x0001112 0x6 1 0x0000125 0x8 0x9 0xA 1 0x0000111 0xB 0xC 0xD 0x3 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 z Baja tasa de fallos por conflicto, más sencillo que cache asociativo 0x003A541 1 0x0000125 1 0x0000111 0x6 0x7 0x8 0x9 0xA 0xB 0xC 0xD 0xE 0xF Cache asociativa por conjuntos Ej. dirección: 0x34500100 N=8M=4 K = 1 (2-way) Tag: 25 bits 7 6 31 V Tag Datos : : : Tag Dir = 4 3 Índice Tag Ej: 0x345000 | 0b Sel1 Ej: 0x0 Datos 1 Mux 0 Sel0 0 Desplazamiento Ej: 0x1 Tag : V : : = Tag Dir OR Hit ©Mario Medina C. 1 0x5 0x004E5135 0xE Cache asociativo por conjuntos (set-associative) Para cache de 2N bytes, bloques de 2M bytes Æ 2(N-M) bloques Asociatividad 2K-way Æ conjuntos de 2K líneas, 2(N-M-K) conjuntos z 0x003A540 0x2 Traza de direcciones 0x003A5400 0x003A5401 0x003A5410 Fallo! 0x00001256 0x00001112 0x004E5135 Cache asociativa por conjuntos z 16 bytes Datos 28 bits Tag 1 0x1 0xF z 1 bit V 0x0 Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits 0x4 0x5 0x7 0x0000111 0xB 0x4 Traza de direcciones 0x003A5400 0x003A5401 0x003A5410 Acierto! 0x00001256 0x00001112 0x004E5135 1 0x9 Cache completamente asociativa 16 bytes Datos 0x1 0x3 0x0000125 0x8 0xF 1 bit V 0x0 1 0x6 0x0001256 0xE Cache completamente asociativa 28 0x003A541 0x5 0xF Tag 1 0x4 0x6 0xA 0x003A540 0x2 Traza de direcciones 0x003A5400 0x003A5401 0x003A5410 Acierto! 0x00001256 0x00001112 0x004E5135 0x5 0x7 16 bytes Datos 28 bits Tag 1 0x1 0x4 Traza de direcciones Acierto! 0x003A5400 0x003A5401 0x003A5410 0x00001256 0x00001112 0x004E5135 1 bit V 0x0 Cache de 16 bloques líneas de 16 bytes direcciones de 32 bits 0x1 0x3 Cache completamente asociativa Dato 7 Cache asociativa por conjuntos Cache asociativa por conjuntos 25 3 4 25 3 4 Tag Ind. Despl. Tag Ind. Despl. Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits Traza de direcciones 0x003A5400 0x003A5401 1 bit 0x003A5410 V 0x0 1 0x00001256 1 0x1 0x00001112 0x2 0x002C0510 Línea 0 25 bits Tag 16 bytes Datos 1 bit V Línea 1 25 bits Tag Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits Traza de direcciones 0x003A5400 0x003A5401 1 bit 0x003A5410 V 0x0 1 0x00001256 1 0x1 0x00001112 0x2 0x002C0510 16 bytes Datos 0x003A54 | 0b 1 0x003A54 | 0b 0x000011 | 0b 0x3 Acierto! 1 Acierto! 0x000012 | 0b 0x5 0x6 0x7 0x7 Traza de direcciones 0x003A5400 0x003A5401 1 bit 0x003A5410 V 0x0 1 0x00001256 0x1 1 0x00001112 0x2 0x002C0510 16 bytes Datos 0x003A54 | 0b 1 0x003A54 | 0b 1 0x000011 | 0b 0x000012 | 0b 25 3 4 25 3 4 Tag Ind. Despl. Tag Ind. Despl. Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits Línea 0 25 bits Tag 16 bytes Datos 1 bit V Línea 1 25 bits Tag Traza de direcciones 0x003A5400 0x003A5401 1 bit 0x003A5410 V 0x0 1 0x00001256 0x1 1 0x00001112 0x2 0x002C0510 16 bytes Datos 0x003A54 | 0b 1 0x003A54 | 0b 0x000011 | 0b 0x3 0x5 Línea 0 25 bits Tag 16 bytes Datos 1 bit V Línea 1 25 bits Tag 16 bytes Datos 0x003A54 | 0b 0x003A54 | 0b 1 0x000011 | 0b 0x3 0x4 1 Acierto! 0x000012 | 0b 0x4 0x5 0x6 0x6 0x7 0x7 0x003A5410 1 0x000012 | 0b 0x00001256 Clasificación de fallos Cache asociativa por conjuntos 25 3 4 Tag Ind. Despl. Obligatorios (compulsory) Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits z Traza de direcciones 0x003A5400 0x003A5401 1 bit 0x003A5410 V 0x0 1 0x00001256 0x1 1 0x00001112 0x2 0x002C0510 z Línea 0 25 bits Tag 16 bytes Datos 1 bit V Línea 1 25 bits Tag 0x003A54 | 0b 0x003A54 | 0b 1 0x000011 | 0b z 0x6 0x7 Tamaño del cache insuficiente para datos del programa Conflicto (conflict) z Dos bloques compiten por el mismo lugar en el cache Cero para cache completamente asociativo, máximo para cache directo 0x4 0x5 Fallo por primer acceso al bloque Muy bajos en programas grandes con buena localidad Capacidad (capacity) 16 bytes Datos 0x3 ©Mario Medina C. Línea 1 25 bits Tag Cache asociativa por conjuntos Cache de 16 bloques, 2-way, líneas de 16 bytes, direcciones de 32 bits 0x00001112 V 0x003A5401 Cache asociativa por conjuntos Acierto! 1 bit 0x4 0x6 0x003A5400 Acierto! 16 bytes Datos 0x3 0x4 0x5 Línea 0 25 bits Tag 1 0x000012 | 0b Coherencia (coherence) z z Elemento externo modifica memoria principal Necesario invalidar copia almacenada en el cache 8 Tasas de fallo por tipo 0.14 1-way (directo) Tasa de fallo por tipo 0.12 0.1 Aumentar la asociatividad disminuye la tasa de fallos Conflicto 2-way Tasas de fallo por tipo 4-way 0.08 z 8-way 0.06 Capacidad (asociativa) Obligatorio 0.04 0.02 0 Aumentar el tamaño de la cache disminuye la tasa de fallos 128 64 32 16 8 2 4 z 1 Mayores beneficios al pasar de cache directa a asociativa de 2 conjuntos z Tamaño del cache (KB) Pasado un cierto tamaño, ventajas son marginales Fallos obligatorios son dominantes Alternativas de diseño 1. ¿Cómo se encuentra el bloque si éste está en el cache? (identificación del bloque) Ubicación del bloque (I) Cache de traducción directa z Sólo en línea identificada por índice en dirección 24 2. Al traer un nuevo bloque, ¿dónde almacenar el bloque en el cache? (ubicación del bloque) Tag 4 4 Índice Despl. 1 bit V 24 bits Tag 16 bytes Datos 0x0 Dirección 0x00001256 0x1 0x2 0x3 3. 0x4 ¿Qué bloque reemplazar en caso de un fallo? (reemplazo del bloque) 0x5 0x6 0x7 0x8 0x9 4. 0xA ¿Qué pasa al escribir? (estrategia de escritura) 0xB 0xC 0xD 0xE 0xF Ubicación del bloque (II) Cache asociativo por conjuntos Cache completamente asociativo z Ubicación del bloque (III) En cualquier línea z z 28 Tag Dirección 0x00001256 4 1 bit V Despl. 24 bits Tag 16 bytes Datos Sólo en conjunto indicado por índice En cualquier línea dentro del conjunto 27 Tag 3 4 Ind. Despl. 0x0 0x1 0x2 0x3 Dirección 0x00001256 0x000012|0b56 Conjunto 0 0x4 1 bit V 0x5 0x6 0x7 0x0 0x8 0x1 0x9 0x2 0xA 0x3 0xB 0x4 0xC 0x5 0xD 0x6 0xE 0x7 27 bits Tag 16 bytes Datos Conjunto 1 1 bit V 27 bits Tag 16 bytes Datos 0xF ©Mario Medina C. 9 Alternativas de diseño 1. ¿Cómo se encuentra el bloque si éste está en el cache? (identificación del bloque) 2. Al traer un nuevo bloque, ¿dónde almacenar el bloque en el cache? (ubicación del bloque) 3. ¿Qué bloque reemplazar en caso de un fallo? (reemplazo del bloque) 4. ¿Qué pasa al escribir? (estrategia de escritura) Reemplazo de bloque Cache de traducción directa z No hay elección: sólo una línea disponible Cache completamente asociativo z Todas las líneas disponibles, elegir la mejor Cache asociativo por conjuntos z Todas las líneas dentro del conjunto disponibles, elegir la mejor Elección de línea a reemplazar Objetivo z Reemplazar línea a ser utilizada más lejos en el futuro Elección de línea a reemplazar Ejemplo: Tasas de fallo medidas en un benchmark z Algoritmos de reemplazo z z z Random: elegir línea al azar FIFO: Primera en entrar, primera en salir LRU (Least Recently Used) Elegir línea menos recientemente utilizada por última vez Asociatividad 2. 4. 4-way 8-way LRU Random LRU Random LRU Random 16KB 5.2% 5.7% 4.7% 5.3% 4.4% 5.0% 64KB 1.9% 2.0% 1.5% 1.7% 1.4% 1.5% 1.15% 1.17% 1.13% 1.13% 1.12% 1.12% 256KB Estrategias de escritura ¿Cómo se encuentra el bloque si éste está en el cache? (identificación del bloque) Escritura sincrónica (Write Through) Al traer un nuevo bloque, ¿dónde almacenar el bloque en el cache? (ubicación del bloque) Escritura asincrónica (Write Back) z z 3. 2-way Tamaño Alternativas de diseño 1. Para la mayoría de las aplicaciones, LRU tiene mejor desempeño que FIFO o Random ¿Qué bloque reemplazar en caso de un fallo? (reemplazo del bloque) z Escribir en el cache y en el nivel siguiente de la jerarquía Escribir sólo en el cache, escribir en nivel siguiente sólo al reemplazar el bloque Requiere un bit de estado adicional en el cache para indicar que bloque ha sido modificado ¿Qué pasa al escribir? (estrategia de escritura) ©Mario Medina C. 10 Comparación de estrategias Write-Through z z Buffer de escritura para Write-Through Buffer almacena escrituras pendientes Fallo de lectura no produce escrituras Alto costo de escritura a menos que se use un buffer z z Buffer siempre se usa para no esperar por DRAM Write-Back z z Procesador escribe datos tanto en buffer como en la cache Controlador de memoria de la CPU escribe contenidos del buffer a memoria Buffer de escritura es FIFO Evita escrituras múltiples del mismo bloque a DRAM Más complejo, fallo de lectura puede producir escritura z Número típico de entradas: 4-8 Cache CPU DRAM Buffer de escritura Política ante fallo de escritura Buffer de escritura para Write-Through Uso de buffer de escritura puede producir conflictos z ¿Qué hacer si escritura produce un fallo? z Fallo de lectura por un bloque que está en en buffer de escritura antes que éste haya sido escrito en DRAM Última versión de ese bloque está en el buffer! Esperar a vaciar el buffer antes de servir el fallo de lectura y leer bloque desde DRAM Al servir fallo de lectura, verificar contenidos del buffer antes de ir a la DRAM (búsqueda asociativa en buffer) Desempeño de memorias cache AMAT: Average Memory Access Time Tiempo promedio de acceso a memoria Se calcula como AMAT = tasa de acierto*tiempo de acierto + tasa de fallo*penalidad de fallo z Tiempo de acierto: tiempo de transferencia entre cache y la CPU z Penalidad de fallo: Tiempo de transferencia de un bloque entre DRAM y cache z z ©Mario Medina C. Traer bloque al cache (Write Allocate) Evita fallo posterior si se lee del mismo bloque Pero si no se lee, habríamos sacado del cache un bloque potencialmente importante z Sólo escribir a DRAM Ahorra espacio en el cache si el bloque escrito no se accesa de nuevo en un tiempo largo Desempeño de memorias cache Memoria cache pequeña pero rápida Tasa de acierto: 0.9 Tiempo de acierto: 1 Penalidad de fallo: 100 Memoria cache grande pero lenta Tasa de acierto: 0.98 Tiempo de acierto: 8 Penalidad de fallo: 100 AMAT = 0.9 * 1 + (1 – 0.9) * 100 AMAT = 10.9 ciclos AMAT = 0.98 * 8 + (1 – 0.98) * 100 AMAT = 9.84 ciclos 11 Mejoras al desempeño AMAT = tasa de acierto*tiempo de acierto + tasa de fallo*penalidad de fallo ¿Cómo mejorar el desempeño? z z z Reducir tasa de fallos Explotar localidad espacial con bloques más grandes z z Pero incrementa penalidad de fallo También incrementa fallos por conflicto (menos bloques) 25% Reducir tasa de fallos Reducir penalidad de fallos Reducir tiempo de acierto 1K 20% Tasa de Fallos 4K 15% 16K 10% 64K 5% 256 128 64 32 256K 16 0% Tamaño de bloque (bytes) Reducir tasa de fallos Aumentar asociatividad y/o tamaño z Cache de víctimas (Victim Cache) También aumenta tiempo de acierto Tasa de fallo por tipo 0.14 0.12 z 1-way (directo) Conflicto 2-way 0.1 4-way 0.08 Reducir tasa de fallos z 8-way 0.06 Capacidad (asociativa) Obligatorio 0.04 z 128 64 32 8 4 2 1 0 16 0.02 Tamaño del cache (KB) z Pequeño buffer asociativo almacena bloques recientemente eliminados del cache Reduce fallos por conflicto en cache directo manteniendo acceso rápido Jouppi[1990]: cache de víctimas de 4 entradas elimina 20%-95% de fallos de conflicto en cache directo de 4KB Utilizado en procesadores DEC Alpha y HP Reducir tasa de fallos Búsqueda anticipada (Prefetch) z z z z Transferir bloques de DRAM a la cache antes de que el programa los requiera Reduce fallos obligatorios (Compulsory misses) Útil cuando localidad espacial es muy buena (instrucciones), pero requiere predicción de saltos En el caso de data prefetch, puede sacar de la cache bloques que aún están en uso ©Mario Medina C. Tags Datos Tag + comp Línea datos Tag + comp Línea datos Tag + comp Línea datos Tag + comp Línea datos Al siguiente nivel de jerarquía Reducir tasa de fallos Cache de trazas (Trace cache) Integrar prefetch y predicción: instrucciones en cache en orden de ejecución Utilizado en arquitectura Netburst de Intel (Pentium 4) z Acceso a datos (ayuda por software): Instrucciones TOUCH Similar a instrucción LOAD, pero indica al cache que dato se accesará pronto Programador puede indicar al compilador patrón de uso de datos 12 Reducir tasa de fallos Arquitecturas “stream” z z z z Sub-procesador especializado lee datos en forma adelantada y los almacena en colas de memoria internas “Coprocesador de transferencias” Útil si el patrón de acceso a datos es predecible, regular y conocido de antemano Utilizado en procesadores digitales de señales (DSP) Mejoras al desempeño AMAT = tasa de acierto*tiempo de acierto + tasa de fallo*penalidad de fallo ¿Cómo mejorar el desempeño? z z z Reducir penalidad de fallos Mejorar desempeño de sistema de memoria principal (DRAM) z Bus de CPU-memoria más rápido, más ancho Buses anchos tienen problemas de skew y interferencia (crosstalk), preferible aumentar velocidad Pentium 4 utiliza un bus de 200MHz – 266MHz pero transfiere datos 4 veces por ciclo para un ancho de banda efectivo de 800MHz – 1066MHz z Reducir penalidad de fallos En caso de fallo, traer al cache primero el dato requerido, y el resto del bloque después z z z z Acceso por bloques entrelazado, paginado, sincrónico Reducir penalidad de fallo Buffer de escritura z z z z Almacena escrituras a memoria pendientes Controlador de memoria escribe bloques a DRAM en forma independiente de CPU Fallo de lectura tiene prioridad sobre buffer de escritura para acceso a DRAM Si fallo de lectura posterior es a bloque residente en buffer de escritura, se debe buscar bloque en buffer de escritura en vez de leerlo desde DRAM ©Mario Medina C. Reducir tasa de fallos Reducir penalidad de fallos Reducir tiempo de acierto Si se necesita el byte 24, traer los bytes 24-63 ahora y los bytes 0-23 después Útil sólo en bloques grandes Latencia es alta de todas maneras Localidad espacial: probablemente hay que esperar el siguiente dato de todas formas Reducir penalidad de fallo Fallos sin bloqueo z Permitir que procesador ejecute otras instrucciones mientras se resuelve el fallo Ejecución desordenada de instrucciones puede traer problemas si no se maneja adecuadamente z z Útil en procesadores superescalares o multihebra Problema: puede producirse otro fallo antes de resolver el primero Pentium 4 puede manejar hasta 4 fallos simultáneos Múltiples bancos de memoria mejoran desempeño 13 Reducir penalidad de fallo Usar una cache de nivel 2 z Atiende a los accesos que producen un fallo en la cache de nivel 1 Tener cache de nivel 2 afecta a la penalidad de fallo de cache de nivel 1 z La penalidad de fallo de cache de nivel 2 será el tiempo de acceso a DRAM y los tiempos de reemplazo correspondientes Esquema extensible a 3 o más niveles Reducir penalidad de fallo AMAT = tasa de acierto L1*tiempo de acierto L1 + tasa de fallo L1*penalidad de fallo L1 penalidad de fallo L1 = tasa de acierto L2*tiempo de acierto L2 + tasa de fallo L2*penalidad de fallo L2 Penalidad de fallo L2 = tiempo de acceso DRAM Desempeño de memorias cache Recordar el ejemplo anterior Memoria cache pequeña pero rápida Tasa de acierto: 0.9 Tiempo de acierto: 1 Penalidad de fallo: 100 Memoria cache grande pero lenta Tasa de acierto: 0.98 Tiempo de acierto: 8 Penalidad de fallo: 100 AMAT = 0.9 * 1 + (1 – 0.9) * 100 AMAT = 10.9 ciclos AMAT = 0.98 * 8 + (1 – 0.98) * 100 AMAT = 9.84 ciclos Desempeño de memorias cache Usar cache pequeño pero rápida como cache L1 y cache grande pero más lenta como cache L2 AMAT L2 = 9.84 AMAT = 1*0.9 + 0.1*9.84 CPU AMAT = 1.88 ciclos Cache L1 Cache L2 Mejoras al desempeño AMAT = tasa de acierto*tiempo de acierto + tasa de fallo*penalidad de fallo ¿Cómo mejorar el desempeño? z z z Reducir tasa de fallos Reducir penalidad de fallos Reducir tiempo de acierto ©Mario Medina C. Reducir tiempo de acierto Tiempo de acierto es el parámetro crítico del desempeño de cache L1 Utilizar L1 directo + cache de víctimas o L2 Segmentar (pipeline) acceso a L1 z z Etapa 1: determinar hit/miss Etapa 2: transferir dato a CPU 14 Reducir tiempo de acierto Cache unificado vs. Harvard Cache unificado: Un cache L1 para datos e instrucciones z z CPU Cache L1 Unificada Mejor tasa de acierto Puede hacer conflictos estructurales (stalls) z Elimina conflictos estructurales División del cache aumenta tasa de fallos CPUS comerciales utilizan arq. Harvard z Típicamente, cache L2 unificado Cache unificada z z z z Ignorar efectos de L2, que es igual para ambas Asumir que 1/3 de las instrucciones leen ó escriben datos Tiempo de acierto: 1 ciclo Penalidad de fallo: 50 ciclos AMAT = AMATinstrucción+AMATdatos*1/3 1 + 1/3 Cache unificado vs. Harvard AMAT de Cache unificada z [(0.9801*1 + 0.0199*50) + 0.33*(1 + 0.9801*1 + 0.0199*50)]/1.33 AMAT Cache unificada = 2.223 ciclos AMAT de Arquitectura Harvard z ©Mario Medina C. Arquitectura Harvard Ejemplo z Cache unificada: 32KB, tasa de fallo 1.99% z Harvard: 16KB instrucciones (fallo 0.64%) 16 KB datos (fallo 6.47%) Cache unificado vs. Harvard ¿Cuál es mejor? D-Cache L1 Cache L2 Unificada Cache L2 Unificada Arquitectura Harvard: Dos caches L1 para datos e instrucciones z CPU I-Cache L1 [(0.9936*1 + 0.0064*50) + 0.33*(0.9353*1 + 0.0647*50)]/1.33 AMAT Harvard = 2.022 ciclos 15
