Gestión de memoria

Arquitectura de Sistemas Paralelos (1)

Gestión de memoria Índice y bibliografía • Índice – Jerarquía de memoria – Memorias cache • Organización física • Organización lógica • Optimización

– Memoria virtual

• Bibliografía – Arquitectura de computadores: Un enfoque cuantitativo, John L. Hennessy y David A. Patterson – Organización y arquitectura de computadores, W. Stalling. Arquitectura de Sistemas Paralelos (2)

Jerarquía de memoria Introducción • Necesidad de grandes cantidades de memoria rápida • Diferentes tipos de memorias según los criterios de tamaño, velocidad y coste (tecnología) • Principio de localidad: los programas favorecen una parte de su espacio de direcciones Idealmente sería deseable una capacidad indefinidamente grande de memoria tal que cualquier particular…palabra estuviese inmediatamente disponible… Estamos… forzados a reconocer la posibilidad de construir una jerarquía de memorias, cada una de las cuales tenga mayor capacidad que la precedente pero que sea menos rápidamente accesible A.W. Burks, H.H. Goldstine y J. von Neumann, Discusión preliminar del diseño lógico de un instrumento de cálculo electrónico (1946) Arquitectura de Sistemas Paralelos (3)

Jerarquía de memoria Principio de localidad

• Localidad temporal – Si se referencia un elemento, éste tenderá a ser referenciado pronto (p.e. bucles)

• Localidad espacial – Si se referencia un elemento, los elementos cercanos a él tenderán a ser referenciado pronto (p.e. tablas) Arquitectura de Sistemas Paralelos (4)

Jerarquía de memoria Definición • Una jerarquía de memoria es una reacción natural a la localidad y tecnología • Una jerarquía en memoria está organizada en varios niveles, cada uno más pequeño, más rápido y más caro por byte que el siguiente • Los niveles de la jerarquía están contenidos en el siguiente: todos los datos de un nivel se encuentran también en el nivel siguiente y así sucesivamente hasta que alcancemos el extremo inferior de la jerarquía Arquitectura de Sistemas Paralelos (5)

Jerarquía de memoria Conceptos básicos • •

• • • •

Nivel (level) Bloque o línea (block or line): mínima unidad de información que puede estar presente o no en la jerarquía de dos niveles (tamaño fijo o variable) Acierto/Fallo (hit/miss) Frecuencia de aciertos/fallos (hit rate/miss rate) Tiempo de acierto (hit time) Penalización por fallo (miss penalty) – Tiempo de acceso (access time): tiempo para acceder a la primera palabra de un bloque en un fallo – Tiempo de transferencia (transfer time): tiempo adicional para transferir las restantes palabras del bloque Arquitectura de Sistemas Paralelos (6)

Nivel superior

Bloques

Nivel inferior

Jerarquía de memoria Ejemplo

Coste/bit (+) Capacidad (-) Velocidad (+) Frecuencia de accesos (+)

Registros procesador Cache Memoria principal Cache de disco Disco magnético CD-DVD

Arquitectura de Sistemas Paralelos (7)

Jerarquía de memoria Evaluación del rendimiento • Tiempo medio de acceso a memoria Tiempo de acceso medio a memoria = Tiempo de acierto + + Frecuencia de fallos*Penalización por fallo

• Influencia de parámetros – El tamaño de bloque influye sobre: • Penalización por fallo → Tiempo de acceso medio a memoria • Frecuencia de fallos

Arquitectura de Sistemas Paralelos (8)

Evaluación del rendimiento Relación entre parámetros Tiempo medio de acceso

Tamaño del bloque

Penalización por fallo

Tiempo de transferencia

Frecuencia por fallo

Tiempo de acceso Tamaño del bloque

Tamaño del bloque

Arquitectura de Sistemas Paralelos (9)

Jerarquía de memoria Criterios para clasificar los niveles • Ubicación de bloque ¿Dónde puede ubicarse un bloque en el nivel superior?

• Identificación de bloque ¿Cómo se encuentra un bloque si está en el nivel superior?

• Sustitución de bloque ¿Qué bloque debe reemplazarse en caso de fallo?

• Estrategia de escritura ¿Qué ocurre en una escritura? Arquitectura de Sistemas Paralelos (10)

