Protocolo MESI

El protocolo MESI es un protocolo de coherencia de caché basado en invalidación y es uno de los protocolos más comunes que admiten cachés de escritura diferida . También se le conoce como protocolo Illinois debido a su desarrollo en la Universidad de Illinois en Urbana-Champaign . ^{[ 1 ]} Las cachés de escritura diferida pueden ahorrar un ancho de banda considerable que generalmente se desperdicia en una caché de escritura directa . Siempre hay un estado de modificación presente en las cachés de escritura diferida que indica que los datos en la caché son diferentes de los de la memoria principal. El protocolo Illinois requiere una transferencia de caché a caché en caso de fallo si el bloque reside en otra caché. Este protocolo reduce el número de transacciones de memoria principal con respecto al protocolo MSI . Esto marca una mejora significativa en el rendimiento. ^{[ 2 ]}

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

Modificado (M)

La línea de caché solo está presente en la caché actual y está modificada (estado M) respecto al valor de la memoria principal . La caché debe escribir los datos de vuelta a la memoria principal en algún momento futuro, antes de permitir cualquier otra lectura del estado de la memoria principal (que ya no es válido). La escritura de los datos cambia la línea al estado Compartido (S).

Exclusivo (E)

La línea de caché solo está presente en la caché actual, pero está limpia ; coincide con la memoria principal. Puede cambiar al estado Compartido en cualquier momento, en respuesta a una solicitud de lectura. Alternativamente, puede cambiar al estado Modificado al escribir en ella.

Compartido (S)

Indica que esta línea de caché puede almacenarse en otras cachés de la máquina y está limpia ; coincide con la memoria principal. La línea puede descartarse (cambiar al estado Inválido) en cualquier momento.

Inválido (I)

Indica que esta línea de caché no es válida (no se utiliza).

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

Cuando el bloque está marcado como M (modificado) o E (exclusivo), las copias del bloque en otras cachés se marcan como I (inválidas).

El protocolo MESI se define mediante una máquina de estados finitos que transita de un estado a otro en función de dos 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 recibe una solicitud para leer o escribir en ese bloque.

El segundo estímulo se proporciona a través del bus que conecta los procesadores. En particular, las "solicitudes del lado del bus" provienen de otros procesadores que no tienen el bloque de caché ni los datos actualizados en su caché. Las solicitudes del bus se supervisan con la ayuda de Snoopers ^{[ 4 ]} , que monitorean todas las transacciones del bus.

A continuación se detallan los diferentes tipos de solicitudes del procesador y solicitudes del lado del bus:

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

1. PrRd: El procesador solicita leer un bloque de caché.
2. PrWr: El procesador solicita escribir un bloque de caché.

Las solicitudes que se pueden realizar en la parada del autobús son las siguientes:

1. BusRd: Solicitud interceptada que indica que hay una solicitud de lectura a un bloque de caché solicitada por otro procesador.
2. BusRdX: Solicitud interceptada que indica que hay una solicitud de escritura en un bloque de caché solicitada por otro procesador que aún no tiene el bloque.
3. BusUpgr: Solicitud interceptada que indica que hay una solicitud de escritura a un bloque de caché solicitada por otro procesador que ya tiene ese bloque de caché residiendo en su propia caché .
4. Flush: Solicitud interceptada que indica que otro procesador escribe un bloque de caché completo de vuelta a la memoria principal.
5. FlushOpt: Solicitud interceptada que indica que se publica un bloque de caché completo en el bus para suministrarlo a otro procesador (transferencias de caché a caché).

( Estas transferencias de caché a caché pueden reducir la latencia de fallo de lectura si la latencia para recuperar el bloque de la memoria principal es mayor que la de las transferencias de caché a caché, lo cual suele ser el caso en los sistemas basados ​​en bus ) .

Operación de espionaje : En un sistema de espionaje, todas las cachés de un bus supervisan todas las transacciones en dicho bus. Cada caché tiene una copia del estado de compartición de cada bloque de memoria física que almacena. El estado del bloque cambia según el diagrama de estados del protocolo utilizado. (Consulte la imagen superior para ver el diagrama de estados MESI). El bus cuenta con espionaje en ambos extremos.

1. Espía hacia el lado del procesador/caché.
2. La función de espionaje en el lado de la memoria la realiza el controlador de memoria .

Explicación:

