Computador Paralelo (Multiprocesador)

Un computador paralelo, también conocido como multiprocesador, es un sistema informático que cuenta con múltiples unidades de procesamiento. Estas unidades trabajan de forma cooperativa y necesitan comunicarse entre sí de manera constante. La creación de estos computadores se remonta a una época anterior a la preocupación por el consumo de potencia, impulsada por factores como:

  • Aumento del rendimiento: La necesidad de procesar grandes volúmenes de datos de forma más rápida.
  • Eficiencia: La capacidad de resolver múltiples tareas por unidad de tiempo.
  • Replicación: La necesidad de replicar la información para aumentar la tolerancia a fallos, almacenándola en más de una ubicación.

Se dice que un sistema es escalable si, al aumentar el número de procesadores, otros factores como el ancho de banda, la memoria, etc., también aumentan proporcionalmente. Si algún elemento se convierte en un cuello de botella, es decir, se satura, entonces el sistema no es escalable.

Arquitecturas de Memoria

Arquitecturas de Memoria Compartida

En las arquitecturas de memoria compartida, existe un espacio de direcciones compartido entre todos los procesos. El objetivo principal es la productividad. Las comunicaciones son implícitas, realizándose a través de operaciones LOAD/STORE. Para las sincronizaciones, se puede invocar al sistema operativo o utilizar operaciones atómicas.

Arquitecturas de Paso de Mensajes

En las arquitecturas de paso de mensajes, no hay memoria compartida. Las comunicaciones individuales son punto a punto, lo que significa que un proceso solo se comunica con otro proceso específico cuando es necesario.

Redes de Interconexión

Una red de interconexión está compuesta por los siguientes elementos:

  • Enlaces (cables): Medio físico que permite la transmisión de la información.
  • Conmutadores (switches): Repetidores que deciden el camino que debe seguir el mensaje en función de su destino.
  • Interfaces de red: Encargadas de inyectar la información en la red y gestionar la comunicación.

Descripción Estructural

  • Mensaje: Unidad lógica de comunicación, que puede estar dividida en uno o más paquetes.
  • Paquete: Unidad de transferencia entre interfaces de red.
  • Phit (w): Unidad de transferencia por ciclo de reloj.
  • Enlace punto a punto: Conecta directamente dos unidades de procesamiento. Posee colas FIFO y de otro tipo para almacenamiento, un gestor de colas y un planificador que gestiona el envío y recepción de mensajes.

Características de un Enlace

  • Longitud: Corta si solo hay un phit en el enlace, o larga si hay varios (envío segmentado).
  • Ancho: Medido en phits (w).
  • Velocidad de señal: f = 1 / T
  • Ancho de banda: Cantidad de información que viaja por la red por unidad de tiempo. B = w*f
  • Flit (flow-control unit): Unidad de control de flujo. Un flit no puede ser más pequeño que un phit.

Conmutador

Un conmutador es un elemento que redirige la información que llega por uno de sus canales de entrada hacia uno de sus canales de salida. En algunas redes, la función de un conmutador es similar a la de un nodo procesador. Sus características principales son:

  • Grado de un conmutador/nodo (d): Número de canales de entrada y salida.
  • Implementación del conmutador interno: Cómo está construido internamente.
  • Buffers de entrada/salida.
  • Lógica de control: Determina el enrutamiento de los mensajes (canal de salida) mediante arbitraje y encaminamiento.

Red de Interconexión como Grafo

Una red de interconexión se puede representar como un grafo donde los vértices son conmutadores y nodos interconectados por canales de comunicación.

Ruta: Secuencia de nodos y canales que sigue un mensaje desde el origen hasta el destino.

Características de las Redes de Interconexión

  • Topología: Estructura de la interconexión física de la red, definida por su función de interconexión.
    • Redes regulares (diseño homogéneo) vs. Redes irregulares (diseño irregular).
    • Medio compartido: Red a la que tienen acceso más de dos nodos.
      • Estáticas: Todos los nodos están conectados directamente a un número fijo de nodos vecinos.
      • Dinámicas: No necesariamente hay conexiones con nodos vecinos; puede haber nodos no conectados directamente.
  • Conmutación: Forma en que el mensaje atraviesa la red de origen a destino.
    • Conmutación de circuitos vs. conmutación de paquetes.
    • Control de flujo: Momento en que las porciones del mensaje se mueven a lo largo de la ruta.
  • Encaminamiento: Ruta que siguen los mensajes para llegar del nodo origen al nodo destino.
    • Encaminamiento determinista: Ruta predefinida para un origen y destino dados.
    • Encaminamiento adaptativo: Considera diferentes rutas y elige en función de variables.
  • Control de flujo: Momento en que el mensaje, o sus porciones, se mueven a lo largo de la ruta.