Memorias cache Introducción • Representa el nivel de jerarquía de memoria entre la CPU y la memoria principal • Se le pueden aplicar todos los conceptos vistos para la jerarquía de memoria (principio de localidad, terminología, etc.) • Algunos datos (década del 90)

Arquitectura de Sistemas Paralelos (11)

Memorias cache Arquitecturas

• Organización física • Según su ubicación dentro o fuera del chip procesador: internas o externas • Según su ubicación con respecto al resto de dispositivos (configuración)

• Organización lógica • Según su estructura interna y funcionamiento: ubicación, identificación, sustitución y escritura • Según el tipo de información que contienen: unificadas o separadas Arquitectura de Sistemas Paralelos (12)

Arquitecturas de memorias cache Organización física • Según su ubicación – Caches externas: No se encuentran en el interior del chip del procesador (cache-off-chip) – Caches internas: Se encuentran en el propio chip del proceador (cache-on-chip)

• Según la configuración – Configuración en serie (Look-Through Architecutre) – Configuración en paralelo (Look-Aside Architecture) Arquitectura de Sistemas Paralelos (13)

Organización física según la configuración Configuración en serie CPU

Bus local Cache

DMA

I/O

Memoria

Bus – Ventajas: Si el dato se encuentra en la cache no hay acceso a memoria y no se ocupa el bus – Inconvenientes: La cache debe tener 2 interfaces de buses diferentes y el tiempo de acceso es mayor (igual al tiempo de acceso a cache más el tiempo de acceso a memoria principal) Arquitectura de Sistemas Paralelos (14)

Organización física según la configuración Configuración en paralelo Cache

DMA

I/O

Memoria

Bus

CPU

– Ventajas: Sólo hay una interfaz con el bus y el tiempo de acceso es menor (igual al tiempo de acceso a memoria principal) – Inconvenientes: El bus se ocupa en cualquier acceso a memoria, evitando que otros dispositivos puedan acceder a él Arquitectura de Sistemas Paralelos (15)

Organización física Ejemplo: Pentium II

Arquitectura de Sistemas Paralelos (16)

Organización lógica Ubicación de bloque • ¿Dónde puede ubicarse un bloque en una cache? – Caches de mapeado o correspondencia directa: si cada bloque sólo tiene un lugar donde puede aparecer en la cache (dirección del bloque) MOD (número de bloques en cache)

– Caches totalmente o completamente asociativas: si cada bloque se puede colocar en cualquier parte de la cache – Caches asociativas por conjuntos (asociativas por conjuntos de n vías): si cada bloque se puede colocar en un subconjunto restringido de lugares de la cache (conjunto). Un conjunto es un grupo de dos o más bloques de la cache (dirección del bloque) MOD (número de conjuntos en cache) Arquitectura de Sistemas Paralelos (17)

Ubicación de bloque

Memoria: 32 bloques Caches: 8 bloques Tres tipos: - Completamente asociativas - De correspondencia directa - Asociativa por conjuntos de 2 vías

Arquitectura de Sistemas Paralelos (18)

Organización lógica Identificación de bloque • ¿Cómo se encuentra un bloque si está en el nivel superior? La dirección se descompone en varios campos: – Etiqueta (tag): se utiliza para comparar la dirección requerida por la CPU con aquellos bloques que pueden contener la información deseada (búsqueda en paralelo de etiquetas) – Índice (index): se usa para seleccionar el conjunto en el caso de las asociativas por conjunto o el bloque en las de mapeado directo (conjuntos de una vía). No existe para las completamente asociativas – Desplazamiento de bloque (block offset): selecciona el dato deseado dentro del bloque

• ¿Cómo se sabe que un bloque contiene información válida? Mediante el bit de válido (valid bit) • Al calcular el coste de las caches hay que incluir el coste debido al almacenamiento de las etiquetas y el de los bits necesarios Arquitectura de Sistemas Paralelos (19)

Identificación de bloque Según el tipo de cache (I) • En caches de mapeado directo: Etiqueta

Índice

Desplazamiento

(Bloque)

• En caches asociativas por conjunto: Etiqueta

Índice

Desplazamiento

(Conjunto)

• En caches completamente asociativas: Etiqueta

Arquitectura de Sistemas Paralelos (20)

Desplazamiento

Identificación de bloque Según el tipo de cache (II)

Memoria: 32 bloques Caches: 8 bloques Tres tipos: - Completamente asociativas - De correspondencia directa - Asociativa por conjuntos de 2 vías

