Protocolo MESI

El protocolo MESI es un protocolo de coherencia de caché basado en Invalidate, y es uno de los protocolos más comunes que admiten cachés de reescritura. También se conoce como el protocolo de Illinois (debido a su desarrollo en la Universidad de Illinois en Urbana-Champaign). Las cachés de reescritura pueden ahorrar una gran cantidad de ancho de banda que generalmente se desperdicia en una caché de escritura directa. Siempre hay un estado sucio presente en los cachés de reescritura que indica que los datos en el caché son diferentes de los de la memoria principal. El Protocolo de Illinois requiere una transferencia de caché a caché en caso de error si el bloque reside en otro caché. Este protocolo reduce el número de transacciones de la memoria principal con respecto al protocolo MSI. Esto marca una mejora significativa en el rendimiento.

Estados

Las letras del acrónimo MESI representan cuatro estados exclusivos con los que se puede marcar una línea de caché (codificada con dos bits adicionales):

Modificado (M)

La línea de caché está presente sólo en el caché actual, y es sucio - ha sido modificado (Estado M) del valor en la memoria principal. El caché se requiere para escribir los datos de nuevo a la memoria principal en algún momento en el futuro, antes de permitir cualquier otra lectura del estado de memoria principal (ya no válido). El revés cambia la línea al estado compartido (S).

Exclusivo (E)

La línea de caché está presente sólo en el caché actual, pero es limpio - coincide con la memoria principal. Puede cambiarse al estado compartido en cualquier momento, en respuesta a una solicitud de lectura. Alternativamente, puede ser cambiado al estado Modificado al escribirlo.

Compartida (S)

Indica que esta línea de caché puede almacenarse en otros caches de la máquina y es limpio - coincide con la memoria principal. La línea puede ser descartada (cambiada al estado Inválido) en cualquier momento.

Inválidos (I)

Indica que esta línea de caché es inválida (no utilizada).

Para cualquier par de cachés, los estados permitidos de una línea de caché determinada son los siguientes:

	M	E	S	I
M	N	N	N	Y
E	N	N	N	Y
S	N	N	Y	Y
I	Y	Y	Y	Y

Cuando el bloque se marca M (modificado) o E (exclusivo), las copias del bloque en otros Cachés se marcan como I (No válido).

Operación

El protocolo MESI está definido por una máquina de estados finitos que pasa de un estado a otro en función de 2 estímulos.

El primer estímulo es la solicitud de lectura y escritura específica del procesador. Por ejemplo: un procesador P1 tiene un bloque X en su caché y hay una solicitud del procesador para leer o escribir desde ese bloque.

El segundo estímulo se da a través del bus que conecta los procesadores. En particular, las "Solicitudes del lado del autobús" provienen de otros procesadores que no tienen el bloque de caché o los datos actualizados en su Caché. Las solicitudes de autobús se monitorean con la ayuda de Snoopers, que monitorean todas las transacciones de autobús.

Los siguientes son los diferentes tipos de solicitudes del procesador y solicitudes del lado del bus:

Las solicitudes del procesador a la memoria caché incluyen las siguientes operaciones:

1. PrRd: El procesador solicita leído un bloque Cache.
2. PrWr: El procesador solicita escribir un bloque de caché

Las solicitudes del lado del autobús son las siguientes:

1. BusRd: Solicitud sinoped que indica que hay un leído solicitar un bloque Cache solicitado por otro procesador
2. BusRdX: Solicitud sinoped que indica que hay un escribir solicitar un bloque Cache solicitado por otro procesador que no tiene el bloque.
3. BusUpgr: Solicitud sinoped que indica que hay una solicitud de escritura a un bloque Cache solicitada por otro procesador que ya tiene que bloque de caché que reside en su propio cache.
4. Flush: Soplado petición que indica que un bloque de caché entero está escrito de vuelta a la memoria principal por otro procesador.
5. FlushOpt: Solicitud sofocada que indica que un bloque de caché entero está colocado en el autobús para suministrarlo a otro procesador (Cache to Cache transfers).

(Tales transferencias de caché a caché pueden reducir la latencia de errores de lectura si la latencia para traer el bloque desde la memoria principal es mayor que las transferencias de caché a caché, lo que suele ser el caso en los sistemas basados en bus. Pero en arquitecturas multinúcleo, donde la coherencia se mantiene al nivel de las cachés L2, hay una caché L3 en el chip, puede ser más rápido recuperar el bloque perdido de la caché L3 en lugar de otra L2)

Operación de indagación: en un sistema de indagación, todos los cachés en un bus monitorean todas las transacciones en ese bus. Cada caché tiene una copia del estado de uso compartido de cada bloque de memoria física que ha almacenado. El estado del bloque se cambia de acuerdo con el diagrama de estado del protocolo utilizado. (Consulte la imagen de arriba para el diagrama de estado MESI). El autobús tiene fisgones en ambos lados:

1. Snooper hacia el lado Procesador/Cache.
2. La función de snooping en el lado de memoria es hecha por el controlador de memoria.

