Optimización de sistemas de directorios

Los sistemas de directorios están compuestos por nodos conectados entre si por medio de alguna de las redes de interconexión dadas en clase. Lo importante es que dada una dirección cualquier nodo puede mandar un mensaje a cualquier otro.
Internamente un nodo está compuesto por un procesador, un trozo de memoria principal, un directorio y una memoria caché. Aunque la memoria principal tiene un espacio de direcciones completo, simulando estar unificada, cada nodo es responsable de una sección de las direcciones.

La caché de cada nodo contiene los bloques de memoria que esté usando en ese momento, ya sean propiedad suya o de otro nodo (dependiendo de la dirección del bloque).
El directorio contiene la información necesaria para la gestión de caché de los bloques propiedad de ese nodo, no de los que tenga en su caché.
En el sistema de directorio simple, el más básico, el directorio contiene por cada bloque un bit de presencia para el resto de procesadores y un bit de modificación.

Directorio del Nodo 0:

Caché del Nodo 0:

El problema es que este sistema escala mal y para demostrarlo vamos a usar el concepto de sobrecarga.

Sobrecarga

La sobrecarga nos dice cuanto espacio estamos malgastando con este sistema de directorios, es la proporción entre lo que ocupa el directorio de un bloque y lo que ocupa el propio bloque. Por ejemplo, si tenemos bloques de 4096 bytes y una red con 32768 nodos:

En este caso tenemos una sobrecarga del 200%, es decir, usamos el doble de espacio para el directorio que para la propia memoria. Para solucionar esto existen varios métodos de optimización. El más sencillo consiste en simplemente aumentar el tamaño de bloque.
Aunque las principales optimizaciones son estructurales y algo más complejas, pero se pueden entender muy bien visualmente. El problema que tenemos es que la tabla del directorio es demasiado grande, así que tenemos que reducir el número de filas o columnas.

Optimizaciones

Las optimizaciones se pueden organizar de manera muy sencilla en esta tabla, que además muestra lo limitado que es el temario de esta asignatura, tocando solamente unas pocas de las posibilidades.

Vector grueso

Vamos a agrupar varias columnas en una sola. Por ejemplo podemos hacer grupos de 2 nodos y marcar la presencia con que cualquiera de ellos lo tenga.

Lo malo es que al invalidar bloques tenemos que enviar señales de más a nodos que no lo tenían realmente.

De punteros limitados

Ya que normalmente un bloque solo va a ser usado por pocos procesadores a la vez es un desperdicio usar una columna por procesador, en vez de eso se puede guardar la dirección de unos pocos procesadores, limitando cuantos pueden tener cada bloque.

Tan solo hemos usado 15+1 bits en vez de 32+1.
Lo malo es que limitamos el número de procesadores que pueden tener un nodo, teniendo que invalidar alguno de ellos si otro quiere solicitarlo.

Basado en caché

El resto de directorios que estamos viendo están basados en memoria, pero si extendemos la idea del anterior, de punteros limitados, llegamos a la idea del directorio basado en caché. En este tipo de directorio tenemos un solo puntero que apunta al ultimo nodo que solicitó este bloque. Además, en la caché del propio nodo se almacenan también los punteros al nodo anterior y al siguiente, creando una lista doblemente enlazada que se recorre cada vez que se quiera mandar una señal.
Este modelo pierde mucho en velocidad, ya que cada señal tendrá que ser repetida varias veces entre los nodos de las listas. Pero a cambio perdemos la limitación de cuantos nodos pueden compartir un bloque y tan solo usamos una dirección para el almacenamiento.

Estructurado como caché

Funciona igual al de punteros, pero esta vez apuntando a la RAM. Limitamos el número de columnas pero ahora debemos almacenar la dirección que se está referenciando.

Lo malo de esto es que solo un número limitado de bloques podrán ser cacheables. Además tenemos que añadir tantas columnas como sean necesarias para almacenar una dirección de memoria, no confundir con cuando antes almacenábamos la dirección del procesador.