Escalabilidad y Rendimiento en Sistemas MIMD: Comunicación y Coherencia de Caché

1. Escalabilidad

La escalabilidad se refiere a la capacidad de un sistema para aumentar sus prestaciones conforme se le añaden recursos, tales como procesadores, memoria o discos. En el contexto de sistemas MIMD (Multiple Instruction, Multiple Data), hay cuatro aspectos clave a considerar:

• Productividad (throughput): Idealmente, al aumentar el número de procesadores, la productividad debería incrementarse de manera proporcional.
• Latencia: En una transferencia entre nodos, lo ideal es que la latencia se mantenga constante, incluso al aumentar el número de procesadores.
• Coste: El coste debería aumentar de forma moderada al escalar el sistema.
• Tamaño físico: No existe un estándar fijo, pero es un factor a tener en cuenta.

¿Qué define a una máquina escalable? En una máquina escalable, los procesadores y los módulos de memoria se interconectan mediante enlaces (links) a través de conmutadores (switches).

• Conmutador: Un conmutador es un dispositivo que conecta un número limitado de entradas a un número limitado de salidas. Sin embargo, el coste de un conmutador crece significativamente al aumentar su grado (número de entradas y salidas), lo que puede no compensar en términos de productividad.
• Red de conexión: Una red de conexión está formada por varios conmutadores de grado fijo conectados mediante enlaces. Ofrece una mejor escalabilidad al permitir el aumento del número de conmutadores y enlaces. Se requiere un mecanismo de control para gestionar la red.

1.1. MIMD Escalables de Memoria Centralizada Compartida

Estructura Dancehall:

• Las cachés son necesarias, pero presentan el problema de la coherencia.
• El ancho de banda de la red es escalable con el número de procesadores.
• Debe permitir el aumento de los accesos a memoria, la comunicación entre procesadores y el tráfico de coherencia.

1.2. MIMD Escalables de Memoria Distribuida

Esta es la organización más común en los MIMD escalables, ya que ofrece mayor escalabilidad que la arquitectura Dancehall. Cada nodo consta de:

• Uno o más procesadores.
• Memoria local.
• Asistente de comunicaciones.

Los componentes de un mismo nodo se comunican generalmente a través de un bus de alto rendimiento.

2. Escalabilidad en los MIMD

2.1. Escalabilidad de la Productividad

Para lograr una buena escalabilidad de la productividad, es necesario que la red que conecta los nodos, los protocolos de transferencia de datos entre nodos y las técnicas de sincronización sean escalables. Las características típicas de un sistema escalable incluyen:

• No hay un arbitraje global de los recursos.
• Se pueden producir un gran número de transacciones concurrentes (iniciadas independientemente). La red debe proporcionar un gran número de caminos entre los nodos.
• Las transacciones generalmente no son visibles a todos los nodos, solo a los involucrados en la transacción.

2.2. Escalabilidad de la Latencia

La latencia de una transferencia de n bytes entre dos nodos conectados a la red se puede expresar como:

T(n) = Overhead + Channel Time + Routing Delay

Donde:

• Overhead: Tiempo de procesador empleado en iniciar o finalizar la transferencia. Puede ser fijo o aumentar con n si el procesador debe copiar los datos para la transferencia.
• Channel time: n/B, donde B es el ancho de banda del canal más "estrecho" del camino entre los dos nodos. Un canal es el enlace entre dos conmutadores o entre un conmutador y un nodo de la red, incluyendo el transmisor (que convierte la información digital en analógica) y el receptor (que realiza la conversión inversa).
• Routing delay: Retardo debido al enrutamiento. Depende del número de pasos del camino (hops), que es el número de canales por los que pasa el camino. La longitud del camino aumenta al aumentar el número de nodos, lo que incrementa el retardo de enrutamiento. Normalmente, se utilizan métodos de enrutamiento en los que el retardo por cada hop es fijo. Sin embargo, hay métodos en los que ese retardo crece con el número de bytes del mensaje transferido, lo que genera mayores retardos de enrutamiento para mensajes más grandes.

Ejemplo:

• Overhead: 1 μs por mensaje.
• Ancho de banda de los canales: 64 MB/s.
• Tamaño de la transferencia: 128 bytes.
• Routing delay: 200 ns por hop.
• Longitud de camino en una red de m nodos: log₂m.

¿Cómo aumenta la latencia al pasar de 64 a 1024 nodos?

