Transmisión de dos árboles

La difusión de dos árboles (abreviada como difusión de 2 árboles o difusión de 23 ) es un algoritmo que implementa un patrón de comunicación de difusión en un sistema distribuido mediante paso de mensajes . Una difusión es una operación colectiva de uso común que envía datos de un procesador a todos los demás procesadores. La difusión de dos árboles se comunica concurrentemente a través de dos árboles binarios que abarcan todos los procesadores. Esto logra el uso completo del ancho de banda en el modelo de comunicación dúplex completo mientras que tiene una latencia de inicio logarítmica en el número de procesadores participantes. ^{[ 1 ]} El algoritmo también puede adaptarse para realizar una reducción o suma de prefijos .

Algoritmo

Una difusión envía un mensaje desde un procesador raíz específico a todos los demás procesadores. La difusión mediante árbol binario utiliza un árbol binario para modelar la comunicación entre los procesadores. Cada procesador corresponde a un nodo del árbol, y el procesador raíz es la raíz del árbol. Para difundir un mensaje $M$ , la raíz envía $M$ a sus dos hijos (nodos hijos). Cada procesador espera hasta recibir $M$ y luego $lo$ envía a sus hijos. Dado que las hojas no tienen hijos, no tienen que enviar ningún mensaje. El proceso de difusión se puede segmentar dividiendo el mensaje en $k$ bloques, que luego se difunden consecutivamente. En un árbol binario de este tipo, las hojas solo reciben datos, pero nunca envían datos por sí mismas. Si la comunicación es bidireccional (dúplex completo), lo que significa que cada procesador puede enviar y recibir un mensaje al mismo tiempo, las hojas solo utilizan la mitad del ancho de banda disponible.

La idea de la difusión de dos árboles es utilizar dos árboles binarios $T 1$ y $T 2$ y comunicarse en ambos simultáneamente. ^{[ 1 ]} Los árboles se construyen de manera que los nodos interiores de un árbol correspondan a los nodos hoja del otro árbol. Los datos que deben difundirse se dividen en bloques de igual tamaño. En cada paso del algoritmo, cada procesador recibe un bloque y envía el bloque anterior a uno de sus hijos en el árbol en el que es un nodo interior. Se necesita una planificación para que ningún procesador tenga que enviar o recibir dos mensajes en el mismo paso. Para crear dicha planificación, las aristas de ambos árboles se colorean con 0 y 1 de manera que

Ningún procesador está conectado a sus nodos padres en $T 1$ y $T 2$ mediante aristas del mismo color.
Ningún procesador está conectado a sus nodos hijos en $T 1$ o $T 2$ mediante aristas del mismo color.

Los bordes con color 0 se utilizan en pasos pares, los bordes con color 1 se utilizan en pasos impares. Esta programación permite que cada procesador envíe un mensaje y reciba un mensaje en cada paso, utilizando completamente el ancho de banda disponible. ^{[ 1 ]} Supongamos que el procesador $i$ quiere transmitir un mensaje. Los dos árboles se construyen para los procesadores restantes. El procesador $i$ envía bloques alternadamente a las raíces de los dos árboles, de modo que cada árbol transmite la mitad del mensaje.

Análisis

Sea $p$ el número de elementos de procesamiento (PE), numerados del $0$ al $p - 1$ .

Construcción de los árboles

Árboles binarios de tamaño 6, 12, 7 y 9 mediante simetría (arriba) y desplazamiento (abajo). $T 1$ en rojo, $T 2$ en azul.

Sea $h = ⌈log(p + 2)⌉$ . $T 1$ y $T 2$ se pueden construir como árboles de altura $h - 1$ , de modo que ambos árboles formen una numeración en orden de los procesadores, con el siguiente método: ^{[ 1 ]} $T 1$ : Si $p = 2 h - 2$ , $T 1$ es un árbol binario completo de altura $h - 1$ excepto que falta la hoja más a la derecha. De lo contrario, $T 1$ consiste en un árbol binario completo de altura $h - 2$ que cubre PE $[0, 2 h -1 - 2]$ , un árbol construido recursivamente que cubre PE $[2 h -1, p - 1]$ , y una raíz en PE $2 h -1 - 1$ cuyos hijos son las raíces del subárbol izquierdo y derecho. $T 2$ : Hay dos maneras de construir $T 2$ . Con $el$ desplazamiento , $T2$ se construye primero como $T1$ , excepto que contiene un procesador adicional. Luego, $T2$ $se desplaza$ una posición a la izquierda y se elimina la hoja más a la izquierda. Con $el$ reflejo , $T2$ es la imagen especular de $T1 (con el eje$ $de$ reflexión entre los procesadores $p$ $/ 2 - 1 y$ p $/$ $2$ $)$ $.$ $El$ $reflejo solo funciona para p$ par .

Se puede demostrar que existe una coloración con las propiedades deseadas para todo $p$ . ^{[ 1 ]} Cuando se utiliza el reflejo para construir $T 2$ , cada procesador puede calcular de forma independiente el color de sus bordes incidentes en tiempo $O (log p) .$ ^{[ 1 ]}

