PDF de programación - Memoria / Memoria Caché II

MEMORIA

MEMORIA CACHÉ II





MEMORIA

MEMORIA CACHÉ II

© Todos los derechos de propiedad intelectual de esta obra pertenecen en exclusiva a la Universidad
Europea de Madrid, S.L.U. Queda terminantemente prohibida la reproducción, puesta a disposición del
público y en general cualquier otra forma de explotación de toda o parte de la misma.

La utilización no autorizada de esta obra, así como los perjuicios ocasionados en los derechos de
propiedad intelectual e industrial de la Universidad Europea de Madrid, S.L.U., darán lugar al ejercicio
de las acciones que legalmente le correspondan y, en su caso, a las responsabilidades que de dicho
ejercicio se deriven.

2





Índice

Presentación

MEMORIA

MEMORIA CACHÉ II

Problemas de la función de correspondencia directa

Función de correspondencia asociativa

Función de correspondencia asociativa por conjuntos

¿Qué tal si intentamos aprovechar lo bueno de cada una de ellas y al mismo tiempo minimizar las
defectos?

¿En qué consiste?

¿Pero en cuantas ocurrencias dividimos nuestra caché?

Jerarquía de caché

Ejemplo con la caché asociativa por conjuntos

Problemas de la función de correspondencia asociativa por conjuntos

¿Qué pasa cuando la caché está totalmente llena y hay que meter un nuevo elemento?

Políticas de reemplazo

LRU (Least Recently Used)

Problemas con el reemplazamiento

¿Puede ocurrir alguna vez que el valor de una variable almacenada en RAM y su copia en caché no
tengan el mismo valor?

Resumen

4

5

7

9

9

9

9

11

13

16

16

18

20

21

21

23

3





Presentación

MEMORIA

MEMORIA CACHÉ II

En este tema terminamos con la caché. Veremos cómo mejorar la función de correspondencia

directa y cuáles son los problemas que puede causar una memoria caché en un sistema

informático.

Ampliaremos las funciones de correspondencia con la correspondencia asociativa por

conjuntos.

Revisaremos la idea de jerarquía de caché y el porqué de su existencia.

Descubriremos la necesidad de las políticas de reemplazo, que se encargan de determinar

cuál y cuándo se elimina un dato de la caché.

También veremos las políticas de escritura, que sirven para prevenir los problemas e

incoherencia de caché.

Con este tema, damos por finalizada la memoria caché. Por lo que será necesario, al igual que

en el tema anterior, hacer algún ejercicio para afianzar los conocimientos.

4





MEMORIA

MEMORIA CACHÉ II

Problemas de la función de correspondencia directa

La implementación por hardware de la función de correspondencia directa es muy simple. Es

más, no es un algoritmo en sí misma, sino una segmentación de las direcciones de memoria, lo
que hace que la función sea extremadamente rápida de implementar y tenga una efectividad
muy alta.

Sin embargo tiene un inconveniente muy grande: a cada dirección le corresponde una

y solo una posición posible en la caché. No parece grave, pero piensa en tu agenda y

considera que una de sus entradas solo pudiese contener un nombre. Los nombres

Andrés y Álvaro no podrían estar simultáneamente en la agenda, ya que los dos

consumen la entrada A de la agenda.

Este caso esta exagerado, ya que en la caché no tenemos solo 28 entradas, sino que
tenemos miles. Es como si tuviésemos una agenda, en la que no ordenásemos por la primera
letra, sino por las 2 o 3 primeras letras. Ahora si que podríamos tener a Álvaro y a Andrés

simultáneamente en la agenda, ya que no solo se busca la A, sino que se ordena por AL y AN.

Pero si en vez de pensar en dichos nombres pensamos en Fernando y Fernández también
tendríamos el mismo problema. Aunque tuviéramos una agenda de 2, 3 o incluso 7 caracteres
como índice, encontraríamos el mismo problema y, en tal caso, estaríamos hablando de una
agenda de 287=13492928512 entradas. Si tuviésemos una agenda con tal cantidad de entradas,
muchas de ellas (muchísimas de ellas) estarían sin utilizar, y aun así habría otras súper-

utilizadas.

5





MEMORIA

MEMORIA CACHÉ II

Aquí surge el segundo problema de una caché con demasiadas líneas: pueden existir
líneas de caché infra-utilizadas y también súper-utilizadas. Con las súper-utilizadas
no hay problema, simplemente producen fallos de caché, pero las infrautilizadas son un

desperdicio, en coste y espacio, no admisible.

¿Queda claro el problema? En una caché con correspondencia directa, hay un grupo de

direcciones de RAM a las que se les asigna una misma línea de caché. Puede ocurrir, y de

hecho ocurre con mayor probabilidad de la deseada, que dos direcciones de caché luchen por la

misma línea, lo que causa que estén provocando fallos de caché constantemente.

Así, aunque la función de correspondencia directa es una función muy utilizada, no es perfecta y

