Operación colectiva

Las operaciones colectivas son los componentes básicos de los patrones de interacción, que se utilizan con frecuencia en los algoritmos SPMD dentro del contexto de la programación paralela . Por lo tanto, existe interés en lograr implementaciones eficientes de estas operaciones.

La realización de las operaciones colectivas la proporciona la Interfaz de Paso de Mensajes ^{[ 1 ]} (MPI).

En todas las funciones de tiempo de ejecución asintóticas, denotamos la latencia.${\displaystyle \alpha }$(o tiempo de inicio por mensaje, independientemente del tamaño del mensaje), el costo de comunicación por palabra${\displaystyle \beta }$, el número de unidades de procesamiento${\displaystyle p}$y el tamaño de entrada por nodo${\displaystyle n}$En los casos en que tenemos mensajes iniciales en más de un nodo, asumimos que todos los mensajes locales son del mismo tamaño. Para dirigirnos a unidades de procesamiento individuales, utilizamos${\displaystyle p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}}$.

Si no tenemos una distribución igual, es decir, nodo${\displaystyle p_{i}}$tiene un mensaje de tamaño${\displaystyle n_{i}}$, obtenemos un límite superior para el tiempo de ejecución estableciendo${\displaystyle n=\max(n_{0},n_{1},\dots ,n_{p-1})}$.

Se asume un modelo de memoria distribuida . Los conceptos son similares para el modelo de memoria compartida . Sin embargo, los sistemas de memoria compartida pueden proporcionar soporte de hardware para algunas operaciones, como la difusión ( §  Broadcast ), por ejemplo, lo que permite una lectura concurrente conveniente. ^{[ 2 ]} De este modo, se abren nuevas posibilidades algorítmicas.

El patrón de difusión ^{[ 3 ]} se utiliza para distribuir datos de una unidad de procesamiento a todas las unidades de procesamiento, lo cual suele ser necesario en programas paralelos SPMD para distribuir valores de entrada o globales. La difusión puede interpretarse como una versión inversa del patrón de reducción ( §Reduce )  . Inicialmente, solo la raíz${\displaystyle r}$con${\displaystyle id}$${\displaystyle 0}$almacena mensaje${\displaystyle m}$Durante la transmisión${\displaystyle m}$se envía a las unidades de procesamiento restantes, de modo que finalmente${\displaystyle m}$Está disponible para todas las unidades de procesamiento.

Dado que una implementación mediante un bucle for secuencial con${\displaystyle p-1}$Las iteraciones se convierten en un cuello de botella, los enfoques de divide y vencerás son comunes. Una posibilidad es utilizar una estructura de árbol binomial con el requisito de que${\displaystyle p}$tiene que ser una potencia de dos . Cuando una unidad de procesamiento es responsable de enviar${\displaystyle m}$a las unidades de procesamiento${\displaystyle i..j}$, envía${\displaystyle m}$a la unidad de procesamiento${\displaystyle \left\lceil (i+j)/2\right\rceil }$y delega la responsabilidad de las unidades de procesamiento.${\displaystyle \left\lceil (i+j)/2\right\rceil ..j}$a ello, mientras que su propia responsabilidad se reduce a${\displaystyle i..\left\lceil (i+j)/2\right\rceil -1}$.

Los árboles binomiales tienen un problema con los mensajes largos.${\displaystyle m}$. La unidad receptora de${\displaystyle m}$Solo puede propagar el mensaje a otras unidades, después de haber recibido el mensaje completo. Mientras tanto, la red de comunicación no se utiliza. Por lo tanto, se utiliza el procesamiento en paralelo en árboles binarios , donde${\displaystyle m}$se divide en una serie de${\displaystyle k}$paquetes de tamaño${\displaystyle \left\lceil n/k\right\rceil }$Los paquetes se transmiten uno tras otro, de modo que los datos se distribuyen rápidamente en la red de comunicación.

La difusión segmentada en un árbol binario equilibrado es posible en${\displaystyle {\mathcal {O}}(\alpha \log p+\beta n)}$, mientras que para el caso no canalizado se necesita${\displaystyle {\mathcal {O}}((\alpha +\beta n)\log p)}$costo.

