Red mariposa

Red mariposa es una topología de red de interconexión de múltiples etapas (RIME), la cual se puede utilizar para conectar distintos nodos en un sistema de multiprocesador. La red interconectada para un sistemas de multiprocesador de memoria compartida necesita tener la latencia baja y el ancho de banda alto comparado a otros sistemas de red como redes de área local (LANs) o internet. Esto es porque en sistemas de multiprocesador :-

Los mensajes son relativamente cortos, como la mayoría de los mensajes son peticiones de coherencia de protocolo y respuestas sin datos.
Los mensajes se generan con frecuencia porque cada error de lectura o escritura (se produce cuando los datos solicitados no están en la caché de los procesadores y deben ser extraídos de la memoria u otro caché del procesador) genera mensajes a cada nodo en el sistema para asegurar coherencia.
Dado que los mensajes se generan con frecuencia, es difícil para los procesadores ocultar el retraso de la comunicación.

Los componentes importantes de una red interconectada son:-^[1]

Nodos de procesador - consisten en uno o más procesadores junto con su cachés, memorias y ayuda de comunicación.
Nodos de conmutación (Router) - conectan la ayuda de comunicación de diferentes nodos de procesador en un sistema. En RIMEs, los nodos de conmutación el nivel más alto conectan a los del nivel más bajos como se muestra en la figura 1. Nodos de conmutación de rango 0 conectan a nodos de procesador directamente, mientras que los nodos de conmutación de rango 1 conectan a a los de rango 0.
Enlace - cables Físicos entre dos nodos de conmutación (routers). Pueden ser uni-direccionales o bi-direccionales.

Estas redes multi-etapa tienen un costo más bajo que una cross bar pero aún obtienen una contención más baja que un bus. También la relación de nodos de conmutación a nodos de procesador es mayor que uno en una red mariposa. Tal topología donde la relación de nodos de conmutación a nodos de procesador es mayor que uno se llama topología indirecta.^[2]

La red deriva su nombre de las conexiones entre los nodos en dos filas adyacentes (como se muestra en la figura 1), que se asemeja a una mariposa. Cuando los rangos superior e inferior se combinan en un solo rango, se denomina Red Mariposa Envuelta.^[2] En la figura 1, si los nodos de rango 3 están conectados atrás de los respectivos nodos de rango 0, entonces deviene una red mariposa envuelta .

BBN Butterfly, un ordenador paralelo masivo construido por Bolt, Beranek y Newman en los años1980s, usaron una red mariposa interconectada.^[3] También, Cray C90, usaron una red mariposa para la comunicación entre sus 16 procesadores y 1024 bancos de memoria.^[4]

Construcción de una Red mariposa^[2][editar]

Para una red mariposa con 'p' nodos de procesador, necesitas tener $p(\log _{2}p+1)$ nodos de conmutación. La figura 1 muestra una red con 8 nodos de procesador, lo cual significa que tenemos 32 nodos de conmutación. También representa cada nodo como N(rango, número de columna). Por ejemplo, el nodo en columna 6 en rango 1 está representado como (1,6) y el nodo en columna 2 en rango 0 está representado como (0,2).

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), dónde m se obtene moviendo el i^ésimo bit más significativo de j. Por ejemplo, considere el nodo N(1,6). Aquí, i es 1 y j es 6. Por lo tanto m se obtiene cambiando el primer bit más significativo de 6.

Variable	Representación binaria	Representación decimal
j	110	6
m	010	2

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

N(i,j)	N(i-1,j)	N(i-1,m)
(1,6)	(0,6)	(0,2)

Curiosamente, N(0,6), N(1,6), N(0,2), N(1,2) forma un patrón de mariposa. Podemos encontrar muchos de estos patrones de mariposa en la figura y por tanto, esta red se nombre Red Mariposa.

Enrutamiento de Red mariposa^[2][editar]

Considera que en una red mariposa envuelta (lo que significa que el rango 0 se fusiona con el rango 3. En la figura 2, se muestra mediante la replicación de los nodos de procesador por debajo de rango 3) , necesitamos enviar un mensaje del procesador 5 al procesador 2. El paquete transmitido sobre el enlace es de la forma :-

