Protocolo del dragón

El Protocolo Dragon ^[1] es un protocolo de coherencia de caché basado en actualizaciones que se utiliza en sistemas multiprocesador . La propagación de escritura se realiza actualizando directamente todos los valores almacenados en caché en varios procesadores. Los protocolos basados ​​en actualizaciones, como el protocolo Dragon, funcionan de manera eficiente cuando una escritura en un bloque de caché es seguida por varias lecturas realizadas por otros procesadores, ya que el bloque de caché actualizado está disponible en las cachés asociadas con todos los procesadores.

Estados

Cada bloque de caché reside en uno de los cuatro estados: limpieza exclusiva, limpieza compartida, modificación compartida y modificación.

• Limpieza exclusiva (E) : esto significa que el procesador actual obtuvo el bloque de caché por primera vez y ningún otro procesador ha accedido desde entonces.
• Limpieza compartida (Sc) : esto significa que el bloque de caché definitivamente existe en las cachés de varios procesadores y que el procesador actual no es el último en escribir el bloque. Los estados E y Sc se mantienen por separado por el protocolo para evitar que las operaciones de lectura y escritura en bloques de caché que no son compartidos induzcan transacciones de bus y, por lo tanto, ralenticen la ejecución. Esta es una ocurrencia común en programas de un solo subproceso.
• Compartido modificado (Sm) : Esto significa que el bloque existe en cachés de múltiples procesadores, y el procesador actual es el último en modificar el bloque. En consecuencia, el procesador actual se denomina propietario del bloque. A diferencia de los protocolos de invalidación, el bloque no necesita estar actualizado en la memoria principal, sino solo en el procesador. Es responsabilidad del procesador actualizar la memoria principal cuando se expulsa el bloque de caché.
• Modificar (M) : Esto significa que solo un procesador tiene el bloque de memoria, y también que ha modificado el valor desde que se trajo de la memoria.

Para cualquier par de cachés, los estados permitidos de un bloque de caché dado junto con los estados de los otros estados de la caché son los siguientes (los estados abreviados en el orden anterior):

	mi	Carolina del Sur	Sm	METRO
mi	norte	norte	norte	norte
Carolina del Sur	norte	Y	Y	norte
Sm	norte	Y	norte	norte
METRO	norte	norte	norte	norte

Actas

Hay 4 transacciones de procesador y 2 transacciones de bus.

Lectura del procesador (PrRd) : esto sucede cuando el procesador completa una lectura exitosa en un determinado bloque de caché ubicado en su caché.

Escritura del procesador (PrWr) : esto sucede cuando el procesador completa una escritura exitosa en un determinado bloque de caché ubicado en su caché. Esto hace que el procesador sea el último en actualizar el bloque de caché.

Error de lectura del procesador (PrRdMiss) : esto ocurre cuando el procesador no puede leer un bloque de caché de su caché y necesita recuperar el bloque de la memoria o de otro caché.

Error de escritura del procesador (PrWrMiss) : esto ocurre cuando el procesador no puede escribir en un bloque de caché desde su caché y necesita recuperar el bloque de la memoria u otra caché y luego escribir en él. Esto nuevamente hace que el procesador sea el último en actualizar el bloque de caché.

Bus Read (BusRd) : esto sucede cuando un procesador solicita al bus que obtenga el último valor del bloque de caché, ya sea de la memoria principal o de la caché de otro procesador.

Flush : esto sucede cuando un procesador coloca un bloque de caché completo en el bus. Esto es para reflejar los cambios realizados por el procesador en el bloque en caché en la memoria principal.

Actualización de bus (BusUpd) : esto ocurre cuando un procesador modifica un bloque de caché y otros procesadores necesitan una actualización en sus respectivos bloques de caché. Esto es exclusivo para escribir solo protocolos de actualización. BusUpd toma menos tiempo en comparación con la operación Flush, ya que las escrituras realizadas en cachés son más rápidas que en la memoria. Otro punto a tener en cuenta es que una caché no puede actualizar su copia local de un bloque de caché y luego solicitar al bus que envíe una actualización de bus. Si esto sucede, es posible que dos cachés actualicen independientemente su copia local y luego soliciten el bus. A continuación, verían las dos escrituras simultáneamente, lo que no seguiría la coherencia secuencial .

