Download Gestión de memoria - Departamento de Arquitectura y Tecnología

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<3;i++)
for(j=0;j<100;j++)
a[i][j]=b[j][0]*b[j+1][0];
Fallos de cache = (3*100)/2 + 101 = 251
for(j=0;j<100;j++){
prefetch(b[j+7][0]);
prefetch(a[0][j+7]);
a[0][j]=b[j][0]*b[j+1][0];}
for(i=1;i<3;i++)
for(j=0;j<100;j++){
prefetch(a[i][j+7]);
a[i][j]=b[j][0]*b[j+1][0];
a[i][7] ... a[i][99] y b[7][0] ... b[99][0] pre-buscados
Fallos de cache = (3*7)/2 + 8 = 19
(se evitan 232 fallos con 400 instrucciones prefetch)
Arquitectura de Sistemas Paralelos (48)
Reducción de fallos de la cache
Técnica: Optimización del compilador
• Optimización del compilador: El compilador reordena el
código de manera que por la forma en como se hacen los
accesos se reducen los fallos de cache
– Detectando conflictos y reordenando las instrucciones se han
reducido los fallos un 50% en una cache de correspondencia
directa de 2Kb con bloques de 4 bytes y 75% en una de 8Kb
(McFarling 1989)
– Técnicas:
• Mejora de la localidad espacial: Mezcla de arrays e Intercambio
de bucles
• Mejora de la localidad temporal: Fusión de bucles y Bloqueado
Arquitectura de Sistemas Paralelos (49)
Reducción de la penalización por fallo
Técnica: Dar prioridad a los fallos de lectura sobre la escritura (I)
• Dar prioridad a los fallos de lectura sobre la escritura: En la
caches WT el buffer de post-escritura mejora el rendimiento pero
también complica los accesos a memoria cuando el bloque buscado
se encuentra en el buffer (aún no ha sido escrito en memoria) y se
produce un fallo en lectura de dicho bloque. ¿Qué hacer?
Ejemplo:
Una cache de correspondencia directa WT con buffer de post-escritura
(conflicto entre las posiciones 512 y 1024) ¿El contenido de R2 y R3 es
igual?
M[512] ← R3 -- escritura en buffer
R1 ← M[1024] -- fallo en lectura
R2 ←M[512] -- fallo en lectura (aún no se ha copiado el bloque)
-- El fallo en lectura debe esperar a que finalice la escritura
Arquitectura de Sistemas Paralelos (50)
Reducción de la penalización por fallo
Técnica: Dar prioridad a los fallos de lectura sobre la escritura (II)
– Solución: Para evitar que los fallos en lectura esperen
siempre a que el buffer se vacíe (en un buffer de cuatro
palabras supone un incremento de la penalización de un
50%) se puede comprobar el contenido del buffer y si no
hay conflicto permitir que el fallo en lectura continúe
– Esta técnica también permite reducir la penalización por
fallo en caso de caches CB (escritura del bloque sucio)
Arquitectura de Sistemas Paralelos (51)
Reducción de la penalización por fallo
Técnica: Uso de Sub-bloques
• Uso de sub-bloques:
– Cuando las etiquetas son demasiado grandes (ocupan mucho y su
comparación es costosa) pueden reducirse haciendo bloques más grandes
pero eso aumenta la penalización por fallo (tiempo de transferencia)
– Para evitarlo pueden dividirse los bloques en sub-bloques y utilizar en vez
de un bit de válido tantos como sub-bloques tengamos. Las transferencias
son a nivel de sub-bloques
Caché de correspondencia directa
Arquitectura de Sistemas Paralelos (52)
-
Cache por bloques:
16 etiquetas
16 bits de válido
-
Caches con sub-bloques:
4 etiquetas
16 bits de válido
Reducción de la penalización por fallo
Técnica: Re-arranque rápido y primera palabra crítica
• Re-arranque rápido y primera palabra crítica: Estas
técnicas se basan en el hecho de que en un momento
dado la CPU sólo necesita una palabra del bloque para
continuar la ejecución
– Re-arranque rápido (Early restart): Consiste en no esperar
a leer todo el bloque sino que en cuanto se haya transferido la
palabra solicitada enviarla a la CPU y luego continuar
trayendo el bloque
– Primera palabra crítica (Critical word first): Consiste en
solicitar a la memoria sólo la palabra que falló y enviarla tan
pronto como llegue a la CPU. Mientras ésta continua con la
ejecución, se rellena el resto de palabras del bloque
Arquitectura de Sistemas Paralelos (53)
Reducción de la penalización por fallo
Técnica: Caches no bloqueantes
• Caches no bloqueantes: Esta técnica se utiliza en
máquinas con pipeline ( se verán en el tema de
Introducción al Paralelismo). Por ejemplo, es posible
continuar la búsqueda de una instrucción en la cache
de instrucciones mientras se espera que se traiga un
bloque fallido en la cache de datos
Arquitectura de Sistemas Paralelos (54)
Reducción de la penalización por fallo
Técnica: Caches de segundo nivel (I)
• Caches de segundo nivel: Añadiendo un nivel más en la jerarquía
de memoria (L1 y L2)
Rendimiento (tiempo medio de acceso a memoria, tmam)
tmam=t_aciertoL1+f_falloL1*(t_aciertoL2+f_falloL2*p_falloL2)
– Frecuencia de fallos local: número de fallos en la cache dividido por el
número total de accesos a esa cache (en L2 es f_ falloL2)
– Frecuencia de fallos global: número de fallos en la cache dividido por
el número total de accesos a memoria generados por la CPU (en L2 es
f_falloL1*f_falloL2)
Ejemplo:
1000 referencias a memoria, 40 fallos en la cache L1 y 20 en la cache L2
Frecuencia de fallos en L1 (tanto local como global) = 40/1000 =4%
Frecuencia de fallos local para L2 = 20/40 =50%
Frecuencia de fallos global para L2= 20/1000=2% (4%*50%)
Arquitectura de Sistemas Paralelos (55)
Reducción de la penalización por fallo
Técnica: Caches de segundo nivel (II)
Frecuencia de fallo
vs.
Tamaño de cache
(escalas lineal y logarítmica)
Cache de un único nivel:
single cache miss rate
Cache de dos niveles:
(primer nivel: 32Kb)
local miss rate
global miss rate
Arquitectura de Sistemas Paralelos (56)
Reducción de la penalización por fallo
Técnica: Caches de segundo nivel (III)
Ejemplo
• ¿Cuál es el impacto de la asociatividad de la cache de segundo nivel sobre
la penalización?
• Datos:
–
–
–
–
–
Un grado de asociatividad 2 incrementa el tiempo de acierto en un 10%
Tiempo de acierto de L2 para cache de mapeado directo = 10 ciclos
Frecuencia de fallos local de L2 para cache de mapeado directo = 25%
Frecuencia de fallos local de L2 para cache asociativa de 2 vías = 20%
Penalización por fallo de L2 = 50 ciclos
Solución
P_fallo1-vía-L1=10+25%*50=22,5 ciclos
P_fallo2-vías-L1=10.1+20%*50=20.1 ciclos
El segundo nivel de cache
debe estar sincronizado con
el primero (t_acierto=10 o
11 ciclos)
Arquitectura de Sistemas Paralelos (57)
Reducción del tiempo acierto
Técnica: caches pequeñas y simples
• Caches pequeñas y simples: Buena parte del tiempo de
acierto se dedica a leer y comparar las etiquetas
– Las caches pequeñas (on-chip) permiten tiempos de acierto
reducidos pero poca capacidad. Una posible solución: etiquetas onchip y datos off-chip
– En las caches de correspondencia directa (simples) la comprobación
de la etiqueta y el acceso al dato se hace a la vez
– En el primer nivel de cache se utilizan caches pequeñas y simples
Arquitectura de Sistemas Paralelos (58)
Reducción del tiempo acierto
Técnica: Evitar la traducción de direcciones
• Evitar la traducción de direcciones durante la
indexación de la cache: Consiste en almacenar
direcciones virtuales ( se verá en el apartado de
Memoria Virtual) en la cache, evitando así la
traducción de direcciones virtuales a físicas en caso
de acierto (Caches virtuales vs. Caches físicas)
Arquitectura de Sistemas Paralelos (59)
Reducción del tiempo acierto
Técnica: Escrituras en pipeline para aciertos en escritura rápidos
• Escrituras en pipeline para aciertos en escritura
rápidos: Consiste en crear un pipeline ( se verán en el
tema de Introducción al Paralelismo) para las operaciones
de escritura, de manera que la escritura actual se hace
solapada en el tiempo con la comparación de etiquetas de
la escritura siguiente. Las operaciones de lectura no son
parte de este pipeline pues la comparación de etiquetas y la
lectura del bloque se hacen siempre en paralelo
Arquitectura de Sistemas Paralelos (60)
Memoria virtual
Objetivos
• Los objetivos de la memoria virtual son:
– Permitir a los programas usar más memoria de la disponible
físicamente. Se gestiona automáticamente los dos niveles de la
jerarquía de memoria representada por la memoria principal y la
secundaria, liberando al programador de esta tarea (origen histórico)
... se ha inventado un sistema para hacer que la combinación de tambores de
núcleos magnéticos parezca al programador como un simple nivel de
almacenamiento, realizando automáticamente las transferencias precisas
Kilburn y cols. [1962]
– Compartir una misma memoria física entre diferentes procesos con
su propio espacio de direcciones (sistemas multitarea). Sería muy
costoso dedicar una memoria de tamaño igual al espacio total de
direcciones a cada proceso. Se requiere un esquema de protección
Arquitectura de Sistemas Paralelos (61)
Memoria virtual
Definiciones (I)
• Página/Marco (page) o segmento (segment): en los términos
definidos para la jerarquía de memoria es un bloque
• Fallo de página (page fault) o de dirección (address fault): en los
términos definidos para la jerarquía de memoria es un fallo
• Direcciones virtuales: son las direcciones que genera la CPU
• Direcciones físicas: son las direcciones que atacan a la memoria
principal
• Correspondencia de memoria (memory mapping) o traducción de
direcciones (address translation): el proceso (software/hardware) para
traducir las direcciones virtuales a direcciones físicas
• Niveles de la jerarquía controlados por la memoria virtual:
Memoria RAM y disco duro
Arquitectura de Sistemas Paralelos (62)
Memoria virtual
Definiciones (II)
Traducción de direcciones
Direcciones virtuales
Direcciones físicas
0
A
4K
B
8K
C
8K
12K
D
12K
0
C
A
Memoria virtual
4K
Página
16K
20K
B
24K
28K
Memoria principal
D
Fallo de página
Arquitectura de Sistemas Paralelos (63)
Disco
Memoria virtual
Diferencias entre cache y memoria virtual (I)
• El reemplazo en los fallos de cache está controlado
principalmente por hardware, mientras que el reemplazo en
memoria virtual está controlador principalmente por el
sistema operativo
• El tamaño de la dirección del procesador determina el
tamaño de la memoria virtual, pero el tamaño de la cache
es normalmente independiente de la dirección del
procesador
• Además de actuar como memoria de más bajo nivel para la
memoria principal en la jerarquía, la memoria secundaria
se utiliza para el sistema de ficheros que normalmente no
es parte del espacio de direcciones
Arquitectura de Sistemas Paralelos (64)
Memoria virtual
Diferencias entre cache y memoria virtual (II)
Parámetro
Primer nivel de cache
Memoria virtual
Tamaño de bloque
16-128 bytes
4096-65536
Tiempo de acierto
1-2 ciclos de reloj
40-100 ciclos de reloj
Penalización por fallo:
Tiempo de acceso
Tiempo de transferencia
8-100 ciclos de reloj
2-60 ciclos de reloj
2-40 ciclos de reloj
700000-6000000 ciclos de reloj
500000-4000000 ciclos de reloj
200000-2000000 ciclos de reloj
Frecuencia de fallo
0.5-10%
0.00001-0.001%
Tamaño de la memoria
0,0016-1Mb
16-8192Mb
Arquitectura de Sistemas Paralelos (65)
Memoria virtual
Paginación vs. Segmentación (I)
• En los sistemas de memoria virtual los bloques pueden ser:
– de tamaño fijo: Página (ligado al hardware)
– de tamaño variable: Segmento (ligado al proceso)
• Cuando el bloque es de tamaño fijo se habla de paginación y
cuando es variable de segmentación
• Lo más habitual es utilizar la paginación pues es más sencilla de
implementar (direccionamiento, política de reemplazo, etc.)
• Hay soluciones híbridas: segmentación paginada en la que un
segmento es un número entero de páginas (la política de reemplazo
es más sencilla, pues no se necesita que la memoria sea contigua ni
que los segmentos completos estén en memoria principal)
Arquitectura de Sistemas Paralelos (66)
Memoria virtual
Paginación vs. Segmentación (II)
Arquitectura de Sistemas Paralelos (67)
Paginación vs. Segmentación (III)
Fragmentación
• Fragmentación externa (Segmentación)
Fragmentación externa
Proceso1
Proceso1
Proceso1
Proceso2
Proceso2
Proceso1
Proceso3
Proceso3
Proceso1
Proceso4
Solución: Compresión
(muy costosa)
Proceso3
Tiempo
• Fragmentación externa (Paginación)
...
Página
Marco1
Marco2
Fragmentación interna
Influencia del tamaño de página
a) Pagina grande: Mayor eficiencia en la
transferencia
b) Página pequeña: Menor fragmentación
y menor tiempo de arranque
...
Arquitectura de Sistemas Paralelos (68)
Memoria virtual
Ubicación de bloque en paginación
• ¿Dónde puede ubicarse un bloque en memoria principal?
– Los sistemas operativos permiten que los bloques se
coloquen en cualquier parte de la memoria principal
(totalmente asociativa)
– Al ser muy alta la penalización por fallo en la memoria
virtual, los diseñadores de S.O. optan por reducir la
frecuencia de fallos en vez de utilizar un algoritmo de
ubicación más sencillo
Arquitectura de Sistemas Paralelos (69)
Memoria virtual
Identificación de bloque en paginación
• ¿Cómo se encuentra un bloque si está en memoria principal?
– La dirección virtual se descompone en dos campos: número de
página virtual y desplazamiento de página
– La dirección física se obtiene concatenando simplemente la
dirección física de la página con el desplazamiento de página
– Se utiliza una estructura de datos (tabla de páginas) que contiene
la dirección física de la página y es indexada por la dirección
virtual
Arquitectura de Sistemas Paralelos (70)
Identificación de bloque en paginación
Correspondencia entre dirección virtual y física
Arquitectura de Sistemas Paralelos (71)
Memoria virtual
Sustitución de bloque en paginación
• ¿Qué bloque debería sustituirse en un fallo de memoria
virtual?
– Con objeto de minimizar los fallos de página, se intenta sustituir
la página que menos recientemente ha sido usada (LRU)
– Implementación de una política LRU: Muchas máquinas
proporcionan un bit de uso o bit de referencia para cada
página, que se pone a uno siempre que dicha página es
accedida. El S.O. borra periódicamente los bits de uso y más
tarde los registra para poder determinar qué páginas fueron
accedidas durante un periodo de tiempo determinado. De esta
manera, el S.O. puede seleccionar una página que se encuentre
entre la menos recientemente referenciadas
Arquitectura de Sistemas Paralelos (72)
Memoria virtual
Política de escritura en paginación
• ¿Qué ocurre en una escritura?
– La estrategia de escritura es siempre la post-escritura
(write back) debido a la gran diferencia que existe entre
los tiempos de acceso en uno y otro nivel
– Los sistemas de memoria virtual incluyen un bit de
modificado o sucio (dirty) para que sólo los bloques
que han sido alterados desde que se cargaron sean
escritos en la memoria secundaria
Arquitectura de Sistemas Paralelos (73)
Memoria virtual
Tabla de páginas (I)
•
•
•
•
•
•
Permite traducir direcciones virtuales a direcciones físicas
Está indexada por el número de página virtual y contiene la dirección física de
la página. Se requiere un bit de válido para indicar que la entrada contiene un
página física válida (se encuentra en memoria principal y no se produce fallo de
página)
El tamaño de la tabla de páginas es inversamente proporcional al tamaño de
página
Las tablas de páginas son habitualmente tan grandes que se almacenan en
memoria principal y, con frecuencia, paginadas ellas mismas: se requiere un
acceso a memoria para obtener la dirección física y otro para obtener el dato
Bits de control: válido, uso, sucio, permiso lectura y permiso escritura
Optimización: Jerarquía de tablas de página, técnicas hashing (tablas de páginas
invertidas) y Buffer de Traducción Anticipada (TLB)
Arquitectura de Sistemas Paralelos (74)
Memoria virtual
Tabla de páginas (II)
Ejemplo:
Dirección virtual de 28 bits, páginas de 4Kb y 4 bytes/entrada
(256Mb/4Kb)*4 = 256Kb
Arquitectura de Sistemas Paralelos (75)
Memoria virtual
Buffer de traducción anticipada o TLB (I)
•
•
•
•
De nuevo el principio de localidad: Si las referencias tienen localidad entonces
la traducción de direcciones también debe tener localidad
El buffer de traducción anticipada (translation-lookaside buffer) o TLB es una
cache, habitualmente totalmente asociativa o asociativa por conjuntos, cuyas
entradas contienen: en la parte de la etiqueta, el número de página virtual (o
parte) y en la parte del dato, el número de página física y los bits de control
Un tamaño de página mayor hace que más memoria pueda estar mapeada con
una entrada, por lo que se reduce el numero de fallos en la TLB
Hay TLBs unificadas y separadas (datos e instrucciones)
Tamaño de bloque
4-8 bytes (una entrada de tabla de página)
Tiempo de acierto
1 ciclo de reloj
Penalización de fallos 10-30 ciclos de reloj
Frecuencia de fallos
0.1%-0.2%
Tamaño TLB
32-8192
Arquitectura de Sistemas Paralelos (76)
Valores típicos
de parámetros
Memoria virtual
Buffer de traducción anticipada o TLB (II)
Arquitectura de Sistemas Paralelos (77)
Buffer de traducción anticipada o TLB (III)
Ejemplo: TLB del VAX-11/780
Tamaño de página de 512bytes
Entrada de TP de 4bytes
TLB de 512bytes asociativa por
conjuntos de 2 vías
Pasos:
1: Envío del índice de la
dirección virtual
2: Comprobación de válido y
tipo de acceso a memoria
3: Comparación de etiquetas
4: Envío de la dirección física a
través del multiplexor
5: Combinación del número
y desplazamiento de página
Arquitectura de Sistemas Paralelos (78)
Buffer de traducción anticipada o TLB (IV)
TLB y cache
• Cuando se combinan caches y memoria virtual, la dirección virtual debe ser
traducida a una dirección física mediante la TLB antes de que pueda acceder a
la cache (elevado tiempo de acierto)
• Una forma de reducir el tiempo de acierto es:
– acceder a la cache únicamente con el desplazamiento de página (no necesita
ser traducido) y mientras se están leyendo las etiquetas de dirección de la
cache, el número de página virtual es enviado a la TLB para ser traducido
– como la TLB es habitualmente más pequeña y rápida que la memoria de
etiquetas de la cache, la lectura de la TLB puede hacerse de forma simultánea
a la lectura de la memoria de etiquetas sin ralentizar los tiempos de acierto de
la cache
– después la comparación de direcciones se realiza entre la dirección física de la
TLB y la etiqueta de la cache
• Inconveniente: una cache de correspondencia directa no puede ser mayor que
una página
• Otra alternativa es utilizar caches virtuales (transparencia 59)
Arquitectura de Sistemas Paralelos (79)