Teo. 4: Operaciones básicas de comunicación
-
Upload
courtney-bradshaw -
Category
Documents
-
view
49 -
download
2
description
Transcript of Teo. 4: Operaciones básicas de comunicación
![Page 1: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/1.jpg)
Teo. 4: Operaciones básicas de comunicación
Algoritmos paralelos
Glen Rodríguez
![Page 2: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/2.jpg)
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.
![Page 3: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/3.jpg)
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
![Page 4: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/4.jpg)
Usos: multipl. matriz-vector, Eliminación Gaussiana, Ruta más corta, producto punto
![Page 5: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/5.jpg)
Ejemplo en anillo o arreglo lineal
Duplicación recursiva, acá origen es el nodo 0. En 3 pasos de tiempo se termina el broadcasting.
![Page 6: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/6.jpg)
Duplicación recursiva, pero en reducción. Los nodos intermedios guardanresultados intermedios. Ej.: 6 guarda resultado de 6 y 7.
![Page 7: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/7.jpg)
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
![Page 8: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/8.jpg)
En un hipercubo
2d nodos, d dimensiones, entonces se puede hacer en d pasos
![Page 9: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/9.jpg)
Costo
Asumiendo p procesos, con data de m bytes, tenemos:
T= (ts + n*tw) log(p)
![Page 10: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/10.jpg)
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
![Page 11: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/11.jpg)
![Page 12: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/12.jpg)
Ejemplo: anillo
En p-1 pasos
![Page 13: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/13.jpg)
Ejemplo: mesh
![Page 14: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/14.jpg)
Costos
En un anillo T= (ts + n*tw) (p-1)
En un mesh T= 2ts (√√p -1) +ntw(p-1)
![Page 15: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/15.jpg)
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
![Page 16: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/16.jpg)
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.
![Page 17: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/17.jpg)
En un hipercubo, el patrón es parecido a un broadcast
![Page 18: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/18.jpg)
Costo:
T= ts log(p)+
n*tw (p-1)
![Page 19: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/19.jpg)
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.
![Page 20: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/20.jpg)
![Page 21: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/21.jpg)
Ejemplo: matriz transpuesta
![Page 22: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/22.jpg)
Ejemplo: anillo
Enviar (p-1) mensajes a otro nodo, ese nodo lee su mensaje y reenvía (p-2) mensajes a otro nodo, …
![Page 23: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/23.jpg)
Ejemplo mesh
Crear √p gruposde mensajes1: repartirlo a lafila propia2: repartirlo en lacolumna propia
![Page 24: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/24.jpg)
Costos
Anillo:
Mesh:
![Page 25: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/25.jpg)
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.
![Page 26: Teo. 4: Operaciones básicas de comunicación](https://reader036.fdocumento.com/reader036/viewer/2022081513/56812a5d550346895d8dc736/html5/thumbnails/26.jpg)
Ejemplo: en mesh
Costo:T= (ts+ntw) (√√p +1)