Download Caches unificadas vs. Caches separadas

Profesores y Horarios de Tutorías
Temas 3 y 4
„
Teoría:
‰
Daniel Cascado Caballero ([email protected])
Despacho: F070
‰
Lourdes Miró Amarante ([email protected])
Despacho: F061
Horario de tutorías:
Martes:
11:00h a 13:00h; 17:30 a 19:30
Miércoles: 10:30h a 12:30h
1
Bibliografía Básica
Temas 3 y 4
‰
‰
Estructura y Diseño de Computadores, J. L.
Hennessy y D. A. Patterson. Ed. Reverte,
2000.
Organización y arquitectura de computadores,
W. Stalling. Prentice-Hall, 2000.
2
1
Estructura Básica de un Computador
Máquina Von Neumann
CPU
Interconexiones
Memoria
E/S
Periféricos
3
Ampliación Máquina Von Neumann
Programa principal
I1
I2
TEMA 4
TEMA 3
CPU
palabras
.
.
Memoria principal
Interrupción
Ii
Ii+1
(Mc)
páginas
bloques
.
.
In
Rutina de servicio
i1
i2
.
.
im
Sistema de interrupciones
(Mp)
Memoria cache
Memoria principal
Memoria secundaria
(Mp)
(Ms)
Sistema de memoria cache
Sistema de memoria virtual
4
2
Tema 3: GESTIÓN DE MEMORIA
ÍNDICE
Jerarquía de memoria
Memorias caché
1.
2.
Introducción
Organización física
Organización lógica
Optimización
1.
2.
3.
4.
3.
Memoria virtual
5
Jerarquía de memoria
Introducción
„
Necesidad de grandes cantidades de memoria rápida con
tiempos de acceso y transferencia pequeños.
„
Diferentes tipos de memorias según los criterios de tamaño,
velocidad y coste (tecnología).
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,
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)
1. Jerarquía de memoria
6
3
Definición
Una jerarquía de 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.
„
Coste/bit (+)
Capacidad (-)
Velocidad (+)
Frecuencia
de accesos (+)
Registros
procesador
Caché
Memoria principal
Caché de disco
Disco magnético
CD-DVD
1. Jerarquía de memoria
7
Propiedades
„
Inclusión: Cualquier información almacenada en un nivel de memoria,
debe encontrarse también en los niveles inferiores.
nivel i+1
nivel i
„
Coherencia: Las copias de la misma información existentes en los
distintos niveles deben ser consistentes.
„
Localidad de referencia: Los programas favorecen una parte de su
espacio de direcciones en cualquier instante de tiempo.
‰ 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).
1. Jerarquía de memoria
8
4
Funcionamiento
„
El procesador sólo accede al nivel más alto
(más rápido y de menor tamaño).
„
Si el procesador pide un dato y éste se
encuentra en el nivel superior (acierto).
„
Si el dato no se encuentra en este nivel
(fallo) se trae del nivel inferior al superior.
Nivel superior
Bloques
„
Las transferencias de datos entre niveles se
hace con bloques de varios bytes.
Nivel inferior
1. Jerarquía de memoria
9
Conceptos básicos
„
„
„
„
„
„
Nivel (level).
Bloque (block): 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, Hr /miss rate, Mr ).
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.
1. Jerarquía de memoria
10
5
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
„
„
„
„
‰
Por el principio de localidad, Mr suele ser <= 10%
El Mr se obtiene mediante TRAZAS de accesos a memoria.
Habrá un Mr por cada nivel de la jerarquía.
Influencia de parámetros
El tamaño de bloque influye sobre:
„ Penalización por fallo
Tiempo de acceso medio a memoria
„ Frecuencia de fallos
1. Jerarquía de memoria
11
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
1. Jerarquía de memoria
Tamaño del bloque
12
6
Memoria caché
Introducción
CPU
palabras
„
Representa
el
nivel
de
jerarquía de memoria entre la
CPU y la memoria principal.
Memoria
Memoria
caché
caché
Controlador
Controlador
de
decaché
caché
bloques
„
Se le pueden aplicar todos los
conceptos vistos para la
jerarquía
de
memoria
(propiedades, funcionamiento,
conceptos
básicos,
rendimiento).
Memoria principal
(Mp)
2. Memoria cache
13
Estructura Memoria Caché/Memoria Principal
„
Mp (memoria principal):
‰
‰
‰
formada por 2n palabras direccionables.
“dividida” en nB bloques de tamaño fijo
2K (palabras por bloque).
Campos de una dirección física:
Dirección
de
memoria
Mp
1
DF:
B
P
Mc
0
Bloque 0
(n-k bits) (k bits)
Bloque
Palabra
.
n
Bloque 1
.
dirección
„
Mc (memoria cache):
‰
„
Línea 0
2
formada por nL líneas de
(nL << nB).
2K
.
palabras
.
Línea de caché (contenido):
‰
‰
Información de bloque
Datos adicionales
„ Bit de línea válida.
„ Info. identificación de bloque
„ Otros...
2. Memoria cache
.
Línea nL -1
.
Bloque 2n/2k -1= nB -1
2n
-1
14
7
Funcionamiento
2. Memoria cache
15
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 el tipo de información que contienen:
unificadas o separadas.
Según su estructura interna y funcionamiento:
ubicación, identificación, sustitución y escritura
2. Memoria cache
16
8
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
procesador (cache-on-chip).
„
Según la configuración
‰ Configuración en serie (Look-Trough Architecutre).
‰ Configuración en paralelo (Look-Aside Architecture).
2. Memoria cache.
cache Organización Física
17
Configuración en serie
CPU
Bus
Cache
DMA
I/O
Memoria
Bus
Tc
Tmp
t
‰
‰
‰
Ventajas: Si el dato se encuentra en la caché no hay
acceso a memoria y no se ocupa el bus.
Inconvenientes: La caché debe tener 2 interfaces de
buses diferentes y el tiempo de acceso, en caso de fallo,
es mayor (igual al tiempo de acceso a caché más el
tiempo de acceso a memoria principal).
Tacc = Hr*Tcache +(1-Hr)*(Tcache+Tmemp)
2. Memoria cache. Organización Física según la CONFIGURACIÓN
18
9
Configuración en paralelo
Cache
DMA
I/O
Memoria
Bus
CPU
Tc
Tmp
t
‰
‰
‰
Ventajas: Sólo hay una interfaz con el bus y el tiempo de fallo 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.
Tacc=Tcache*Hr + (1-Hr)*Tmemp
2. Memoria cache. Organización Física según la CONFIGURACIÓN
19
Organización lógica
‰
Según el tipo de información que contienen:
unificadas o separadas.
„
Separadas:
‰
‰
Tacc= %instrucciones * Tacc_inst + %datos*Tacc_datos
Según su estructura interna y funcionamiento
(Políticas):
„
„
„
„
Ubicación (función de correspondencia).
Localización.
Sustitución.
Escritura.
2. Memoria cache. Organización Lógica
20
10
Caches unificadas vs. Caches separadas
„
„
Caches unificadas o mixtas (unified or mixed): Contienen tanto datos como
instrucciones
Caches separadas (separated): Existe una caché para datos y otra para
instrucciones
‰
‰
‰
‰
Ventajas
No hay competencia entre acceso a datos y acceso a instrucciones.
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 caché dedicado a cada tipo
No se equilibra la carga de trabajo de forma automática
2. Memoria cache. Organización Lógica. Cache unificada vs cache separada.
21
Ejemplo caches separadas: Pentium II
Depósito de instrucciones. Buffer de reordenación.
Unidad de lectura y
decodificación de
instrucciones.
Caché de
instrucciones L1.
(8-16K)
Unidad de
retirada
Unidad de
ejecución y
envío
Caché de datos L1. (8-16K)
Cada caché tiene
asociada al menos
una unidad de
control que controla
las peticiones de
datos.
Interfaz con el bus
Bus del sistema
Caché L2. (256-1M)
2. Memoria cache. Organización Lógica. Cache unificada vs cache separada.
22
11
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 caché unificada de 32KB: 4.3%
En caches separadas de 16KB: 53%*3.6%+47%*5.3%=4.4%
2. Memoria cache. Organización Lógica. Cache unificada vs cache separada.
23
Comparativa (II)
Ejemplo: (75% de accesos a instrucción)
„
a)
b)
Caches separadas de 16KB. Penalización: 50 ciclos, Tiempo
de acierto para instrucción: 1 ciclo, para datos: 2 ciclos (un
solo puerto)
Cache unificada de 32KB. Penalización: 50 ciclos, Tiempo
de acierto: 1 ciclo
Solución:
a)
Tacceso medio =75%*(1+3.6%*50)+25%*(2+5.3*50)= 3.26 ciclos
b)
Tacceso medio=1+4.3%*50 = 3.0 ciclos=3.15 ciclos
2. Memoria cache. Organización Lógica. Cache unificada vs cache separada.
24
12
Políticas de Ubicación y Localización.
„
Ubicación: Dado un bloque de Mp, con una
dirección Db, que se quiere subir a caché,
¿En qué línea hay que ubicarlo?
‰
„
Función de correspondencia:
Línea = f(Db)
Localización: ¿En qué líneas de caché tengo
que buscar para saber si un bloque de Mp
con dirección Db está en ella?
‰
Se utiliza la función de correspondencia.
2. Memoria cache. Organización Lógica. Políticas de UBICACIÓN y LOCALIZACIÓN
25
Ubicación de un bloque.
¿Qué hay que hacer cuando se quiere subir un bloque a
caché?
„ Se averiguan las líneas en las que es posible ubicar
mediante la función de correspondencia.
„ Se selecciona una mediante la política de reemplazo
(se verá más adelante).
„ Si la línea está vacía, el bloque se guarda en ésta.
„ Si no,se produce un conflicto, y habrá que bajar el
antiguo bloque a memoria principal y subir el nuevo a
la línea seleccionada.
2. Memoria cache. Organización Lógica. UBICACIÓN
26
13
Identificación de un bloque
Una vez que se sabe en qué líneas buscar un bloque con dirección
Db ¿Cómo se sabe si está realmente en caché?
„ Se mira el bit de válido de la línea para saber si es válida.
„ Se descompone la dirección Db al menos, en estos campos:
‰ Etiqueta (tag):
‰ Desplazamiento de bloque (block offset): selecciona el dato
deseado dentro del bloque.
„ Se extrae el campo etiqueta y se compara con el campo etiqueta
de la línea.
Si la línea es válida y las etiquetas son iguales, el bloque está en
caché.
‰
2. Memoria cache. Organización Lógica. IDENTIFICACIÓN
27
Políticas de Ubicación y Localización.
Mp
Mc
.
.
.
B0
B1
B2
B3
B4
B5
B6
B7
Mc
B0
B1
B2
B3
B4
B5
B6
B7
DIRECTA
ASOCIATIVA
Mc
C0
C1
C2
C3
ASOCIATIVA POR
CONJUNTOS
2. Memoria cache. Organización Lógica. Políticas de UBICACIÓN y LOCALIZACIÓN
28
14
Ejemplo de Ubicación de bloque
Memoria: 32 bloques
Caches: 8 bloques
Tres tipos:
- Asociativas
- Directa
- Asociativa por
conjuntos de 2 vías
2. Memoria cache. Organización Lógica. Política UBICACIÓN
29
Ejemplo de localización e identificación de un
bloque
Memoria: 32 bloques
Caches: 8 bloques
Tres tipos:
- Completamente
asociativas
- De correspondencia
directa
- Asociativa por
conjuntos de 2 vías
2. Memoria cache. Organización Lógica. LOCALIZACIÓN
30
15
Cache de Mapeado Directo
Líneas MC
Memoria Principal (Mp):
16MB direccionables por bytes
(dirección de 24bits).
‰
Memoria Cache (Mc):
64KB.
‰
Tamaño de bloque 16 Bytes:
Nº Bloques en MP: nB = 1M (20 bits)
Nº Líneas en MC: nM = 4K (12 bits)
‰
‰
M = B mod nM
Interpretación de DF en correspondencia
DIRECTA:
4
20
B
P
ETQ
M
P
8
12
4
2. Memoria cache. Organización Lógica. Política UBICACIÓN
31
Cache de Mapeado Directo
•Ventajas:
•Baja complejidad hardware
Dirección solicitada (de CPU)
6 5 4 3 2 1 0
1 1 1 1 0 1 1
ETI INDICE
W B
•Rapidez en la identificación
•Inconvenientes:
V
Datos
•Alta tasa de fallos si varios bloques
compiten por la misma línea.
DECODER
COMPARADOR
Etiqueta
Memoria principal
1 1
Encontrado (si)
Bloque 0
ACADA...B3
Bloque 1
(y sigue)
Y
Dato solicitado
(AF)
Dato
A1
A2
A3
A4
A5
A6
A7
A8
A9
AA
AB
......
Selector
Acierto (si)
Dirección
0000000
0000001
0000010
0000011
0000100
0000101
0000110
0000111
0001000
0001001
0001010
Bloque 15 1111000
1111001
1111010
1111011
1111100
1111101
1111110
1111111
2. Memoria cache. Organización Lógica. IDENTIFICACIÓN
AC
AD
AE
AF
B0
B1
B2
B3
32
16
Cache Totalmente Asociativa
Líneas Mc
Memoria Principal (Mp):
„
‰
16MB direccionables por bytes
(dirección de 24bits).
Memoria Cache (Mc):
„
‰
Cada bloque B
64KB.
puede ubicarse en
Tamaño de bloque 16 Bytes:
„
‰
‰
cualquier línea M.
Nº Bloques en MP: nB = 1M (20 bits)
Nº Líneas en MC: nM = 4K (12 bits)
Interpretación de DF en correspondencia
TOTALMENTE ASOCIATIVA:
20
4
B
P
ETIQUETA
P
20
4
2. Memoria cache. Organización Lógica. Política UBICACIÓN
33
Cache Totalmente Asociativa
•Ventajas:
•Baja tasa de fallos
Dirección solicitada (de CPU)
6 5 4 3 2 1 0
1 1 1 1 0 1 1
ETI
W B
•Inconvenientes:
•Alta complejidad hardware.
COMPARADOR
Etiqueta
V
Datos
•Lentitud en la identificación.
Memoria principal
1111 1 ACADA...B3
Bloque 0
Bloque 1
(y sigue)
Encontrado (si)
Y
Dirección
0000000
0000001
0000010
0000011
0000100
0000101
0000110
0000111
0001000
0001001
0001010
Dato
A1
A2
A3
A4
A5
A6
A7
A8
A9
AA
AB
......
Selector
Acierto (si)
Dato solicitado
(AF)
2. Memoria cache. Organización Lógica. IDENTIFICACIÓN
Bloque 15 1111000
1111001
1111010
1111011
1111100
1111101
1111110
1111111
AC
AD
AE
AF
B0
B1
B2
B3
34
17
Cache Asociativa por Conjuntos
Línea
Memoria Principal (Mp):
„
‰
16MB direccionables por bytes (24bits).
Memoria Cache (Mc):
„
‰
64KB.
Tamaño de bloque 16 Bytes:
„
‰
‰
Nº Bloques en MP: nB = 1M (20 bits)
Nº Líneas en MC: nM = 4K (12 bits)
4 vías:
„
‰
‰
C = B mod nC
Nº de Líneas por Conjunto: 4
Nº de Conjuntos en Mc: nC = 1K (10 bits)
Interpretación de DF en correspondencia
ASOCIATIVA POR CONJUNTOS:
20
4
B
P
ETQ
C
P
10
10
4
2. Memoria cache. Organización Lógica. Política UBICACIÓN
35
Cache Asociativa por Conjuntos
DECODER
Dirección solicitada (de CPU)
6 5 4 3 2 1 0
1 1 1 1 0 1 1
ETI CJTO W
B
Memoria principal
Eti V
VIA 0
Datos
Eti V
Bloque 0
VIA 1
Datos
Bloque 1
(y sigue)
11 1 ACADA...B3
=
Dirección
0000000
0000001
0000010
0000011
0000100
0000101
0000110
0000111
0001000
0001001
0001010
Dato
A1
A2
A3
A4
A5
A6
A7
A8
A9
AA
AB
......
=
Y
Y
Acierto
vía 1(no)
Acierto
vía 0 (si)
Selector
Bloque 15 1111000
1111001
1111010
1111011
1111100
1111101
1111110
1111111
AC
AD
AE
AF
B0
B1
B2
B3
Dato solicitado
(AF)
2. Memoria cache. Organización Lógica. IDENTIFICACIÓN
36
18
Ejemplo (I)
•
•
•
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 totalmente 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
Byte:1bit
Bloque: 10bits
Byte:1bit
Desplazamiento: 3bits
Palabra: 2bits
2. Memoria cache. Organización Lógica. IDENTIFICACIÓN
Byte:1bit
37
Ejemplo (II)
- 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
2. Memoria cache. Organización Lógica. IDENTIFICACIÓN
38
19
Políticas de escritura
Frente acierto en la cache
Escritura directa (Write through):
„
‰
Escritura en Memoria cache (Mc) y Memoria principal (Mp).
Postescritura (Copy Back):
„
‰
‰
‰
‰
La información se escribe sólo en el bloque de la Mc.
Este bloque se denomina sucio o modificado.
El bloque modificado de la Mc se escribirá en la Mp sólo cuando éste sea
reemplazado.
Para reducir la frecuencia de postescrituras en el reemplazo, se usa el bit
de modificación o sucio (dirty bit), de manera que si el bloque está limpio
no se escribe Mp.
2. Memoria cache. Organización Lógica. Política ESCRITURA
39
Políticas de escritura
Ventajas e Inconvenientes
„
Escritura directa (Write through):
‰
Ventajas:
„
„
„
‰
Inconvenientes:
„
„
„
Fácil de implementar.
Bajo coste hardware.
La Mp tiene la copia más reciente de los datos (coherencia de cache,
multiprocesadores y E/S).
Tráfico importante en Mp.
Velocidad de la escritura es la velocidad de escritura en Mp (Solución: Buffer de
escritura).
Postescritura (Copy Back):
‰
Ventajas:
„
„
„
‰
Las escrituras se realizan a la velocidad de la memoria caché.
Múltiples escrituras en un bloque requieren sólo una escritura en Mp.
Disminuye tráfico entre Mc y Mp.
Inconvenientes:
„
„
„
Inconsistencia Temporal entre Mc y Mp.
Necesidad de bit adicional, bit dirty.
Implementación más compleja.
2. Memoria cache. Organización Lógica. Política ESCRITURA
40
20
Políticas de escritura
Frente fallo en la cache
„
Ubicación en escritura (Write allocate):
‰ El bloque se carga en Mc y a continuación se escribe
sobre él (similar a acierto en escritura).
‰ Apropiado para Copy Back (CB-WA).
„
No ubicación en escritura (No write allocate):
‰ El bloque se modifica en Mp y no se carga en Mc.
‰ Apropiado para Write Through (WT-NWA).
2. Memoria cache. Organización Lógica. Política ESCRITURA
41
Políticas de reemplazo
Espacio de Ubicación
„
Espacio de Ubicación ES el conjunto de posibles bloques de
Mc que pueden ser reemplazadas por un nuevo bloque.
„
Depende de la función de correspondencia:
‰ Mapeado directo: Sólo hay una opción.
‰ Totalmente asociativa: Cualquier bloque que reside en la
cache.
‰ Asociativa por conjuntos: Cualquier bloque que reside en
el conjunto que tiene asignado el nuevo bloque.
2. Memoria cache. Organización Lógica. Política SUSTITUCIÓN
42
21
Políticas de reemplazo
„
„
„
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
2. Memoria cache. Organización Lógica. Política SUSTITUCIÓN
43
EJEMPLO
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)
2. Memoria cache. Organización Lógica. Política SUSTITUCIÓN
44
22
Optimización
Cómo mejorar el rendimiento de las caches
El objetivo es reducir el tiempo medio de acceso a memoria:
„
Tacceso_medio = Tacierto + ffallos*Penalización_fallo
Se puede actuar sobre 3 términos:
1.
Reducir el tiempo de acceso en caso de acierto (hit time)
2.
Reducir la frecuencia de fallos (miss rate).
3.
Reducir las penalizaciones por fallo (miss penalty).
„
2. Memoria cache. Optimización
45
Reducir la frecuencia de fallos
Tipos de fallos
„
Forzosos (Compulsory):
‰
„
Capacidad (Capacity):
‰
„
En el primer acceso a un bloque, éste no se encuentra en la caché.
La caché 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).
2. Memoria cache. Optimización. Reducción de fallos
46
23
Tipos de fallos
Frecuencia total de fallos
para cada tamaño de cache:
2. Memoria cache. Optimización. Reducción de fallos
1.
Fallo forzoso:
Independiente del
tamaño de cache.
2.
Fallo de capacidad:
Decrece al aumentar
tamaño de la cache.
3.
Fallo de conflicto:
Decrece al aumentar la
asociatividad.
47
Tipos de fallos
2. Memoria cache. Optimización. Reducción de fallos
48
24
Reducir la frecuencia de fallos
Técnicas
„
Aumento del tamaño del bloque.
„
Aumento de la asociatividad.
2. Memoria cache. Optimización. Reducción de fallos
49
Incremento del tamaño de bloque
„
Ventaja:
‰
„
Se reducen los fallos forzosos (principio de localidad espacial).
Inconvenientes:
‰
‰
Aumentan los fallos por conflicto al reducirse el número de bloques de la
caché.
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
2. Memoria cache. Optimización. Reducción de fallos
Tamaño del bloque
50
25
Incremento del tamaño de bloque
forzosos
Conflicto
Capacidad
2. Memoria cache. Optimización. Reducción de fallos
51
Ejemplo incremento del tamaño de bloque
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
2. Memoria cache. Optimización. Reducción de fallos
52
26
Incremento de la asociatividad
„
Ventaja:
‰
„
Se reducen los fallos por conflicto.
Inconveniente:
‰
Aumenta el tiempo de acceso medio al incrementarse el tiempo de acierto.
También aumenta el coste debido 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+(0.0088*50)=1.44 ciclos
Tiempo medio de acceso a memoria (ciclos)
2. Memoria cache. Optimización. Reducción de fallos
53
Memoria virtual
Objetivos
‰
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
3. Memoria virtual
54
27
Definiciones (I)
Traducción de direcciones
Direcciones virtuales
Direcciones físicas
0
A
4K
B
8K
C
8K
12K
D
12K
Espacio virtual del
proceso A.
0
A’
4K
0
C
A
4K
Página
16K
20K
B
24K
A’
28K
Memoria principal
8K
12K
Espacio virtual del
proceso B.
D
Disco o Memoria Secundaria
3. Memoria virtual
55
Definiciones (II)
„
„
„
„
„
„
„
Página (page):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):
cuando la página solicitada está en disco (y ha de subirse a
memoria).
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
Marco: sitio donde se ubica una página en disco o en MP.
3. Memoria virtual
56
28
Memoria virtual
Visión general.
‰
Cada proceso tiene un espacio de direcciones propio, (espacio
virtual) mayor incluso que la MP.
„
„
El espacio virtual se divide en páginas .
El procesador genera direcciones virtuales.
‰
‰
‰
‰
‰
Número de página virtual.
Desplazamiento.
Las páginas pueden estar en MP o en disco. Los lugares donde
se meten las páginas se llaman marcos.
En MS existe un fichero especial en el que se encuentran los
marcos de MS. Es gestionado por el S.O.
Las direcciones virtuales son traducidas en direcciones físicas
para su acceso a MP.
„
„
La tabla de páginas (una para cada proceso) relaciona las
direcciones virtuales con las físicas (marcos).
Existe una tabla de páginas por proceso activo en el sistema.
‰
#pag_física = TablaPaginas(#pagina virtual)
3. Memoria virtual
57
Tabla de Páginas
„
¿Cómo se sabe si una página 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
‰ La tabla de páginas reside en memoria principal.
3. Memoria virtual
58
29
Tabla de páginas
Correspondencia entre dirección virtual y física
Registro de la tabla de páginas
Número de página virtual (20)
1
Pag. V (20bits) V D R W LRU
0
1
1 0 1 1
--...
Desplazamiento (12)
120
Marco (18 bits)
46544
1048575
Marco (18)
46544
Desplazamiento (12)
120
3. Memoria virtual
59
Funcionamiento.
Dirección virtual
Página en
MP?
si
Tratamiento del fallo de
página (S. O.)
no
MP llena?
no
Dato en
caché?
si
no
si
Bajar página a MS
Subir página a MP y
actualizar TP.
Bajar subir bloque a
Caché
Dato (desde caché)
Dir. física (desde TP)
3. Memoria virtual
60
30
Ciclo de vida de un proceso en memoria
virtual.
„
„
„
„
Cuando un proceso se inicia, se hace sitio en MS para todas sus
páginas, y se le crea su propia tabla de páginas.
Cuando una página se quiere usar y no está en MP se produce un
fallo de página, (paginación bajo demanda) y hace que la página
pase a MP.
En esta situación se produce una excepción en la CPU, y se llama
al S.O. para que gestione el fallo de página.
Una página se va a MS cuando la MP está llena y tiene que entrar
una página nueva (reemplazo).
‰
„
El intercambio excesivo de páginas, se llama hiperpaginación.
Cuando un programa termina, se liberan sus marcos de MS y MP.
3. Memoria virtual
61
Buffer de traducción anticipada o TLB (I).
Motivación y definición.
„
La velocidad de un sistema con memoria virtual se ve mermada por su misma
naturaleza. Un acceso a dato implica:
‰
‰
‰
Acceso a la tabla de páginas (en MP o en caché) para traducción.
Acceso al dato (en caché, en MP o en disco)
Por lo tanto, el sistema es al menos, el doble de lento de lo que era cuando no tenía
memoria virtual.
„
Se puede mejorar el rendimiento, aplicando el concepto de localidad referencial a
los accesos a la tabla de páginas.
„
Definiendo una TLB.
‰
Se puede tener una caché de la tabla de páginas = TLB.
‰
Es un mecanismo de aceleración de las consultas a la TP con objeto de traducir lo antes
posible.
‰
La memoria perteneciente a la TP no es cacheable por la caché ordinaria.
Sólo existe una para todo el sistema, y es interna al procesador.
Las referencias pueden pertenecer a uno o a varios procesos (TP):
„
‰
‰
„
„
‰
Una vez realizada la traducción a dir. Física, deja de actuar.
Uno: la TLB se borra al cambiar de proceso.Produce más fallos por iniciación.
Varios: campo PID de proceso en la TLB. Evita algunos fallos por iniciación.
Puede ser unificada o separada.
3. Memoria virtual
62
31
TLB. Esquema
3. Memoria virtual
63
TLB. Funcionamiento.
„
„
Cuando un proceso se vuelve activo en el sistema se cambia de TP, y la TLB se
borra, si sólo tiene refs a un proceso.
La CPU genera internamente una dirección virtual que es cotejada en la TLB para
ver si está su traducción.
‰
La dirección virtual sólo existe dentro del procesador.
„
Si la referencia a la TP no está: fallo de TLB: Se trae un bloque de entradas de la
TP a TLB y a continuación se consulta ésta.
„
Cuando hay un acierto en TLB, la página está en MP, y puede que sus datos estén
en caché.
‰
Si además, la página no está en MP: fallo de página.
Tamaño de bloque
4-8 bytes (una entrada de TP)
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
3. Memoria virtual
Valores típicos
de parámetros
64
32
TLB. Funcionamiento (II).
Dirección virtual
Acierto
en TLB?
si
Dir. física (desde TLB)
no
Página en
MP?
si
no
MP llena?
Dato en
caché?
no
si
no
si
Bajar página a MS
Subir página a MP y
actualizar TP.
Bajar subir bloque a
Caché
Dato (desde caché)
Dir. física (desde TP) y
actualiza TLB.
3. Memoria virtual
65
TLB. Implementación típica.
„
„
„
„
„
„
„
Líneas de 1 entrada de la TP.
32-1024 líneas
Totalmente asociativo, o asociativo por conjuntos.
Mr=0.001 - 0.01
Implementación dentro del procesador. Sólo una.
CB-WA. Reemplazo aleatorio.
Para cada bloque:
‰
‰
‰
‰
Bit de válido.
Bits de etiqueta (nº de página virtual, si blq=1entrada).
Entrada de la TP.
Bit de Dirty.
66
33
Buffer de traducción anticipada o TLB (IV)
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
3. Memoria virtual
67
34