Mostramos en este tutorial qué es el protocolo MESI y cómo funciona en pequeños sistemas con multiprocesadores simétricos. Indicamos la optimización que supone el protocolo MESI en el caso de transferencia de caché a caché y algunos resultados de simulaciones en determinadas condiciones.

• Introducción al protocolo MESI.
• Optimización del protocolo MESI.
• Rendimiento del multiproceso MESI.
• Resultados de la simulación y conclusión.
  • Resultados de Productor-Consumidor.
  • Resultados de la multiplicación de matrices.
• Bibliografía.
• Créditos.

Introducción al protocolo MESI

La coherencia de caché hace referencia a la integridad de los datos almacenados en las cachés locales de los recursos compartidos. La coherencia de la caché es un caso especial de la coherencia de memoria.

Múltiples caches con recursos comunes: cuando los clientes de un sistema, en particular las CPU en un multiprocesador, mantienen cachés de una memoria compartida, los conflictos crecen.

Varios modelos y protocolos han sido desarrollados para mantener la coherencia de la caché, tales como protocolo MSI, protocolo MESI, protocolo MOSI y el protocolo MOESI. La elección de un modelo de consistencia es crucial a la hora de diseñar un sistema de caché coherente. Los modelos de coherencia difieren en rendimiento y escalabilidad, por lo que deben ser evaluados para cada sistema diseñado. Además, las transiciones entre estados en una implementación en concreto de estos protocolos pueden variar. Por ejemplo una implementación puede elegir diferentes transiciones para actualizar y actualiza tales como actualización-en-lectura, actualización-en-escritura, invalidación-en-lectura, o invalidación-en-escritura. La elección de una transición puede afectar a la cantidad de tráfico entre cachés, lo que a su vez podría afectar al ancho de banda disponible por las cachés para la operación actual. Esto debe ser tenido en consideración en el diseño de software distribuido que podría causar problemas de contención entre cachés de múltiples procesadores.

El nombre del protocolo (MESI) viene de los nombres de los estados que puede tomar una línea: modificada, exclusiva, compartida e inválida que en inglés significan Modified, Exclusive, Shared, Invalid, y lo cierto es que este nombre se usa más que el de Illinois.

M - Modified (Modificado): la línea de caché sólo está en la caché actual, y está "sucia"; ha sido modificado el valor de la memoria principal. Es necesario que los datos sean escritos otra vez en la memoria principal antes de permitir cualquier otra lectura del estado de la memoria (ya no es válida).

E - Exclusive (Exclusivo): la línea de caché sólo se encuentra en la caché actual, pero está "limpia"; coincide con el valor de la memoria principal.

S - Shared (Compartido): indica que esta línea de caché puede estar duplicada en otras cachés.

I - Invalid (Inválido): indica que esta línea de caché no es válida.

Una línea que es propiedad de cualquier caché puede estar como exclusiva o modificada. Las líneas que están en el estado compartida no son propiedad de nadie en concreto. La aproximación MESI permite la determinación de si una línea es compartida o no cuando se carga. Una línea modificada es enviada directamente al peticionario desde la caché que la contiene. Esto evita la necesidad de enviar comandos de invalidación para todas aquellas líneas que no estaban compartidas.

Se puede leer de caché en cualquier estado excepto en Inválidos. Una línea inválida puede ser cogida (de los estados Compartido o Exclusivo) para satisfacer una lectura. Una escritura sólo puede ser llevada a cabo si la línea de caché está en estado Modificado o Exclusivo. Si está en estado Compartido todas las otras copias en otras cachés deben ser puestas en estado Inválido antes. Esto se hace habitualmente con una operación broadcast.

Una caché puede cambiar el estado de una línea en cualquier momento, pasándolo a estado Inválido. Una línea Modificada debe ser escrita antes. Una caché que contenga una línea en estado Modificado debe sondear (interceptar) todos los intentos de lectura (de todas las CPU del sistema) a la memoria principal y copiar los datos que tiene. Esto se hace habitualmente forzando la lectura back off (cancelar el bus de transferencia a memoria), para luego escribir los datos en memoria principal y cambiar la línea de caché a estado Compartido.

Una caché que contenga una línea en estado Compartido debe también sondear todas las operaciones broadcast inválidas de otras CPU, y descartar la línea (cambiándola a estado Inválido) una vez hecho.

Una caché que contenga una línea en estado Exclusivo también debe sondear todas las peticiones de lecturas del resto de CPU y cambiar la línea a estado Compartido una vez hecho.