El patrón de reducción ^{[ 4 ]} se utiliza para recopilar datos o resultados parciales de diferentes unidades de procesamiento y combinarlos en un resultado global mediante un operador elegido. Dado${\displaystyle p}$unidades de procesamiento, mensaje${\displaystyle m_{i}}$está en la unidad de procesamiento${\displaystyle p_{i}}$Inicialmente. Todo${\displaystyle m_{i}}$son agregados por${\displaystyle \otimes }$y el resultado finalmente se almacena en${\displaystyle p_{0}}$El operador de reducción${\displaystyle \otimes }$debe ser asociativo como mínimo. Algunos algoritmos requieren un operador conmutativo con un elemento neutro. Operadores como${\displaystyle sum}$,${\displaystyle min}$,${\displaystyle max}$son comunes.

Las consideraciones de implementación son similares a las de difusión ( §  Difusión ). Para la segmentación en árboles binarios, el mensaje debe poder representarse como un vector de objetos más pequeños para su reducción componente a componente.

Es posible realizar una reducción segmentada en un árbol binario equilibrado.${\displaystyle {\mathcal {O}}(\alpha \log p+\beta n)}$.

El patrón all-reduce ^{[ 5 ]} (también llamado allreduce) se utiliza si el resultado de una operación reduce ( §  Reduce ) debe distribuirse a todas las unidades de procesamiento. Dado${\displaystyle p}$unidades de procesamiento, mensaje${\displaystyle m_{i}}$está en la unidad de procesamiento${\displaystyle p_{i}}$Inicialmente. Todo${\displaystyle m_{i}}$son agregados por un operador${\displaystyle \otimes }$y el resultado finalmente se almacena en todos${\displaystyle p_{i}}$. Análogo a la operación de reducción, el operador${\displaystyle \otimes }$debe ser al menos asociativo.

All-reduce puede interpretarse como una operación de reducción con una difusión posterior ( §  Difusión ). Para mensajes largos es adecuada una implementación correspondiente, mientras que para mensajes cortos, la latencia puede reducirse utilizando una topología de hipercubo ( Hipercubo (patrón de comunicación) §  All-Gather/ All-Reduce ), si${\displaystyle p}$es una potencia de dos. All-reduce también se puede implementar con un algoritmo mariposa y lograr una latencia y un ancho de banda óptimos. ^{[ 6 ]}

La reducción total es posible en${\displaystyle {\mathcal {O}}(\alpha \log p+\beta n)}$, ya que reducir y difundir son posibles en${\displaystyle {\mathcal {O}}(\alpha \log p+\beta n)}$con procesamiento en paralelo en árboles binarios balanceados . La reducción total implementada con un algoritmo mariposa logra el mismo tiempo de ejecución asintótico.

La operación de suma de prefijos o escaneo ^{[ 7 ]} se utiliza para recopilar datos o resultados parciales de diferentes unidades de procesamiento y para calcular resultados intermedios mediante un operador, que se almacenan en dichas unidades de procesamiento. Puede considerarse una generalización de la operación de reducción ( §  Reduce ). Dado${\displaystyle p}$unidades de procesamiento, mensaje${\displaystyle m_{i}}$está en la unidad de procesamiento${\displaystyle p_{i}}$El operador${\displaystyle \otimes }$debe ser al menos asociativo, mientras que algunos algoritmos también requieren un operador conmutativo y un elemento neutro. Los operadores comunes son${\displaystyle sum}$,${\displaystyle min}$y${\displaystyle max}$Unidad de procesamiento final${\displaystyle p_{i}}$almacena la suma del prefijo${\displaystyle \otimes _{i'<=i}}$${\displaystyle m_{i'}}$. En el caso de la llamada suma de prefijo exclusivo, unidad de procesamiento${\displaystyle p_{i}}$almacena la suma del prefijo${\displaystyle \otimes _{i'<i}}$${\displaystyle m_{i'}}$Algunos algoritmos requieren almacenar la suma total en cada unidad de procesamiento, además de las sumas de los prefijos.