Tiempo de comunicación

Para este análisis, se utiliza el siguiente modelo de comunicación: Un mensaje de tamaño $n$ tiene un tiempo de comunicación de $α + βn$ , independientemente de qué procesadores se comuniquen. $α$ representa la sobrecarga de inicio para enviar el mensaje, $β$ representa el tiempo de transmisión por elemento de datos. ^{[ 2 ]}

Supongamos que el mensaje de tamaño $m$ se divide en $2k bloques$ . Cada paso de comunicación toma un tiempo $α + β ⁠ m / 2k ⁠ .$ Sea $h =log p$ la altura de la estructura de comunicación con la raíz en el procesador $i$ y los dos árboles debajo de él. Después de $2h pasos$ , el primer bloque de datos ha llegado a cada nodo en ambos árboles. Luego, cada procesador recibe un bloque en cada paso hasta que recibe todos los bloques. El número total de pasos es $2h + 2k$ $,$ lo que resulta en un tiempo total de comunicación de $($ $2h$ $+$ $2k$ $)$ $($ $α$ $+$ $β$ $⁠$ $m$ $/$ $2k$ $⁠$ $)$ . Usando un $k óptimo = k *$ $=$ $($ $⁠$ $βmh$ $/$ $2α$ $⁠$ $)$ $1/2$ $,$ $el tiempo total$ $de$ comunicación es $βm$ $+$ $2α$ $log$ $p$ $+$ $\sqrt8αβm$ $log$ $p$ $.$

Comparación con algoritmos similares

En una difusión en pipeline lineal , el mensaje se divide en $k$ bloques. En cada paso, cada procesador $i$ recibe un bloque del procesador $i -1 (mod p)$ y envía un bloque al procesador $i +1 (mod p)$ . La difusión en pipeline lineal tiene un rendimiento óptimo, pero un tiempo de inicio de $O (p)$ . ^{[ 3 ]} Para valores grandes $de p$ , la latencia de inicio de $O (log p)$ de la difusión en árbol doble es más rápida. Dado que ambos algoritmos tienen un rendimiento óptimo, el algoritmo de árbol doble es más rápido para un gran número de procesadores.

La difusión mediante árbol binomial se comunica a lo largo de un árbol binomial . Cada proceso recibe el mensaje que se difunde (la raíz ya lo posee) y luego lo envía a sus hijos. La difusión mediante árbol binomial tiene solo la mitad del tiempo de inicio que la difusión mediante dos árboles, pero un factor de $log(p)$ más de comunicación. ^{[ 4 ]} La difusión mediante árbol binomial es más rápida que la difusión mediante dos árboles para mensajes pequeños, pero más lenta para mensajes grandes.

Una difusión de árbol binario en paralelo divide el mensaje en $k$ bloques y los difunde consecutivamente a través de un árbol binario. Al usar un árbol de Fibonacci en lugar de un simple árbol binario equilibrado , la latencia de inicio se puede reducir a $α log(p)$ . ^{[ 5 ]} Un árbol de Fibonacci de altura $h$ consta de una raíz que tiene un árbol de Fibonacci de altura $h -1$ como su hijo izquierdo y un árbol de Fibonacci de altura $h -2$ como su hijo derecho. La difusión de árbol de Fibonacci en paralelo tiene la mitad de la latencia de inicio que la difusión de dos árboles, pero también solo la mitad del rendimiento. Es más rápida para mensajes pequeños, mientras que la difusión de dos árboles es más rápida para mensajes grandes.

Uso para otras primitivas de comunicación

Reducción

Una reducción ( MPI_Reduceen el estándar MPI ) calcula ${\textstyle \bigoplus _ {i=0}^{p-1}M_ {i}}$ donde $M i$ es un vector de longitud $m$ originalmente disponible en el procesador $i$ y ${\textstyle \bigoplus }$ es una operación binaria que es asociativa, pero no necesariamente conmutativa. El resultado se almacena en un procesador raíz especificado $r$ .

Supongamos que $r = 0$ o $r = p -1$ . En este caso, la comunicación es idéntica a la difusión, excepto que la dirección de la comunicación está invertida. ^{[ 1 ]} Cada proceso recibe dos bloques de sus hijos, los reduce con su propio bloque y envía el resultado a su padre. La raíz recibe alternativamente bloques de las raíces de $T 1$ y $T 2$ y los reduce con sus propios datos. El tiempo de comunicación es el mismo que para la difusión y la cantidad de datos reducidos por procesador es $2 m$ . Si la operación de reducción es conmutativa, el resultado se puede obtener para cualquier raíz renumerando los procesadores.

Si la operación no es conmutativa y la raíz no es $0$ o $p -1$ , entonces $2 βm$ es un límite inferior para el tiempo de comunicación. ^{[ 1 ]} En este caso, los procesadores restantes se dividen en dos subgrupos. Los procesadores $< r$ realizan una reducción a la raíz $r -1$ y los procesadores $> r$ realizan una reducción a la raíz $r +1$ . El procesador $r$ recibe bloques alternados de las dos raíces de los subgrupos.

