Memoria I I

  • Published on
    05-Jul-2015

  • View
    5.027

  • Download
    4

Embed Size (px)

Transcript

<ul><li> 1. Sistemas de Memoria (II) Cecilia Hernndez</li></ul> <p> 2. Algunas preguntas Alternativas de diseo </p> <ul><li>Cmo sabemos si est en cache? </li></ul> <ul><li>Identificacin del bloque </li></ul> <ul><li>Dnde lo ponemos en cache? </li></ul> <ul><li>U bicacin del bloque </li></ul> <ul><li>Qu ocurre si cache est llena y queremos traer algo nuevo?</li></ul> <ul><li>Reemplazo del bloque </li></ul> <ul><li><ul><li>Qu ocurre si queremos traer algo nuevo y el lugar donde queremos ponerlo ya est ocupado?estrategia de escritura </li></ul></li></ul> <p> 3. Reemplazo de bloque </p> <ul><li>Cache de traduccin directa </li></ul> <ul><li><ul><li>No hay eleccin: slo una lnea disponible </li></ul></li></ul> <ul><li>Cache completamente asociativo </li></ul> <ul><li><ul><li>Todas las lneas disponibles, elegir lamejor </li></ul></li></ul> <ul><li>Cache asociativo por conjuntos </li></ul> <ul><li><ul><li>Todas las lneas dentro del conjunto disponibles, elegir lamejor </li></ul></li></ul> <p> 4. Eleccin de la lnea a reemplazar </p> <ul><li>Objetivo </li></ul> <ul><li><ul><li>Reemplazar la lnea que va a ser utilizada ms lejos en el futuro </li></ul></li></ul> <ul><li>Algoritmos de reemplazo </li></ul> <ul><li><ul><li>Random: elegir lnea al azar </li></ul></li></ul> <ul><li><ul><li>LRU (least recently used): elegir lnea menos recientemente utilizada </li></ul></li></ul> <p>Asociatividad 2-way 4-way 8-way Ejemplo: Tasas de fallo medidas en un benchmark 1.12% 1.12% 1.13% 1.13% 1.17% 1.15% 256KB 1.5% 1.4% 1.7% 1.5% 2.0% 1.9% 64KB 5.0% 4.4% 5.3% 4.7% 5.7% 5.2% 16KB Random LRU Random LRU Random LRU Tamao 5. Algunas preguntas Alternativas de diseo </p> <ul><li>Cmo sabemos si est en cache? </li></ul> <ul><li>Identificacin del bloque </li></ul> <ul><li>Dnde lo ponemos en cache? </li></ul> <ul><li>U bicacin del bloque </li></ul> <ul><li>Qu ocurre si cache est llena y queremos traer algo nuevo?</li></ul> <ul><li>Reemplazo del bloque </li></ul> <ul><li><ul><li>Qu ocurre si queremos traer algo nuevo y el lugar donde queremos ponerlo ya est ocupado?estrategia de escritura </li></ul></li></ul> <p> 6. Estrategia de escritura </p> <ul><li>Escritura sincrnica (write-through) </li></ul> <ul><li><ul><li>Escribir en el cache y en el nivel siguiente de la jerarqua </li></ul></li></ul> <ul><li>Escritura asincrnica (write-back) </li></ul> <ul><li><ul><li>Escribir slo en el cache, escribir en nivel siguiente slo al reemplazar el bloque </li></ul></li></ul> <ul><li><ul><li>Requiere un bit de estado adicional en el cache para indicar que bloque ha sido modificado (bit M) </li></ul></li></ul> <ul><li>Comparacin </li></ul> <ul><li><ul><li>WT </li></ul></li></ul> <ul><li><ul><li><ul><li>Pro: fallo de lectura no produce escrituras </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Con: alto costo de escritura a menos que se use un buffer</li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li><ul><li>Buffer siempre se usa para no esperar por DRAM </li></ul></li></ul></li></ul></li></ul> <ul><li><ul><li>WB </li></ul></li></ul> <ul><li><ul><li><ul><li>Pro: evitar escrituras mltiples del mismo bloque a DRAM </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Con: Ms complejo, fallo de lectura puede producir escritura </li></ul></li></ul></li></ul> <p> 7. Buffer de escritura para write-through </p> <ul><li>Buffer almacena escrituras pendientes </li></ul> <ul><li><ul><li>Procesador escribe en buffer y cache </li></ul></li></ul> <ul><li><ul><li>Controlador de memoria escribe contenidos del bloque a memoria </li></ul></li></ul> <ul><li>Buffer de escritura es FIFO </li></ul> <ul><li><ul><li>Nmero tpico de entradas: 4-8 </li></ul></li></ul> <ul><li>Nota: buffer de escritura puede producir conflicto RAW </li></ul> <ul><li><ul><li>Fallo de lectura antes de que el buffer haya escrito en DRAM </li></ul></li></ul> <ul><li><ul><li>Soluciones </li></ul></li></ul> <ul><li><ul><li><ul><li>Esperar a buffer vaco antes de servir el fallo de lectura </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Al servir fallo de lectura, verificar contenidos del buffer antes de ir a DRAM (bsqueda asociativa en buffer) </li></ul></li></ul></li></ul> <p>CPU Cache Buffer de escritura DRAM 8. Poltica ante fallo de escritura </p> <ul><li>Qu hacer si store produce un fallo? </li></ul> <ul><li><ul><li>Traer bloque al cache (write-allocate) </li></ul></li></ul> <ul><li><ul><li><ul><li>Evita fallo posterior si se lee del mismo bloque </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Pero si no se lee, habramos sacado del cache un bloque potencialmente importante </li></ul></li></ul></li></ul> <ul><li><ul><li>Slo escribir a DRAM (write-around) </li></ul></li></ul> <ul><li><ul><li><ul><li>Ahorra espacio en el cache si el bloque escrito no se accesa de nuevo en un tiempo largo </li></ul></li></ul></li></ul> <p> 9. Mejoras al desempeo </p> <ul><li>Cmo mejorar el desempeo? </li></ul> <ul><li><ul><li>Reducir tasa de fallos </li></ul></li></ul> <ul><li><ul><li>Reducir penalidad de fallos </li></ul></li></ul> <ul><li><ul><li>Reducir tiempo de acierto </li></ul></li></ul> <p>Desempeo dado por Tiempo Promedio de Acceso a Memoria En ingls Average Memory Access Time AMAT = tasa de aciertos*tiempo de acierto + (1- tasa de fallos)*penalidad de fallo AMAT = (1 - tasa de fallos) * tiempo de acierto + tasa de fallos * penalidad de fallo 10. Mejoras al desempeo </p> <ul><li>Cmo mejorar el desempeo? </li></ul> <ul><li><ul><li>Reducir tasa de fallos </li></ul></li></ul> <ul><li><ul><li>Reducir penalidad de fallos </li></ul></li></ul> <ul><li><ul><li>Reducir tiempo de acierto </li></ul></li></ul> <p>Desempeo dado por Tiempo Promedio de Acceso a Memoria En ingls Average Memory Access Time AMAT = tasa de aciertos*tiempo de acierto + (1- tasa de fallos)*penalidad de fallo AMAT = (1 -tasa de fallos ) * tiempo de acierto +tasa de fallos* penalidad de fallo 11. Reducir tasa de fallos (I) </p> <ul><li>Explotar localidad espacial con bloques ms grandes </li></ul> <ul><li><ul><li>Pero incrementa penalidad de fallo </li></ul></li></ul> <ul><li><ul><li>Tambin incrementa fallos por conflicto (menos bloques) </li></ul></li></ul> <p>Tamao de bloque (bytes)Tasa de Fallos0% 5% 10% 15% 20% 25% 16 32 64 128 256 1K 4K 16K 64K 256K 12. Reducir tasa de fallos (II) </p> <ul><li>Aumentar asociatividad </li></ul> <ul><li><ul><li>Regla 2:1 </li></ul></li></ul> <ul><li><ul><li><ul><li>Tasa fallos cache directo tamao N = tasa fallos cache APC de 2 vas tamao N/2 </li></ul></li></ul></li></ul> <ul><li><ul><li>Pero recordar que tiempo de acierto es mayor. </li></ul></li></ul> <p>Conflict Cache Size (KB)Miss Rate per Type 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 1 2 4 8 16 32 64 128 1-way 2-way 4-way 8-way CapacityCompulsory 13. Reducir tasa de fallos (III) </p> <ul><li>Cache de vctimas (victim cache) </li></ul> <ul><li><ul><li>Pequeo buffer asociativo almacena bloques recientemente eliminados del cache </li></ul></li></ul> <ul><li><ul><li>Reduce fallos por conflicto en cache directo manteniendo acceso rpido </li></ul></li></ul> <ul><li><ul><li>Jouppi[1990]: cache de vctimas de 4 entradas elimina 20%-95% de fallos de conflicto en cache directo de 4KB </li></ul></li></ul> <ul><li><ul><li>Utilizado en procesadores DEC Alpha y HP </li></ul></li></ul> <p>Al siguiente nivel de jerarqua Datos Tags Tag + comp Tag + comp Tag + comp Tag + comp Lnea datos Lnea datos Lnea datos Lnea datos 14. Operacin con Cache Vctima </p> <ul><li>1. Acierto en L1, no se necesita accesar a cache vctima </li></ul> <ul><li>2. Fallo en L1 por bloque en ubicacin b, acierto en cache vctima en ubicacin v, intercambiar contenido de b y v (toma un ciclo extra) </li></ul> <ul><li>3. Fallo en L1, fallo en cache vctima, cargar bloque del siguiente nivel en jerarqua y ponerlo en L1, poner bloque que estaba en L1 en cache vctima, si cache vctima esta llena, reemplazar una de las entradas </li></ul> <ul><li>Buffer vctima de 4 u 8 entradas para una cache mapeada directa funciona bien </li></ul> <p> 15. Cache vctima Fallo en L1 Fallo CV CPU direccin b DRAM Cache CV (1) Fallo L1 (2) Fallo CV 16. Cache vctima Fallo en L1 Fallo CV CPU direccin b DRAM m Cache CV (3) AciertoDRAMDato en bloque m 17. Cache vctima Fallo en L1 Fallo CV CPU direccin m DRAM m Cache CV (4) Copia bloque m En donde estaba b Y b en cache CV b 18. Cache vctima Fallo en L1, Acierto en CV CPU direccin b DRAM Cache CV Acierto En CV (2) Fallo en L1 (1) v 19. Reducir tasa de fallos (IV) </p> <ul><li>Prefetch </li></ul> <ul><li><ul><li>Traer bloques al cache antes de que el programa los requiera </li></ul></li></ul> <ul><li><ul><li>Reduce fallos obligatorios (compulsory) </li></ul></li></ul> <ul><li><ul><li>til cuando localidad espacial es muy buena (instrucciones y datos), pero requiere prediccin de saltos </li></ul></li></ul> <ul><li><ul><li>Cache de trazas (trace cache) </li></ul></li></ul> <ul><li><ul><li><ul><li>Integrar prefetch y prediccin: instrucciones en cache en orden de ejecucin </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Utilizado en arquitectura Netburst de Intel (Pentium 4) </li></ul></li></ul></li></ul> <ul><li><ul><li>Acceso a datos (ayuda por software): Instrucciones touch </li></ul></li></ul> <ul><li><ul><li><ul><li>Similar a load, pero indica al cache que dato se accesar pronto </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Presentes en procesadores IBM Power PC </li></ul></li></ul></li></ul> <p> 20. Mejoras al desempeo </p> <ul><li>Cmo mejorar el desempeo? </li></ul> <ul><li><ul><li>Reducir tasa de fallos </li></ul></li></ul> <ul><li><ul><li>Reducir penalidad de fallos </li></ul></li></ul> <ul><li><ul><li>Reducir tiempo de acierto </li></ul></li></ul> <p>Desempeo dado por Tiempo Promedio de Acceso a Memoria En ingls Average Memory Access Time AMAT = tasa de aciertos*tiempo de acierto + (1- tasa de fallos)*penalidad de fallo AMAT = (1 - tasa de fallos) * tiempo de acierto + tasa de fallos *penalidad de fallo 21. Reducir penalidad de fallos (I) </p> <ul><li>Mejorar desempeo de sistema de memoria principal (DRAM) </li></ul> <ul><li><ul><li>Bus de acceso a memoria ms rpido, ms ancho </li></ul></li></ul> <ul><li><ul><li><ul><li>Buses anchos tienen problemas de skew, preferible aumentar velocidad (ej. DDR, double-pumped Front Side Bus) </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Pentium 4 utiliza un bus de 200MHz 266MHz pero transfiere datos 4 veces por ciclo para un ancho de banda efectivo de 800MHz 1066MHz (quad-pumped) </li></ul></li></ul></li></ul> <ul><li><ul><li>Acceso por bloques entrelazado, paginado, sincrnico </li></ul></li></ul> <ul><li><ul><li><ul><li>Usado en servidores (chipset intel Orion) por costo de implem. </li></ul></li></ul></li></ul> <ul><li>En caso de fallo, traer al cache dato requerido primero, y resto del bloque despus </li></ul> <ul><li><ul><li>Latencia es alta de todas maneras </li></ul></li></ul> <ul><li><ul><li>til slo en bloques grandes </li></ul></li></ul> <ul><li><ul><li>Localidad espacial: probablemente hay que esperar el siguiente dato de todas formas </li></ul></li></ul> <p> 22. Reducir penalidad de fallo (II) </p> <ul><li>Buffer de escritura </li></ul> <ul><li><ul><li>Almacena escrituras a memoria pendientes </li></ul></li></ul> <ul><li><ul><li>Fallo de lectura tiene prioridad sobre buffer de escritura para acceso a DRAM </li></ul></li></ul> <ul><li><ul><li>Resolver conflictos RAW: buscar bloque en buffer de escritura antes de traer de DRAM </li></ul></li></ul> <ul><li>Fallos sin bloqueo </li></ul> <ul><li><ul><li>Permitir que procesador ejecute otras instrucciones mientras se resuelve el fallo </li></ul></li></ul> <ul><li><ul><li>Ejecucin desordenada de instrucciones </li></ul></li></ul> <ul><li><ul><li>til en procesadores superescalares o multihebra </li></ul></li></ul> <ul><li><ul><li>Problema: puede producirse otro fallo antes de resolver el primero </li></ul></li></ul> <ul><li><ul><li><ul><li>Pentium 4 puede manejar hasta 4 fallos simultneos </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Mltiples bancos de memoria mejoran desempeo </li></ul></li></ul></li></ul> <p> 23. Mejoras al desempeo </p> <ul><li>Cmo mejorar el desempeo? </li></ul> <ul><li><ul><li>Reducir tasa de fallos </li></ul></li></ul> <ul><li><ul><li>Reducir penalidad de fallos </li></ul></li></ul> <ul><li><ul><li>Reducir tiempo de acierto </li></ul></li></ul> <p>Desempeo dado por Tiempo Promedio de Acceso a Memoria En ingls Average Memory Access Time AMAT = tasa de aciertos*tiempo de acierto + (1- tasa de fallos)*penalidad de fallo AMAT = (1 - tasa de fallos) *tiempo de acierto+ tasa de fallos * penalidad de fallo 24. Reducir tiempo de acierto </p> <ul><li>Parmetro crtico para L1 </li></ul> <ul><li>Utilizar L1 directo + cache de vctimas o L2 </li></ul> <ul><li>Segmentar (pipeline) acceso a L1 </li></ul> <ul><li><ul><li>Etapa 1: determinar hit/miss </li></ul></li></ul> <ul><li><ul><li>Etapa 2: transferir dato a CPU </li></ul></li></ul> <ul><li>Tratar conflictos estructurales por acceso a L1 </li></ul> <ul><li><ul><li>Cache unificado: Un cache L1 para datos e instrucciones </li></ul></li></ul> <ul><li><ul><li><ul><li>Ventaja: mejor tasa de acierto </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Desventaja: conflictos estructurales (stalls) </li></ul></li></ul></li></ul> <ul><li><ul><li>Arquitectura Harvard: Dos cache L1 independientes para datos e instrucciones </li></ul></li></ul> <ul><li><ul><li><ul><li>Ventaja: elimina conflictos estructurales </li></ul></li></ul></li></ul> <ul><li><ul><li><ul><li>Desventaja: divisin del cache aumenta tasa de fallos </li></ul></li></ul></li></ul> <ul><li><ul><li>Hoy procesadores comerciales utilizan arquitectura Harvard </li></ul></li></ul> <ul><li><ul><li>Cache L2 tpicamente unificado </li></ul></li></ul> <p> 25. Arquitectura Harvard versus unificada </p> <ul><li>Ejemplo </li></ul> <ul><li><ul><li>Unificada: 32KB (tasa fallo 1.99%) </li></ul></li></ul> <ul><li><ul><li>Harvard: 16KB inst (tasa fallo 0.64%), 16 KB datos (tasa fallo 6.47%) </li></ul></li></ul> <ul><li>Cul es mejor? Ignorar L2 </li></ul> <ul><li><ul><li>Asumir 33% load/store, tpo. acierto: 1 ciclo, penalidad fallo: 50 ciclos </li></ul></li></ul> <p>CPU I-Cache L1 CPU Cache L1 Unificada Cache L2 Unificada D-Cache L1 Cache L2 Unificada Unificada Arquitectura Harvard AMAT = [AMAT fetch+ 0.33*AMAT datos ]/1.33 AMAT (Harvard) = [(0.9936*1 + 0.0064*50) + 0.33*(0.9353*1 + 0.0647*50)]/1.33 AMAT (Harvard) = 2.022 ciclos AMAT (Unificada) = [(0.9801*1 + 0.0199*50) + 0.33*(1 + 0.9801*1 + 0.0199*50)]/1.33 AMAT (Harvard) = 2.223 ciclos 26. Limitaciones de memoria principal </p> <ul><li>Cache acorta brecha entre velocidad de CPU y memoria principal (DRAM) </li></ul> <ul><li><ul><li>Cules son las limitaciones de la memoria principal? </li></ul></li></ul> <ul><li>Tamao </li></ul> <ul><li><ul><li>Programas poseen espacio de direcciones de 32 o 64 bits (registros de direcciones) </li></ul></li></ul> <ul><li><ul><li>Con 32 bits de direcciones, cada programa puede accesar 4GB de memoria </li></ul></li></ul> <ul><li><ul><li>20 programas en ejecucin (procesos): 80 GB de memoria principal! </li></ul></li></ul> <ul><li><ul><li>DRAM demasiado cara, disco demasiado lento </li></ul></li></ul> <ul><li><ul><li>Pero programas no utilizan realmente todo el espacio disponible </li></ul></li></ul> <ul><li>Reubicacin </li></ul> <ul><li><ul><li>Procesos pueden residir en cualquier parte de la memoria </li></ul></li></ul> <ul><li><ul><li>Pero programador/compilador no sabe dnde van a ejecutarse </li></ul></li></ul> <ul><li><ul><li>Cmo determinar las direcciones de memoria? </li></ul></li></ul> <ul><li>Proteccin </li></ul> <ul><li><ul><li>Procesos podran acceder a datos de otros programas en ejecucin </li></ul></li></ul> <ul><li><ul><li>O a datos del sistema operativo </li></ul></li></ul> <ul><li><ul><li>Vulnerabilidad de seguridad </li></ul></li></ul> <ul><li>Solucin:memoria virtual </li></ul> <p> 27. Memoria virtual </p> <ul><li>Procesos generan direcciones de memoriavirtuales </li></ul> <ul><li><ul><li>Ej. lw $t4, 128($t7) #[$t7+128] es una direccin virtual </li></ul></li></ul> <ul><li>Memoria principal (DRAM) acta como cache del disco </li></ul> <ul><li>Unidad de manejo de memoria ( MMU ) examina direccin virtual y determina si dato reside actualmente en DRAM </li></ul> <ul><li><ul><li>S: MMU genera direccin real (direccin en DRAM) </li></ul></li></ul> <ul><li><ul><li>No: MMU determina ubicacin en disco del dato y provoca excepcin </li></ul></li></ul> <ul><li>MMU adems provee protecciones </li></ul> <ul><li><ul><li>Direcciones de memoria slo para lectura, ejecucin, sistema operativo </li></ul></li></ul> <ul><li><ul><li>Espacios de memoria real separados para diferentes usuarios </li></ul></li></ul> <p> 28. Memoria Virtual </p> <ul><li>DRAM cache de disco </li></ul> <ul><li>Espacio virtual y fsico de direcciones </li></ul> <p>Espacio fsico de direcciones Espacio virtual de direcciones Disco 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 Tamao (bytes): ~32K ~512M-4G Cache L1 Inst Cache L1 Datos ~5-12 ~32K 29. Ventajas de memoria virtual </p> <ul><li>Traduccin </li></ul> <ul><li><ul><li>Memoria virtual lineal para cada proceso, pginas desordenadas en memoria principal </li></ul></li></ul> <ul><li><ul><li>Facilita mltiples procesos concurrentes en ejecucin </li></ul></li></ul> <ul><li><ul><li>Procesos ocupan slo una fraccin del espacio virtual disponible (conjunto de trabajo: working set) </li></ul></li></ul> <ul><li>Proteccin </li></ul> <ul><li><ul><li>Un proceso no puede corromper el espacio de memoria de otro </li></ul></li></ul> <ul><li><ul><li>Asignar roles distintos a diferentes pginas (cdigo, datos, sistema operativo) </li></ul></li></ul> <ul><li><ul><li>Proteccin de datos del sistema operativo </li></ul></li></ul> <ul><li>Compartir datos entre procesos </li></ul> <ul><li><ul><li>Direcciones virtuales de dos procesos pueden ser traducidas al mismo marco de pgina en memoria fsica. </li></ul></li></ul> <p> 30. Memoria virtual versus cache </p> <ul><li>Nomenclatura </li></ul> <ul><li><ul><li>Cache: bloque o lnea; MV: pgina, marcos de pgina </li></ul></li></ul> <ul><li>Principal diferencia: penalidad de fallo </li></ul> <ul><li><ul><li>Cache: tpo. acceso DRAM: ~100ns (~100 ciclos) </li></ul></li></ul> <ul><li><ul><li>MV: tpo. acceso disco: ~10ms (~10.000.000 ciclos!) </li></ul></li></ul> <ul><li>Consecuencias </li></ul> <ul><li><ul><li>Minimizar fallos: ubicacin de pginas completamente asociativa </li></ul></li></ul> <ul><li><ul><li>Poltica de escritura asincrnica (write-back) </li></ul></li></ul> <ul><li><ul><li>Pginas grandes: 4KB 16MB </li></ul></li></ul> <ul><li><ul><li><ul><li>Disco tiene alta latencia pero mejor ancho de banda: bajo costo incremental de accesar bloques ms grandes</li></ul></li></ul></li></ul> <ul><li><ul><li>Traduccin de direcciones por hardware, manejo de fallos por software </li></ul></li></ul> <ul><li><ul><li><ul><li>Sistema operativo ordena acceso a disco e implementa algoritmo de reemplazo </li></ul></li></ul></li></ul> <ul><li><ul><li>Penalidad de fallo demasiado alta para esperar: entregar CPU a otro proceso (o hebra) hasta que pgina est en memoria </li></ul></li></ul> <p> 31. Implementacin de Memoria Virtual </p> <ul><li>Paginacin </li></ul> <ul><li><ul><li>DRAM dividida en porciones iguales denominados marcos de pginas </li></ul></li></ul> <ul><li><ul><li>En MV denominadas pginas o pgina virtual </li></ul></li></ul> <ul><li><ul><li>Usa tabla de pgina traduccin de direcciones </li></ul></li></ul> <p>Espacio fsico de direcciones Espacio virtual de direcciones Disco pgina Marco