sesion14

Vista previa del material en texto

Ingeniería de los Computadores 
Sesión 14. Coherencia de memoria 
(multiprocesadores) 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de 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 
demás cachés 
 
• Protocolos basados en directorio: 
 Utilizado en redes donde el broadcast no es posible a causa de la 
degradación 
 Redes multietapa 
 Se utiliza para ello un directorio centralizado o distribuido 
 
 
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 
bus 
 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 
 
 
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 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
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) 
 
 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 
 
 
Transacciones en el bus 
observadas por las cachés 
para cambiar su estado 
(monitorización) 
Flush = dato en bus + 
actualizacion de memoria 
principal 
Operaciones del procesador 
+ transacciones que se 
generan en el bus por dichas 
operaciones de procesador 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de 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 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de sondeo o snoopy – Write Once 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• 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 
Modificado (M) 
 Transiciones según operaciones sobre cachés: fallo de lectura, escritura, 
reemplazo 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. CoherenciaConceptos 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 
especial de bus 
 Estados de línea de caché: Lectura_Privada(LP), Lectura_Compartida (LC) y 
Sucia_Privada (SP) 
 Transiciones según operaciones sobre cachés: fallo de lectura, escritura, 
reemplazo 
 
 
SP LP 
LC 
PrRd/- 
PrWr/BusUpdate 
BusRd/BusCache 
BusUptadte/- 
PrRd/- 
PrWr/- 
PrRd/- 
PrWr/BusRd PrWr/BusRd 
PrRd/BusRd 
PrWr/BusRd 
BusRd/BusCache 
PrWr/BusUpdate 
BusRd/BusWB 
PrWr/- 
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ó b j h j d li ió 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio (centralizado o distribuido) 
 Sistemas multiprocesador con varias subredes locales de 
interconexión y muchos elementos conectados 
 Directorio común que almacena el estado de las líneas de caché 
 La red de interconexión no soporta broadcast o provoca mucha 
degradación 
 El comando de invalidación/actualización se envía a aquellas 
caches que disponen de copia local de un bloque 
 La entrada del directorio tiene un bit de permiso de actualización 
 Existen varias copias compartidas de la misma línea de caché para 
mejorar el rendimiento sin incrementar el tráfico 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Centralizado 
 Tabla centralizada que almacena ubicación de cada copia de 
caché 
 Tamaño grande  búsqueda asociativa 
 Inconvenientes: competencia de acceso y tiempos largos de 
búsqueda 
 Protocolos de mapeado completo o limitado 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Mapeado completo 
 Protocolo DirN NB 
 En el directorio: cada entrada de bloque tiene unos bits de 
presencia por cada caché y un bit de inconsistencia única 
 Bits de presencia: especifica la presencia en las cachés de copias del 
bloque de memoria 
 Bit de inconsistencia única: cuando este bit está activado, sólo uno de los 
bits presencia está a uno, es decir, sólo existe una caché con la copia de 
ese bloque o línea, con lo que sólo esa caché tiene permiso para actualizar 
la línea 
 Por cada caché: 
 Bit de validación (v): indica si la copia es válida o no 
 Bit de privacidad (p): indica si la copia tiene permiso de escritura, es decir, 
cuando este bit es uno entonces es la única copia que existe de esta línea 
en las cachés y por tanto tiene permiso para escribir 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Mapeado completo 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Mapeado completo 
 Fallo de lectura: 
 Supongamos que una caché envía una petición de fallo de lectura a la 
memoria 
 Si el bit de inconsistencia simple está activado, la memoria envía una 
petición de actualización a la caché que tenga el bit de privado activo, o 
sea, a la única caché que tenga la línea 
 La caché devuelve el bloque a la memoria y desactiva su bit de privado 
 El bit de inconsistencia simple también es desactivado del directorio central 
 La memoria activa el bit de presencia de la caché correspondiente que solicitó el bloque 
y envía una copia a dicha caché 
 Cuando la caché recibe la copia, activa el bit de válido y desactiva el de privado 
 Si el bit de inconsistencia simple está desactivado, trae el bloque de la 
memoria activando el de válido y desactivando el de privado como en el 
caso anterior 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Mapeado completo 
 Fallo de escritura: 
 Supongamos que una caché envía una petición de fallo de escritura a la 
