Red de mariposas

Una red mariposa es una técnica para conectar múltiples computadoras en una red de alta velocidad. Este tipo de topología de red de interconexión multietapa se puede utilizar para conectar diferentes nodos en un sistema multiprocesador .

La red de interconexión para un sistema multiprocesador de memoria compartida debe tener baja latencia y alto ancho de banda , a diferencia de otros sistemas de red, como las redes de área local (LAN) o Internet, por tres razones:

• Los mensajes son relativamente cortos, ya que la mayoría son solicitudes y respuestas del protocolo de coherencia sin datos.

• Los mensajes se generan con frecuencia porque cada fallo de lectura o escritura genera mensajes a todos los nodos del sistema para garantizar la coherencia. Los fallos de lectura/escritura ocurren cuando los datos solicitados no se encuentran en la caché del procesador y deben recuperarse de la memoria o de la caché de otro procesador.

• Los mensajes se generan con frecuencia, lo que dificulta que los procesadores oculten el retraso en la comunicación.

Los componentes principales de una red de interconexión son:

• Los nodos de procesamiento, que constan de uno o más procesadores junto con sus cachés , memorias y sistemas de comunicación, facilitan su uso.
• Los nodos de conmutación ( enrutadores ) conectan la comunicación entre los diferentes nodos de procesamiento de un sistema. En topologías multietapa, los nodos de conmutación de nivel superior se conectan a los nodos de conmutación de nivel inferior, como se muestra en la figura 1, donde los nodos de conmutación de rango 0 se conectan directamente a los nodos de procesamiento, mientras que los nodos de conmutación de rango 1 se conectan a los nodos de conmutación de rango 0.
• Los enlaces son cables físicos que conectan dos nodos de conmutación. Pueden ser unidireccionales o bidireccionales.

Estas redes multietapa tienen un costo menor que una matriz de barras cruzadas , pero obtienen una contención menor que un bus . La relación entre nodos de conmutación y nodos de procesamiento es mayor que uno en una red mariposa. Dicha topología , donde la relación entre nodos de conmutación y nodos de procesamiento es mayor que uno, se denomina topología indirecta. ^{[ 1 ]}

La red recibe su nombre de las conexiones entre nodos de dos rangos adyacentes (como se muestra en la figura 1), que se asemejan a una mariposa . Al fusionar los rangos superior e inferior en un solo rango, se crea una red de mariposa envuelta. ^{[ 1 ]} En la figura 1, si los nodos de rango 3 se conectan de nuevo a sus respectivos nodos de rango 0, se forma una red de mariposa envuelta.

BBN Butterfly , una computadora paralela masiva construida por Bolt, Beranek y Newman en la década de 1980, utilizó una red de interconexión tipo mariposa. ^{[ 2 ]} Más tarde, en 1990, la máquina Cray C90 de Cray Research utilizó una red tipo mariposa para comunicarse entre sus 16 procesadores y 1024 bancos de memoria. ^{[ 3 ]}

Para una red mariposa con p nodos procesadores, se necesitan p(log₂ _p + 1) nodos de conmutación. La Figura 1 muestra una red con 8 nodos procesadores, lo que implica 32 nodos de conmutación. Representa cada nodo como N(rango, número de columna). Por ejemplo, el nodo en la columna 6 en el rango 1 se representa como (1,6) y el nodo en la columna 2 en el rango 0 se representa como (0,2). ^{[ 1 ]}

Para cualquier 'i' mayor que cero, un nodo de conmutación N(i,j) se conecta a N(i-1, j) y N(i-1, m), donde m es el bit invertido en la i-ésima ^posición de j. Por ejemplo, consideremos el nodo N(1,6): i es igual a 1 y j es igual a 6, por lo tanto, m se obtiene invirtiendo el i- ^ésimo bit de 6.

Como resultado, los nodos conectados a N(1,6) son  :

Así, N(0,6), N(1,6), N(0,2) y N(1,2) forman un patrón de mariposa. En la figura aparecen varios patrones de mariposa, por lo que esta red se denomina Red de Mariposa.