Suma de prefijo

Una suma de prefijos ( MPI_Scan) calcula ${\textstyle \bigoplus _ {i=0}^{j}M_ {i}}$ para cada procesador $j$ donde $M i$ es un vector de longitud $m$ originalmente disponible en el procesador $i$ y ${\textstyle \bigoplus }$ es una operación asociativa binaria. Utilizando un árbol binario en orden, se puede calcular una suma de prefijos realizando primero una fase ascendente en la que cada nodo interior calcula una suma parcial. ${\textstyle \bigoplus _ {i=l}^{r}M_ {i}}$ para las hojas más a la izquierda y más a la derecha $l$ y $r$ , seguidas de una fase descendente en la que se utilizan prefijos de la forma ${\textstyle \bigoplus _ {i=0}^{l-1}M_ {i}}$ se envían a través del árbol y permiten que cada procesador termine de calcular su suma de prefijos. ^{[ 6 ]}^{[ 1 ]} La comunicación en la fase ascendente es equivalente a una reducción al procesador $0$ y la comunicación en la fase descendente es equivalente a una difusión desde el procesador $0.$ El tiempo total de comunicación es aproximadamente el doble del tiempo de comunicación de la difusión de dos árboles. ^{[ 1 ]}

Emisión de ESBT

Si $p$ es una potencia de dos , existe un algoritmo de difusión óptimo basado en árboles binomiales de expansión disjuntos de aristas (ESBT) en un hipercubo. ^{[ 7 ]} El hipercubo, excluyendo la raíz $0 d$ , se divide en $log p$ ESBT. El algoritmo utiliza segmentación dividiendo los datos de difusión en $k$ bloques. El procesador $0 d$ distribuye cíclicamente bloques a las raíces de los ESBT y cada ESBT realiza una difusión de árbol binario segmentada. En el paso $i$ , cada procesador envía y recibe un mensaje a lo largo de la dimensión $i mod d$ . El tiempo de comunicación del algoritmo es $βm + α log p + \sqrt 4 αβm log p$ , ^{[ 7 ]} por lo que la latencia de inicio es solo la mitad de la latencia de inicio de la difusión de dos árboles. El inconveniente de la difusión ESBT es que no funciona para otros valores de $p$ y no se puede adaptar para la reducción (no conmutativa) o la suma de prefijos.

Referencias

1 2 3 4 5 6 7 8 9 10 Sanders, Peter; Speck, Jochen; Träff, Jesper Larsson (2009). "Algoritmos de dos árboles para difusión, reducción y escaneo de ancho de banda completo". Computación paralela . 35 (12): 581– 594. doi : 10.1016/j.parco.2009.09.001 . ISSN 0167-8191 .
↑ Hockney, Roger W. (1994). "El desafío de la comunicación para MPP: Intel Paragon y Meiko CS-2". Computación paralela . 20 (3): 389– 398. doi : 10.1016/S0167-8191(06)80021-9 . ISSN 0167-8191 .
↑ Pješivac-Grbović, Jelena; Angskun, Thara; Bosilca, George; Fagg, Graham E.; Gabriel, Edgar; Dongarra, Jack J. (2007). "Análisis de rendimiento de operaciones colectivas MPI". Cluster Computing . 10 (2): 127– 143. CiteSeerX 10.1.1.80.3867 . doi : 10.1007/s10586-007-0012-0 . ISSN 1386-7857 . S2CID 2142998 .
↑ Chan, Ernie; Heimlich, Marcel; Purkayastha, Avi; Van De Geijn, Rober (2007). "Comunicación colectiva: teoría, práctica y experiencia". Concurrency and Computation: Practice and Experience . 19 (13): 1749– 1783. doi : 10.1002/cpe.v19:13 . ISSN 1532-0626 .
↑ Bruck, Jehoshua; Cypher, Robert; Ho, CT (1992). "Difusión de mensajes múltiples con árboles de Fibonacci generalizados". [ 1992 ] Actas del Cuarto Simposio IEEE sobre Procesamiento Paralelo y Distribuido (PDF) . IEEE. págs. 424–431 . doi : 10.1109/SPDP.1992.242714 . ISBN 978-0-8186-3200-6. S2CID 2846661 .
↑ Sanders, Peter; Träff, Jesper Larsson (2006). "Algoritmos de prefijo paralelo (escaneo) para MPI". Avances recientes en máquinas virtuales paralelas e interfaz de paso de mensajes . Lecture Notes in Computer Science. Vol. 4192. Springer. pp. 49–57 . CiteSeerX 10.1.1.495.5815 . doi : 10.1007/11846802_15 . ISBN 978-3-540-39110-4ISSN 0302-9743 {{cite book}}: |journal=ignorado ( ayuda )
1 2 Johnsson, SL; Ho, C.-T. (1989). "Difusión óptima y comunicación personalizada en hipercubos". IEEE Transactions on Computers . 38 (9): 1249– 1268. doi : 10.1109/12.29465 . ISSN 0018-9340 .