puede ser mejorada, aunque para ello tendremos que buscar una nueva función de

correspondencia.

Gran cantidad de entradas

¡¡Esto ya es una súper agenda!!

¿Cuántos de nosotros tienen una agenda con más de 13 millones de nombres?

Dos direcciones de caché luchen por la misma línea

Por el contrario, si la caché tiene muchas líneas, se reduce el número de direcciones de
memoria que compiten por la misma línea de caché, pero entonces puede haber líneas de
caché que no se utilizan o que se utilizan demasiado poco.

6





MEMORIA

MEMORIA CACHÉ II

Función de correspondencia asociativa

Una caché que implementa una función de correspondencia asociativa lo que hace es,
simplemente, no tener una función que asigne una única posición de caché a cada dirección
de memoria. En cambio, a cada dirección de memoria le corresponde cualquier línea de caché.

Esta función elimina por completo el problema de la súper-utilización y de la infrautilización de

líneas, aunque nos surge una pregunta: dado que al no haber un sistema de asignación de líneas

no hay un sistema de búsqueda en caché:

¿Cómo hacemos para encontrar una dirección en la caché y determinar si hay acierto o

fallo de caché?

La solución es colocar un comparador en cada una de las líneas, de manera que compruebe
todas a la vez de manera simultánea. Con este método sí podríamos buscar el posible dato

guardado de manera rápida determinando si hay acierto o fallo de caché y, en caso de acierto,

leerlo para enviárselo al microprocesador.

Esta es una caché muy eficiente, rápida y extremadamente cara. ¿Por qué? Por los

comparadores que hay que poner en cada línea.

Supongamos una caché más o menos actual (la que podría llevar nuestro ordenador), de 4Mb,

con un conjunto de vecindad de 32 vecinos. ¿Cuantas líneas tiene esta caché? Recordemos que
el número de líneas viene determinado por 4Mb/32 = 232/25 = 227 ≈ 128 millones de
comparadores.

Para colmo, al no haber línea, la etiqueta de la caché tendría que contener toda la información

necesaria para determinar qué dato está guardado en la línea de caché, por lo que los bits de

línea y etiqueta de la función de correspondencia directa se convierten íntegramente en etiqueta

en la función de correspondencia asociativa.

7





MEMORIA

MEMORIA CACHÉ II

Por tanto, esta caché tendría (32-5=27) bits en el campo etiqueta, con lo que tendría

128 millones de comparadores y de 27bits cada uno.

Esto no es mucho, es muchísimo. No se puede poner 128 millones de comparadores en una
caché o, al menos, en un espacio y precio aceptables, por lo que, a pesar de ser una caché con

muchos beneficios, físicamente es muy difícil de implementar.

¿Acierto o fallo de caché?

Está claro que el sistema de la lista, o de ir comprobando cada línea, una por una, tardaría

demasiado.

Además, el tiempo de respuesta dependería de dónde se ha guardado el dato, si en las

primeras líneas de caché o en las últimas.

8





MEMORIA

MEMORIA CACHÉ II

Función de correspondencia asociativa por conjuntos

Tenemos dos algoritmos para seleccionar una posición en caché del nuevo dato: la función de

correspondencia directa y la función de correspondencia asociativa, cada una con sus ventajas e

inconvenientes.

¿Qué tal si intentamos aprovechar lo bueno de cada una de ellas y al mismo tiempo
minimizar las defectos?

Volvamos a nuestra archiconocida agenda para ver cómo solucionar el solapamiento de nombres

y, al mismo tiempo, maximizar el uso de cada hoja.

La solución es simple: teniendo pocas entradas, 28, es suficiente utilizar una función de

asignación directa como puede ser la primera letra del nombre, para que las búsquedas sean

rápidas y, además, permitir que en una entrada de la agenda, se pueda guardar más de un dato.

Este sistema, conocido como caché asociativa por conjuntos, es el que se termina
adoptando para la caché.

¿En qué consiste?

En tener varias cachés que trabajen en paralelo en vez de una directa. Por tanto, la función de

asignación directa, determina la línea donde se guardara, pero no en qué replica de caché, lo

que permite tener más de un valor por línea (un valor en cada copia de caché).

Al dividir la caché en varias iguales, reducimos el tamaño de cada una de ellas de manera

individual, lo que reduce el número de líneas y provoca que sea más difícil que alguna línea de la

caché se infrautilice.

¿Pero en cuantas ocurrencias dividimos nuestra caché?

De nuevo la respuesta no es simple, hay que llegar a un convenio entre número de líneas y

número de entradas por línea. La respuesta la encontramos otra vez en la estadística.

9





MEMORIA

MEMORIA CACHÉ II

En un sistema multiproceso (como son todos los sistemas operativos actuales), ¿Qué probabilidad

hay de que dos procesos distintos luchen por la misma línea de caché? ¿Y de que sean tres,

cuatro, etc.?

Cuando una caché se divide en 2, 4 o más cachés, a cada una de ellas se la conoce co