Latencia en Redes de Interconexión

La latencia es el tiempo que tarda en enviarse un mensaje desde que el nodo emisor comienza el envío hasta que el nodo receptor lo recibe completamente. Se compone de:

  • Inicio de envío: Tiempo de preparación previo al envío.
  • Tiempo de vuelo: Tiempo que tarda el primer bit del mensaje en llegar al destino.
  • Tiempo de transmisión: Tiempo que tardan los datos en transmitirse.
  • Latencia de transporte: Tiempo que tarda el mensaje en atravesar la red sin contención y sin sobrecargas de inyección o salida. Es la suma del tiempo de vuelo y el tiempo de transmisión.
  • Latencia total: Inicio de envío + latencia de transporte + fase de recepción.

Definiciones y Propiedades

  • Grado de la red: Número de conexiones de un nodo.
  • Tamaño de la red: Número de elementos de procesamiento (nodos) conectados.
  • Número de conmutadores: Número de nodos que redirigen el tráfico.
  • Diámetro de la red: Máxima longitud de los caminos óptimos (más cortos) entre pares de elementos de procesamiento.
  • Simetría: Visión de la red que tienen los nodos. Si un nodo ve lo mismo a ambos lados, la red es simétrica; de lo contrario, es asimétrica. Una red simétrica tiene un patrón de tráfico uniforme.
  • Homogeneidad: Si todos los nodos son iguales y tienen las mismas características.
  • Regularidad: Si los nodos siguen un patrón de organización en la red y tienen el mismo grado.
  • Ancho de bisección: Número de enlaces físicos que se deben cortar para dividir la red en dos mitades iguales.
  • Ancho de banda de bisección: Cantidad de información que puede transmitirse a través del ancho de bisección.

Redes Estáticas

  • Anillo unidireccional: 4 nodos, la información fluye en un solo sentido. Grado 1, diámetro p-1, simétrico.
  • Anillo bidireccional: Similar al anterior, pero la información fluye en ambas direcciones. Grado 2, diámetro reducido.
  • Mallas: 4 funciones de interconexión (una por eje). Grado 4, diámetro 6, no simétrica.
  • Toro: Conexiones circulares entre nodos. Mismo grado para todos los nodos, simétrico, diámetro 4.
  • Hipercubo binario: Número de nodos = 2n. n funciones de interconexión. Ejemplo: Hipercubo de orden 3, nodo 4 (binario 100) se conecta con 000, 110 y 101 (0, 6 y 5).
  • Árboles binarios:
    • Árbol equilibrado: Mismo número de nodos a derecha e izquierda.
    • Árbol no equilibrado: Diferente número de nodos a derecha e izquierda.
  • Topologías híbridas: Buscan reducir el grado del nodo manteniendo un diámetro pequeño.

Redes Dinámicas

Crossbar

Un crossbar es un tipo de red que proporciona una interconexión global. Cada intersección representa un punto de conmutación. Con N entradas y M salidas, permite hasta min(M, N) interconexiones punto a punto sin contención. Propiedades:

  • Permite conexión siempre que los puertos origen y destino estén libres.
  • Coste proporcional a NxM, caro y difícil de construir.

Aplicaciones:

  • Procesadores UMA, para conectar procesadores con un módulo de memoria compartida.
  • Para construir conmutadores de otras redes de interconexión.

MIN (Multistage Interconnection Network)

Las MIN conectan dispositivos de entrada a dispositivos de salida a través de etapas compuestas por conmutadores y patrones de conexión. Cada conmutador puede conectar sus entradas con sus salidas en cualquier permutación deseada. Se usan en redes multietapa.

Modelo General de MIN

Redes Banyan: Red con una sola ruta entre origen y destino.

  • Red delta de N nodos: Subclase de Banyan con N = kn nodos, donde k es el grado de cada computador y n el número de etapas. N/k da el número de computadores, conectados como crossbars con conectividad total.
  • Permutaciones: Conexiones uno a uno entre los kn puertos que definen los patrones de interconexión entre etapas.
  • Conectividad:
    • Redes bloqueantes: Un mensaje puede impedir el establecimiento de otras conexiones.
    • Redes no bloqueantes: El conjunto de entradas puede conectarse con el conjunto de salidas simultáneamente en cualquier permutación, similar a un crossbar.

Permutaciones y Redes MIN

  • Perfect shuffle (σ): Mueve el bit más significativo a la posición menos significativa.
  • Butterfly (β): Intercambia los bits de la posición i con el menos significativo.
  • Exchange (E): Para cada posición i, complementa el bit i.

