En ingeniería informática , la coherencia de caché basada en directorios es un tipo de mecanismo de coherencia de caché , donde los directorios se utilizan para administrar cachés en lugar de métodos snoopy debido a su escalabilidad. Los métodos de espionaje en el autobús escalan mal debido al uso de la radiodifusión . Estos métodos se pueden utilizar para apuntar tanto al rendimiento como a la escalabilidad de los sistemas de directorio. [1]
Formato vectorial de bits completo
En el formato vectorial de bits completo, para cada posible línea de caché en la memoria , se usa un bit para rastrear si cada procesador individual tiene esa línea almacenada en su caché . [2] El formato vectorial 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. [3]
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 lleva a que el tamaño total requerido sea (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 de bloque de caché × 8) .
Se puede observar que la sobrecarga del directorio escala linealmente con el número de procesadores. Si bien esto puede estar bien para una pequeña cantidad de procesadores, cuando se implementa en sistemas grandes, los requisitos de tamaño del directorio se vuelven excesivos. Por ejemplo, con un tamaño de bloque de 32 bytes y 1024 procesadores, la tasa de sobrecarga de almacenamiento se convierte en 1024 / (32 × 8) = 400%. [2]
Formato vectorial de bits gruesos
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 línea. Esto mejora los requisitos de tamaño a expensas del ahorro de tráfico de bus (procesadores por nodo) × (líneas totales) bits de espacio. [3] Por lo tanto, la tasa de sobrecarga es la misma, simplemente reemplazando el número de procesadores con el número de grupos de procesadores. Cuando se realiza una solicitud de bus para una línea de caché que tiene un procesador del grupo, el directorio transmite la señal a todos los procesadores del nodo en lugar de solo a los cachés que la contienen, lo que genera tráfico innecesario a los nodos que no tienen los datos. en caché. [2]
En este caso, la entrada del directorio usa 1 bit para un grupo de procesadores para cada línea de caché. Para el mismo ejemplo que el formato vectorial de bits completo, si consideramos 1 bit para 8 procesadores como un grupo, la sobrecarga de almacenamiento será 128 / (32 × 8) = 50%. Esta es una mejora significativa con respecto al formato Full Bit Vector.
Formato de directorio disperso
Un caché solo almacena un pequeño subconjunto de bloques en la memoria principal en un momento determinado. Por lo tanto, la mayoría de las entradas del directorio pertenecerán a bloques no almacenados en caché. En el formato de directorio disperso, el desperdicio se reduce almacenando solo los bloques almacenados en caché en el directorio. [2] Considere un procesador con un tamaño de caché de 64 KB con un tamaño de bloque de 32 bytes y el tamaño de la memoria principal de 4 MB. El número máximo de entradas que puede tener el directorio en el formato de directorio disperso es 2048. Si el directorio tiene una entrada para todos los bloques en la memoria, el número de entradas en el directorio será 131072. Por lo tanto, es evidente que la mejora de almacenamiento proporcionado por el formato de directorio disperso es muy significativo.
Formato de árbol binario equilibrado en números
En este formato el directorio está descentralizado y distribuido entre las cachés que comparten un bloque de memoria. Los 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 tiene la información del nodo raíz (HEAD) y el campo Contador de uso compartido (SC). El campo SC tiene el número de cachés que comparten el bloque. Cada entrada de caché tiene punteros a las siguientes cachés compartidas conocidas como L-CHD y R-CHD. Una condición para este directorio es que el árbol binario debe estar equilibrado en número, 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 en número. [4]
Formato de directorio encadenado
En este formato, la memoria contiene el puntero del directorio al último caché que accedió al bloque y cada caché tiene el puntero al caché anterior que accedió al bloque. Entonces, cuando un procesador envía una solicitud de escritura a un bloque en la memoria, el procesador envía invalidaciones a lo largo de la cadena de punteros. En este directorio, cuando se reemplaza un bloque de caché, debemos recorrer la lista para cambiar el directorio, lo que aumenta la latencia . Para evitar esto, ahora se usan ampliamente listas doblemente enlazadas en las que cada copia en caché tiene punteros a la caché anterior y siguiente que accede al bloque. [5]
Formato de puntero limitado
El formato de puntero limitado utiliza un número determinado de punteros para realizar un seguimiento de los procesadores que almacenan en caché los datos. Cuando un nuevo procesador almacena en caché un bloque, se elige un puntero libre de un grupo para apuntar a ese procesador. Hay algunas opciones para manejar casos en los que el número de participantes excede el número de punteros libres. Un método consiste en invalidar uno de los participantes, utilizando su puntero para el nuevo solicitante, aunque esto puede resultar costoso en los casos en los que un bloque tiene una gran cantidad de lectores, como un candado. Otro método es tener un grupo separado de punteros gratuitos disponibles para todos los bloques. Este método suele ser eficaz ya que la cantidad de bloques compartidos por una gran cantidad de procesadores no suele ser muy grande. [2]
Referencias
- ↑ a b Reihnhart, Steven; Basu, Arkaprava; Beckmann, Bradford; Hill, Mark (11 de julio de 2013). "Coherencia del directorio CMP: una granularidad no sirve para todos" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ a b c d e Solihin, Yan (9 de octubre de 2015). Fundamentos de la arquitectura multinúcleo paralela . Raleigh, Carolina del Norte: Solihin Publishing and Consulting, LLC. págs. 331–335. ISBN 978-1-4822-1118-4.
- ^ a b Laudon, James; Lenoski, Daniel (1 de junio de 1997). SGI Origin: un servicio ccNUMA altamente escalable . Actas del 24º simposio internacional anual sobre arquitectura informática.
- ^ Seo, Dae-Wha; Cho, Jung Wan (1 de enero de 1993). "Esquema de coherencia de caché basado en directorios utilizando árbol binario equilibrado en número". Microprocesamiento y Microprogramación . 37 (1): 37–40. doi : 10.1016 / 0165-6074 (93) 90011-9 .
- ^ Chaiken, D .; Fields, C .; Kurihara, K .; Agarwal, A. (1 de junio de 1990). "Coherencia de caché basada en directorios en multiprocesadores a gran escala". Computadora . 23 (6): 49–58. CiteSeerX 10.1.1.461.8404 . doi : 10.1109 / 2.55500 . ISSN 0018-9162 .