Las redes de interconexión de múltiples etapas ( MIN ) son una clase de redes de computadoras de alta velocidad generalmente compuestas por elementos de procesamiento (PE) en un extremo de la red y elementos de memoria (ME) en el otro extremo, conectados por elementos de conmutación (SE). Los propios elementos de conmutación suelen estar conectados entre sí por etapas, de ahí el nombre.
Los MIN se utilizan normalmente en computación paralela o de alto rendimiento como una interconexión de baja latencia (a diferencia de las redes tradicionales de conmutación de paquetes ), aunque podrían implementarse sobre una red de conmutación de paquetes. Aunque la red se usa típicamente para propósitos de enrutamiento, también podría usarse como un coprocesador para los procesadores reales para usos tales como clasificación ; desplazamiento cíclico , como en una red de mezcla perfecta ; y clasificación bitónica .
Fondo
Las redes de interconexión se utilizan para conectar nodos, donde los nodos pueden ser un solo procesador o un grupo de procesadores, a otros nodos.
Las redes de interconexión se pueden clasificar en función de su topología. La topología es el patrón en el que un nodo está conectado a otros nodos.
Hay dos tipos principales de topología: estática y dinámica.
Las redes de interconexión estática están cableadas y no pueden cambiar sus configuraciones. Una interconexión estática regular se utiliza principalmente en redes pequeñas compuestas por nodos con pares sueltos. La estructura regular significa que los nodos están dispuestos en una forma específica y la forma se mantiene en todas las redes.
Algunos ejemplos de interconexiones regulares estáticas son: [1]
- Red completamente conectada En una red de malla, varios nodos están conectados entre sí. Cada nodo de la red está conectado a todos los demás nodos de la red. Esta disposición permite una comunicación adecuada de los datos entre los nodos. Pero hay una gran cantidad de gastos generales de comunicación debido al mayor número de conexiones de nodos.
- Bus 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 de bus garantiza que no se envíen datos al nodo incorrecto. Pero el tráfico de autobuses 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 están conectados entre sí para formar un anillo. Para que un nodo se comunique con otro nodo, tiene que enviar los mensajes a su vecino. Por tanto, el mensaje de datos pasa por una serie de otros nodos antes de llegar al destino. Esto implica una mayor latencia en el sistema.
- Árbol Esta topología implica la conexión de los nodos para formar un árbol. Los nodos están conectados para formar grupos y los grupos, a su vez, están conectados para formar el árbol. Esta metodología provoca una mayor complejidad en la red.
- Hipercubo Esta topología consta de conexiones de los nodos para formar cubos. Los nodos también están conectados a los nodos de los otros cubos.
- Mariposa Esta es una de las conexiones más complejas de los nodos. Como sugiere la figura, hay nodos que están conectados y organizados en términos de sus rangos. Están dispuestos en forma de matriz.
En las redes de interconexión dinámica, los nodos están interconectados a través de una matriz de elementos de conmutación simples. [2] Esta interconexión se puede cambiar mediante el uso de algoritmos de enrutamiento, de modo que se pueda variar la ruta de un nodo a otros nodos. Las interconexiones dinámicas se pueden clasificar como:
- Red de interconexión de una sola etapa
- Red de interconexión multietapa
- Conexiones del interruptor de barra transversal
Conexiones del interruptor de barra transversal
En el conmutador de barra cruzada, hay una ruta dedicada de un procesador a otros procesadores. Por lo tanto, si hay n entradas y m salidas, necesitaremos n * m interruptores para realizar una barra transversal.
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 esquema es la conmutación por etapas.
Red de interconexión de una sola etapa
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 sola etapa de interruptores.
La figura muestra un interruptor de una sola etapa de 8 * 8 usando intercambio aleatorio .
Como se puede ver, con una sola reproducción aleatoria, no todas las entradas pueden llegar a todas las salidas. Se requieren varias combinaciones para que todas las entradas se conecten a todas las salidas.
Red de interconexión de varias etapas
Una red de interconexión de varias etapas se forma mediante la conexión en cascada de varios conmutadores de una sola etapa. Los conmutadores pueden utilizar su propio algoritmo de enrutamiento o ser controlados por un enrutador centralizado, para formar una red completamente interconectada.
La red de interconexión de varias etapas se puede clasificar en tres tipos: [3]
- Sin bloqueo: una red sin bloqueo puede conectar cualquier entrada inactiva a cualquier salida inactiva, independientemente de las conexiones ya establecidas en la red. Crossbar es un ejemplo de este tipo de red.
- Sin bloqueo reorganizable : este tipo de red puede establecer todas las conexiones posibles entre entradas y salidas reorganizando sus conexiones existentes.
- 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.
El número de elementos de conmutación necesarios para realizar una red sin bloqueo en el nivel más alto, seguido por el no bloqueo reorganizable. La red de bloqueo utiliza la menor cantidad de elementos de conmutación.
Ejemplos de
Existen varios tipos de redes de interconexión de múltiples etapas.
Red Omega
Una red Omega consta de múltiples etapas de elementos de conmutación 2 * 2. Cada entrada tiene una conexión dedicada a una salida. Una red omega N * N tiene un número log (N) de etapas y una cantidad N / 2 de elementos de conmutación en cada etapa para una mezcla perfecta entre las etapas. Por tanto, la red tiene una complejidad de 0 (N log (N)). Cada elemento de conmutación puede emplear su propio algoritmo de conmutación. Considere una red omega 8 * 8. ¡Hay 8! = 40320 Mapeos 1 a 1 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.
Clos de la red
Una red Clos utiliza 3 etapas para cambiar de N entradas a N salidas. En la primera etapa, hay interruptores de barra transversal r = N / n y cada interruptor es de tamaño n * m. En la segunda etapa hay m interruptores de tamaño r * r y finalmente la última etapa es un espejo de la primera etapa con r interruptores de tamaño m * n. Una red cerrada será completamente sin bloqueo si m> = 2n-1. La cantidad de conexiones, aunque más que la red omega, es mucho menor que la de una red de barras cruzadas.
Red Beneš
Una red Beneš es una red sin bloqueo reordenable derivada de la red clos inicializando n = m = 2. Hay (2log (N) - 1) etapas, y cada etapa contiene N / 2 2 * 2 interruptores de barra transversal. Una red Beneš de 8 * 8 tiene 5 etapas de elementos de conmutación, y cada etapa tiene 4 elementos de conmutación. El centro de tres etapas tiene dos redes de 4 * 4 benes. La red Beneš 4 * 4, puede conectar cualquier entrada a cualquier salida de forma recursiva.
Referencias
- ^ Solihin, Yan (2009). Fundamentos de la Arquitectura de Computadores Paralelos . Estados Unidos: OmniPress. ISBN 978-0-9841630-0-7.
- ^ Blake, JT; Trivedi, KS (1 de noviembre de 1989). "Fiabilidad de la red de interconexión multietapa". Transacciones IEEE en computadoras . 38 (11): 1600–1604. doi : 10.1109 / 12.42134 . ISSN 0018-9340 .
- ^ "Redes de interconexión multietapa" (PDF) .