T1(128) = 1 μs + 128 B / (64 MB/s) + (log2 64) * 0.2 μs = 4.2 μs

T2(128) = 1 μs + 128 B / (64 MB/s) + (log2 1024) * 0.2 μs = 5 μs

T2(128) / T1(128) = 5 / 4.2 ≈ 1.19

El número de nodos se ha multiplicado por 16 y la latencia solo ha aumentado un 19%.

2.3. Escalabilidad del Coste y Física

Un criterio razonable para una buena escalabilidad del coste es que a mayor velocidad, mayor coste. En cuanto al tamaño físico, un menor tamaño implica mayor velocidad (enlaces más cortos y rápidos), mientras que un mayor tamaño permite el uso de componentes comerciales más baratos, lo que reduce el coste y el tiempo de diseño.

2.4. Escalabilidad y Diseño

Para un diseño adecuado, se debe encontrar el equilibrio entre el rendimiento computacional y de comunicaciones, y el coste de diseño y producción. Tanto el hardware como el software deben escalar correctamente. Se deben evitar las serializaciones, colisiones, el mal reparto de la carga de trabajo entre los procesadores, etc.

3. Paso de Mensajes

La comunicación entre procesadores se realiza mediante operaciones de E/S. Las más comunes son variantes de send y receive. La combinación de un send y un receive concordantes (según la regla del receive):

• Establece un canal lógico de comunicación entre los dos procesos.
• Implica la copia del valor de X en Y.
• Conlleva una sincronización entre los dos procesos.

Existen variados protocolos de implementación del paso de mensajes (síncronos, asíncronos, de dos o de tres fases...). Un conjunto de primitivas de paso de mensajes frecuentemente utilizado es una parte del estándar MPI (Message Passing Interface), que incluye funciones para:

• Comunicación punto a punto (send-receive).
• Comunicación colectiva (por ejemplo, un procesador envía mensajes a todos los procesadores).

El paso de mensajes es propio de los clústeres. Sin embargo, hay un uso creciente de modelos de programación de espacios de direcciones compartidas en MIMD escalables.

• Se puede crear un modelo de programación de paso de mensajes sobre un hardware de direcciones compartidas: Send lee y receive escribe en un búfer compartido.
• Se puede crear un modelo de programación de direcciones compartidas sobre un hardware de paso de mensajes, pero es más difícil y el rendimiento puede ser inaceptable.

4. Redes de Conexión

Se distinguen dos tipos de redes:

• Redes directas (estáticas o distribuidas): Cada conmutador forma un nodo de la red junto a uno o varios dispositivos (procesadores, memorias). Son propias de computadores MIMD de memoria distribuida.
• Redes indirectas (dinámicas o centralizadas): La red forma un subsistema a algunos de cuyos conmutadores se conectan los nodos que necesitan comunicarse (procesadores, memorias, periféricos). Son típicas en los MIMD de memoria compartida.

Estrategias de conmutación:

• Conmutación de circuitos: Se reserva un camino entre el nodo fuente y el destino hasta que el mensaje es transferido. Es apropiado solo para mensajes largos.
• Conmutación de paquetes: El mensaje se divide en una secuencia de paquetes. Cada paquete incluye datos e información de control que permite a los conmutadores dirigir el paquete por un camino que termina en el nodo destino. Ofrece una mejor utilización de los recursos de la red, ya que quedan libres cuando ningún paquete los utiliza. Es la estrategia más utilizada.

Redes escalables en MIMD de memoria compartida:

• Redes multietapa (de bus múltiple): Son las más usadas.
• Bus compartido: El ancho de banda es poco o nada escalable. Poco aconsejables.
• Red de barras cruzadas: El escalado del coste es malo. Poco aconsejables.

Redes directas: magnitudes importantes

• Indicadores de coste:
  • Grado de un nodo: Número de nodos con los que está directamente conectado.
  • Número total de enlaces de la red.
• Indicadores de latencia:
  • Diámetro: La mayor de las longitudes de los caminos más cortos entre dos nodos.
  • Distancia media entre nodos.
• Indicador de ancho de banda:
  • Bisección: Mínimo número de enlaces que atraviesa una división imaginaria de la red en dos partes con igual número de nodos (+/- 1).

Redes directas: topología de anillo