Explicación:

Cada bloque de caché tiene su propia máquina de estado finito de 4 estados (consulte la imagen 1.1). Las transiciones de estado y las respuestas en un estado particular con respecto a diferentes entradas se muestran en la Tabla 1.1 y la Tabla 1.2

Una escritura solo se puede realizar libremente si la línea de caché está en estado Modificado o Exclusivo. Si está en estado Compartido, primero se deben invalidar todas las demás copias almacenadas en caché. Normalmente, esto se realiza mediante una operación de transmisión conocida como Solicitud de propiedad (RFO).

Un caché que contiene una línea en el estado Modificado debe fisgonear (interceptar) todos los intentos de lectura (de todos los demás cachés del sistema) de la ubicación de memoria principal correspondiente e insertar los datos que contiene. sostiene Esto se puede hacer forzando la lectura a retroceder (es decir, volver a intentarlo más tarde), luego escribiendo los datos en la memoria principal y cambiando la línea de caché al estado Compartido. También se puede hacer enviando datos desde la memoria caché modificada a la memoria caché que realiza la lectura. Tenga en cuenta que la indagación solo es necesaria para los errores de lectura (el protocolo garantiza que Modificado no puede existir si cualquier otro caché puede realizar un acierto de lectura).

Un caché que contiene una línea en el estado Compartido debe escuchar transmisiones invalidadas o de solicitud de propiedad de otros cachés y descartar la línea (moviéndola al estado Inválido) en una coincidencia.

Los estados Modificado y Exclusivo siempre son precisos: es decir, coinciden con la verdadera situación de propiedad de la línea de caché en el sistema. El estado Compartido puede ser impreciso: si otro caché descarta una línea Compartida, este caché puede convertirse en el único propietario de esa línea de caché, pero no se promoverá al estado Exclusivo. Otros cachés no transmiten avisos cuando descartan líneas de caché, y este caché no podría usar dichas notificaciones sin mantener un recuento del número de copias compartidas.

En ese sentido, el estado Exclusivo es una optimización oportunista: si la CPU desea modificar una línea de caché en el estado S, es necesaria una transacción de bus para invalidar todas las demás copias en caché. El estado E permite modificar una línea de caché sin transacción de bus.

Ilustración de las operaciones del protocolo MESI

Supongamos que el siguiente flujo de referencias de lectura/escritura. Todas las referencias corresponden a la misma ubicación y el dígito se refiere al procesador que emite la referencia.

La secuencia es: R1, W1, R3, W3, R1, R3, R2.

Al principio, se supone que todos los cachés están vacíos.

Nota: El término snooping al que se hace referencia a continuación es un protocolo para mantener la coherencia de la memoria caché en entornos de multiprocesamiento simétrico. Todos los cachés en el bus monitorean (fisgonean) el bus si tienen una copia del bloque de datos que se solicita en el bus.

• Paso 1: Como el caché está inicialmente vacío, por lo que la memoria principal proporciona P1 con el bloque y se convierte en estado exclusivo.
• Paso 2: Como el bloque ya está presente en el caché y en un estado exclusivo por lo que modifica directamente que sin ninguna instrucción de autobús. El bloque está ahora en un estado modificado.
• Paso 3: En este paso, un BusRd se publica en el autobús y el snooper en P1 siente esto. Luego cambia los datos y cambia su estado para compartir. El bloque en P3 también cambia su estado para compartir ya que ha recibido datos de otro caché. Los datos también se escriben de nuevo a la memoria principal.
• Paso 4: Aquí un BusUpgr se publica en el autobús y el snooper en P1 siente esto e invalida el bloque ya que va a ser modificado por otro caché. P3 entonces cambia su estado de bloque para modificar.
• Paso 5: Como el estado actual es inválido, por lo tanto, colocará un BusRd en el autobús. El snooper en P3 se dará cuenta de esto y así eliminará los datos. El estado de ambos bloques en P1 y P3 se compartirá ahora. Observe que esto es cuando incluso la memoria principal se actualizará con los datos previamente modificados.
• Paso 6: Hay un éxito en el caché y está en el estado compartido por lo que no se hace ninguna solicitud de autobús aquí.
• Paso 7: Hay falta de caché en P2 y un BusRd es publicado. El snooper en P1 y P3 siente esto y ambos intentarán una descarga. Cualquiera que tenga acceso al autobús primero hará esa operación.

Leer para propiedad

Una lectura para propiedad (RFO) es una operación en los protocolos de coherencia de caché que combina una transmisión de lectura y de invalidación. La operación es emitida por un procesador que intenta escribir en una línea de caché que se encuentra en los estados compartido (S) o no válido (I) del protocolo MESI. La operación hace que todas las demás cachés establezcan el estado de dicha línea en I. Una transacción de lectura para propiedad es una operación de lectura con la intención de escribir en esa dirección de memoria. Por lo tanto, esta operación es excluyente. Trae datos a la memoria caché e invalida todas las demás memorias caché del procesador que contienen esta línea de memoria. Esto se denomina "BusRdX" en las tablas de arriba.