Los estados Modificado y Exclusivo son siempre precisos: corresponden a los poseedores de la línea correcta en el sistema. El estado Compartido puede ser impreciso: si alguna otra CPU descarga una línea Compartida, y esta CPU es la única que tiene una copia, la línea no será cambiada a estado Exclusivo. En ese sentido el estado Exclusivo es una optimización oportunista: si la CPU quiere modificar la línea de caché a estado Compartido, es necesario un intercambio por el bus para invalidar cualquier otra copia en caché. El estado Compartido permite modificar una línea de caché sin ningún intercambio por el bus.

Optimización del protocolo MESI

La correcta optimización de los protocolos generales de uso de la caché, en el caso de multiprocesamiento simétrico con memoria compartida, puede suponer un importante incremento en el rendimiento general de la capacidad de procesamiento de un sistema informático.

La optimización que se busca, en la transferencia caché a caché, es significativa porque las condiciones para que se produzca suceden con mucha frecuencia cuando los hilos de las aplicaciones multitarea se ejecutan en procesadores separados de una máquina SMP (Symmetric Multi-Processing o Multiproceso Simétrico). En el apartado siguiente se muestran con qué frecuencia:

• Resultados de la simulación y conclusión.

A continuación se muestra una explicación sobre cómo funciona un procesador que no implementa esta optimización, un PowerPC 604 y un procesador que sí la implementa, un Pentium II.

"Espionaje" en acierto de lectura sin transferencias caché a caché

En el caso de la figura anterior, un ejemplo de funcionamiento de la a caché de un PowerPC, la caché B tiene actualmente una línea de datos. En ella se han modificado los datos, pero no se han escrito de nuevo en la memoria principal, por lo que está en el estado Modificado. La caché A detecta la dirección y comprueba su valor, resultando un acierto. La caché B "espía" la dirección y comprueba su caché encontrando un acierto. Si se permite que la transacción continúe, la caché A recibiría una copia no válida de los datos. Esto hace que la transacción se aborte inmediatamente y hace esperar a todos los agentes del bus de datos un ciclo de reloj, antes de hacer una nueva solicitud. Durante este ciclo de reloj, la caché que contiene los datos modificados debe tener acceso al bus de datos (ganando el arbitraje) y reescribe los datos en la memoria. Después de esta transacción los datos en la caché B se marcan como Exclusivo, ya que no se han modificado, sin embargo, no existen en ninguna otra caché. Cuando finaliza la transacción, la caché A pide otra vez al bus de datos que solicite una vez más la línea de memoria. Cuando esto sucede la caché B solicita de nuevo esta lectura, pero esta vez solo afirma la señal. La transacción se completa con normalidad, con la memoria del sistema suministrando los datos (incurriendo en la latencia del acceso a la DRAM y en el ciclo de reloj), pero tanto la caché A como la B marcan la línea como si estuviera en estado Compartido.

"Espionaje" en acierto de lectura con transferencias caché a caché

En el caso del Pentium II, la caché B tiene una línea modificada. Cuando la caché A hace una petición desde la memoria, la caché B comprueba esta dirección y ve que tiene una copia modificada. La caché B genera la señal de Modificado y los agentes implicados cambian los roles. La caché A se prepara para recibir los datos desde la otra caché y marcarla como Compartida en vez de Exclusiva, entonces la caché B se hace cargo de proporcionar los datos de la memoria. Esto cambiará el estado de la línea a Compartida. Por último, la memoria cambiará, de proporcionar los datos, a almacenarlos desde la caché B hasta que sea necesario escribirlos de nuevo en la DRAM.

El ahorro en ciclos de reloj que supone el método "transferencia caché a caché" frente al método de "no transferencia de caché a caché" se podrá entender con el siguiente ejemplo. Supongamos que cada sistema se ejecuta en un bus de datos de 128 bits a 100 MHz. Supongamos también que los bloques de cada caché son de 32 bytes de longitud. Por último, digamos que una caché L2 tarda 1 ciclo de reloj en operar, y que estamos utilizando DRAM normal con un tiempo de acceso de 60 ns. Finalmente supongamos que necesitamos 1 ciclo de reloj para solicitar el bus de datos y otro más para poner la dirección en el bus de direcciones. Dada esta configuración, solicitar 32 bytes de memoria DRAM consumirán 1 ciclo de reloj, conseguir la dirección otro ciclo de reloj, 6 ciclos para acceder a la DRAM y 2 ciclos para transferir los datos, es decir, un total de 10 ciclos de reloj. Solicitar los mismos 32 bytes desde otra caché, en cambio, solo tomará 1 ciclo de reloj, otro ciclo para obtener la dirección, 1 ciclo para el acceso y 2 ciclos para transferir los datos, con un total de 5 ciclos de reloj, es decir, la mitad de tiempo. Para el caso de una línea modificada el ahorro es aún mayor: 1 ciclo para la solicitud, 1 para obtener la dirección, 1 para cancelar la transacción, 10 ciclos para volver a escribir los datos, y luego otros 10 para recuperarla de nuevo desde la memoria, es decir, un total de 23 ciclos de reloj.