• Bajo coste y rendimiento.
• Ligeramente más altos si es bidireccional:
  • Grado: 2 (+1).
  • Número de enlaces: N (+N).
  • Diámetro: N/2.
  • Bisección: 2.
• Poco escalable.
• Componente de otras topologías.

Redes directas: topología de malla y toro

• Mayores costes y rendimiento que el anillo.
• 2 o 3 dimensiones en sistemas comerciales.
• Número de enlaces: O(N).
• Distancia media: O(√N).

Redes directas: topología de hipercubo de dimensión n (n=log₂ N)

• Grado: n.
• Número de enlaces: O(N * log₂ N).
• Distancia media: O(n).

Redes directas e indirectas: topologías de árbol

• Un árbol simple tiene una bisección pequeña: Bisección = 1 en un árbol binario.
• Nodo raíz: probable cuello de botella.
• El problema se resuelve con un árbol grueso:
  • El grado de los nodos es mayor cuanto más cerca del nodo raíz: ancho de banda entre el nivel j y el nivel j+1 es igual para todo j.
  • Los nodos con mayor grado se implementan usando varios conmutadores del mismo grado.
  • Muchos mensajes no pasan por el nodo raíz: se puede adelgazar el árbol grueso como en la Connection Machine CM-5.

Redes directas: implementación

• Suelen ser bidimensionales (circuito integrado, circuito impreso).
• Implementar topologías con más de 3 dimensiones conlleva enlaces más largos (también ocurre esto con los enlaces de los nodos cercanos a la raíz de un árbol grueso).
• El número de pines de un nodo formado por un chip o un circuito impreso limita el ancho de banda.

5. Coherencia de Caché Escalable: Protocolos Basados en Directorio

Los protocolos de espionaje no son escalables porque los mensajes de coherencia se difunden a todas las cachés, lo que provoca la saturación de la red y/o las cachés. Por ello, aparecen los protocolos de coherencia de caché basados en directorio:

• Los mensajes de coherencia no se envían a todas las cachés, solo a las que tienen copia del bloque.
• En la memoria principal, se forma un directorio con la información de cada uno de los bloques que pueden copiarse en caché (en qué cachés hay copias del bloque y cuál es su estado). El directorio se distribuye entre los distintos módulos de la memoria para evitar que se convierta en un cuello de botella.
• La información sobre cada bloque está ubicada siempre en un mismo sitio conocido. Esto permite evitar la difusión de mensajes de coherencia, que es la principal ventaja, ya que la difusión impide la escalabilidad.

Estos protocolos son la solución dominante para conseguir coherencia de caché escalable. Cuando cada nodo es en sí mismo un multiprocesador, se puede implementar una jerarquía de dos niveles de protocolos.

Jerarquías de Dos Niveles de Protocolos

Se utiliza un protocolo interno para la coherencia dentro del nodo y otro externo para la coherencia entre distintos nodos. Lo más habitual es que el interno sea de espionaje y el externo basado en directorio, aunque hay más opciones. Conectar pequeños multiprocesadores mediante una red es una opción atractiva porque se pueden usar multiprocesadores comerciales, además de menos nodos en la red y en el protocolo externo de coherencia de caché. Como la comunicación externa se ve reducida, la comunicación es más eficiente dentro de cada nodo.

5.1. Directorios Full-Map

Hay una entrada del directorio por cada bloque. Consta de:

• N bits de presencia (N = número de nodos).
• Un bit de ensuciado (dirty bit, inconsistencia única).
• Si el bit de ensuciado = 0: Los bits de presencia que valgan 1 indican los nodos en cuyas cachés hay copias válidas del bloque.
• Si el bit de ensuciado = 1: Solo un bit de presencia vale 1, e indica el nodo propietario del bloque (el único que tiene en caché una copia actualizada y permiso para escribir en él).

Se precisan dos bits por cada línea de caché:

• Validez: Indica si la copia es válida o no.
• Privacidad: Indica si hay o no permiso de escritura en caché (para estar activo, el dirty bit tiene que estar a 1).

5.1.1. Ejemplo

• Fallo (de cualquier tipo) o escritura en una copia válida: Localizar en el directorio (en memoria principal) la entrada correspondiente al bloque.
• Fallo de lectura y dirty bit = 0:
  • El nodo home (el que contiene la parte de memoria principal con la entrada del directorio) envía el bloque al nodo local (el que hace la petición).
  • En la entrada del directorio, el bit de presencia del nodo local se pone a 1.
  • En el nodo local, el bit de validez del bloque se pone a 1 y el de privacidad a 0.
