Coherencia de caché

En la arquitectura informática , la coherencia de la memoria caché es la uniformidad de los datos de recursos compartidos que terminan almacenándose en múltiples cachés locales . Cuando los clientes de un sistema mantienen cachés de un recurso de memoria común, pueden surgir problemas con datos incoherentes, lo que sucede particularmente con las CPU en un sistema multiprocesador .

En la ilustración de la derecha, supongamos que ambos clientes tienen una copia en caché de un bloque de memoria particular de una lectura anterior. Supongamos que el cliente de la parte inferior actualiza o cambia ese bloque de memoria; el cliente de la parte superior podría quedarse con una caché de memoria no válida sin ninguna notificación del cambio. La coherencia de la caché tiene como objetivo gestionar dichos conflictos manteniendo una vista coherente de los valores de los datos en varias cachés.

En un sistema multiprocesador de memoria compartida con una memoria caché separada para cada procesador, es posible tener muchas copias de los datos compartidos: una copia en la memoria principal y otra en la caché local de cada procesador que la solicitó. Cuando una de las copias de los datos se modifica, las otras copias deben reflejar ese cambio. La coherencia de la caché es la disciplina que garantiza que los cambios en los valores de los operandos compartidos (datos) se propaguen por todo el sistema de manera oportuna. ^[1]

Los siguientes son los requisitos para la coherencia de la caché: ^[2]

Propagación de escritura

Los cambios en los datos de cualquier caché deben propagarse a otras copias (de esa línea de caché) en los cachés pares.

Serialización de transacciones

Las lecturas/escrituras en una única ubicación de memoria deben ser vistas por todos los procesadores en el mismo orden.

En teoría, la coherencia se puede realizar en la granularidad de carga/almacenamiento . Sin embargo, en la práctica, generalmente se realiza en la granularidad de los bloques de caché. ^[3]

La coherencia define el comportamiento de las lecturas y escrituras en una única ubicación de dirección. ^[2]

Un tipo de datos que aparecen simultáneamente en diferentes memorias caché se denomina coherencia de caché o, en algunos sistemas, memoria global.

En un sistema multiprocesador, considere que más de un procesador ha almacenado en caché una copia de la ubicación de memoria X. Las siguientes condiciones son necesarias para lograr la coherencia de la caché: ^[4]

1. En una lectura realizada por un procesador P en una ubicación X que sigue a una escritura del mismo procesador P en X, sin que otro procesador escriba en X entre las instrucciones de escritura y lectura realizadas por P, X siempre debe devolver el valor escrito por P.
2. En una lectura realizada por un procesador P1 en la posición X que sigue a una escritura de otro procesador P2 en X, sin que se produzcan otras escrituras en X realizadas por ningún otro procesador entre los dos accesos y estando la lectura y la escritura suficientemente separadas, X siempre debe devolver el valor escrito por P2. Esta condición define el concepto de visión coherente de la memoria. La propagación de las escrituras a la posición de memoria compartida garantiza que todas las cachés tengan una visión coherente de la memoria. Si el procesador P1 lee el valor antiguo de X, incluso después de la escritura de P2, podemos decir que la memoria es incoherente.

Las condiciones anteriores satisfacen los criterios de propagación de escritura necesarios para la coherencia de la caché. Sin embargo, no son suficientes, ya que no satisfacen la condición de serialización de transacciones. Para ilustrar esto mejor, considere el siguiente ejemplo:

Un sistema multiprocesador consta de cuatro procesadores: P1, P2, P3 y P4, todos conteniendo copias en caché de una variable compartida S cuyo valor inicial es 0. El procesador P1 cambia el valor de S (en su copia en caché) a 10, después de lo cual el procesador P2 cambia el valor de S en su propia copia en caché a 20. Si aseguramos solo la propagación de escritura, entonces P3 y P4 seguramente verán los cambios realizados a S por P1 y P2. Sin embargo, P3 puede ver el cambio realizado por P1 después de ver el cambio realizado por P2 y, por lo tanto, devolver 10 en una lectura a S . P4 por otro lado puede ver los cambios realizados por P1 y P2 en el orden en que se realizan y, por lo tanto, devolver 20 en una lectura a S . Los procesadores P3 y P4 ahora tienen una vista incoherente de la memoria.