Redes MIN Relevantes

  • MIN Butterfly: Conecta los bits de la posición i con el menos significativo. Red Banyan (bloqueante), los patrones inicial y final usan permutaciones B0 (identidad).
  • MIN Omega: Los patrones de interconexión C0, C1, C2 y C3 son siempre los mismos (σ), excepto en la última (identidad). Red Banyan (bloqueante).
  • IN Beneš: Red multietapa, no es una red Banyan, evita el bloqueo. Se pueden construir redes con mayor número de elementos a partir de redes más pequeñas. N = 2n.

Técnicas de Conmutación

Conmutación de Circuitos

En la conmutación de circuitos, antes del envío del mensaje se establece la secuencia de enlaces que atravesarán los datos. Los enlaces reservados no se pueden usar para otras comunicaciones. Un mensaje de cabecera recorre el camino reservando enlaces, y al llegar al destino, se devuelve un ACK al origen por el mismo camino.

Conmutación de Paquetes

En la conmutación de paquetes, cada decisión de enrutado se toma a medida que el mensaje avanza por la red. Los enlaces no usados pueden utilizarse para otra comunicación. Existen variantes como Store-and-forward o Cut-through.

Es importante considerar la latencia, suponiendo que no hay congestión en la red. El mensaje atravesará h enlaces, el ancho de banda es B y el tiempo para decidir el siguiente enlace y establecer la conexión es Δ.

  • Latencia con conmutación de circuitos: Tcc(L,h) = hΔ + L/B (tiempo previo para decidir la ruta más tiempo de transmisión del mensaje completo).
  • Latencia con Store-and-forward: Tsf(L,h) = h(Δ + L/B) (el mensaje completo se transmite de un nodo al siguiente, luego se decide el siguiente enlace y se vuelve a transmitir; h transmisiones + h decisiones).
  • Latencia con Cut-through: Tct(L,h) = hΔ + L/B (el paquete está dividido en flits; al recibir el primer flit, se decide el siguiente enlace y se comienza la retransmisión sin esperar a los demás flits).

Contención y Bloqueo

Un problema básico en la gestión de paquetes es la contención. Toda red debe estar diseñada para evitar bloqueos. En caso de bloqueo, se necesita un mecanismo de arbitraje. Dependiendo de la técnica de conmutación, el paquete bloqueado puede almacenarse en buffers del encaminador (store-forward) o solo almacenar unos pocos flits, mientras el resto permanece en los encaminadores previos (cut-through-wormhole).

Latencia y Ancho de Banda

Mientras el ancho de banda demandado aumenta, la latencia crece hasta llegar al punto de saturación de red, donde crece exponencialmente. Un multiprocesador es un sistema cerrado: al aumentar el ancho de banda demandado, aumenta la latencia, lo que reduce el avance de los programas y, por ende, las peticiones. En resumen, aumentar el ancho de banda demandado al final acaba reduciéndolo.

Encaminamiento

El encaminamiento determina la ruta que debe seguir un mensaje desde el origen hasta el destino, buscando baja latencia, distribución de la carga, tolerancia a fallos y ausencia de interbloqueos.

Mecanismos de Encaminamiento

  • Aritmético: Determina el siguiente tramo de la ruta mediante operaciones aritméticas.
  • Selección de la ruta en origen: La información de la ruta acompaña al paquete, incrementando la longitud del mensaje.
  • Mediante tablas: Cada nodo tiene una tabla de rutas; al llegar un mensaje, se consulta la tabla para obtener el enlace de salida.

Propiedades del Encaminamiento

  • Mínimo / No mínimo: Siempre se escoge la ruta más corta o no.
  • Determinista / Adaptativo: Siempre la misma ruta de origen a destino, o la ruta varía adaptándose a las circunstancias del tráfico.

Problemas en el Encaminamiento

  • Situación de interbloqueo: Un mensaje o paquete está en espera de un evento que es imposible que ocurra.

Evitar Problemas como el Interbloqueo

  • Orden dimensional: Existen dimensiones preferentes. Los enlaces en una dimensión no pueden ser usados hasta que se han recorrido todos los enlaces necesarios en las dimensiones precedentes. Un paquete solo se mueve por una coordenada cuando llega a otra que coincide con el destino en esa dimensión.

Condiciones para que se produzca el interbloqueo:

  • Recurso compartido al que se quiere acceder simultáneamente.
  • Adquisición incremental del recurso (primero envío, luego recepción).
  • No puede haber mecanismo de expulsión.
  • Agentes de espera forman una cola circular.

Maneras de evitar el interbloqueo:

  • Imponer restricciones sobre la adquisición de un canal.
  • Aportar recursos adicionales (canales virtuales, duplicar buffers para tener una vía de escape). Un paquete que entra por un canal usa siempre el mismo, a menos que se haga un giro norte-oeste, liberando un recurso.