Teo. 4: Operaciones básicas de comunicación

Algoritmos paralelos

Glen Rodríguez

Introducción

Tiempo com.= + n* = ts + n*tw

La comunicación afecta el tiempo total= t. proceso + t. comunicación + t. ocioso (idle)

En programas paralelos, muchas veces hay un patrón reconocible de comunicaciones. Los patrones comunes se usan como bloque básicos.

Broadcast Uno-a-todos y Reducción Todos-a-uno

Broadcast: Al inicio solo un proceso tiene el valor M de tamaño m. Al final, hay p copias de ese valor M.

El dual es la reducción: hay p valores diferentes de M (Mi) y al final hay un solo valor de M (combinación de los Mi por ejemplo como promedio, suma, producto, máximo) en un solo proceso

Usos: multipl. matriz-vector, Eliminación Gaussiana, Ruta más corta, producto punto

Ejemplo en anillo o arreglo lineal

Duplicación recursiva, acá origen es el nodo 0. En 3 pasos de tiempo se termina el broadcasting.

Duplicación recursiva, pero en reducción. Los nodos intermedios guardanresultados intermedios. Ej.: 6 guarda resultado de 6 y 7.

Ejemplo en una mesh o malla

Pasos1: broadcast de nodo 0a toda su fila2: cada nodo al inicio deuna columna hace broadcast al resto de la columna.

En ambos pasos puedeusarse duplic. recursiva

En un hipercubo

2d nodos, d dimensiones, entonces se puede hacer en d pasos

Costo

Asumiendo p procesos, con data de m bytes, tenemos:

T= (ts + n*tw) log(p)

Broadcast Todos-a-todos y Reducción Todos-a-todos

B.t.a.t. es la generalización del broadcast. Se hacen p broadcasts (1 por cada proceso o nodo) a la vez

La R.t.a.t. es una en la que cada nodo es sujeto a una reducción.

Se usan mucho en multiplicaciones de matrices

Ejemplo: anillo

En p-1 pasos

Ejemplo: mesh

Costos

En un anillo T= (ts + n*tw) (p-1)

En un mesh T= 2ts (√√p -1) +ntw(p-1)

All-Reduce y Prefix-Sum

All reduce= reducción t.a.uno y luego un broadcast t.a.uno del resultado de dicha reducción

“Sacar una suma y luego copiar la suma a todos”

En vez de esas dos operaciones, en algunas topologías (ej.: hipercubos, anillo) es mejor usar el patrón de comunicaciones de b.t.a.t

Scatter y Gather

Scatter: un nodo tiene p mensajes (1 para cada nodo, incluyendo a si mismo) y los envia.

Gather: un nodo recolecta un mensaje enviado por p nodos, y los junta.

Generalmente, cada mensaje= parte de un vector/matriz.

En un hipercubo, el patrón es parecido a un broadcast

Costo:

T= ts log(p)+

n*tw (p-1)

Comunicación personalizada Todos-a-todos

Cada nodo manda un distinto mensaje del mismo tamaño m a todos los demás nodos.

Se le llama “total exchange” Se usa en transposición de matrices,

transformadas de Fourier, etc.

Ejemplo: matriz transpuesta

Ejemplo: anillo

Enviar (p-1) mensajes a otro nodo, ese nodo lee su mensaje y reenvía (p-2) mensajes a otro nodo, …

Ejemplo mesh

Crear √p gruposde mensajes1: repartirlo a lafila propia2: repartirlo en lacolumna propia

Costos

Anillo:

Mesh:

Desplazamiento circular

Tipo de “Permutación”: cada nodo manda un mensaje de datos a solo otro nodo.

Desp. Circular en q (q-shift): permutación donde nodo 0 manda data al q, el 1 al q+1, el 2 al q+2,…, el (i) al (i+q) mod p, … el p-1 al q-1, el p al q.

Ejemplo: en mesh

Costo:T= (ts+ntw) (√√p +1)