Más adelante se podrá comprobar este ejemplo en los resultados de la simulación.

Rendimiento del multiproceso MESI

A la hora de determinar el rendimiento de un multiprocesador con arquitectura MESI hay que tener en cuenta varios fenómenos combinables, ya que el rendimiento total de la caché es una combinación del comportamiento del tráfico causado por fallos de caché en un uniprocesador y el tráfico causado por la comunicación entre cachés, lo que puede dar lugar a invalidaciones.

El rendimiento se ve afectado por el número de procesadores, tamaño de la caché y tamaño del bloque, llevando al sistema a un comportamiento surgido de la combinación de estos efectos.

Algunas características del protocolo de invalidación MESI que influyen en el rendimiento son:

• Varias escrituras de una misma palabra sin lecturas intermedias solo precisan de una escritura de invalidación.
• Dadas líneas de caché de varias palabras solo es necesaria la escritura de cualquier palabra en la línea.
• El protocolo MESI trabaja sobre bloques de caché, a diferencia de otros protocolos (actualización) que deben trabajar sobre palabras para aumentar su eficiencia.
• Puede existir un retraso entre la escritura de una palabra en un procesador y la lectura de ese valor por otro procesador ya que los datos escritos no son actualizados de forma inmediata en la caché del que lee, por lo que, el que va a leer se invalida primero, así que debe esperar a que esté disponible para realizar dicha operación de lectura.

Como ya hemos comentado anteriormente, el ancho de banda del bus y la memoria van a influir en el rendimiento del protocolo MESI, puesto que es lo que más se demanda en un multiprocesador basado en bus, y esto hace que cualquier protocolo de invalidación, como es el caso de MESI, sea idóneo para sistemas que requieren mucha migración de procesos o sincronización.

Para un rendimiento adecuado del protocolo MESI hay que controlar los fallos en la caché que puedan producirse por la invalidación iniciada por otro procesador previamente al acceso a la caché puesto que incrementaría el tráfico en el bus.

Resultados de la simulación y conclusión

Resultados de Productor-Consumidor

Este benchmark muestra el rendimiento del procesador en el clásico modelo cliente-servidor, aplicado a la computación multihilo. Se han registrado los valores utilizando 2 y 4 hilos en diferentes desfases temporales delta.

• Con 2 hilos:

El siguiente gráfico muestra los valores absolutos de aciertos y fallos, ordenados por cada valor de delta:

Y este muestra los valores relativos de fallos respecto del 100%:

Como se puede comprobar, la optimización en 2 hilos logra un porcentaje entorno al 65 % de fallos, consistente en el intervalo de 1 a 1000 delta sin diferencias significativas. Es indicativo de que el hilo Consumidor (o Cliente) estuvo a la par que el Productor (o Servidor), consumiendo todos los datos antes de pasar al modo reposo.

• Con 4 hilos:

En cuanto a los valores tomados con 4 hilos:

A primera vista se puede apreciar que la escala es mayor que en el caso anterior, puesto que en 1 delta hay casi el doble de aciertos que en los valores obtenidos con 2 hilos y también en el resto de valores de delta para 4 hilos.

Y fallos respecto del 100:

En el caso de la optimización con 4 hilos, para 1 delta ronda el 83%, un valor mayor que para cualquiera de los obtenidos con 2 hilos.

Pero para los demás delta, este porcentaje de optimización cae enormemente debido a que los hilos empiezan a estar desincronizados entre sí, llegando a menos de un 20% para 1000 delta. Comparativamente con 2 hilos, al tener 4 ocurre que para cada dato producido hay 3 veces más fallos (hay 3 consumidores) y cada uno de ellos es optimizable.

Debido a la competición entre clientes y el hecho de que este benchmark fue realizado en un único procesador, a mayores valores de delta resulta en que cada hilo no pudo consumir sus datos antes del reposo. A consecuencia de ello se produce una caída en la compartición de datos entre cachés.

Sin embargo, en caso de haber realizado el benchmark con 4 procesadores funcionando simultáneamente, los 4 hilos habrían logrado un porcentaje de optimización sostenida rondando el 83%, de igual forma que con 2 hilos se lograba un porcentaje consistente rondando el 65%.

Resultados de la multiplicación de matrices

Este benchmark muestra el rendimiento del procesador en la multiplicación de dos matrices cuadradas de 3 dimensiones diferentes (4x4, 64x64 y 160x160), con los valores utilizando 2 y 4 hilos.

