Coherencia basada en directorios

La coherencia basada en directorios es un mecanismo para manejar el problema de coherencia de caché en memoria compartida distribuida (DSM), también conocida como acceso a memoria no uniforme (NUMA). Otra forma popular es usar un tipo especial de bus de computadora entre todos los nodos como un "bus compartido" (también conocido como bus del sistema ). ^{[ 1 ]} La coherencia basada en directorios usa un directorio especial para servir en lugar del bus compartido en los protocolos de coherencia basados ​​en bus. Ambos diseños usan el medio correspondiente (es decir, directorio o bus) como una herramienta para facilitar la comunicación entre diferentes nodos y para garantizar que el protocolo de coherencia esté funcionando correctamente en todos los nodos que se comunican. En la coherencia de caché basada en directorios, esto se hace usando este directorio para hacer un seguimiento del estado de todos los bloques de caché , el estado de cada bloque incluye en qué " estado " de coherencia de caché está ese bloque y qué nodos están compartiendo ese bloque en ese momento, lo que puede usarse para eliminar la necesidad de transmitir todas las señales a todos los nodos y enviarlas solo a los nodos que están interesados ​​en ese bloque en particular.

A continuación se presentan algunas ventajas y desventajas del protocolo de coherencia de caché basado en directorios:

• Escalabilidad : Esta es una de las principales razones para optar por diseños basados ​​en directorios. La escalabilidad , en resumen, se refiere a la capacidad de un sistema para gestionar el creciente volumen de trabajo que debe realizar. En este sentido, los sistemas basados ​​en bus no ofrecen un buen rendimiento debido a la limitación que supone compartir un bus con todos los nodos simultáneamente. Si bien los sistemas de bus pueden funcionar bien con un número relativamente pequeño de nodos, a medida que aumenta el número de nodos, pueden surgir problemas. Esto se debe, en particular, a que solo un nodo puede utilizar el bus a la vez, lo que perjudica significativamente el rendimiento general del sistema. Por otro lado, con los sistemas basados ​​en directorios, no existe este cuello de botella que limita la escalabilidad del sistema.
• Simplicidad : Este es uno de los puntos donde el sistema de bus es superior. Dado que la estructura del bus puede servir como organizador de todo el tráfico que pasa por el sistema y garantizar la atomicidad de todas las señales transmitidas, no será necesario realizar un esfuerzo adicional para garantizar la atomicidad y el orden entre las señales, como ocurre en los sistemas basados ​​en directorios, lo que conlleva una sobrecarga que se presenta posteriormente en el diseño del sistema al tratar problemas como la consistencia .

De la discusión anterior se desprende que el uso de sistemas basados ​​en bus parece más atractivo para sistemas relativamente pequeños. Sin embargo, los sistemas basados ​​en directorio se vuelven cruciales cuando el sistema se expande y aumenta el número de nodos. Por lo tanto, existe una especie de compromiso entre la simplicidad y la escalabilidad al comparar los diseños de coherencia de caché basados ​​en bus y en directorio. ^{[ 1 ]}

La idea de los sistemas de coherencia de caché basados ​​en directorios comenzó hace mucho tiempo. La idea de DASH ( Directory Architecture for SH reded-memory) fue propuesta por primera vez por CK Tang ^{[ 2 ]} a mediados de la década de 1970. Sin embargo, su aplicación a la coherencia de caché se propuso unos años más tarde, en 1978, cuando investigadores de la Universidad de Stanford propusieron la primera versión de este sistema de coherencia llamado Stanford DASH , en un artículo ^{[ 3 ]} que describía el sistema con las dificultades y mejoras asociadas con tales diseños. Además de este enfoque, se hicieron varios intentos para proporcionar sistemas escalables. Por ejemplo, BBN Butterfly ^{[ 4 ]} que se introdujo en 1985, e IBM PR3 ^{[ 5 ]} que se introdujo en 1987, son algunos ejemplos de sistemas multiprocesador escalables . Sin embargo, ambos de estos sistemas tienen un inconveniente; por ejemplo, BBN Butterfly no tiene cachés. De manera similar, IBM PR3 no proporciona coherencia de caché de hardware, lo que limita el rendimiento de ambos diseños, especialmente cuando se emplean procesadores de alto rendimiento. ^{[ 6 ]}

Las limitaciones de otros competidores facilitaron la elección de sistemas basados ​​en DASH al diseñar sistemas de coherencia de caché y otros sistemas que requieren escalabilidad en nodos basados ​​en caché. En 1985, James Archibald ^{[ 7 ]} y Jean-Loup Baer de la Universidad de Washington publicaron un artículo ^{[ 8 ]} que propone una variación más económica, expandible y modular del enfoque de "directorio global" en términos de uso de hardware en el diseño.