Encabezamiento	Carga útil	Remolque

El encabezamiento contiene el destino del mensaje, el cual es procesador 2 (010 en binario). La carga útil es el mensaje M y el remolque contiene la suma de verificación. Por lo tanto el mensaje real transmitido de procesador 5 es :-

010	M	suma de verificación

Al llegar a un nodo de conmutación, se selecciona uno de los dos enlaces de salida en base al bit más significativo de la dirección de destino. Si ese bit es cero, se selecciona el enlace izquierdo. Si ese bit es uno, el enlace correcto está seleccionado. 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 alcanza N (0,5). Desde el encabezado del paquete, elimina el bit más a la izquierda para decidir la dirección. Puesto que es un enlace cero a la izquierda de N (0,5) (que se conecta a N (1,1)) se selecciona. La nueva cabecera es '10'.

El nuevo paquete llega a N (1,1). Desde el encabezado del paquete, elimina el bit más a la izquierda para decidir la dirección. Puesto que es un enlace correcto de N (1,1) (que se conecta a N (2,3)) se selecciona. El nuevo encabezado es '0'.
El nuevo paquete llega a N (2,3). Desde el encabezado del paquete, elimina el bit más a la izquierda para decidir la dirección. Como se trata de un enlace cero a la izquierda de N (2,3) (que se conecta a N (3,2)) se selecciona. El campo de encabezado está vacío.
El procesador 2 recibe el paquete, que ahora contiene solo la carga "M" y la suma de verificación.

Parámetros de Red mariposa^[5][editar]

Hay varios parámetros para evaluar una topología de red, pero los relevantes en el diseño de sistemas multiprocesador a gran escala se discuten aquí. Estos parámetros se resumen a continuación y veremos cómo se calculan para una red mariposa con 8 nodos de procesador como se muestra en la figura 1.

Ancho de banda de bisección: Una medida representativa del ancho de banda de cuello de botella que restringe la comunicación global. Es el ancho de banda máximo necesario para mantener la comunicación entre todos los nodos de la red. Podemos interpretar esto como el número mínimo de enlaces que necesitan ser cortados para dividir el sistema en dos porciones iguales. Por ejemplo, la red mariposa de 8 nodos se puede dividir en dos cortando 4 enlaces que se entrecruzan a través del centro. Por lo tanto, el ancho de banda de bisección de este sistema particular es 4.
Diámetro: Este es el peor caso de latencia (entre dos nodos) posible en el sistema. Se puede calcular 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. Así, en la red mariposas de 8 nodos, parece que N (0,0) y N (3,7) están más alejados. Pero al inspeccionar cuidadosamente podemos ver que debido a la naturaleza simétrica de la red, el desplazamiento 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 total y la complejidad de la implementación. La red de ejemplo mostrada en la figura 1 requiere un total de 48 enlaces (16 enlaces cada uno entre rango 0 y 1, rango 1 y 2, rango 2 y 3).
Grado: Representa la complejidad de cada router en la red. Esto es igual al número de enlaces de entrada / salida conectados a cada nodo de conmutación. Los nodos de conmutación de red mariposa tienen 2 enlaces de entrada y 2 enlaces de salida, de ahí que sea una red de 4 grados.

Comparación con Otras Topologías de Red^[6][editar]

Comparemos la red de mariposa con otras topologías de red, como matriz, anillo, lineales de malla 2-D y el hipercubo.^[7] Tenga en cuenta que una matriz lineal puede considerarse como una topología de malla 1-D. Todos sus parámetros relevantes se recogen en la tabla de abajo ( 'p' representa el número de nodos de procesador).^[6]

Topología	Diámetro	Ancho de banda de bisección	Enlaces	Grado
Arreglo lineal	$p-1$	1	$p-1$	2
Anillo	$p/2$	2	$p$	2
Malla 2-D	$2({\sqrt {p}}-1)$	${\sqrt {p}}$	$2{\sqrt {p}}({\sqrt {p}}-1)$	4
Hipercubo	$\log _{2}p$	$p/2$	$\log _{2}p\times (p/2)$	$\log _{2}p$
Mariposa	$\log _{2}p$	$p/2$	$\log _{2}p\times 2p$	4