Arquitectura de Sistemas Paralelos (21)

Identificación de bloque Ejemplos • • •

1 2 3

Procesador de 16 bits de datos y 24 de direcciones Tamaño de la cache: 8Kb Tamaño de la línea: 8 bytes 1. Cache completamente asociativa 2. Cache asociativa por conjuntos de 4 vías 3. Cache de mapeado directo Etiqueta: 21bits

Desplazamiento: 3bits Palabra: 2bits

Etiqueta: 13bits

Conjunto: 8bits

Desplazamiento: 3bits Palabra: 2bits

Etiqueta: 11bits

Bloque: 10bits

Byte:1bit

Desplazamiento: 3bits Palabra: 2bits

Arquitectura de Sistemas Paralelos (22)

Byte:1bit

Byte:1bit

Identificación de bloque Implementación de caches de mapeado directo

Arquitectura de Sistemas Paralelos (23)

Identificación de bloque Implementación de caches totalmente asociativas

Arquitectura de Sistemas Paralelos (24)

Identificación de bloque Implementación de caches asociativas por conjuntos

Arquitectura de Sistemas Paralelos (25)

Identificación de bloque Ejemplo: VAX-11/780

- Cache asociativa por conjunto de 2 vías - Capacidad de datos: 8Kb - Tamaño de bloque: 8 bytes - Número de conjuntos: 512 Pasos de un acierto: 1) División de la dirección 2) Acceso a ambos bancos 3) Comparación de etiquetas 4) Multiplexación 5) Envío a la CPU

Arquitectura de Sistemas Paralelos (26)

Organización lógica Políticas de sustitución de bloque (I) • ¿Qué bloque debe reemplazarse en caso de fallo? Se pueden seguir diferentes estrategias: – Aleatoria (Random): Se elige un bloque al azar – FIFO (First Input First Out): Se sustituye el bloque que más tiempo ha estado en la cache – LRU (Least Recently Used): Se sustituye el bloque que más tiempo ha estado en la cache sin ser referenciado – LFU (Least Frecuently Used): Se sustituye el bloque que menos referencias ha tenido

• Se tienen en cuenta criterios de coste y eficiencia • Los esquemas más utilizados son el aleatorio y el LRU Arquitectura de Sistemas Paralelos (27)

Organización lógica Políticas de sustitución de bloque (II) Ejemplo de política LRU (cache de 4 bloques) Dirección Bloque LRU

0

3

2

1

0

0

2

3

1

3

0

0

0

0

3

3

3

1

0

0

2

Comparativa de frecuencias de fallos (VAX, 16bytes/bloque)

Arquitectura de Sistemas Paralelos (28)

Organización lógica Políticas de escritura (I) • ¿Qué ocurre en una escritura? Opciones a la hora de escribir en la cache: – Escritura directa (Write through): La información se escribe en el bloque de la cache y en el bloque de la memoria de nivel inferior – Postescritura (Copy Back): La información se escribe sólo en el bloque de la cache. El bloque modificado de la cache se escribe en la memoria de nivel inferior sólo cuando es reemplazado

• Los bloques de las caches copy back se denominan sucios o modificados cuando la información de la cache difiere de la memoria de nivel inferior • Para reducir la frecuencia de postescrituras en el reemplazo se usa el bit de modificación o sucio (dirty bit): si el bloque está limpio no se escribe en el nivel inferior • Cuando una cache es write through, la CPU debe esperar la finalización de cada escritura antes de proceder con la siguiente operación. Para evitarlo se utiliza un buffer de escritura que permite al procesador continuar mientras se actualiza la memoria Arquitectura de Sistemas Paralelos (29)

Organización lógica Políticas de escritura (II) • Ventajas de las caches copy back: – En las caches copy back, las escrituras se realizan a la velocidad de la memoria cache, y múltiples escrituras en un bloque requieren sólo una escritura en la memoria de nivel inferior – Como cada escritura no va a memoria, la postescritura utiliza menos ancho de banda (multiprocesadores)

• Ventajas de las caches write through: – En las caches write through, los fallos de lectura no ocasionan escrituras en el nivel inferior – Las caches write through son más fáciles de implementar – La escritura directa tiene la ventaja también de que la memoria principal tiene la copia más reciente de los datos (coherencia de cache, multiprocesadores y E/S) Arquitectura de Sistemas Paralelos (30)