• Fallo de lectura y dirty bit = 1:
  • El nodo home solicita una copia del bloque a la caché propietaria del mismo.
  • Esta envía una copia del bloque al nodo home, que lo copia en la memoria principal.
  • La caché propietaria deja de serlo: su bit de privacidad y el bit de ensuciado se ponen a 0.
  • Se pone a 1 el bit de presencia de la caché local.
  • La memoria envía una copia del bloque a la caché local.
  • Cuando esta recibe el bloque, pone a 1 el bit de validez y a 0 el de privacidad.
• Acierto de escritura sin permiso de escritura (bit de privacidad = 0):
  • El nodo local envía una petición de permiso de escritura (privacidad) al nodo home.
  • Este envía señales de invalidación a los nodos con copia del bloque, excepto al nodo local (nodos remotos).
  • Cada uno de ellos pone a 0 el bit de validez de su bloque y devuelve una señal de reconocimiento al home.
  • Cuando este recibe las señales, pone a 0 los bits de presencia del bloque en los nodos remotos, pone a 1 el bit de ensuciado y envía permiso de escritura al nodo local.
  • Este, al recibir permiso de escritura, pone a 1 su bit de privacidad y escribe en su caché.
• Fallo de escritura: Las acciones necesarias son las de un fallo de lectura (para llevar una copia al nodo local) más las de un acierto de escritura sin permiso (para adquirir permiso de escritura, escribir en la caché local e invalidar las copias en otras cachés).
• Acierto de lectura o acierto de escritura con permiso de escritura: Solo hay que hacer la operación en caché.

Reemplazo de bloque sucio:

• El bloque se escribe en la memoria principal.
• En la entrada del directorio, se ponen a 0 el bit de ensuciado y el bit de presencia del nodo local.

Reemplazo de bloque válido:

• Se envía un mensaje al directorio para que ponga a 0 el bit de presencia correspondiente.
• No se envía el mensaje: cuando otro nodo escriba en el bloque, se pondrá a 0 el bit de presencia.

5.1.2. Problema Principal

El problema principal es el tamaño elevado del directorio: (bloques en memoria principal) * (N+1) --> O(N2).

Ejemplos con bloques de 64 bytes (ver tabla):

5.2. Directorios Limitados

Aumentar el tamaño de bloque o ubicar más procesadores en cada nodo reduce el tamaño del directorio, pero sigue siendo del orden de N². Con directorios limitados, cada entrada tiene un número fijo, K, de punteros a nodos (más el bit de ensuciado):

• Tamaño de una entrada = 1 + K [log₂ N]. En la práctica, K ≤ 5.
• Tamaño del directorio = O(N * log₂ N). Mejor escalabilidad.

El funcionamiento es el mismo, salvo si más de K cachés quieren tener copia de un bloque: cuando un nodo quiere leer en un bloque del que hay K copias válidas en otros nodos, hay que invalidar una de esas copias (desalojo o eviction) y su puntero pasa a señalar a la caché que pide la lectura.

Ejemplo con K = 5 y bloques de 64 bytes:

Están justificados porque medidas del comportamiento de los programas muestran que en muchas aplicaciones el número de copias válidas de cada bloque es pequeño, y muy pequeño para las escrituras. Por todo ello, está justificado que K ≤ 5.

La implementación detallada de los protocolos basados en directorio plantea diversos problemas derivados del hecho siguiente: que un mensaje se envíe antes a la red no implica que llegue antes a su destino (en la red de un solo bus, sí). Esto trae problemas de serialización de las operaciones, no atomicidad de las transiciones de estado, etc. Los protocolos sencillos no son los más escalables y un buen diseño ha de conseguir un alto rendimiento, preservando la corrección y limitando la complejidad.

6. Sincronización en Computadores MIMD Escalables

La espera activa no es eficiente cuando muchos procesadores compiten por la misma llave: se genera competencia por el directorio (o por el bus) al que hay que acceder secuencialmente. Esta serialización aumenta la latencia media para conseguir la llave.

Algunas opciones:

• Introducir esperas tras cada fallo en adquirir la llave (es eficiente que la espera se duplique tras cada fallo).
• Hacer una cola de procesos que esperan: cuando se libera la llave, se activa el primer proceso de la cola.