PDF de programación - Multiprocesadores / Coherencia de caché

MULTIPROCESADORES

COHERENCIA DE CACHÉ





MULTIPROCESADORES

COHERENCIA DE CACHÉ

© 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





MULTIPROCESADORES

COHERENCIA DE CACHÉ

Índice

Presentación

Acceso a caché en escritura

Multiprocesadores o multinúcleos

¿Pero que pasa en estos sistemas con la caché?

¿Qué pasa con un dato que se necesite en más de un procesador?

¿Qué pasa si al acceso a esta variable, no es solo en lectura?

Multiprocesadores o multinúcleos: ejemplo

¿Cuál de ellas tiene el valor correcto de la variable i?

Jerarquía de caché

Esquemas básicos de coherencia de caché

Protocolo snooping (o fisgoneo)

Snooping para write back

Coherencia basada en directorios

Modelos de directorios

Resumen

4

5

8

8

8

8

10

10

12

14

16

18

20

22

24

3





Presentación

MULTIPROCESADORES

COHERENCIA DE CACHÉ

En este tema veremos cómo solucionar el problema de la coherencia de caché cuando hay

múltiples procesadores, tanto en sistemas monoprocesador con varios núcleos, como en sistemas

con varios procesadores distribuidos.

Analizaremos cuáles son los problemas de la jerarquía de caché en sistemas multiprocesadores y

diferentes métodos para evitar errores de caché, como:

Protocolo Snooping (o fisgoneo).

Snooping para write through.

Snooping para write back.

Coherencia basada en directorios.

Directorios full-map.

Directorios limitados.

Directorios encadenados.

4





MULTIPROCESADORES

COHERENCIA DE CACHÉ

Acceso a caché en escritura

Ya hemos visto que la caché contiene copia de datos en memoria, nunca datos propios. Se
considera un acierto de caché cuando el procesador intenta acceder a un dato, un dato que

siempre está en memoria pero que, a veces, está replicado en memoria caché.

Y aquí es donde está la ventaja de la caché, si este dato se encuentra en caché, es la caché la

que responde al procesador simulando que ya se ha producido el acceso al dato en memoria.

Si los accesos son en lectura todo es perfecto, ¿pero qué pasa cuando un acceso a un dato es

en escritura y la caché tiene una réplica del mismo? El acceso, una vez más, se para en la

caché, por lo que la memoria nunca se entera de que ha habido una modificación del dato. Como

consecuencia, el dato almacenado en caché y en memoria no son el mismo, lo que se conoce
como incoherencia de caché.

Ya hemos visto también que esto tiene una solución, bastante sencilla, las políticas de escritura.

Hemos visto que existen básicamente dos métodos que funcionan bien pero que, como siempre,

no son perfectos.

5





MULTIPROCESADORES

COHERENCIA DE CACHÉ

Escritura inmediata: write
through

Escritura retardada: write
back

La escritura inmediata es segura pero poco eficiente, ya

que todos los accesos a memoria en escritura provocan

fallo de caché, lo que reduce a la mitad el índice de

aciertos por parte de la caché.

Hay técnicas que mejoran este problema, dejando la

responsabilidad a la caché de actualizar el dato en

memoria, dejando que el procesador continúe con la

ejecución de código antes de que la memoria se

actualice por completo. El inconveniente es que carga

de trabajo a la caché, haciéndola sustancialmente más

lenta.

La escritura retardada, por el contrario, penaliza más los

fallos de caché, pues si hay un fallo de caché y hay que

reemplazar un bloque de datos de la misma, si el bloque

tiene activada la señal de bloque modificado, antes de

proceder al reemplazo hay que escribir el bloque en

memoria y, después, proceder a la carga del nuevo

bloque. Esto añade retrasos en la caché cada vez que

hay que reemplazar un bloque que esta modificado

(prácticamente todos).

Al igual que en el caso de la escritura inmediata, hay

técnicas que mejoran este comportamiento. Una de ellas

es hacer que la caché, en sus momentos ociosos y de

manera autónoma, revise qué bloques se han modificado

y vaya actualizando la memoria para que, si hay

reemplazo sobre ellos, ya se haya realizado la mitad del

trabajo.

6





Una gran ventaja

MULTIPROCESADORES

COHERENCIA DE CACHÉ

La ventaja no es otra que el tiempo de espera que el procesador ha tenido que esperar es
muy inferior al que hubiera tenido que hacerlo si el dato no se encontrara en caché.

Escritura inmediata: write through

Los accesos en escritura siempre producen fallo de caché, por lo que la petición de
escritura siempre llega a la memoria principal. No se pueden dar problemas de caché
porque el dato en memoria no se queda desactualizado en ningún momento.