Barreras de memoria

MESI en su implementación simple e ingenua presenta dos problemas de rendimiento particulares. En primer lugar, cuando se escribe en una línea de caché no válida, hay una gran demora mientras la línea se obtiene de otras CPU. En segundo lugar, mover las líneas de caché al estado no válido lleva mucho tiempo. Para mitigar estos retrasos, las CPU implementan búferes de almacenamiento e invalidan colas.

Almacenar búfer

Se utiliza un búfer de almacenamiento cuando se escribe en una línea de caché no válida. Como la escritura continuará de todos modos, la CPU emite un mensaje de lectura no válida (por lo tanto, la línea de caché en cuestión y todas las demás líneas de caché de la CPU que almacenan esa dirección de memoria se invalidan) y luego empuja la escritura en el búfer de almacenamiento, para se ejecutará cuando la línea de caché finalmente llegue a la memoria caché.

Una consecuencia directa de la existencia del búfer de almacenamiento es que cuando una CPU realiza una escritura, esa escritura no se escribe inmediatamente en la memoria caché. Por lo tanto, cada vez que una CPU necesita leer una línea de caché, primero escanea su propio búfer de almacenamiento en busca de la existencia de la misma línea, ya que existe la posibilidad de que la misma CPU haya escrito la misma línea antes pero aún no lo haya hecho. sido escrito en el caché (la escritura anterior todavía está esperando en el búfer de almacenamiento). Tenga en cuenta que, si bien una CPU puede leer sus propias escrituras anteriores en su búfer de almacenamiento, otras CPU no pueden ver esas escrituras hasta que se vacían en el caché; una CPU no puede escanear el búfer de almacenamiento de otras CPU.

Invalidar colas

Con respecto a los mensajes de invalidación, las CPU implementan colas de invalidación, mediante las cuales las solicitudes de invalidación entrantes se reconocen instantáneamente, pero no se actúa de inmediato. En su lugar, los mensajes de invalidación simplemente ingresan a una cola de invalidación y su procesamiento ocurre lo antes posible (pero no necesariamente de manera instantánea). En consecuencia, una CPU puede ignorar el hecho de que una línea de caché en su caché en realidad no es válida, ya que la cola de invalidación contiene invalidaciones que se han recibido pero que aún no se han aplicado. Tenga en cuenta que, a diferencia del búfer de almacenamiento, la CPU no puede escanear la cola de invalidación, ya que la CPU y la cola de invalidación están ubicadas físicamente en lados opuestos de la memoria caché.

Como resultado, se requieren barreras de memoria. Una barrera de almacenamiento vaciará el búfer de almacenamiento, asegurando que todas las escrituras se hayan aplicado a la memoria caché de esa CPU. Una barrera de lectura vaciará la cola de invalidación, lo que garantizará que todas las escrituras de otras CPU sean visibles para la CPU que va a vaciar. Además, las unidades de gestión de memoria no exploran el búfer de almacenamiento, lo que provoca problemas similares. Este efecto es visible incluso en procesadores de un solo subproceso.

Ventajas de MESI sobre MSI

La diferencia más llamativa entre MESI y MSI es el "exclusivo" estado presente en el protocolo MESI. Este estado adicional se agregó ya que tiene muchas ventajas. Cuando un procesador necesita leer un bloque que ninguno de los otros procesadores tiene y luego escribir en él, se realizarán dos transacciones de bus en el caso de MSI. Primero, se emite una solicitud BusRd para leer el bloque seguida de una solicitud BusUpgr antes de escribir en el bloque. La solicitud de BusRdX en este escenario es inútil ya que ninguno de los otros cachés tiene el mismo bloque, pero no hay forma de que un caché sepa sobre esto. Por lo tanto, el protocolo MESI supera esta limitación al agregar un estado Exclusivo, lo que da como resultado guardar una solicitud de bus. Esto marca una gran diferencia cuando se ejecuta una aplicación secuencial. Como solo un procesador trabaja sobre un dato, todos los accesos serán exclusivos. MSI funciona mucho peor en este caso debido a los mensajes de bus adicionales. Incluso en el caso de una aplicación altamente paralela con un intercambio mínimo de datos, MESI es mucho más rápido. Agregar el estado Exclusivo tampoco tiene costo, ya que 3 estados y 4 estados se pueden representar con 2 bits.

Desventaja de MESI

En caso de que varios cachés realicen operaciones continuas de lectura y escritura en un bloque en particular, los datos deben vaciarse en el bus cada vez. Por lo tanto, la memoria principal extraerá esto en cada descarga y permanecerá en un estado limpio. Pero esto no es un requisito y es solo una sobrecarga adicional causada por el uso de MESI. Este desafío fue superado por el protocolo MOESI.

En el caso de S (estado compartido), varios intrusos pueden responder con FlushOpt con los mismos datos (consulte el ejemplo anterior). El estado F en MESIF aborda esta redundancia.