Aunque tiene un grado menor de compartición de datos que el benchmark Productor-Consumidor, es sin embargo lo suficientemente significativo, ya que la multiplicación de matrices opera en diferentes partes que poseen un considerable grado de coordinación y solapamiento de las líneas de datos de las cachés.

• Multiplicación de matrices 4x4:

• Multiplicación de matrices 64x64:

Nota aclaratoria: existe una discrepancia en los valores numéricos obtenidos en la multiplicación de matrices 64x64, puesto que no coinciden con los mostrados en el gráfico original, ni con la explicación en palabras, ni con el resto de experimentos (que sí coinciden todos ellos). Seguramente se trata de un error de transcripción de la página web donde figura el estudio.

• Multiplicación de matrices 160x160:

La versión de 2 procesadores se mantiene entorno al 20% para las tres matrices. El motivo de que aparezca el mismo valor puede ser el código de sincronización compartido entre los hilos. La versión de 4 procesadores tiene alrededor de un 38% de fallos optimizables en la multiplicación 4x4, cayendo hasta el 25% para la de 160x160. En caso de aumentar el tamaño de las matrices, el porcentaje convergería asintóticamente hacia el mismo 20% aparecido en el caso de los dos procesadores.

Bibliografía

• Docsetools, Coherencia de caché. Recuperado de: http://docsetools.com/articulos-informativos/article_70643.html.
• Coherencia de caché y protocolo MESI. Recuperado de: http://arqui-gr4-her-val-dan-ldro.wikispaces.com/Coherencia+de+cache+y+protocolo+MESI.
• Protocolo MESI. Recuperado de: http://es.wikipedia.org/wiki/Protocolo_MESI.
• Escuela Técnica Superior de Ingeniería, Universidad de Valencia, Sistemas Multiprocesadores. Recuperado de: http://ocw.uv.es/ingenieria-y-arquitectura/sistemas-electronicos-para-el-tratamiento-de-la-informacion/seti_materiales/seti10_ocw.pdf.
• Miguel A. Vega, Raúl Martín, Francisco A. Zarallo, Juan M. Sánchez, Juan A. Gómez, SMPCache: Simulador de sistemas de memoria caché en multiprocesadores simétricos. Recuperado de: http://arco.unex.es/smpcache/XIJP00.pdf.
• CLEI ELECTRONIC JOURNAL, VOLUME 12, NUMBER 1, PAPER 5, APRIL 2009, Mesi Caché Coherence Simulator for Teaching Purposes. Recuperado de: http://www.clei.org/cleiej/papers/v12i1p5.pdf.
• School of Computing, University of Utah, Seth H.Pugsle y, Josef B. Spjut, David W. Nellans, Rajee vBalasubr amonian, SWEL: Hardware Cache Coherence Protocols to Map Shared Data onto Shared Caches. Recuperado de: http://www.cs.utah.edu/~rajeev/pubs/pact10p.pdf.
• Universidad de Valencia, Procesamiento paralelo. Recupeado de: http://www.dte.eis.uva.es/Docencia/ETSII/SMP/BAK/tema5/ANEXO1.pdf.
• wHiTeHand, Control de caches de memoria. Recuperado de: http://whitehand-01.blogspot.com.es/2009/01/control-de-caches-de-memoria.html
• Ricardo Galli Granada, Concurrencia: los problemas del hardware moderno y barreras de memoria. Recuperado de: https://gallir.wordpress.com/2015/01/25/concurrencia-los-problemas-del-hardware-moderno-y-barreras-de-memoria.
• Jorge Triguis, Jorge Hiraiwa, Trabajo práctico de TAI2 El Procesado Itanium. Recuperado de: http://jeuazarru.com/wp-content/uploads/2014/10/itanium.pdf (el enlace ya no está disponible, se puede recuperar de la caché de Google cache:http://jeuazarru.com/wp-content/uploads/2014/10/itanium.pdf).
• Antonio García Guirado, Improving the Energy-Efficiency of Cache-Coherent Multi-Cores. Recuperado de: http://www.tdx.cat/bitstream/handle/10803/128665/TAGG.pdf.
• Robert Slater, Neal Tibrewala, Optimizing the MESI Cache Coherence Protocol for Multithreaded Applications on Small Symmetric Multiprocessor Systems. Recuperado de: http://tibrewala.net/papers/mesi98.

Créditos

Artículo realizado por:

• Fernando Hernández López.
• Alberto Valero Sánchez.
• Antonio del Solar Juaranz.
• David Rodríguez Duque.
• Alonso Javier Pérez Díaz.

Para la Universidad Internacional Isabel I de Castilla.

Artículo en inglés.