PDF de programación - Sistemas de memoria

Sistemas de memoria

Jerarquía de memoria

• Conceptos básicos
•
• Memoria caché
• Memoria principal
• Memoria virtual

Estructura de computadores 2

Memoria caché

• Conceptos generales
• Operación de un sistema caché
• Rendimiento caché
•
Fuentes de fallos
• Cachés de instrucciones y datos
• Mejora del rendimiento caché
• Coherencia caché
• Ejemplos de sistemas caché

Estructura de computadores 2

Principio de localidad

• Objetivo: Memoria rápida e ilimitada
• Principio de localidad:

los programas acceden a una parte
relativamente pequeña de su espacio de direcciones en cualquier
instante de tiempo
•
•
✓ El principio de localidad permite proporcionar al usuario la ilusión de
que dispone de tanta memoria como sea posible en la tecnología más
barata, mientras el acceso se produce a la velocidad más alta

Localidad temporal
Localidad espacial

Estructura de computadores 2

Jerarquía de memoria

La memoria se estructura en varios niveles

•
• Comunmente el nivel más cercano al procesador (superior) contiene
un subconjunto de la información almacenada en cualquier nivel más
alejado. El nivel más bajo contiene todos los datos.
La información se ubicará en cada nivel de acuerdo con su
probabilidad de uso

•

Reg.

______

Caché

________________

Mem. principal

_______________________

Coste por bit

Tiempo de

acceso

Capacidad

Mem. secundaria (disco)

________________________________

Mem. auxiliar (cinta)
Estructura de computadores 2

Definiciones

Bloque: Unidad mínima de transferencia de información entre un nivel
superior y otro inferior
Acierto: La información requerida aparece en el nivel superior
Fallos: La información no se encuentra en el nivel superior y es
necesario acceder al inferior
Tasa de aciertos: Fracción de accesos a memoria encontrados en el
nivel superior
Tasa de fallos: Fracción de accesos a memoria no encontrados en el
nivel superior (1- tasa de aciertos)
Tiempo de acierto: Tiempo de acceso al nivel superior

Estructura de computadores 2

Definiciones

Penalización de fallo: Tiempo necesario para sustituir un bloque del
nivel superior por el del nivel inferior, más tiempo para entregar ese
bloque al procesador. Se divide en:

✦ Tiempo de acceso: tiempo para acceder a la primera palabra de un

bloque en un fallo

✦ Tiempo de transferencia: tiempo adicional para transferir las restantes

palabras del bloque

Tiempo de acierto < Penalización de fallos

Estructura de computadores 2

Introducción a las cachés

El término caché es utilizado por primera vez por Conti, Gibson y
Pitowsky (1968)
El primer computador comercial con memoria caché fue el IBM 360/85
La caché es una memoria pequeña y rápida que se sitúa entre el
procesador y la memoria principal
Almacena la información actualmente en uso de la memoria principal
La gestión de la caché es similar a la gestión de la memoria virtual
El principio de localidad justifica el éxito de la memoria caché

Procesador

Caché

Memoria
principal

Estructura de computadores 2

Estructura de computadores 2

En los procesadores la memoria es central

Estructura de computadores 2

Operación de un sistema caché

Al bloque de una caché se le suele llamar
línea
Estructura general de una memoria caché:
Directorio: contiene información sobre las
líneas de la zona de almacenamiento
Zona de almacenamiento: contiene la copia
de algunas líneas de memoria principal
El directorio contiene un conjunto de
etiquetas para identificar si una palabra de la
caché se corresponde con la palabra
buscada
Bit de validez: permite conocer si un bloque
de la caché no tiene información valida

Estructura de computadores 2

Ubicación de líneas (I)

Tres categorías de organización caché (n líneas):
• Correspondencia directa. Cada línea tiene un único lugar donde

puede aparecer en la caché

•

Totalmente asociativa. Cada línea puede estar en cualquier parte
de la caché

• Asociativa por conjuntos de m vías. A cada línea le
líneas de la caché

corresponde un conjunto de m
(nº de conjuntos = n/m = c)

Correspondencia directa: 1 vía, n conjuntos
Totalmente asociativa: n vías, 1 conjunto

Estructura de computadores 2

Ubicación de líneas (y II)

Distintas configuraciones
de una caché de 8 líneas

Ejemplos de ubicación

Estructura de computadores 2

Búsqueda de líneas

•
•

Índice: selecciona un conjunto de la caché

Etíqueta: se compara simultáneamente con todas las etiquetas del conjunto seleccionado

El bit de validez nos indica si la entrada contiene una dirección válida

Aumentar la asociatividad aumenta el tamaño de la etiqueta

Estructura de computadores 2

Reemplazo de líneas

Tenemos que establecer un criterio para reemplazar líneas en un fallo caché

En correspondencia directa una única posibilidad

En asociativa por conjuntos o totalmente asociativa: hay que escoger una línea entre las del
conjunto o entre todas las de la caché, totalmente asociativa

Principales estrategias:
•
•

Aleatoria: se hace una elección aleatoria. Fácil de implementar