Por lo tanto, para satisfacer la serialización de transacciones y, por lo tanto, lograr la coherencia de caché, se debe cumplir la siguiente condición junto con las dos anteriores mencionadas en esta sección:

• Las escrituras en la misma ubicación deben estar secuenciadas. En otras palabras, si la ubicación X recibió dos valores diferentes A y B, en este orden, de dos procesadores cualesquiera, los procesadores nunca podrán leer la ubicación X como B y luego leerla como A. La ubicación X debe verse con los valores A y B en ese orden. ^[5]

La definición alternativa de un sistema coherente es a través de la definición del modelo de memoria de consistencia secuencial : "el sistema coherente de caché debe parecer que ejecuta todas las cargas y almacenamientos de los subprocesos en una única ubicación de memoria en un orden total que respeta el orden del programa de cada subproceso". ^[3] Por lo tanto, la única diferencia entre el sistema coherente de caché y el sistema secuencialmente consistente está en el número de ubicaciones de direcciones de las que habla la definición (una única ubicación de memoria para un sistema coherente de caché y todas las ubicaciones de memoria para un sistema secuencialmente consistente).

Otra definición es: "un multiprocesador es consistente en caché si todas las escrituras en la misma ubicación de memoria se realizan en algún orden secuencial". ^[6]

En raras ocasiones, pero especialmente en algoritmos, la coherencia puede referirse a la localidad de referencia . Pueden existir múltiples copias de los mismos datos en diferentes cachés simultáneamente y, si se permite que los procesadores actualicen sus propias copias libremente, puede resultar en una visión inconsistente de la memoria.

Los dos mecanismos más comunes para garantizar la coherencia son el snooping y los basados ​​en directorios , cada uno con sus propias ventajas y desventajas. ^[7] Los protocolos basados ​​en snooping tienden a ser más rápidos, si hay suficiente ancho de banda disponible, ya que todas las transacciones son una solicitud/respuesta vista por todos los procesadores. El inconveniente es que el snooping no es escalable. Cada solicitud debe transmitirse a todos los nodos de un sistema, lo que significa que a medida que el sistema se hace más grande, el tamaño del bus (lógico o físico) y el ancho de banda que proporciona deben crecer. Los directorios, por otro lado, tienden a tener latencias más largas (con una solicitud/reenvío/respuesta de 3 saltos) pero utilizan mucho menos ancho de banda ya que los mensajes son punto a punto y no se transmiten. Por esta razón, muchos de los sistemas más grandes (>64 procesadores) utilizan este tipo de coherencia de caché.

Introducido por primera vez en 1983, ^[8] el snooping es un proceso en el que los cachés individuales monitorean las líneas de dirección en busca de accesos a ubicaciones de memoria que han almacenado en caché. ^[4] Los protocolos de invalidación de escritura y los protocolos de actualización de escritura hacen uso de este mecanismo.

Para el mecanismo de espionaje, un filtro de espionaje reduce el tráfico de espionaje manteniendo una pluralidad de entradas, cada una de las cuales representa una línea de caché que puede ser propiedad de uno o más nodos. Cuando se requiere el reemplazo de una de las entradas, el filtro de espionaje selecciona el reemplazo de la entrada que representa la línea o líneas de caché propiedad de la menor cantidad de nodos, según lo determinado a partir de un vector de presencia en cada una de las entradas. Se utiliza un algoritmo temporal o de otro tipo para refinar la selección si más de una línea de caché es propiedad de la menor cantidad de nodos. ^[9]

