Coherencia de caché basada en directorios

En ingeniería informática , la coherencia de caché basada en directorios es un tipo de mecanismo de coherencia de caché , donde se utilizan directorios para gestionar las cachés en lugar del rastreo de bus . Los métodos de rastreo de bus tienen una baja escalabilidad debido al uso de difusión . Estos métodos pueden utilizarse para optimizar tanto el rendimiento como la escalabilidad de los sistemas de directorios. ^{[ 1 ]}

En el formato de vector de bits completo, para cada línea de caché posible en la memoria , se utiliza un bit para rastrear si cada procesador individual tiene esa línea almacenada en su caché . El formato de vector de bits completo es la estructura más simple de implementar, pero la menos escalable. ^{[ 1 ]} El SGI Origin 2000 utiliza una combinación de vector de bits completo y vector de bits grueso dependiendo del número de procesadores. ^{[ 2 ]}

Cada entrada de directorio debe tener 1 bit almacenado por procesador por línea de caché, junto con bits para rastrear el estado del directorio. Esto da como resultado un tamaño total requerido de (número de procesadores) × número de líneas de caché , con una relación de sobrecarga de almacenamiento de (número de procesadores) / (tamaño del bloque de caché × 8) .

Se observa que la sobrecarga del directorio aumenta linealmente con el número de procesadores. Si bien esto puede ser aceptable para un número reducido de procesadores, al implementarse en sistemas grandes, los requisitos de tamaño para el directorio se vuelven excesivos. Por ejemplo, con un tamaño de bloque de 32 bytes y 1024 procesadores, la sobrecarga de almacenamiento se convierte en 1024/(32×8) = 400 %.

El formato de vector de bits grueso tiene una estructura similar al formato de vector de bits completo, aunque en lugar de rastrear un bit por procesador para cada línea de caché, el directorio agrupa varios procesadores en nodos , almacenando si una línea de caché está almacenada en un nodo en lugar de un procesador. Esto mejora los requisitos de tamaño a expensas del tráfico del bus ahorrando (procesadores por nodo - 1)×(líneas totales) bits de espacio. ^{[ 2 ]} Por lo tanto, la sobrecarga de relación es la misma, solo que reemplaza el número de procesadores con el número de grupos de procesadores. Cuando se hace una solicitud de bus para una línea de caché que tiene un procesador en el grupo, el directorio difunde la señal a todos los procesadores en el nodo en lugar de solo a las cachés que la contienen, lo que genera tráfico innecesario a los nodos que no tienen los datos en caché.

En este caso, la entrada del directorio utiliza 1 bit para un grupo de procesadores por cada línea de caché. Si, en el mismo ejemplo que con el formato Full Bit Vector, consideramos 1 bit para un grupo de 8 procesadores, la sobrecarga de almacenamiento será del 128/(32×8)=50%. Esto supone una mejora significativa con respecto al formato Full Bit Vector.

Una caché solo almacena un pequeño subconjunto de bloques en la memoria principal en un momento dado. Por lo tanto, la mayoría de las entradas en el directorio corresponderán a bloques no almacenados en caché. En el formato de directorio disperso, el desperdicio se reduce al almacenar únicamente los bloques en caché. Consideremos un procesador con una caché de 64 KB, un tamaño de bloque de 32 bytes y una memoria principal de 4 MB. El número máximo de entradas que puede tener el directorio en el formato de directorio disperso es de 2048. Si el directorio contiene una entrada para cada bloque en la memoria, el número total de entradas será de 131072. Por lo tanto, resulta evidente que la mejora en el almacenamiento que proporciona el formato de directorio disperso es muy significativa.

En este formato, el directorio está descentralizado y distribuido entre las cachés que comparten un bloque de memoria. Las diferentes cachés que comparten un bloque de memoria se organizan en forma de árbol binario . La caché que accede primero a un bloque de memoria es el nodo raíz . Cada bloque de memoria contiene la información del nodo raíz (HEAD) y el campo de contador de compartición (SC). El campo SC contiene el número de cachés que comparten el bloque. Cada entrada de caché tiene punteros a las siguientes cachés que comparten el bloque, conocidas como L-CHD y R-CHD. Una condición para este directorio es que el árbol binario debe estar equilibrado numéricamente, es decir, el número de nodos en el subárbol izquierdo debe ser igual o uno mayor que el número de nodos en el subárbol derecho. Todos los subárboles también deben estar equilibrados numéricamente. ^{[ 3 ]}

En este formato, la memoria almacena el puntero de directorio a la última caché que accedió al bloque, y cada caché tiene el puntero a la caché anterior que accedió al bloque. Por lo tanto, cuando un procesador envía una solicitud de escritura a un bloque en memoria, envía invalidaciones a través de la cadena de punteros. En este directorio, cuando se reemplaza un bloque de caché, es necesario recorrer la lista para cambiar el directorio, lo que aumenta la latencia . Para evitar esto, actualmente se utilizan ampliamente listas doblemente enlazadas, en las que cada copia en caché tiene punteros a la caché anterior y a la siguiente que accede al bloque. ^{[ 4 ]}

El formato de puntero limitado utiliza un número fijo de punteros para rastrear los procesadores que almacenan los datos en caché. Cuando un nuevo procesador almacena un bloque en caché, se elige un puntero libre de un grupo para que apunte a ese procesador. Existen varias opciones para gestionar los casos en que el número de usuarios que comparten el bloque supera el número de punteros libres. Un método consiste en invalidar uno de los usuarios, utilizando su puntero para el nuevo solicitante, aunque esto puede resultar costoso en casos donde un bloque tiene un gran número de lectores, como en el caso de un bloqueo. Otro método consiste en disponer de un grupo independiente de punteros libres a disposición de todos los bloques. Este método suele ser eficaz, ya que el número de bloques compartidos por un gran número de procesadores no suele ser muy elevado.