Organización lógica Políticas de escritura (III) • ¿Qué ocurre en una escritura? Opciones cuando se produce un fallo de escritura: – Ubicar en escritura (Write allocation): El bloque se carga en la cache y a continuación se escribe sobre él (similar a un fallo en lectura) – No ubicar en escritura (No write allocatation): El bloque se modifica en el nivel inferior y no se carga en la cache

• Aunque cualquier política de fallo de escritura puede utilizarse con la escritura directa o con la postescritura, las caches copy back utilizan write allocation (CB-WA) y las write through usan no write allocation (WT-NWA)

Arquitectura de Sistemas Paralelos (31)

Organización lógica Caches unificadas vs. Caches separadas • •

Caches unificadas o mixtas (unified or mixed): Contienen tanto datos como instrucciones Caches separadas (separated): Existe una cache para datos y otra para instrucciones Ventajas – No hay competencia entre el procesador de instrucciones y la unidad de ejecución – Duplicación del ancho de bus (puertos separados) – Parámetros de diseño (capacidad, tamaños de bloque, asociatividad, etc.) diferentes para instrucciones y datos (optimización) Inconvenientes – En general la tasa de fallos global es algo mayor (próxima transparencia): • la caches de instrucciones tienen menor frecuencia de fallos que las de datos (localidad) • la separación de instrucciones y datos elimina fallos debidos a conflictos pero al dividir también se fija el espacio de cache dedicado a cada tipo

– No se equilibra la carga de trabajo de forma automática Arquitectura de Sistemas Paralelos (32)

Caches unificadas vs. Caches separadas Comparativa (I) Comparativa de frecuencias de fallos (VAX, 16 bytes/bloque, LRU, 2 vías)

Ejemplo: Frecuencia de fallos (53% de referencias son instrucciones) – En cache unificada de 32Kb: 4.3% – En caches separadas de 16Kb: 53%*3.6%+47%*5.3%=4.4% Arquitectura de Sistemas Paralelos (33)

Caches unificadas vs. Caches separadas Comparativa (II) •

Ejemplo: (75% de accesos a instrucción) a)

b)

Cache unificada de 32Kb. Penalización: 50 ciclos, Tiempo de acierto para instrucción: 1 ciclo, para datos: 2 ciclos (un solo puerto) Caches separadas de 16Kb. Penalización: 50 ciclos, Tiempo de acierto: 1 ciclo

Solución: a) b)

Tacceso medio =75%*(1+4.3%*50)+25%*(2+4.3*50)= 3.4 ciclos Tacceso medio=75%*(1+3.6%*50)+25%*(1+5.3%*50)= 2.6 ciclos

Arquitectura de Sistemas Paralelos (34)

Optimización Cómo mejorar el rendimiento de las caches • El objetivo es reducir el tiempo medio de acceso a memoria: Tiempo de acceso medio a memoria = Tiempo de acierto + + Frecuencia de fallos*Penalización por fallo • Existen tres formas de reducir el tiempo medio de acceso a memoria: – Reducir los fallos de la cache (miss rate) – Reducir las penalizaciones por fallo (miss penalty) – Reducir el tiempo de acceso en caso de acierto (hit time)

Arquitectura de Sistemas Paralelos (35)

Optimización Reducción de fallos en las caches • Existen tres tipos de fallos en una memoria cache: – Forzosos (Compulsory): En el primer acceso a un bloque éste no se encuentra en la cache (fallos de arranque en frío o de primera referencia) – Capacidad (Capacity): La cache no puede contener todos los bloques necesarios durante la ejecución de un programa – Conflicto (Conflict): Diferentes bloques deben ir necesariamente al mismo conjunto o línea cuando la estrategia es asociativa por conjuntos o de correspondencia directa (fallos de colisión)

Arquitectura de Sistemas Paralelos (36)

Reducción de fallos en las caches Tipos de fallos (I)

Arquitectura de Sistemas Paralelos (37)

Reducción de fallos en las caches Tipos de fallos (II)

Arquitectura de Sistemas Paralelos (38)

Reducción de fallos de la cache Técnica: Incremento del tamaño de bloque (I) • Incrementar el tamaño de bloque – Ventajas: Se reducen los fallos forzosos como sugiere el principio de localidad espacial – Inconvenientes: Aumentan los fallos por conflicto al reducirse el número de bloques de la cache y los fallos de capacidad si la cache es pequeña. La penalización por fallo aumenta al incrementarse el tiempo de transferencia del bloque Penalización por fallo

