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 lo conoce como protocolo de Illinois debido a su desarrollo en la Universidad de Illinois en Urbana-Champaign . [1] Los cachés de escritura diferida pueden ahorrar un ancho de banda considerable que generalmente se desperdicia en un caché de escritura directa . Siempre hay un estado sucio presente en los cachés de escritura diferida 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 falla si el bloque reside en otra caché. Este protocolo reduce la cantidad 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 ):
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 otros cachés se marcan como I (inválido).
El protocolo MESI está definido por una máquina de estados finitos que pasa 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 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 bus" provienen de otros procesadores que no tienen el bloque de caché o los datos actualizados en su caché. Las solicitudes del bus se monitorean con la ayuda de Snoopers [4] , que monitorean todas las transacciones del bus.
A continuación se muestran los diferentes tipos de solicitudes del procesador y solicitudes del lado del bus:
Las solicitudes del procesador al caché incluyen las siguientes operaciones:
Las solicitudes del lado del autobús son las siguientes:
( Estas transferencias de caché a caché pueden reducir la latencia de error de lectura si la latencia para traer el bloque desde la memoria principal es mayor que la de las transferencias de caché a caché, lo que generalmente es el caso en los sistemas basados en bus ) .
Operación de espionaje : en un sistema de espionaje, todos los cachés de 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 modifica de acuerdo con el diagrama de estado del protocolo utilizado. (Consulte la imagen anterior para ver el diagrama de estado de MESI). El bus tiene espías en ambos lados:
Explicación:
Cada bloque de caché tiene su propia máquina de estados finitos 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.
Solo se puede realizar una escritura libremente si la línea de caché está en estado Modificado o Exclusivo. Si está en estado Compartido, todas las demás copias almacenadas en caché deben invalidarse primero. Esto se realiza normalmente mediante una operación de difusión conocida como Solicitud de propiedad (RFO) .
Una caché que contiene una línea en el estado Modificado debe 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. Esto se puede hacer forzando la lectura a retroceder (es decir, reintentar más tarde), luego escribir los datos en la memoria principal y cambiar la línea de caché al estado Compartido. También se puede hacer enviando datos desde la caché Modificada a la caché que realiza la lectura. Tenga en cuenta que el espionaje solo es necesario para errores de lectura (el protocolo garantiza que Modificado no puede existir si cualquier otra caché puede realizar un acierto de lectura).
Un caché que contiene una línea en el estado Compartido debe escuchar transmisiones de invalidación o solicitud de propiedad de otros cachés y descartar la línea (moviéndola al estado Inválido) en caso de una coincidencia.
Los estados Modificado y Exclusivo son siempre precisos: es decir, coinciden con la situación real 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 será promovido 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 de la cantidad 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 almacenadas en caché. El estado E permite modificar una línea de caché sin ninguna transacción de bus.
Ilustración del funcionamiento del protocolo MESI
Por ejemplo, supongamos que el siguiente flujo de referencias de lectura/escritura. Todas las referencias son a la misma ubicación y el dígito se refiere al procesador que emite la referencia.
La corriente es: R1, W1, R3, W3, R1, R3, R2.
Inicialmente 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. Todas las memorias caché del bus monitorean (snoopean) el bus para ver si tienen una copia del bloque de datos que se solicita en el bus.
Una lectura para propiedad (RFO) es una operación en los protocolos de coherencia de caché que combina una lectura y una transmisión de invalidación. La operación la emite 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 todos los 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 exclusiva. Lleva datos a la caché e invalida todos los demás cachés de procesador que contienen esta línea de memoria. Esto se denomina "BusRdX" en las tablas anteriores.
En su implementación sencilla e ingenua, MESI presenta dos problemas de rendimiento particulares. En primer lugar, cuando se escribe en una línea de caché no válida, hay una demora prolongada mientras se obtiene la línea de otras CPU. En segundo lugar, mover las líneas de caché al estado no válido requiere mucho tiempo. Para mitigar estas demoras, las CPU implementan búferes de almacenamiento y colas de invalidación. [5]
Se utiliza un búfer de almacenamiento cuando se escribe en una línea de caché no válida. Como la escritura se realizará 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 las CPU que almacenan esa dirección de memoria quedan invalidadas) y luego envía la escritura al búfer de almacenamiento para que se ejecute 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 caché. Por lo tanto, siempre 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 línea haya sido escrita por la misma CPU antes, pero que aún no se haya escrito en la caché (la escritura anterior aún 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 la caché; una CPU no puede escanear el búfer de almacenamiento de otras CPU.
En lo que respecta 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 inmediatamente sobre ellas. En cambio, los mensajes de invalidación simplemente ingresan a una cola de invalidación y su procesamiento se produce 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 esa CPU y la cola de invalidación están ubicadas físicamente en lados opuestos de la caché.
Como resultado, se requieren barreras de memoria. Una barrera de almacenamiento limpiará el búfer de almacenamiento, lo que garantiza que todas las escrituras se hayan aplicado a la memoria caché de esa CPU. Una barrera de lectura limpiará la cola de invalidación, lo que garantiza que todas las escrituras de otras CPU sean visibles para la CPU que realiza la limpieza. Además, las unidades de gestión de memoria no escanean el búfer de almacenamiento, lo que provoca problemas similares. Este efecto es visible incluso en procesadores de un solo subproceso. [6]
La diferencia más llamativa entre MESI y MSI es el estado "exclusivo" adicional presente en el protocolo MESI. Este estado adicional se agregó porque 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 BusRdX para leer el bloque seguida de una solicitud BusUpgr antes de escribir en el bloque. La solicitud 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é lo sepa. Por lo tanto, el protocolo MESI supera esta limitación agregando un estado exclusivo, lo que da como resultado guardar una solicitud de bus. Esto hace una gran diferencia cuando se ejecuta una aplicación secuencial. Como solo un procesador trabaja en una pieza de datos, todos los accesos serán exclusivos. MSI tiene un rendimiento 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.
En caso de que varias cachés realicen operaciones de lectura y escritura continuas en un bloque en particular, los datos deben volcarse al bus cada vez. Por lo tanto, la memoria principal los extraerá en cada vaciado 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 . [7]
En el caso de S (estado compartido), varios espías pueden responder con FlushOpt con los mismos datos (consulte el ejemplo anterior). El estado F en MESIF soluciona esta redundancia.
{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )