Redes de interconexión multietapa

Las redes de interconexión multietapa ( MIN ) son un tipo de redes informáticas de alta velocidad, generalmente compuestas por elementos de procesamiento (PE) en un extremo y elementos de memoria (ME) en el otro, conectados por elementos de conmutación (SE). Estos elementos de conmutación suelen estar conectados entre sí en etapas, de ahí su nombre.

Las redes MIN se utilizan normalmente en computación de alto rendimiento o paralela como interconexión de baja latencia (a diferencia de las redes de conmutación de paquetes tradicionales ), aunque también podrían implementarse sobre una red de conmutación de paquetes. Si bien la red se utiliza generalmente para enrutamiento, también podría utilizarse como coprocesador para los procesadores reales en tareas como la ordenación , el desplazamiento cíclico (como en una red de mezcla perfecta ) y la ordenación bitónica .

Las redes de interconexión se utilizan para conectar nodos, que pueden ser un solo procesador o un grupo de procesadores, con otros nodos.

Las redes de interconexión se pueden clasificar según su topología. La topología es el patrón en el que un nodo se conecta con otros nodos.

Existen dos tipos principales de topología: estática y dinámica.

Las redes de interconexión estáticas están cableadas de forma fija y no pueden modificar su configuración. Una interconexión estática regular se utiliza principalmente en redes pequeñas compuestas por nodos débilmente acoplados. La estructura regular implica que los nodos están dispuestos de forma específica y que dicha forma se mantiene a lo largo de toda la red.

Algunos ejemplos de interconexiones regulares estáticas son: ^{[ 1 ] [ 2 ]}

• Red completamente conectada

  

  En una red de malla, múltiples nodos están interconectados. Cada nodo de la red está conectado a todos los demás. Esta disposición permite una comunicación fluida de los datos entre los nodos. Sin embargo, el elevado número de conexiones genera una gran sobrecarga de comunicación.
• Autobús compartido

  

  Esta topología de red implica la conexión de los nodos entre sí a través de un bus. Cada nodo se comunica con todos los demás mediante el bus. La utilidad del bus garantiza que no se envíen datos al nodo incorrecto. Sin embargo, el tráfico del bus es un parámetro importante que puede afectar al sistema.
• Anillo

  

  Esta es una de las formas más sencillas de conectar nodos entre sí. Los nodos se conectan formando un anillo. Para que un nodo se comunique con otro, debe enviar mensajes a su vecino. Por lo tanto, el mensaje de datos pasa por una serie de nodos antes de llegar a su destino. Esto incrementa la latencia del sistema.
• Árbol

  

  Esta topología implica la conexión de los nodos para formar un árbol. Los nodos se conectan para formar clústeres, y estos, a su vez, se conectan para formar el árbol. Esta metodología incrementa la complejidad de la red.
• Hipercubo

  

  Esta topología consiste en conexiones de los nodos para formar cubos. Los nodos también están conectados con los nodos de los demás cubos.
• Mariposa

  

  Esta es una de las conexiones más complejas entre los nodos. Como se muestra en la figura, existen nodos conectados y ordenados según su rango. Están organizados en forma de matriz.

En las redes de interconexión dinámica, los nodos se interconectan mediante una matriz de elementos de conmutación simples. ^{[ 3 ]} Esta interconexión puede modificarse mediante algoritmos de enrutamiento, de modo que la ruta de un nodo a otros nodos puede variar. Las interconexiones dinámicas se pueden clasificar como:

• Red de interconexión de una sola etapa
• Red de interconexión multietapa
• Conexiones de interruptores de barra transversal

En una matriz de conmutación de barras cruzadas, existe una ruta dedicada desde un procesador a otros procesadores. Por lo tanto, si hay n entradas y m salidas, necesitaremos n*m conmutadores para implementar una matriz de barras cruzadas.

A medida que aumenta el número de salidas, el número de conmutadores aumenta en un factor de n. Para redes grandes, esto será un problema.

Una alternativa a este plan es el cambio gradual.

En una red de interconexión de una sola etapa, los nodos de entrada están conectados a la salida a través de una única etapa de conmutadores.

La figura muestra un conmutador de una sola etapa de 8*8 que utiliza intercambio aleatorio .

Como se puede observar, con una sola mezcla, no todas las entradas llegan a todas las salidas. Se requieren varias mezclas para que todas las entradas se conecten con todas las salidas.

Una red de interconexión multietapa se forma mediante la conexión en cascada de varios conmutadores de una sola etapa. Estos conmutadores pueden utilizar su propio algoritmo de enrutamiento o ser controlados por un enrutador centralizado para formar una red completamente interconectada.

Las redes de interconexión multietapa se pueden clasificar en tres tipos: ^{[ 4 ]}

1. Sin bloqueo: Una red sin bloqueo puede conectar cualquier entrada inactiva a cualquier salida inactiva, independientemente de las conexiones ya establecidas en la red. La interconexión de barras cruzadas es un ejemplo de este tipo de red.
2. Red reconfigurable sin bloqueo: Este tipo de red puede establecer todas las conexiones posibles entre entradas y salidas reorganizando sus conexiones existentes.
3. Bloqueo: Este tipo de red no puede realizar todas las conexiones posibles entre entradas y salidas. Esto se debe a que una conexión entre una entrada libre y otra salida libre está bloqueada por una conexión existente en la red.

La red sin bloqueo requiere el mayor número de elementos de conmutación, seguida de la red sin bloqueo reconfigurable. La red con bloqueo utiliza el menor número de elementos de conmutación.

Existen varios tipos de redes de interconexión multietapa.

Red Omega

Una red Omega consta de múltiples etapas de 2*2 elementos de conmutación. Cada entrada tiene una conexión dedicada a una salida. Una red Omega N*N tiene log ₂ (N) etapas y N/2 elementos de conmutación en cada etapa para una mezcla perfecta entre etapas. Por lo tanto, la red tiene una complejidad de 0(N log(N)). Cada elemento de conmutación puede emplear su propio algoritmo de conmutación. Consideremos una red Omega 8*8. Hay 8! = 40320 mapeos uno a uno de entrada a salida. Hay 12 elementos de conmutación para una permutación total de 2^12 = 4096. Por lo tanto, es una red de bloqueo.

Red Clos

Una red Clos utiliza tres etapas para conmutar entre N entradas y N salidas. En la primera etapa, hay r = N/n conmutadores de matriz, cada uno de tamaño n*m. En la segunda etapa, hay m conmutadores de tamaño r*r, y finalmente, la última etapa es una réplica de la primera con r conmutadores de tamaño m*n. Una red Clos será completamente no bloqueante si m >= 2n-1. El número de conexiones, aunque mayor que en una red Omega, es mucho menor que en una red de matriz.

Red Beneš

Una red de Beneš es una red no bloqueante reconfigurable derivada de la red clos mediante la inicialización n = m = 2. Hay (2log₂ ₍ N) - 1) etapas, y cada etapa contiene N/2 conmutadores de barra transversal de 2x2. Una red de Beneš de 8x8 tiene 5 etapas de elementos de conmutación, y cada etapa tiene 4 elementos de conmutación. Las tres etapas centrales tienen dos redes de Beneš de 4x4. La red de Beneš de 4x4 puede conectar cualquier entrada a cualquier salida de forma recursiva.