Arquitecturas Paralelas: Redes de Interconexión, Multiprocesadores y Técnicas de Optimización del Rendimiento

Algoritmos de Encaminamiento en Redes

Algoritmo DOR (Dimension Order Routing)

Es el principal algoritmo determinista. Se sigue siempre el mismo orden (por ejemplo, se finaliza primero la dimensión X y luego la dimensión Y).

Algoritmo Oeste Primero

Es un algoritmo determinista. Evita la formación de bucles entre dimensiones y no presenta abrazos mortales (deadlocks).

Redes Virtuales

Este enfoque genera canales virtuales en cada dirección. Los paquetes viajan en uno de los canales virtuales, cada uno por uno diferente, lo que implica que no hay conflictos.

Métricas y Topologías de Redes de Interconexión

Métricas Comunes

• G: Grado del nodo
• D: Diámetro de la red
• AdB: Ancho de Bisección
• C: Coste de la red

Características de Diversas Topologías

Red Barrel (N=2ⁿ)

• G: 2n-1
• D: 2
• AdB: N-2+N/2
• C: N/2+N·(n-1)

Árbol (N=(2ⁿ)-1)

• G: 3
• D: 2(n-1)
• AdB: 1
• C: N-1

Árbol Grueso (N=(2ⁿ)-1)

• G: 2^(n-1)
• D: 2(n-1)
• AdB: G/2
• C: (n-1)·2^(n-1)

Anillo Cordal

• Para un anillo cordal con G=4, el diámetro D=4.

Malla (N=dⁿ)

• G: 2n
• D: n(d-1)
• AdB: d^(n-1)
• C: (d-1)nd^(n-1)

Estrella

• G: 1
• D: 2
• AdB: 1
• C: N-1

Toro (N=dⁿ)

• G: 2n
• D: n · parte entera(d/2)
• AdB: 2d^(n-1)
• C: 2dⁿ

Array Lineal

• G: 2
• D: N-1
• AdB: 1
• C: N-1

Toro 3D (N=kⁿ, usualmente con n=3 para tres dimensiones)

• G: 2n (usualmente 6 para 3D)
• D: n · parte entera(k/2)
• AdB: 2k^(n-1)
• C: 2kⁿ

Anillo

• G: 2
• D (bidireccional): N/2
• D (encaminamiento unidireccional): N-1
• AdB: 2
• C: N

Hipercubo (N=2ⁿ)

• G: n
• D: n
• AdB: 2^(n-1)
• C: n·2^(n-1)

Cube-Connected Cycles (CCC) (N=n·2ⁿ)

• G: 3
• D: 2n
• AdB: 2^(n-1)
• C: 3n·2^(n-1)

Redes de Interconexión Dinámicas Multietapa

Red Omega

Utiliza contactos binarios (2 entradas y 2 salidas) y puede conectar cualquier entrada con cualquier salida. Existen dos tipos principales según su aplicación:

• Multicomputador: A un lado se encuentran los procesadores y al otro la memoria. El número de procesadores y módulos de memoria suele ser potencia de 2.
• Monoprocesador: A ambos lados se encuentran procesadores.

La conexión entre etapas se realiza mediante rotación binaria. En el contacto, la señal de selección indica cómo conectar la entrada (IN) a la salida (OUT).

Características de la Red Omega:

• Número de etapas: log₂N
• Rutado (Encaminamiento): Para dirigir un paquete de una entrada (IN) a una salida (OUT), solo se considera la dirección de destino. Cada bit de la dirección de destino (expresada en binario) gobierna una etapa del encaminamiento, lo que simplifica notablemente este proceso.

Red Mariposa (Butterfly Network)

Un ejemplo de red Mariposa podría configurarse con 2 etapas y contactos de 4x4, permitiendo conectar 16 entradas (IN) con 16 salidas (OUT). La interconexión es simétrica. Para el encaminamiento, se utilizan 2 bits por etapa, sumando un total de 4 bits para las direcciones de entrada/salida, los cuales se dividen en parejas (cada pareja de bits corresponde a una etapa).

Sistemas Operativos para Entornos Paralelos y Distribuidos

Sistema Operativo para Multiprocesador de Memoria Compartida

Presenta un acoplamiento fuerte tanto a nivel de hardware como de software. El sistema se percibe como una única máquina.

Sistema Operativo de Red