Tiempo de transferencia Tiempo de acceso

Frecuencia por fallo

Tamaño del bloque

Tamaño del bloque

Arquitectura de Sistemas Paralelos (39)

Reducción de fallos de la cache Técnica: Incremento del tamaño de bloque (II)

Arquitectura de Sistemas Paralelos (40)

Reducción de fallos de la cache Técnica: Incremento del tamaño de bloque (III)

Ejemplo: Tiempo de búsqueda = 40CLK Tasa de transferencia= 8bytes/CLK Tiempo de acierto= 1CLK a) Cache de 1Kb con línea de 16bytes b) Cache de 256Kb con línea de 256bytes Solución: a) Tiempo de acceso medio a memoria = 1+15.05%*(40+2)=7.321 ciclos b) Tiempo de acceso medio a memoria = 1+0.49%*(40+32)=1.353 ciclos Arquitectura de Sistemas Paralelos (41)

Reducción de fallos de la cache Técnica: Incremento de la asociatividad • Aumentar la asociatividad – Ventajas: Se reducen los fallos por conflicto – Inconveniente: Aumenta el tiempo de acceso medio al incrementarse el tiempo de acierto (multiplexión). También aumenta el coste debidos a los comparadores Cache de mapeado directo (1Kb): tamm= 1+(0.133*50)=7.65 ciclos Cache asociativa por conjuntos de 8 vías (128Kb): tamm= 1.14+(0.006*50)=1.44 ciclos

Tiempo medio de acceso a memoria (ciclos) Arquitectura de Sistemas Paralelos (42)

Reducción de fallos de la cache Técnica: Cache victima (I) • Caches víctimas: Consiste en añadir una pequeña cache totalmente asociativa (1-5 bloques) para almacenar bloques descartados por fallos de capacidad o conflicto. En caso de fallo, antes de acceder a la memoria principal se accede a esta cache. Si el bloque buscado se encuentra en ella se intercambian los bloques de ambas caches – Cache víctima de 4 bloques reduce del 20% al 95% los fallos de conflicto en una cache de correspondencia directa de 4Kb (Jouppi 1990) Arquitectura de Sistemas Paralelos (43)

Reducción de fallos de la cache Técnica: Cache victima (II)

Arquitectura de Sistemas Paralelos (44)

Reducción de fallos de la cache Técnica: Cache pseudo-asociativa • Caches pseudo-asociativas (o columna asociativa): Consiste en utilizar toda la capacidad de la cache para reubicar algunos bloques extra en bloques que en principio no les pertenece – Implementación: Cuando en una cache de correspondencia directa se falla, antes de ir a buscar en la memoria principal puede intentarse en otro bloque (el correspondiente al índice pero con el bit más significativo invertido) del “pseudo conjunto” Tiempo de acierto Tiempo de pseudo-acierto

Tiempo de fallo

Arquitectura de Sistemas Paralelos (45)

Reducción de fallos de la cache Técnica: Pre-búsqueda hardware de instrucciones y datos • Pre-búsqueda hardware de instrucciones y dato: Consiste en que cuando se accede a memoria en caso de fallo no sólo se trae el bloque solicitado sino también los consecutivos, almacenándolos en un buffer. Si en el próximo acceso el bloque se encuentra en el buffer, se cancela el acceso en curso a la cache, se lee el bloque del buffer y comienza una nueva solicitud de pre-búsqueda. – En un sistema con caches de datos e instrucciones separadas de 64Kb asociativas de 4 vías, un buffer de 8 bloques eliminan del 50% al 70% de los fallos (Palacharna and Kessler 1994)

Arquitectura de Sistemas Paralelos (46)

Reducción de fallos de la cache Técnica: Pre-búsqueda controlada por el compilador (I) • Pre-búsqueda controlada por el compilador: Otra alternativa consiste en que es el propio compilador el que inserta instrucciones de pre-búsqueda, solicitando datos cuando aún no son necesarios – Pre-búsqueda en registro: El valor se almacena en un registro – Pre-búsqueda en cache: El valor se almacena en la cache

Arquitectura de Sistemas Paralelos (47)

Reducción de fallos de la cache Técnica: Pre-búsqueda controlada por el compilador (II) for(i=0;i