PDF de programación - Sesión 14. Coherencia de memoria (multiprocesadores) - Ingeniería de los Computadores

Ingeniería de los Computadores

Sesión 14. Coherencia de memoria

(multiprocesadores)

Conceptos

Consistencia de caché

Protocolos de coherencia

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

• Protocolos de sondeo o snoopy:



 Utilizado en redes donde el broadcast (difusión) es posible
 Redes basadas en bus
 Cada caché monitoriza el estado del bus y las transacciones de las

• Protocolos basados en directorio:

 Utilizado en redes donde el broadcast no es posible a causa de la

 Redes multietapa
 Se utiliza para ello un directorio centralizado o distribuido

demás cachés

degradación



Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy

 Objetivo: garantizar las transacciones necesarias en el bus para operaciones de
memoria y que los controladores de caché observen y actúen en transacciones
relevantes

 Todas las transacciones aparecen en el bus y son visibles para los procesadores

en el mismo orden en el que se producen

 Utilizado en sistemas multiprocesador con bus y pocos elementos conectados
 Cada procesador indica el estado de cada línea de su caché
 La red de interconexión debe permitir broadcast (difusión)
 Cada caché monitoriza las transacciones de las demás cachés observando el

 Se utiliza un algoritmo distribuido representado como un conjunto de

máquinas de estados finitos que cooperan entre sí:
 Conjunto de estados asociado con los bloques de memoria en las cachés
 Diagrama de transición entre estados
 Acciones asociadas a las transiciones entre estados

bus



Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy – Protocolo de invalidación en

escritura (write invalidate)



 Constituyen las estrategias más robustas y extendidas
 Basado en asegurar que un procesador tiene acceso exclusivo a un dato antes

de que acceda a él

 Se consigue invalidando todas la líneas de todas las cachés que contengan ese

dato que esta siendo escrito en ese momento

 Cada controlador de caché observa las transacciones de memoria (observa el

bus) de los otros controladores para mantener su estado interno

 Control de coherencia de caché mediante transacciones de lectura y de lectura

exclusiva

 Cuando un procesador quiera leer un dato invalidado, falle su caché y tenga

que ir a memoria a buscarlo

 Protocolos MSI, MESI, Write Once y Brekeley

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy – Protocolo de actualización en

escritura (write-update)
 Menos utilizados que el anterior (write-invalidate)



 Cada vez que un procesador escribe un dato, se actualizan las

cachés que contienen el dato en los demás procesadores


 Problemas para mantener el ancho de banda bajo control debido

a la alta cantidad de transacciones que se generan


 Mejora: escritura en una localización  actualización de cachés

relacionadas



 Protocolos Dragon y Firefly

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy - MSI

 Protocolo de invalidación básico para cachés write-back (MSI)
 Estados: Inválido (I), Compartido (S), Modificado (M)

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia



 Inválido: no es válido el bloque
 Compartido: el bloque esta presente en la caché y no ha sido

modificado, la memoria principal esta actualizada y cero o
más cachés pueden tener también una copia actualizada
(compartida)

 Modificado: únicamente este procesador tiene una copia
válida, la copia de la memoria principal esta anticuada y
ninguna otra caché puede tener una copia válida del bloque
(ni en estado modificado ni compartido)


Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy - MSI



Operaciones del procesador
+ transacciones que se
generan en el bus por dichas
operaciones de procesador

Transacciones en el bus
observadas por las cachés
para cambiar su estado
(monitorización)
Flush = dato en bus +
actualizacion de memoria
principal

Conceptos

Consistencia de caché

Protocolos de coherencia

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

• Protocolos de sondeo o snoopy - MESI



 Ampliación del protocolo de invalidación de 3 estados. Refinamiento para

aplicaciones “secuenciales” que corren en multiprocesadores (carga común
usada en multiprocesadores de pequeña escala)

 En el MSI el programa cuando lee y modifica un dato tiene que generar 2

transacciones incluso en el caso de que no exista compartición (solo presente
en una caché) del dato (BusRd y BusRdX)

 Estados: Modificado (M), *Exclusivo (E), Compartido (S), Inválido (I)
 *Exclusivo (E): indica que el bloque es al única copia (exclusiva) del sistema