Caracterizado por un acoplamiento débil. Permite realizar operaciones en máquinas remotas, como operaciones de Entrada/Salida (E/S), a través del adaptador de red.

Sistema Operativo Distribuido

Combina un acoplamiento fuerte a nivel de software con un acoplamiento débil a nivel de hardware. Una máquina multicomputador se visualiza como una única máquina virtual.

Middleware

El middleware surge ante la necesidad de funcionalidades de sistema operativo distribuido que no siempre están presentes de forma nativa. Actúa como una capa de software intermedia entre el sistema operativo base y el nivel de aplicación.

Funcionalidades y Ejemplos:

• Añade al sistema operativo existente la funcionalidad propia de un sistema operativo distribuido.
• En algunos casos, implica añadir extensiones al sistema operativo que requieren su recompilación. Un ejemplo es MOSIX, que se añade a Linux; tras recompilar, se obtiene un sistema operativo distribuido que puede repartir tareas entre procesadores y balancear la carga.
• PVM (Parallel Virtual Machine): Es un sistema de paso de mensajes que ofrece servicios adicionales y mayor tolerancia a fallos en comparación con enfoques más básicos.
• MPI (Message Passing Interface): Considerado superior a PVM en algunos aspectos, ofrece una librería más completa pero, en sus versiones estándar, no soporta la tolerancia a fallos de forma inherente.
• Balanceo de carga: En sistemas como PVM o MPI, el balanceo de carga explícito puede no existir; la aproximación más cercana es la generación dinámica de procesos hijos para distribuir el trabajo.

Arquitecturas Multiprocesador

SMP (Symmetric Multiprocessing - Multiprocesamiento Simétrico)

Típicamente con un número de nodos inferior a 64. Cada nodo se compone de un procesador y su caché, compartiendo todos ellos una memoria común. Para sistemas con más de 64 nodos, se suelen emplear otras arquitecturas.

Mecanismos de Interconexión en SMP:

• Bus: Es una conexión dinámica de bajo coste, sencilla y económica. La coherencia de caché se mantiene mediante protocolos de observación (snooping) del bus.
• Crossbar (Matriz de Conmutación): Proporciona una conexión de alto rendimiento, pero es más cara y compleja. La coherencia de caché se gestiona mediante políticas de directorios. Un ejemplo de sistema con crossbar es el ALPHA SERVER 8400.

MPP (Massively Parallel Processing - Procesamiento Masivamente Paralelo)

Sistemas como el Intel Paragon podían alcanzar los 2000 nodos. En MPP, los nodos no comparten hardware (memoria distribuida). Utilizan redes estáticas.

Características del Encaminamiento en MPP (ej. en Mallas):

• El encaminamiento es relativamente fácil (por ejemplo, en una malla se pueden necesitar dos contadores para los saltos en el eje X y en el eje Y).
• Suele permitir un cambio de dirección (por ejemplo, al finalizar los saltos en el eje X, se comienza con los del eje Y - algoritmo XY).
• Este tipo de encaminamiento es óptimo (siempre la ruta más corta), determinista y mínimo.
• Sin embargo, puede ser propenso a la congestión en caminos con mucho tráfico, llevando a la saturación de la red (por ejemplo, una malla puede saturarse).

Optimización del Rendimiento: Pipelining y Procesamiento Vectorial

Pipelining (Segmentación)

• Tiempo de ejecución sin pipeline: T = k · n · t
• Tiempo de ejecución con pipeline (k etapas): T = n · t + (k-1) · t

(Donde 'k' es el número de etapas del pipeline, 'n' el número de instrucciones/tareas, y 't' el tiempo por etapa).

Super Pipelining

• Tiempo de ejecución con superpipeline: T = n · t + t · (k-m)/m

Nota: La fórmula de superpipeline T = n · t + t · (k-m)/m puede requerir clarificación adicional sobre la definición de los términos, especialmente 'm'.

Procesamiento Vectorial vs. SIMD

En el procesamiento vectorial, las unidades funcionales están fuertemente solapadas, utilizando pipelines muy profundos.

En SIMD (Single Instruction, Multiple Data), el tratamiento vectorial de los datos se consigue mediante múltiples unidades funcionales escalares que operan en paralelo (en lugar de solapadamente como en las arquitecturas vectoriales puras). Un sistema SIMD puede tener un multiprocesador dedicado al cálculo vectorial, mientras que el resto de las operaciones son escalares.