Operación colectiva

Las operaciones colectivas son bloques de construcción para patrones de interacción, que a menudo se utilizan en algoritmos SPMD en el contexto de programación paralela . Por tanto, existe interés en la realización eficiente de estas operaciones.

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

Si no tenemos una distribución igual, es decir, el nodo tiene un mensaje de tamaño , obtenemos un límite superior para el tiempo de ejecución mediante la configuración . ${\ Displaystyle p_ {i}}$ ${\ Displaystyle n_ {i}}$ ${\ 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 transmisión ( § Transmisión ), por ejemplo, lo que permite una lectura concurrente conveniente. ^[2] Por lo tanto, pueden estar disponibles nuevas posibilidades algorítmicas.

El patrón de transmisión se utiliza para distribuir datos desde una unidad de procesamiento a todas las unidades de procesamiento, lo que a menudo se necesita en los programas paralelos de SPMD para dispensar valores de entrada o globales. La transmisión se puede interpretar como una versión inversa del patrón de reducción ( § Reducir ). Inicialmente solo root con mensaje de tiendas . Durante la difusión se envía al resto de unidades de procesamiento, de modo que eventualmente esté disponible para todas las unidades de procesamiento. ${\ Displaystyle r}$ ${\ ID de estilo de pantalla}$ ${\ displaystyle 0}$ ${\ Displaystyle m}$ ${\ Displaystyle m}$ ${\ Displaystyle m}$

Flujo de información de la operación de transmisión realizada en tres nodos.

Hay tres cuadrados alineados verticalmente a la izquierda y tres cuadrados alineados verticalmente a la derecha. Se coloca un círculo con la letra f en el interior entre las dos columnas. Tres líneas continuas conectan el círculo con los tres cuadrados de la izquierda. Una línea continua conecta el círculo y el cuadrado superior derecho. Las letras a, byc están escritas en los cuadrados de la izquierda de mayor a menor. La letra alfa está escrita en el cuadrado superior derecho.

Flujo de información de la operación Reducir realizada en tres nodos. f es el operador asociativo y α es el resultado de la reducción.

Flujo de información de la operación All-Reduce realizada en tres nodos. f es el operador asociativo y α es el resultado de la reducción.

Flujo de información de la operación Prefix-Sum / Scan realizada en tres nodos. El operador + puede ser cualquier operador asociativo.

Hay tres cuadrados alineados verticalmente a la izquierda y tres rectángulos alineados verticalmente a la derecha. Una línea de puntos conecta el cuadrado superior izquierdo con el rectángulo superior derecho. Dos líneas continuas conectan los cuadrados izquierdo medio y bajo con el rectángulo superior derecho. Las letras a, byc están escritas en los cuadrados de la izquierda de mayor a menor. Las letras a, byc están escritas en el rectángulo superior derecho en una fila.

El flujo de información de la operación Gather se realiza en tres nodos.

Hay tres cuadrados alineados verticalmente a la izquierda y tres rectángulos alineados verticalmente a la derecha. Tres líneas de puntos conectan el cuadrado superior izquierdo con el rectángulo superior derecho, el cuadrado medio izquierdo con el rectángulo medio derecho y el cuadrado inferior izquierdo con el rectángulo inferior derecho. Dos líneas continuas conectan los cuadrados izquierdo medio y bajo con el rectángulo superior derecho. Dos líneas continuas conectan los cuadrados izquierdo alto y bajo con el rectángulo medio derecho. Dos líneas continuas conectan los cuadrados izquierdo alto y medio con el rectángulo derecho bajo. Las letras a, byc están escritas en los cuadrados de la izquierda de mayor a menor. Las letras a, byc están escritas en todos los rectángulos rectos seguidos.

El flujo de información de la operación All-Gather se realiza en tres nodos.

Hay tres rectángulos alineados verticalmente a la izquierda y tres cuadrados alineados verticalmente a la derecha. Una línea de puntos conecta el rectángulo superior izquierdo con el cuadrado superior derecho. Dos líneas continuas conectan el rectángulo superior izquierdo con los cuadrados medio y bajo derecho. Las letras c, by a están escritas en el rectángulo superior izquierdo en una fila. Las letras a, byc están escritas en los cuadrados de la derecha de mayor a menor.

Flujo de información de la operación Scatter realizada en tres nodos.

Hay tres rectángulos alineados verticalmente a la izquierda y tres rectángulos alineados verticalmente a la derecha. Los rectángulos son tres veces más altos que anchos. Los términos a1, a2 y a3 están escritos en el rectángulo superior izquierdo uno debajo del otro. Los términos b1, b2 y b3 están escritos en el rectángulo central izquierdo uno debajo del otro. Los términos c1, c2 y c3 están escritos en el rectángulo inferior izquierdo uno debajo del otro. Los términos a1, b1 y c1 están escritos en el rectángulo superior derecho uno debajo del otro. Los términos a2, b2 y c2 están escritos en el rectángulo central derecho uno debajo del otro. Los términos a3, b3 y c3 están escritos en el rectángulo inferior derecho uno debajo del otro. Una línea de puntos conecta a1 del rectángulo superior izquierdo y a1 del rectángulo superior derecho. Una línea de puntos conecta b2 desde el rectángulo central izquierdo y b2 desde el rectángulo central derecho.Una línea de puntos conecta c3 desde el rectángulo inferior izquierdo y c3 desde el rectángulo inferior derecho. Las líneas continuas conectan los otros términos correspondientes entre los rectángulos izquierdo y derecho.

Flujo de información de la operación All-to-All realizada en tres nodos. Las letras indican nodos y los números indican elementos de información.