En 1992, Daniel Lenoski, de la Universidad de Stanford, publicó un artículo ^{[ 9 ]} en el que proponía avances en los protocolos de coherencia de caché para sistemas basados ​​en directorios. En un artículo de 1996 ^{[ 10 ]} , presentó el diseño del SGI Origin 2000 , una familia de servidores que empleaban coherencia de caché basada en directorios. El posterior Origin 3000 ^{[ 11 ]} se presentó en julio de 2000.

A diferencia de los protocolos de coherencia snoopy , en un enfoque de coherencia basado en directorios, la información sobre qué cachés tienen una copia de un bloque se mantiene en una estructura llamada directorio . En un esquema basado en directorios, las cachés participantes no envían solicitudes de difusión a todas las demás cachés que comparten el bloque para localizar copias almacenadas en caché, sino que consultan el directorio para recuperar la información sobre qué bloques tienen copias almacenadas en caché y la envían solo a esos procesadores específicos, lo que resulta en un gran ahorro de tráfico en comparación con un protocolo snoopy. En aplicaciones bien optimizadas, la mayor parte del intercambio de datos se limita a datos de solo lectura, y hay poco intercambio de datos que se leen y escriben con frecuencia. Un enfoque basado en directorios puede generar un ahorro de tráfico sustancial en comparación con el enfoque de difusión/snoopy en dichas aplicaciones.

Como se muestra en el diagrama de flujo de datos, los actores involucrados en un sistema de memoria compartida distribuida que implementa un protocolo de coherencia basado en directorios son:

• Nodo solicitante : Este nodo es el procesador que solicita la lectura/escritura de un bloque de memoria.
• Nodo de directorio : Este nodo mantiene la información del estado de cada bloque de caché en el sistema y el solicitante dirige sus solicitudes al nodo de directorio.
• Nodo propietario : Un nodo propietario posee el estado más reciente del bloque de caché; tenga en cuenta que el directorio puede no estar siempre actualizado con los datos más recientes.
• Nodo compartidor : Uno o varios nodos que comparten una copia del bloque de caché.

Los nodos solicitante y propietario mantienen su transición de estado de forma similar a los protocolos de coherencia de tipo "snoopy" como el protocolo MESI . Sin embargo, a diferencia de una implementación basada en bus, donde los nodos se comunican mediante un bus común, la implementación basada en directorio utiliza un modelo de paso de mensajes para intercambiar la información necesaria para mantener la coherencia de la caché .

El nodo de directorio actúa como punto de serialización y todas las comunicaciones se dirigen a través de este nodo para mantener la corrección.

Un nodo de directorio realiza un seguimiento del estado general de un bloque de caché en todo el sistema de caché para todos los procesadores. Puede estar en tres estados  :

• Sin caché (U) : Ningún procesador tiene datos en caché, la memoria está actualizada.
• Compartido (S) : uno o más procesadores tienen datos en caché y la memoria está actualizada. En este estado, el directorio y los usuarios que comparten los datos tienen una copia limpia del bloque almacenado en caché.
• Exclusivo/Modificado (EM) : un procesador (propietario) tiene datos en caché; la memoria está desactualizada. Tenga en cuenta que el directorio no puede distinguir si un bloque está en caché en estado exclusivo o modificado en el procesador, ya que los procesadores pueden pasar de un estado exclusivo a un estado modificado sin ninguna transacción de bus.

La explicación de la máquina de estados finitos de transición de estado de directorio (ver imagen 1) se muestra a continuación en la tabla:

Además del estado de la caché, un directorio debe rastrear qué procesadores tienen datos cuando se encuentran en estado compartido. Esto es necesario para enviar solicitudes de invalidación e intervención a las cachés de procesadores individuales que tienen el bloque de caché en estado compartido. Algunos de los enfoques de implementación más comunes son:

• Vector de bits completo : Se mantiene un campo de bits para cada procesador en el nodo del directorio. La sobrecarga de almacenamiento aumenta con el número de procesadores.
• Puntero limitado: En este enfoque, la información del directorio de un número limitado de bloques se mantiene en el directorio para reducir la sobrecarga de almacenamiento.

El protocolo descrito anteriormente es la implementación básica, y pueden producirse condiciones de carrera debido a que el directorio puede estar desincronizado con las cachés y a que los mensajes entre procesadores pueden superponerse. Existen implementaciones más complejas, como la Interfaz Coherente Escalable , que cuenta con múltiples estados.

El protocolo de coherencia de caché DASH ^{[ 3 ]} es otro protocolo que utiliza un esquema de coherencia basado en directorios. El protocolo DASH emplea un enfoque de clúster, donde los procesadores dentro de un clúster mantienen la coherencia mediante un esquema de inspección basado en bus, mientras que los clústeres se conectan mediante un enfoque de directorio. Si bien varios protocolos utilizan diferentes implementaciones para el seguimiento de los bloques de caché, el concepto de directorio permanece invariable.

• Protocolo de coherencia
• Protocolo MSI
• Matriz de bits
• Memoria compartida distribuida
• Caché de Snoopy