multiprocesador y que no está modificado, ningún otro procesador tiene el
bloque en la caché y la memoria principal está actualizada

 Al ser exclusivo es posible realizar una escritura o pasar al estado modificado

sin ninguna transacción en el bus, al contrario que en el caso de estar en el
estado compartido; pero no implica pertenencia, así que al contrario que en el
estado modificado la caché no necesita responder al observar una petición de
dicho bloque (la memoria tiene una copia válida)

 Conocido como protocolo Illinois (publicado por la U. de Illinois en 1984)



Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy - MESI



BusRd(S) = cuando la transacción
de lectura en el bus ocurre, se activa
la señal (S).

Este protocolo necesita
una señal adicional que
sea proporcionada por
el bus (S) que esté
disponible para que los
controladores puedan
determinar en una
transacción BusRd si
existe otra caché que
tenga el mismo bloque

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy – Write Once

 Cada línea de caché tiene dos bits extra para almacenar el estado de esa línea
 Líneas adicionales de control para inhibir la memoria principal
 Estados líneas de caché:

 Válida (V): la línea de caché, es consistente con la copia de memoria, ha

sido leída de la memoria principal y no ha sido modificada

 Inválida (I): la línea no se encuentra en la caché o no es consistente con la

copia en memoria

 Reservada (R): los datos han sido escritos una única vez desde que se leyó
de la memoria compartida, la línea de caché es consistente con la copia en
memoria que es la única otra copia

 Sucia (S): la línea de caché ha sido escrita más de una vez, y la copia de la
caché es la única en el sistema (por lo tanto inconsistente con el resto de
copias)

 Transiciones según operaciones sobre cachés: fallo de lectura, acierto de

escritura, fallo de escritura, acierto de lectura y cambio de línea



Conceptos

Consistencia de caché

Protocolos de coherencia

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia



• Protocolos de sondeo o snoopy – Write Once



• Protocolos de sondeo o snoopy - Dragon

 Protocolo de actualización en escritura básico para cachés write-back (Dragón)
 Estados: Exclusivo (E), Compartido (C), Compartido_Modificado (SM) y

 Transiciones según operaciones sobre cachés: fallo de lectura, escritura,

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



Modificado (M)

reemplazo



 Estados de línea de caché: Lectura_Privada(LP), Lectura_Compartida (LC) y

 Transiciones según operaciones sobre cachés: fallo de lectura, escritura,

especial de bus

Sucia_Privada (SP)

reemplazo



Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy - Firefly

 Protocolo de actualización en escritura, que hace uso de una línea compartida

PrRd/-
PrWr/BusUpdate
BusRd/BusCache
BusUptadte/-

PrRd/BusRd
PrWr/BusRd

LC

BusRd/BusCache

BusRd/BusWB

PrRd/-

LP

PrWr/BusUpdate

PrWr/-

SP

PrRd/-
PrWr/-

PrWr/BusRd

PrWr/BusRd

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché

Protocolos de coherencia



• Protocolos de sondeo o snoopy. Rendimiento

 Consideraciones a tener en cuenta para evaluar el rendimiento de un

protocolo:
 Tráfico causado por fallos de caché
 Tráfico de comunicación entre cachés

 Diferencias de rendimiento entre protocolos de invalidación y actualización:

 Varias escrituras a la misma palabra sin lecturas intermedias
 Líneas de caché de varias palabras: los de invalidación trabajan sobre el
bloque y los de actualización sobre palabras para aumentar la eficiencia

 Retraso entre escritura de palabra en un procesador y la lectura por parte

de otro; mejor en lo protocolos de actualización

 Rendimiento según los requerimientos:

 Gestión de ancho de banda y memoria crítica: para aprovechar mejor el

ancho de banda del bus y la memoria, se utilizan los protocolos de
invalidación

 Migración de procesos o sincronización intensivas: cuando se requiera
mucha migración de procesos o mucha sincronización, un protocolo de
i

lid ió

ió

d

h

b j



j



li

Ingeniería de los Computadores
Sesión 14. Memoria. Coherencia

Conceptos

Consistencia de caché