También se requiere una línea compartida para indicar si un determinado bloque de caché está disponible en múltiples cachés. Esto es necesario porque una de las cachés podría desalojar el bloque sin necesidad de actualizar los otros bloques. La línea compartida ayuda a reducir las transacciones de memoria y bus en algunos casos en los que el bloque está disponible en un solo caché y, por lo tanto, no se requiere una actualización de bus. Esta línea dedicada para detectar el intercambio se ve a través de protocolos de actualización de escritura, como el protocolo Firefly, y se implementa en base a estándares de bus como Futurebus (estándar IEEE P896.1). ^[2]

Transiciones

Protocolo Dragon: transacciones iniciadas por el procesador

Transiciones iniciadas por el procesador

Según el estado actual del bloque y la transacción iniciada por el procesador, el bloque de caché experimenta una de las siguientes transiciones de estado:

• Cuando se produce un error de lectura del procesador ( PrRdMiss ) y el bloque de caché no se comparte, el estado cambia a Exclusivo
• Cuando se produce un error de lectura del procesador ( PrRdMiss ) y se comparte el bloque de caché, el estado cambia al estado Shared Clean
• Cuando se produce un error de escritura del procesador ( PrWrMiss ) y se comparte el bloque de caché, el estado cambia a Shared Modified y el procesador se convierte en propietario.
• Cuando se produce un error de escritura del procesador ( PrWrMiss ) y el bloque de caché no se comparte, el estado cambia a Modificado
• Cuando hay un golpe de lectura del procesador ( PrRd ), el estado del bloque de caché no cambia y conserva el valor. Esto se debe a que es solo un comando de lectura y no genera ninguna transacción de bus.
• Si el bloque de caché está en el estado Modificado y el procesador escribe ( PrWr ) el bloque, no hay transición ya que el bloque no se comparte.
• Cuando el bloque de caché está en el estado Modificado Compartido y un procesador escribe ( PrWr ), pero la línea compartida no está confirmada , el estado cambia a Modificado .
• Si el bloque de caché está en el estado Shared Modified cuando se produce una escritura ( PrWr ) y se afirma la línea compartida, se genera una actualización de bus ( BusUpd ) para actualizar el otro bloque de caché.
• Si el bloque de caché está en el estado Shared Clean cuando se produce una escritura ( PrWr ) y se afirma la línea compartida, se genera una actualización de bus ( BusUpd ) para actualizar el otro bloque de caché y el estado cambia a Shared Modified .
• Pero si el bloque de caché está en el estado Shared Clean cuando se produce una escritura ( PrWr ), pero la línea compartida no se afirma, el estado cambia a Modified y no se generan transacciones de bus.
• Cuando el bloque está en estado exclusivo y el procesador escribe ( PrWr ) en él, se cambiará al estado modificado .

Protocolo Dragon: transacciones iniciadas por bus

Transiciones iniciadas por bus

Según el estado actual del bloque y la transacción iniciada por el bus, el bloque de caché experimenta una de las siguientes transiciones de estado:

• Si el bloque de caché está en Modificado y se emite una lectura de bus ( BusRd ), se emite un Flush para actualizar la memoria principal y el estado cambia a Shared Modified , ya que el bloque ahora está en múltiples cachés.
• Si el bloque de caché se encuentra en el estado Shared Modified y una lectura de bus ( BusRd ), se emite un Flush para actualizar la memoria principal y el estado sigue siendo el mismo.
• Si el bloque de caché está en estado Shared Modified y se emite una transacción de actualización de bus ( BusUpd ), el estado cambia a Shared Clean y se actualizan todas las cachés.
• Si el bloque de caché está en estado Shared Clean y recibe una lectura de bus ( BusRd ) o una actualización de bus ( BusUpd ), continúa reteniendo su estado ya que el valor aún se comparte. Sin embargo, en el caso de una actualización, actualizará el valor en el bloque de caché.
• Si el bloque de caché está en el estado exclusivo y el bus lee el valor ( BusRd ), el estado pasará a Shared Clean, ya que el bloque ya no reside solo en un caché.

Opciones de diseño de bajo nivel

Eliminación del estado modificado compartido

El procesador con el bloque de caché en estado Sm es responsable de actualizar la memoria cuando se reemplaza el bloque de caché. Pero si la memoria principal se actualiza cada vez que se produce una transacción de actualización del bus, no hay necesidad de estados Sm y Sc separados, y el protocolo puede permitirse un solo estado compartido. Sin embargo, esto provoca muchas más transacciones de memoria ^[3] que pueden ralentizar el sistema, especialmente cuando varios procesadores escriben en el mismo bloque de caché.

Transmitiendo el reemplazo del bloque Sc