Menos recientemente usado (LRU): el bloque que es sustituido es el que hace más
tiempo que no es utilizado

Estructura de computadores 2

Implementación del algoritmo LRU
Implementación con listas enlazadas. Muy costosa. ALTERNATIVAS:
- ALGORITMO 1 (PURO)

Caché asociativa por conjuntos (E líneas / conjunto)
R[E][E] Matriz triangular superior. Necesidad de (E*(E-1)/2) bits de
memoria. Algoritmo rápido
ACTUALIZACIÓN

Línea i referenciada => R[i][*] <- 1 y R[*][E-i-1] <- 0

TEST LRU

Línea LRU: i si R[i][*]=0 y R[*][E-i-1]=1 (o vacías)

Ejemplo algoritmo LRU (puro) E=4:
L.0 L.2 L.3 L.1 L.3 L.2 L.0 línea referenciada

1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 1 1 0 1 0 0 0 0 matriz
0 1 0 0 0 1 1
(L1) (L1) (L1) (L0) (L0) (L0) (L1) línea LRU

Estructura de computadores 2

Implementación del algoritmo LRU
- ALGORITMO 2 (VARIANTE)

Caché asociativa por conjuntos (E líneas / conjunto)
El núméro de bits que necesita el algoritmo puro aumenta con el
cuadrado del tamaño de cada conjunto. Es un tamaño inaceptable
para tamaños mayores que 16
Aplicación del algoritmo 1 en varios niveles
* CARATERÍSTICAS: Necesidad de menos bits de memoria.
Algoritmo menos rápido

Ejemplo algoritmo LRU (puro) E=8 líneas por conjunto: Dividos en
4 pares de 2 líneas. 4*(4-1)/2=6 bits para seleccionar el par y
2*(2-1)/2=1 bit para seleccionar la línea dentro del conjunto. Frente
a los 8*(8-1)/2=28 bits del algoritmo puro
Matriz de pares: 0 0 0 Par 0: 0 Par 1: 0 Par 2: 0 Par 3: 0
0 0
0

Estructura de computadores 2

Implementación del algoritmo LRU

Ejemplos y número de bits necesarios para implementación

IBM

370/168-3

IBM 3033

E

8

16

PURO

2 niveles

3 niveles

BITS PURO BITS VARIABLE

-

-

4*2

-

-

4*2*2

28

120

10

18

Estructura de computadores 2

Implementación de otros algoritmos

• Algoritmo FIFO: Un contador módulo E por
cada conjunto. Se incrementa en cada
reemplazamiento y apunta a la siguiente línea
a ser reemplazada
• Algoritmo RAND: Un contado módulo E único.
Se incrementa: cada ciclo de reloj, cada
referencia a memoria o cada vez que se
produzca un reemplazamiento

Estructura de computadores 2

Operación de escritura (I)

Hay 2 opciones básicas para escribir en la caché:

•

•

Escritura directa: La información se escribe en la caché y en la
memoria del nivel inferior
Postescritura: Sólo se escribe en la caché. Cuando se
reemplaza la línea se escribe en memoria

Bit de modificación: bit de estado que se utiliza en postescritura para
indicar si una línea se ha modificado o no. Reduce la frecuencia de
escritura ante reemplazos de línea, ya que si la línea no se ha
modificado no hace falta escribirla en memoria.

Estructura de computadores 2

Operación de escritura (II)

Ventajas de la escritura directa:

•

•
•

Fácil de implementar (detención de la UCP en la escritura =>
buffer de escritura)
Fallos de lectura menos costosos
La memoria del nivel inferior está siempre actualizada

Estructura de computadores 2

Operación de escritura (III)

Ventajas de la postescritura:

Escritura a la velocidad de la caché

•
• Múltiples escrituras en una línea implican una sola escritura de

la línea completa en la memoria

• Menos ancho de banda de memoria
•

Se puede hacer uso efectivo del ancho del nivel más bajo

Estructura de computadores 2

Operación de escritura (y IV)

Opciones en un fallo de escritura:

• Ubicar en escritura o búsqueda en escritura: La línea se carga
y siguen las acciones de acierto de escritura (en postescritura).
Se busca que las escrituras subsiguientes en la línea no
provoquen fallos

• No ubicar en escritura o evitar escritura: La línea se modifica
en el nivel inferior y no se carga en la caché (en escritura
directa). Las escrituras subsiguiente en la línea provocarán
escrituras a memoria.

Estructura de computadores 2

Ejemplo VAX-11/780

•
•
•
•
•
•
•
•

Tamaño caché: 8kb=8192 bytes

Tamaño línea: 8 bytes

Asociativa por conjunto de 2 vías.
8192/(8*2)=512 conjuntos

Reemplazo aleatorio

Escritura directa

Buffer de escritura de una palabra

No ubicación en un fallo de escritura

Dos bancos: cada banco contiene una
línea de cada conjunto

Estructura de computadores 2

Ejemplo VAX-11/780

¿Qué ocurre en un acierto caché?

(1)

La dirección se descompone en Etiqueta
e Índice

(2) El índ