En un sistema basado en directorios, los datos que se comparten se colocan en un directorio común que mantiene la coherencia entre las cachés. El directorio actúa como un filtro a través del cual el procesador debe solicitar permiso para cargar una entrada de la memoria principal a su caché. Cuando se modifica una entrada, el directorio actualiza o invalida las demás cachés con esa entrada.

Los sistemas de memoria compartida distribuida imitan estos mecanismos en un intento de mantener la consistencia entre bloques de memoria en sistemas débilmente acoplados. ^[10]

Los protocolos de coherencia aplican la coherencia de caché en sistemas multiprocesador. La intención es que dos clientes nunca vean valores diferentes para los mismos datos compartidos.

El protocolo debe cumplir los requisitos básicos de coherencia y puede ser personalizado para el sistema o la aplicación de destino.

Los protocolos también se pueden clasificar como de espionaje o basados ​​en directorios. Por lo general, los primeros sistemas utilizaban protocolos basados ​​en directorios, en los que un directorio mantenía un registro de los datos que se compartían y de los usuarios que los compartían. En los protocolos de espionaje, las solicitudes de transacción (de lectura, escritura o actualización) se envían a todos los procesadores. Todos los procesadores espían la solicitud y responden de forma adecuada.

La propagación de escritura en protocolos snoopy se puede implementar mediante cualquiera de los siguientes métodos:

Invalidar escritura

Cuando se observa una operación de escritura en una ubicación de la cual un caché tiene una copia, el controlador de caché invalida su propia copia de la ubicación de memoria observada, lo que fuerza una lectura desde la memoria principal del nuevo valor en su próximo acceso. ^[4]

Actualización de escritura

Cuando se observa una operación de escritura en una ubicación de la cual un caché tiene una copia, el controlador de caché actualiza su propia copia de la ubicación de memoria observada con los nuevos datos.

Si el diseño del protocolo establece que siempre que se modifique una copia de los datos compartidos, todas las demás copias deben "actualizarse" para reflejar el cambio, entonces se trata de un protocolo de escritura y actualización. Si el diseño establece que una escritura en una copia almacenada en caché por parte de cualquier procesador requiere que otros procesadores descarten o invaliden sus copias almacenadas en caché, entonces se trata de un protocolo de escritura e invalidación.

Sin embargo, la escalabilidad es una deficiencia de los protocolos de transmisión.

Se han ideado varios modelos y protocolos para mantener la coherencia, como MSI , MESI (también conocido como Illinois), MOSI , MOESI , MERSI , MESIF , write-once , Synapse, Berkeley, Firefly y el protocolo Dragon . ^[1] En 2011, ARM Ltd propuso AMBA 4 ACE ^[11] para gestionar la coherencia en SoC . La especificación AMBA CHI (Coherent Hub Interface) ^[12] de ARM Ltd , que pertenece al grupo de especificaciones AMBA5, define las interfaces para la conexión de procesadores totalmente coherentes.

• Modelo de consistencia
• Coherencia basada en directorios
• Barrera de la memoria
• Acceso a memoria no uniforme (NUMA)
• Compartir falsamente

• Patterson, David ; Hennessy, John (2009). Organización y diseño de computadoras (4.ª ed.). Morgan Kaufmann . ISBN 978-0-12-374493-7.
• Handy, Jim (1998). El libro de la memoria caché (2.ª edición). Morgan Kaufmann . ISBN 9780123229809.
• Sorin, Daniel; Hill, Mark; Wood, David (2011). Introducción a la coherencia de la memoria y la coherencia de la memoria caché (PDF) . Morgan y Claypool. ISBN 978-1608455645. Recuperado el 20 de octubre de 2017 .
• Steinke, Robert C.; Nutt, Gary J. (1 de septiembre de 2004). "Una teoría unificada de la consistencia de la memoria compartida". Revista de la ACM . 51 (5): 800–849. arXiv : cs/0208027 . doi :10.1145/1017460.1017464. S2CID  3206071.