memoria 
 La memoria envía peticiones de invalidación a todas las cachés que tienen 
copias de ese bloque poniendo a cero sus bits de presencia 
 Las cachés aludidas invalidan sus líneas poniendo a 0 el bit de línea válida 
 Si hay alguna caché con una copia del bloque con el bit de privado 
activado, la memoria actualiza su copia 
 Una vez la memoria recibe todos los reconocimientos, activa el bit de 
presencia en la caché y manda la copia dicha caché 
 El bit de inconsistencia simple se pone a 1 puesto que solo hay una copia 
 La caché que recibe la copia, se modifica y pone los bit de válido y privado 
a uno 
 i d i 
 
 
 
 
 
 
 
 
 
 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Mapeado completo 
 Acierto de escritura: 
 Si el bit de privado es 0, la caché envía una petición de 
privacidad a la memoria 
 La memoria invalida todas las demás cachés que tienen una copia del 
bloque 
 Se pone el bit de inconsistencia a 1 
 Cuando la caché recibe el reconocimiento de que las demás cachés 
han sido invalidadas, modifica su bloque pone el bit de privado a uno 
 Si el bit de privado es 1, entonces escribe sin más puesto que 
es la única caché que tiene copia de esa línea 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Mapeado completo 
 Principales problemas: 
 Tamaño_directorio = (1 + Número_cachés) x 
Número_líneas_memoria 
 Crecimiento del directorio proporcional a N2 
 Para evitar el crecimiento cuadrático del mapeado completo 
es posible restringir el número de copias de caché activas de 
forma simultánea de un bloque. De esta forma se limita el 
crecimiento del directorio hacia un valor constante 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Mapeado limitado 
 Diri NB, i<N 
 Idéntico al protocolo de mapeado completo pero reduciendo el número de 
copias de caché activas simultáneas de un bloque: 
 Cada entrada de bloque tiene un bit de presencia en cada caché y un bit de 
inconsistencia única 
 Cada caché tiene un bit de validación (v) y un bit de privacidad (p) 
 Punteros limitados 
 Llamada de desalojo: la memoria invalida una de las cachés que utilizaba el 
puntero y le asigna ese puntero libre a la nueva caché 
 Tamaño punteros: log2 N bits 
 Tamaño_directorio = (1 + Punterosx log2 N) x Bloques_memoria 
 Crecimiento proporcional a N·Log2N 
 Protocolo “escalable” 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Directorio distribuido 
 Tabla distribuida entre cachés 
 Cada tabla local almacena el estado de caché y qué copias de 
bloques 
 Protocolos de mapeado distribuidos de directorio: 
 Encadenados: listas de cachés encadenadas 
 Jerárquicos: división del directorio entre grupos de 
procesadores interconectados (clusters) 
 
 
Ingeniería de los Computadores 
Sesión 14. Memoria. Coherencia 
Conceptos Consistencia de caché 
 
Protocolos de coherencia 
 
• Protocolos de directorio. Directorio distribuido encadenado 
 Lista simple o doble enlazada de punteros entre distintas cachés 
con copia de un mismo bloque: 
 Cada entrada del directorio apunta a una caché con copia del bloque y 
esta caché a su vez tiene un puntero que apunta a otra, etc. 
 Una entrada en el directorio contiene un único puntero que apunta a la 
cabeza de la lista 
 
 
	Ingeniería de los Computadores
	Número de diapositiva 2
	Número de diapositiva 3
	Número de diapositiva 4
	Número de diapositiva 5
	Número de diapositiva 6
	Número de diapositiva 7
	Número de diapositiva 8
	Número de diapositiva 9
	Número de diapositiva 10
	Número de diapositiva 11
	Número de diapositiva 12
	Número de diapositiva 13
	Número de diapositiva 14
	Número de diapositiva 15
	Número de diapositiva 16
	Número de diapositiva 17
	Número de diapositiva 18
	Número de diapositiva 19
	Número de diapositiva 20
	Número de diapositiva 21
	Número de diapositiva 22
	Número de diapositiva 23
	Número de diapositiva 24
	Número de diapositiva 25