En una red mariposa envuelta (lo que significa que el rango 0 se fusiona con el rango 3), se envía un mensaje del procesador 5 al procesador 2. ^{[ 1 ]} En la figura 2, esto se muestra replicando los nodos de procesador por debajo del rango 3. El paquete transmitido a través del enlace sigue el siguiente formato:

El encabezado contiene el destino del mensaje, que es el procesador 2 (010 en binario). La carga útil es el mensaje, M, y el tráiler contiene la suma de verificación . Por lo tanto, el mensaje real transmitido desde el procesador 5 es:

Al llegar a un nodo de conmutación, se selecciona uno de los dos enlaces de salida en función del bit más significativo de la dirección de destino. Si este bit es cero, se selecciona el enlace izquierdo. Si es uno, se selecciona el enlace derecho. Posteriormente, este bit se elimina de la dirección de destino en el paquete transmitido a través del enlace seleccionado. Esto se muestra en la figura 2.

• El paquete anterior llega a N(0,5). Se elimina el bit más a la izquierda de la cabecera para determinar la dirección. Dado que es cero, se selecciona el enlace izquierdo de N(0,5) (que se conecta a N(1,1)). La nueva cabecera es '10'.
• El nuevo paquete llega a N(1,1). Se extrae el bit más a la izquierda de la cabecera para determinar la dirección. Dado que es un uno, se selecciona el enlace derecho de N(1,1) (que conecta con N(2,3)). La nueva cabecera es '0'.
• El nuevo paquete llega a N(2,3). Se extrae el bit más a la izquierda de la cabecera para determinar la dirección. Dado que es cero, se selecciona el enlace izquierdo de N(2,3) (que conecta con N(3,2)). El campo de la cabecera queda vacío.
• El procesador 2 recibe el paquete, que ahora contiene únicamente la carga útil 'M' y la suma de verificación.

Diversos parámetros ayudan a evaluar la topología de una red. A continuación, se resumen los más relevantes para el diseño de sistemas multiprocesador a gran escala y se explica cómo se calculan para una red tipo mariposa con 8 nodos de procesador, como se muestra en la figura 1.

• Ancho de banda de bisección : El ancho de banda máximo necesario para mantener la comunicación entre todos los nodos de la red. Esto se puede interpretar como el número mínimo de enlaces que deben cortarse para dividir el sistema en dos partes iguales. Por ejemplo, la red mariposa de 8 nodos se puede dividir en dos cortando 4 enlaces que se cruzan en el centro. Por lo tanto, el ancho de banda de bisección de este sistema en particular es 4. Es una medida representativa del cuello de botella de ancho de banda que restringe la comunicación general.
• Diámetro : La latencia máximaposible (entre dos nodos) en el sistema. Se calcula en términos de saltos de red, que es el número de enlaces que un mensaje debe recorrer para llegar al nodo de destino. En la red mariposa de 8 nodos, parece que N(0,0) y N(3,7) son los más alejados, pero tras un análisis, resulta evidente que, debido a la simetría de la red, el trayecto desde cualquier nodo de rango 0 a cualquier nodo de rango 3 requiere solo 3 saltos. Por lo tanto, el diámetro de este sistema es 3.
• Enlaces : Número total de enlaces necesarios para construir toda la estructura de la red. Este es un indicador del costo y la complejidad generales de la implementación. La red de ejemplo que se muestra en la figura 1 requiere un total de 48 enlaces (16 enlaces entre los rangos 0 y 1, 16 entre los rangos 1 y 2, y 16 entre los rangos 2 y 3).
• Grado : La complejidad de cada enrutador en la red. Esto equivale al número de enlaces de entrada/salida conectados a cada nodo de conmutación. Los nodos de conmutación de la red Butterfly tienen 2 enlaces de entrada y 2 de salida, por lo que se trata de una red de grado 4.

Esta sección compara la red mariposa con redes de arreglo lineal, anillo, malla 2D e hipercubo . ^{[ 4 ]} El arreglo lineal puede considerarse como una topología de malla 1D. Los parámetros relevantes se compilan en la tabla ('p' representa el número de nodos de procesador).

• Computación paralela
• Topología de red
• Redes de malla