El protocolo permite que los bloques de caché en el estado Sc se reemplacen silenciosamente sin ninguna actividad de bus. Si se realizó una transmisión para que otros cachés sepan que se está reemplazando un bloque Sc, podrían probar la línea compartida y pasar al estado E si no hubiera otros compartidores. La ventaja de tener un bloque en el estado E es que si el bloque se escribe más tarde, pasa al estado M y no es necesario generar una transacción de actualización del bus. Entonces, a costa de transmitir los reemplazos de bloques Sc, podemos evitar transacciones de actualización de bus. Y dado que la transmisión de reemplazos no es un factor crítico en el tiempo, si no se requiere un caché para procesar el reemplazo de inmediato, no hay inconvenientes. Por otro lado, si un caché no procesa una actualización de inmediato, puede dar lugar a actualizaciones fuera de servicio. En tales casos, un protocolo de actualización de tres estados, como elEl protocolo Firefly puede tener ventajas de rendimiento.

Comparaciones

Protocolos de invalidación de Dragon vs Write

Write Invalidate es otro conjunto de protocolos de coherencia de caché , donde una vez que se modifica un bloque de caché, los otros valores del mismo bloque en otras cachés no se actualizan, sino que se invalidan. ^[4]Los protocolos de invalidación de escritura son más eficientes en los casos en los que hay muchas escrituras posteriores en el mismo bloque de caché, ya que la invalidación ocurre una vez y se evitan más transacciones de bus de otros procesadores. Sin embargo, el protocolo de actualización de escritura es más eficiente en los casos en los que una escritura en un bloque va seguida de varias lecturas en el mismo bloque. Dado que estamos actualizando los otros valores almacenados en caché una vez que los escribimos, tienen acceso a los datos de inmediato. En cuyo caso. el protocolo de invalidación de escritura es muy desventajoso porque cada vez que se modifica un bloque de caché en otro caché, el resto de los cachés necesarios encontrarán una falta de coherenciae inicie una transacción de bus para leer el nuevo valor. Por el contrario, el protocolo de actualización de escritura tiende, en ocasiones, a mantener actualizados los valores del bloque durante más tiempo del necesario, lo que conducirá a un aumento de otros tipos de fallos, es decir, conflictos y fallos de capacidad .

Protocolo Dragon vs Firefly

En el caso de Firefly , las transferencias de caché a caché de bloques modificados también se vuelven a escribir en la memoria principal al mismo tiempo. Pero dado que los accesos realizados a la memoria principal son más lentos por órdenes de magnitud en comparación con los cachés, requiere una complejidad adicional para realizar una escritura como una operación de bus separada. En cualquier caso, se traduce en un menor rendimiento. ^[5] Este problema se evita por completo en el caso del protocolo Dragon, ya que los bloques compartidos no se vuelven a escribir en la memoria en absoluto. Sin embargo, esto tiene el costo de un estado adicional (modificado compartido).

Referencias

1. Atkinson, Russell R .; McCreight, Edward M. (1 de enero de 1987). El Procesador Dragón . Actas de la Segunda Conferencia Internacional sobre Soporte Arquitectónico para Lenguajes de Programación y Sistemas Operativos . ASPLOS II. Los Alamitos, CA, EE.UU .: IEEE Computer Society Press. págs. 65–69. doi : 10.1145 / 36206.36185 (inactivo el 31 de mayo de 2021). ISBN 978-0818608056.
2. Stenström, Per (1 de junio de 1990). "Una encuesta de esquemas de coherencia de caché para multiprocesadores". Computadora . 23 (6): 12-24. doi : 10.1109 / 2.55497 . ISSN 0018-9162 . 
3. Culler, David; Singh, Jaswinder Pal; Gupta, Anoop (1999). Arquitectura informática paralela, 1ª edición | David Culler, Jaswinder Pal Singh y Anoop Gupta | . store.elsevier.com . ISBN 9781558603431. Consultado el 24 de octubre de 2016 .
4. Solihin, Yan (2015). Fundamentos de la arquitectura multinúcleo paralela . Chapman y Hall / CRC. págs. 205–206, 231–232. ISBN 9781482211184.
5. Archibald, James; Baer, ​​Jean-Loup (1 de septiembre de 1986). "Protocolos de coherencia de caché: evaluación mediante un modelo de simulación multiprocesador". ACM Trans. Computación. Syst . 4 (4): 273-298. doi : 10.1145 / 6513.6514 . ISSN 0734-2071 . S2CID 713808 .  

Ver también

• Protocolo de coherencia
• Protocolo de luciérnaga
• Protocolo MESI
• Protocolo MOSI
• Protocolo MOESI
• Protocolo MESIF