Ventajas[editar]

Las redes mariposas tienen un diámetro menor que otras toplogías como arreglo lineal, anillo y malla 2-D. Esto implica que en la red de mariposa, un mensaje enviado desde un procesador llegaría a su destino en un menor número de saltos de red.
Las redes mariposas tienen mayor ancho de banda de bisección que otras toplogías como arreglo lineal, anillo y malla 2-D. Esto implica que en la red de mariposas, un mayor número de enlaces deben romperse para evitar la comunicación global.

Desventajas[editar]

Las redes de mariposas son más complejas y costosas que otras topologías como arreglo lineal, anillo y malla 2-D debido al mayor número de enlaces necesarios para mantener la red.

La diferencia entre el hipercubo y la mariposa está en su implementación. Red Mariposa tiene una estructura simétrica donde todos los nodos del procesador entre dos rangos son equidistantes entre sí, mientras que el hipercubo es más adecuado para un sistema multiprocesador que exige distancias desiguales entre sus nodos. Al mirar el número de enlaces necesarios, puede parecer que el hipercubo es más barato y más simple en comparación con una red mariposas. Pero a medida que el número de nodos del procesador va más allá de 16, el costo y la complejidad del enrutador (representado por el grado) de la red mariposas se hace menor que hipercubo porque su grado es independiente del número de nodos.

La conclusión es que no hay una sola topología de red que sea la mejor para todos los escenarios. La decisión tiene que ser hecha sobre la base de factores como el número de nodos de procesador en el sistema, los requisitos de ancho de banda, latencia, el costo y la escalabilidad.

Véase también[editar]

Computación paralela

Topología de red

Malla de red

Referencias[editar]

↑ Fundamentals of Parallel Computer Architecture. Solihin Books. 2016. pp. 373-374. ISBN 978-0-9841630-0-7.
↑ ^a ^b ^c ^d Leighton, F.Thomson (1992). Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers. ISBN 1-55860-117-1.
↑ Large-Scale Parallel Programming: Experience with the BBN Butterfly Parallel Processor. 1 de enero de 1988.
↑ Advanced Computer Architecture and Computing. Technical Publications. pp. Section 3-22. ISBN 9788184315721.
↑ Fundamentals of Parallel Computer Architecture. Solihin Books. 2016. pp. 377-378. ISBN 978-0-9841630-0-7.
↑ ^a ^b Solihin, Yan (2016). Fundamentals of Parallel Computer Architecture. Solihin Books. pp. 379-380. ISBN 978-0-9841630-0-7.
↑ M. Arjomand, H. Sarbazi-Azad, "Performance Evaluation of Butterfly on-Chip Network for MPSoCs", International SoC Design Conference, pp. 1–296-1-299, 2008

Datos: Q28008694

[1] Fundamentals of Parallel Computer Architecture. Solihin Books. 2016. pp. 373-374. ISBN 978-0-9841630-0-7.

[:0-2] Leighton, F.Thomson (1992). Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers. ISBN 1-55860-117-1.

[3] Large-Scale Parallel Programming: Experience with the BBN Butterfly Parallel Processor. 1 de enero de 1988.

[4] Advanced Computer Architecture and Computing. Technical Publications. pp. Section 3-22. ISBN 9788184315721.

[5] Fundamentals of Parallel Computer Architecture. Solihin Books. 2016. pp. 377-378. ISBN 978-0-9841630-0-7.

[:1-6] Solihin, Yan (2016). Fundamentals of Parallel Computer Architecture. Solihin Books. pp. 379-380. ISBN 978-0-9841630-0-7.

[7] M. Arjomand, H. Sarbazi-Azad, "Performance Evaluation of Butterfly on-Chip Network for MPSoCs", International SoC Design Conference, pp. 1–296-1-299, 2008

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Construcción de una Red mariposa[2]​[editar]

Enrutamiento de Red mariposa[2]​[editar]

Parámetros de Red mariposa[5]​[editar]

Comparación con Otras Topologías de Red[6]​[editar]