Para mensajes cortos, esto se puede lograr con una topología de hipercubo si${\displaystyle p}$es una potencia de dos. Para mensajes largos, la topología de hipercubo ( Hipercubo (patrón de comunicación) §  Suma de prefijo , Suma de prefijo §  Memoria distribuida: algoritmo de hipercubo ) no es adecuada, ya que todas las unidades de procesamiento están activas en cada paso y, por lo tanto, no se puede utilizar el procesamiento en paralelo. Una topología de árbol binario es más adecuada para mensajes arbitrarios.${\displaystyle p}$y mensajes largos ( Suma de prefijo §  Tamaños de mensajes grandes: Árbol binario en pipeline ).

La suma de prefijos en un árbol binario se puede implementar con una fase ascendente y otra descendente. En la fase ascendente se realiza la reducción, mientras que la fase descendente es similar a la difusión, donde las sumas de prefijos se calculan enviando datos diferentes a los hijos izquierdo y derecho. Con este enfoque es posible la segmentación, ya que las operaciones son equivalentes a la reducción ( §  Reduce ) y la difusión ( §  Broadcast ).

La suma de prefijos en paralelo en un árbol binario es posible en${\displaystyle {\mathcal {O}}(\alpha \log p+\beta n)}$.

La barrera ^{[ 8 ],} como operación colectiva, es una generalización del concepto de barrera , que puede utilizarse en computación distribuida . Cuando una unidad de procesamiento llama a la barrera, espera hasta que todas las demás unidades de procesamiento también la hayan llamado. Por lo tanto, la barrera se utiliza para lograr la sincronización global en la computación distribuida.

Una forma de implementar barrera es llamar a all-reduce ( §  All-Reduce ) con un operando vacío/ficticio. Sabemos que el tiempo de ejecución de All-reduce es${\displaystyle {\mathcal {O}}(\alpha \log p+\beta n)}$El uso de un operando ficticio reduce el tamaño.${\displaystyle n}$a un factor constante y conduce a un tiempo de ejecución de${\displaystyle {\mathcal {O}}(\alpha \log p)}$.

El patrón de comunicación de recopilación ^{[ 9 ]} se utiliza para almacenar datos de todas las unidades de procesamiento en una sola unidad de procesamiento. Dado${\displaystyle p}$unidades de procesamiento, mensaje${\displaystyle m_{i}}$en la unidad de procesamiento${\displaystyle p_{i}}$Para una unidad de procesamiento fija${\displaystyle p_{j}}$, queremos almacenar el mensaje${\displaystyle m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}}$en${\displaystyle p_{j}}$. Gather puede considerarse como una operación de reducción ( §  Reduce ) que utiliza el operador de concatenación. Esto funciona debido a que la concatenación es asociativa. Al utilizar el mismo algoritmo de reducción de árbol binomial, obtenemos un tiempo de ejecución de${\displaystyle {\mathcal {O}}(\alpha \log p+\beta pn)}$Observamos que el tiempo de ejecución asintótico es similar al tiempo de ejecución asintótico de reduce.${\displaystyle {\mathcal {O}}(\alpha \log p+\beta n)}$, pero con la adición de un factor p al término${\displaystyle \beta n}$Este factor adicional se debe a que el tamaño del mensaje aumenta en cada paso a medida que los mensajes se concatenan. Compárese esto con la reducción, donde el tamaño del mensaje es constante para operadores como${\displaystyle min}$.

El patrón de comunicación all-gather ^{[ 9 ]} se utiliza para recopilar datos de todas las unidades de procesamiento y para almacenar los datos recopilados en todas las unidades de procesamiento. Dado${\displaystyle p}$unidades de procesamiento${\displaystyle p_{i}}$, mensaje${\displaystyle m_{i}}$almacenado inicialmente en${\displaystyle p_{i}}$, queremos almacenar el mensaje${\displaystyle m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}}$en cada${\displaystyle p_{j}}$.

Se puede pensar de varias maneras. La primera es como una operación de reducción total ( §  All-Reduce ) con la concatenación como operador, de la misma manera que gather puede representarse mediante reduce. La segunda es como una operación de recopilación seguida de una difusión del nuevo mensaje de tamaño${\displaystyle pn}$. Con esto vemos que todos se reúnen en${\displaystyle {\mathcal {O}}(\alpha \log p+\beta pn)}$es posible.