Escritura retardada: write back

La memoria caché, mantiene información interna de que datos han sido actualizados por
una escritura, y estos datos antes de ser eliminados de caché, son escritos en memoria.
Los datos permanecen desactualizados solo mientras hay una copia de los mismos en
caché, pero nunca se pierden datos, porque la caché se guarda de actualizar la memoria
antes de eliminar los datos actualizados

7





MULTIPROCESADORES

COHERENCIA DE CACHÉ

Multiprocesadores o multinúcleos

Como hemos visto en temas anteriores, el desarrollo de sistemas multiprocesadores o

multinúcleos está muy en boga.

¿Pero que pasa en estos sistemas con la caché?

Lo primero que tenemos que pensar es cómo se organiza la jerarquía de memoria en estos

sistemas, diferenciemos multiprocesadores y multinúcleos.

Multiprocesador

Máquina con dos a más procesadores completos.
Normalmente podemos hablar de una sola maquina con
más de un procesador o incluso en dos máquinas
diferentes: UMA vs NUMA.

Multinúcleo

Procesador con dos o más núcleos en un solo chip. Una
máquina que tiene un solo procesador, internamente
construido por más de un núcleo funcional, instalado.

En ambas máquinas la jerarquía de memoria es muy diferente, pero tienen un problema, aunque

sea a niveles diferentes.

¿Qué pasa con un dato que se necesite en más de un procesador?

Una variable compartida por más de un procesador está replicada en los sistemas de memoria de

cada una. Recordemos que esta es una máxima a cumplir, para agilizar los accesos a esa

variable. Por ejemplo, este es el principio de existencia de la caché.

Si la variable está replicada en la memoria común a todos los procesadores, ya que ambos deben

poder acceder a ella, por lo tanto no es un dato local. Además, está replicada en cada una de las

memorias locales ya el acceso a los datos debe ser lo más rápido posible, consiguiendo reducir

latencia en los accesos.

¿Qué pasa si al acceso a esta variable, no es solo en lectura?

8





MULTIPROCESADORES

COHERENCIA DE CACHÉ

Tras una serie de accesos al dato en escritura, las copias de la variable en las cachés de los

procesadores tendrán datos diferentes, ya que no es suficiente con que cada procesador se

encargue de mantener el valor correcto de la variable en la memoria compartida cada vez que se

actualiza, sino que es necesario que el valor correcto de esta se chequee antes de acceder a él

en lectura.

9





MULTIPROCESADORES

COHERENCIA DE CACHÉ

Multiprocesadores o multinúcleos: ejemplo

Para simplificar el ejemplo, quitemos las cachés de nuestro problema. Para ello supongamos una

maquina UMA con dos procesadores. El sistema completo tiene una memoria privada para cada

procesador y una memoria compartida a todos los procesadores para el intercambio de

información.

Supongamos que ambos procesadores acceden al dato compartido i donde guardan información

de sincronización sobre las operaciones que están realizando conjuntamente. Supongamos la

siguiente secuencia de accesos a la variable i.

Interpretación de los datos

¿Cuál de ellas tiene el valor correcto de la variable i?

Nadie. El valor correcto debería ser 9 (5+3+1), y dicho valor que no está almacenado en ninguna

de las memorias.

10





MULTIPROCESADORES

COHERENCIA DE CACHÉ

Este problema, ocurre siempre que haya una memoria más rápida enmascarando a otra memoria

mayor y compartida, pero más lenta, y haya datos compartidos entre todos los procesos. Esto

significa que cuando hay más de una memoria caché de una memoria y hay datos compartidos

entre ellas, estos datos pueden no ser coherentes, por eso se le llama incoherencia de caché. La

incoherencia de caché es complicada de solucionar, aunque no imposible, y solo se da en

sistemas multiprocesador o multinúcleo.

Dato en más de un procesador

La memoria caché, mantiene información interna de que datos han sido actualizados por
una escritura, y estos datos antes de ser eliminados de caché, son escritos en Memoria.
Los datos permanecen desactualizados, solo mientras hay una copia de los mismos en
caché, pero nunca se pierden datos, porque la caché se guarda de actualizar la memoria
antes de eliminar los datos actualizados

Interpretación de los datos

Cuando los procesadores leen la variable compartida en los pasos 1 y 2, todo va bien.

En el paso 3, el procesador 1 accede a la variable en escritura guardando un 8 (5+3),

por lo que su copia local almacena un 8 y se encarga de actualizar la copia en la

memoria compartida para futuros accesos. Sin em