Cada bloque de caché tiene su propia máquina de estados finitos de 4 estados (véase 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.

La 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é. Esto se suele hacer mediante una operación de difusión conocida como Solicitud de Propiedad (RFO) .

Una caché que mantiene una línea en estado Modificado debe interceptar todos los intentos de lectura (desde todas las demás cachés del sistema) de la ubicación correspondiente en la memoria principal e insertar los datos que contiene. Esto se puede lograr forzando la lectura a retroceder (es decir, reintentándola más tarde), escribiendo los datos en la memoria principal y cambiando la línea de caché al estado Compartido. También se puede lograr enviando datos desde la caché Modificada a la caché que realiza la lectura. Cabe destacar que la interceptación solo es necesaria para los fallos de lectura (el protocolo garantiza que la caché Modificada no pueda existir si alguna otra caché puede realizar una lectura exitosa).

Una caché que mantiene una línea en estado Compartido debe estar atenta a las transmisiones de invalidación o de solicitud de propiedad de otras cachés, y descartar la línea (cambiándola a estado Inválido) cuando se produzca una coincidencia.

Los estados Modificado y Exclusivo siempre son precisos: es decir, coinciden con la situación real de propiedad de las líneas de caché en el sistema. El estado Compartido puede ser impreciso: si otra caché descarta una línea compartida, esta caché puede convertirse en la única propietaria de esa línea, pero no pasará al estado Exclusivo. Otras cachés no emiten notificaciones cuando descartan líneas de caché, y esta caché no podría utilizar 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 quiere modificar una línea de caché en el estado S, es necesaria una transacción de bus para invalidar todas las demás copias almacenadas 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

Por ejemplo, supongamos que la siguiente secuencia de referencias de lectura/escritura. Todas las referencias apuntan 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.

Inicialmente se asume que todas las cachés están vacías.

Nota: El término "snooping" al que se hace referencia a continuación es un protocolo para mantener la coherencia de la caché en entornos de multiprocesamiento simétrico. Todas las cachés del bus monitorizan (snoop) el bus para comprobar si disponen de una copia del bloque de datos solicitado.

• Paso 1: Como la caché está inicialmente vacía, la memoria principal proporciona a P1 el bloque y este pasa a un estado exclusivo.
• Paso 2: Como el bloque ya está presente en la caché y en estado exclusivo, lo modifica directamente sin ninguna instrucción de bus. El bloque ahora está en estado modificado.
• Paso 3: En este paso, se publica un BusRd en el bus y el snooper en P1 lo detecta. A continuación, vacía la memoria caché y cambia su estado a compartido. El bloque en P3 también cambia su estado a compartido, ya que ha recibido datos de otra caché. Los datos también se escriben de nuevo en la memoria principal.
• Paso 4: Aquí se publica un BusUpgr en el bus y el snooper en P1 lo detecta e invalida el bloque, ya que va a ser modificado por otra caché. Luego, P3 cambia el estado de su bloque a modificado.
• Paso 5: Dado que el estado actual no es válido, se enviará un mensaje BusRd al bus. El snooper en P3 lo detectará y borrará los datos. El estado de ambos bloques en P1 y P3 se compartirá. Cabe destacar que en este momento la memoria principal también se actualizará con los datos modificados previamente.
• Paso 6: Hay una coincidencia en la caché y está en estado compartido, por lo que no se realiza ninguna solicitud de bus aquí.
• Paso 7: Se produce un fallo de caché en P2 y se publica un BusRd. Los snoopers en P1 y P3 lo detectan e intentan vaciar el bus. El que acceda primero al bus realizará la operación.

La diferencia más notable entre MESI y MSI radica en el estado "exclusivo" adicional presente en el protocolo MESI. Este estado se añadió debido a sus numerosas ventajas. Cuando un procesador necesita leer un bloque al que ningún otro procesador tiene acceso y luego escribir en él, en el caso de MSI se producen dos transacciones de bus. Primero, se emite una solicitud BusRd para leer el bloque, seguida de una solicitud BusUpgr antes de escribir en él. La solicitud BusUpgr en este escenario resulta inútil, ya que ninguna de las otras cachés tiene el mismo bloque, pero no hay forma de que una caché lo sepa. Por lo tanto, el protocolo MESI supera esta limitación añadiendo un estado exclusivo, lo que permite ahorrar una solicitud de bus. Esto supone una gran diferencia cuando se ejecuta una aplicación secuencial. Dado que solo un procesador trabaja con un fragmento de datos, todos los accesos serán exclusivos. En este caso, el rendimiento de MSI es mucho peor debido a los mensajes de bus adicionales. Incluso en el caso de una aplicación altamente paralela con un mínimo intercambio de datos, MESI es mucho más rápido. Agregar el estado exclusivo tampoco tiene costo, ya que tanto 3 como 4 estados se pueden representar con 2 bits.

En caso de que varias cachés realicen operaciones continuas de lectura y escritura en un bloque específico, los datos deben volcarse al bus cada vez. Por lo tanto, la memoria principal los recuperará en cada vaciado y permanecerá en un estado limpio. Sin embargo, esto no es un requisito y solo representa una sobrecarga adicional causada por el uso de MESI. Este problema se superó con el protocolo MOESI . ^{[ 7 ]}

En el caso de S (estado compartido), varios snoopers pueden responder con FlushOpt con los mismos datos (véase el ejemplo anterior). El estado F en MESIF soluciona esta redundancia.

• Protocolo de coherencia
• Protocolo MSI , el protocolo básico del que se deriva el protocolo MESI.
• Escritura única (coherencia de caché) , una forma temprana del protocolo MESI.
• Protocolo MOSI
• Protocolo MOESI
• Protocolo MESIF
• Protocolo MERSI
• Protocolo del dragón
• Protocolo de luciérnagas

• Una simulación interactiva de MESI
• Un controlador MESI de código abierto (Verilog)