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 conoce como el protocolo de Illinois (debido a su desarrollo en la Universidad de Illinois en Urbana-Champaign [1] ). Los cachés de escritura diferida pueden ahorrar mucho ancho de banda que generalmente se desperdicia en un caché de escritura a través. Siempre hay un estado sucio 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 de Illinois requiere un caché para transferir en 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. [2]
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 solo en la caché actual y está sucia ; se ha modificado (estado M) del valor en la memoria principal . Se requiere que la caché vuelva a escribir los datos en la memoria principal en algún momento en el futuro, antes de permitir cualquier otra lectura del estado de la memoria principal (que ya no es válido). La escritura diferida cambia la línea al estado Compartido (S).
- Exclusivo (E)
- La línea de caché está presente solo en el caché actual, pero está limpia : coincide con la memoria principal. Puede cambiarse al estado Compartido en cualquier momento, en respuesta a una solicitud de lectura. Alternativamente, se puede cambiar al estado Modificado al escribir en él.
- Compartido (S)
- Indica que esta línea de caché puede estar almacenada en otras cachés de la máquina y está limpia ; coincide con la memoria principal. La línea se puede descartar (cambiar al estado no válido) en cualquier momento.
- Inválido (I)
- Indica que esta línea de caché no es válida (sin usar).
Para cualquier par de cachés, los estados permitidos de una línea de caché determinada son los siguientes:
METRO | mi | S | I | |
---|---|---|---|---|
METRO | ||||
mi | ||||
S | ||||
I |
Cuando el bloque está marcado como M (modificado) o E (exclusivo), las copias del bloque en otros cachés se marcan como I (no válido).
Operación
El estado del FSM pasa de un estado a otro basándose en 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 proviene de otro procesador, que no tiene el bloque Cache o los datos actualizados en su Cache, a través del bus que conecta los procesadores. Las solicitudes de 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 para almacenar en caché incluyen las siguientes operaciones:
- PrRd: el procesador solicita leer un bloque de caché.
- PrWr: el procesador solicita escribir un bloque de caché
Las solicitudes del lado del autobús son las siguientes:
- BusRd: solicitud snooped que indica que hay una solicitud de lectura a un bloque de caché solicitado por otro procesador
- BusRdX: solicitud snooped que indica que hay una solicitud de escritura en un bloque de caché solicitada por otro procesador que aún no tiene el bloque.
- BusUpgr: solicitud snooped que indica que hay una solicitud de escritura en un bloque de caché solicitada por otro procesador, pero ese procesador ya tiene ese bloque de caché que reside en su propia caché .
- Flush: solicitud snooped que indica que otro procesador vuelve a escribir un bloque de caché completo en la memoria principal.
- FlushOpt: solicitud snooped que indica que un bloque de caché completo se publica en el bus para suministrarlo a otro procesador (transferencias de caché a caché).
( Dichas 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é, que es generalmente el caso en sistemas basados en bus. Pero en arquitecturas multinúcleo, donde la coherencia se mantiene en el nivel de las cachés L2, hay una caché L3 del chip, puede ser más rápido recuperar el bloque perdido de la caché L3 que de otra L2 )
Operación de espionaje: En un sistema de espionaje, todas las cachés del bus monitorean (o espían) todas las transacciones del 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 ver el diagrama de estado de MESI). El autobús tiene fisgones en ambos lados:
- Snooper hacia el lado del procesador / caché.
- 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 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.
Estado inicial | Operación | Respuesta |
---|---|---|
Inválido (I) | PrRd |
|
PrWr |
| |
Exclusivo (E) | PrRd |
|
PrWr |
| |
Compartido (S) | PrRd |
|
PrWr |
| |
Modificado (M) | PrRd |
|
PrWr |
|
Estado inicial | Operación | Respuesta |
---|---|---|
Inválido (I) | BusRd |
|
BusRdX / BusUpgr |
| |
Exclusivo (E) | BusRd |
|
BusRdX |
| |
Compartido (S) | BusRd |
|
BusUpgr |
| |
Modificado (M) | BusRd |
|
BusRdX |
|
Una escritura solo se puede realizar libremente si la línea de caché está en el estado Modificado o Exclusivo. Si está en el estado Compartido, todas las demás copias en caché deben invalidarse primero. Por lo general, 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 espiar (interceptar) todos los intentos de lectura (de todos los demás cachés en el sistema) de la ubicación de la 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 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 caché modificada a la caché que realiza la lectura. Tenga en cuenta que solo se requiere espionaje para errores de lectura (el protocolo garantiza que Modified no pueda existir si cualquier otro caché puede realizar un hit de lectura).
Un caché que contiene una línea en el estado Compartido debe escuchar las transmisiones de invalidación o solicitud de propiedad de otros cachés y descartar la línea (moviéndola al estado No válido) en 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 se promoverá al estado exclusivo. Otros cachés no emiten avisos cuando descartan líneas de caché, y este caché no podría usar tales 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é que está 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 [5]
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.
El flujo es: R1, W1, R3, W3, R1, R3, R2.
Inicialmente se asume que todas las cachés están vacías.
Solicitud local | P1 | P2 | P3 | Generado Solicitud de bus | Proveedor de datos | |
---|---|---|---|---|---|---|
0 | Inicialmente | - | - | - | - | - |
1 | R1 | mi | - | - | BusRd | Mem |
2 | W1 | METRO | - | - | - | - |
3 | R3 | S | - | S | BusRd | Caché de P1 |
4 | W3 | I | - | METRO | BusUpgr | - |
5 | R1 | S | - | S | BusRd | Caché de P3 |
6 | R3 | S | - | S | - | - |
7 | R2 | S | S | S | BusRd | Caché de P1 / P3 |
Nota: El término espionaje 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 en el bus monitorean (fisgonean) el bus si tienen una copia del bloque de datos que se solicita en el bus.
Paso 1: Como la caché está inicialmente vacía, la memoria principal proporciona a P1 el bloque y se convierte en estado exclusivo.
Paso 2: Como el bloque ya está presente en la caché y en un estado exclusivo, lo modifica directamente sin ninguna instrucción de bus. El bloque está ahora en un estado modificado.
Paso 3: En este paso, se publica un BusRd en el bus y el fisgón en P1 lo detecta. Luego vacía los datos 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é. Aquí no hay acceso a la memoria principal.
Paso 4: Aquí se publica un BusUpgr en el bus y el fisgón en P1 lo detecta e invalida el bloque, ya que va a ser modificado por otra caché. P3 luego cambia su estado de bloque a modificado.
Paso 5: Como el estado actual no es válido, publicará un BusRd en el bus. El fisgón en P3 detectará esto y, por lo tanto, eliminará los datos. El estado de ambos bloques en P1 y P3 se compartirá ahora. Tenga en cuenta que esto es cuando incluso la memoria principal se actualizará con los datos previamente modificados.
Paso 6: hay un acierto en la caché y está en el estado compartido, por lo que no se realiza ninguna solicitud de bus aquí.
Paso 7: Hay una falta de caché en P2 y se publica un BusRd. El fisgón en P1 y P3 siente esto y ambos intentarán un rubor. Cualquiera que tenga acceso al autobús primero hará esa operación.
Leer para ser propietario
Una lectura para propiedad (RFO) es una operación en protocolos de coherencia de caché que combina una lectura y una transmisión invalidada. 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 invá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 tanto, esta operación es exclusiva. Trae datos al caché e invalida todos los demás cachés del procesador que contienen esta línea de memoria. Esto se denomina "BusRdX" en las tablas anteriores.
Barreras de memoria
MESI, en su implementación sencilla e ingenua, exhibe dos problemas de desempeño 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 otra CPU. En segundo lugar, mover las líneas de caché al estado no válido requiere mucho tiempo. Para mitigar estos retrasos, las CPU implementan búferes de almacenamiento e invalidan las colas. [6]
Almacenar búfer
Se utiliza un búfer de almacenamiento cuando se escribe en una línea de caché no válida. Dado que 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 líneas de caché de las demás CPU que almacenan esa dirección de memoria están invalidadas) y luego empuja la escritura al búfer de almacenamiento para que se ejecute. cuando la línea de caché finalmente llega a la 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, cada vez que una CPU necesita leer una línea de caché, primero tiene que escanear su propio búfer de almacenamiento para detectar 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 aún no lo ha hecho. se ha escrito en la caché (la escritura anterior todavía está esperando en el búfer de la tienda). 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 antes de que se vacíen del búfer de almacenamiento al 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, por lo que las solicitudes de invalidación entrantes se reconocen instantáneamente pero de hecho no se actúa sobre ellas. En cambio, los mensajes de invalidación simplemente ingresan a una cola de invalidación y su procesamiento ocurre lo antes posible (pero no necesariamente instantáneamente). 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 tienda vaciará el búfer de la tienda, asegurando que todas las escrituras se hayan aplicado al caché de esa CPU. Una barrera de lectura vaciará la cola de invalidación, asegurando así que todas las escrituras de otras CPU sean visibles para la CPU de vaciado. 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. [7]
Ventajas de MESI sobre MSI
La diferencia más notable entre los dos protocolos es el estado extra "exclusivo" presente en el protocolo MESI. Se agregó este estado adicional 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 llevarán a cabo dos transacciones de bus en el caso de MSI. Primero, se emite una solicitud BusRd para leer el bloque seguida de una solicitud BusRdX antes de escribir en el bloque. La solicitud BusRdX en este escenario es inútil ya que ninguna de las otras memorias caché tiene el mismo bloque, pero no hay forma de que una memoria caché lo sepa. Por lo tanto, el protocolo MESI supera esta limitación agregando un estado exclusivo, lo que resulta en guardar una solicitud de bus. Esto hace una gran diferencia cuando se ejecuta una aplicación secuencial. Como solo un procesador estará trabajando en él, todos los accesos serán exclusivos. MSI funciona muy mal en este caso. Incluso en el caso de una aplicación altamente paralela donde el intercambio de datos es mínimo, MESI es mucho más rápido. La adición del estado exclusivo también es gratuita, ya que 3 estados y 4 estados están codificados con 2 bits.
Desventaja de MESI
En caso de que varias memorias caché en un bloque en particular realicen operaciones continuas de lectura y escritura, los datos deben descargarse 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 la implementación de MESI. Este desafío fue superado por el protocolo MOESI . [8] En el caso de S (estado compartido), varios fisgones pueden responder con FlushOpt con los mismos datos (ver el ejemplo anterior). Estado F en direcciones MESIF para eliminar esta redundancia.
Ver también
- Protocolo de coherencia
- Protocolo MSI , el protocolo básico del que se deriva el protocolo MESI.
- Escritura única (coherencia de caché) , una de las primeras formas del protocolo MESI.
- Protocolo MOSI
- Protocolo MOESI
- Protocolo MESIF
- Protocolo MERSI
- Protocolo del dragón
- Protocolo de luciérnaga
Referencias
- ^ Papamarcos, MS; Patel, JH (1984). "Una solución de coherencia de bajo costo para multiprocesadores con memorias caché privadas" (PDF) . Actas del XI simposio internacional anual sobre arquitectura de computadoras - ISCA '84 . pag. 348. doi : 10.1145 / 800015.808204 . ISBN 0818605383. Consultado el 19 de marzo de 2013 .
- ^ Gómez-Luna, J .; Herruzo, E .; Benavides, JI "Simulador de coherencia de caché MESI para fines docentes". Revista electrónica Clei . 12 (1, DOCUMENTO 5, ABRIL DE 2009). CiteSeerX 10.1.1.590.6891 .
- ^ Culler, David (1997). Arquitectura informática paralela . Editores Morgan Kaufmann. págs. Figura 5–15 Diagrama de transición de estado para el protocolo MESI de Illinois. Pág 286.
- ^ Bigelow, Narasiman, Suleman. "Una evaluación de los protocolos de coherencia de caché basados en Snoopy" (PDF) . Departamento de ECE, Universidad de Texas en Austin.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Solihin, Yan (9 de octubre de 2015). Fundamentos de la arquitectura multinúcleo paralela . Raleigh, Carolina del Norte: Solihin Publishing and Consulting, LLC. ISBN 978-1-4822-1118-4.
- ^ Handy, Jim (1998). El libro de memoria caché . Morgan Kaufmann. ISBN 9780123229809.
- ^ Chen, G .; Cohen, E .; Kovalev, M. (2014). "Reducción de búfer de almacenamiento con MMU". Software verificado: teorías, herramientas y experimentos . Apuntes de conferencias en informática. 8471 . pag. 117. doi : 10.1007 / 978-3-319-12154-3_8 . ISBN 978-3-319-12153-6.
- ^ "Sistema de memoria (protocolo y coherencia de la memoria)" (PDF) . Tecnología AMD64. Septiembre de 2006.
enlaces externos
- Una simulación interactiva de MESI
- Un controlador MESI de código abierto (Verilog)