El patrón de comunicación dispersa ^{[ 10 ]} se utiliza para distribuir datos desde una unidad de procesamiento a todas las demás. Se diferencia de la difusión en que no envía el mismo mensaje a todas las unidades de procesamiento, sino que lo divide y entrega una parte a cada una.

Dado${\displaystyle p}$unidades de procesamiento${\displaystyle p_{i}}$una unidad de procesamiento fija${\displaystyle p_{j}}$que contiene el mensaje${\displaystyle m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}}$Queremos transmitir el mensaje.${\displaystyle m_{i}}$sobre${\displaystyle p_{i}}$. Se aplican las mismas consideraciones de implementación que para gather ( §  Gather ). Esto conduce a un tiempo de ejecución óptimo en${\displaystyle {\mathcal {O}}(\alpha \log p+\beta pn)}$.

La comunicación de todos a todos ^{[ 11 ]} es el patrón de comunicación más general. Para${\displaystyle 0\leq i,j<p}$, mensaje${\displaystyle m_{i,j}}$es el mensaje que se almacena inicialmente en el nodo${\displaystyle i}$y debe ser entregado al nodo${\displaystyle j}$Podemos expresar todas las primitivas de comunicación que no utilizan operadores a través de la comunicación de todos a todos. Por ejemplo, la difusión de mensajes.${\displaystyle m}$desde el nodo${\displaystyle p_{k}}$se emula configurando${\displaystyle m_{i,j}=m}$para${\displaystyle i=k}$y configuración${\displaystyle m_{l,j}}$vacío para${\displaystyle l\neq k}$.

Suponiendo que tenemos una red totalmente conectada, el mejor tiempo de ejecución posible para la comunicación de todos a todos es en${\displaystyle {\mathcal {O}}(p(\alpha +\beta n))}$Esto se logra mediante${\displaystyle p}$ rondas de intercambio de mensajes directos. Para${\displaystyle p}$potencia de 2, en la ronda de comunicación${\displaystyle k}$, nodo${\displaystyle p_{i}}$intercambia mensajes con el nodo${\displaystyle p_{j},j=i\oplus k}$.

Si el tamaño del mensaje es pequeño y la latencia domina la comunicación, se puede utilizar un algoritmo de hipercubo para distribuir los mensajes en el tiempo.${\displaystyle {\mathcal {O}}(\log p(\alpha +\beta pn))}$.

Esta tabla ^{[ 12 ]} ofrece una visión general de los mejores tiempos de ejecución asintóticos conocidos, suponiendo que podemos elegir libremente la topología de la red . Ejemplos de topologías que buscamos para un tiempo de ejecución óptimo son el árbol binario , el árbol binomial y el hipercubo . En la práctica, debemos adaptarnos a las topologías físicas disponibles, por ejemplo, la libélula, el árbol gordo y la red de cuadrícula (también se incluyen referencias a otras topologías).

Para cada operación, el algoritmo óptimo puede depender del tamaño de las entradas.${\displaystyle n}$Por ejemplo, la difusión de mensajes cortos se implementa mejor utilizando un árbol binomial, mientras que para mensajes largos la comunicación en paralelo sobre un árbol binario equilibrado es la opción óptima.

Las complejidades indicadas en la tabla dependen de la latencia.${\displaystyle \alpha }$y el coste de comunicación por palabra${\displaystyle \beta }$además del número de unidades de procesamiento${\displaystyle p}$y el tamaño del mensaje de entrada por nodo${\displaystyle n}$Las columnas # remitentes y # receptores representan el número de remitentes y receptores involucrados en la operación, respectivamente. La columna # mensajes indica el número de mensajes de entrada y la columna ¿Cálculos? indica si se realizan cálculos sobre los mensajes o si estos se entregan sin procesar. La complejidad proporciona la complejidad asintótica de tiempo de ejecución de una implementación óptima bajo libre elección de topología.

Sanders, Peter ; Mehlhorn, Kurt ; Dietzfelbinger, Martin; Dementiev, Roman (2019). Algoritmos y estructuras de datos secuenciales y paralelos: la caja de herramientas básica . Springer Nature Switzerland AG. ISBN 978-3-030-25208-3.