Comunicación colectiva

Propiedades: todos los procesos del comunicador participan (cada llamada colectiva debe incluirlos a todos); no interfiere con punto a punto; el buffer se reutiliza cuando el proceso termina la llamada. La librería optimiza la comunicación (árboles).

Rutina	Qué hace
MPI_Barrier(comm)	sincroniza: nadie sigue hasta que todos llegan. Casi nunca hace falta (útil para debugging/medir tiempos)
MPI_Bcast(&buf, count, type, root, comm)	root → todos
MPI_Scatter(&sbuf, scnt, stype, &rbuf, rcnt, rtype, root, comm)	root reparte trozos de scnt elementos por proceso, en orden de rank
MPI_Gather(&sbuf, scnt, stype, &rbuf, rcnt, rtype, root, comm)	inverso de Scatter: root junta en orden de rank
MPI_Allgather(...) (sin root)	Gather + Bcast: todos obtienen todo
MPI_Reduce(&sbuf, &rbuf, count, type, op, root, comm)	combina con op (MPI_SUM, MPI_MAX, MPI_MIN, MPI_PROD…) en root
MPI_Allreduce(&sbuf, &rbuf, count, type, op, comm)	Reduce + resultado en todos

Colectivas MPI: lineal vs árbol

Cada paso = mensajes simultáneos; costo del paso = α + β·(mensaje más grande). La raíz es P0.

MPI_BcastMPI_ScatterMPI_GatherMPI_ReduceMPI_Allreduce

Topología linealÁrbol binario

p = 8α (latencia) = 1e-6 sβ (s/elemento) = 1e-9 sm (elementos) = 1e6

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

paso 0/3

Pasos (arbol)3

T simulado (arbol)0.003 s

Pasos (lineal)7

T (lineal)0.00701 s

log₂ p3

Lineal: $O(p(\alpha+m\beta))$  ·  Árbol: $O(\log p\,(\alpha+m\beta))$
El árbol reduce el término de latencia de αp a α log p; en Scatter/Gather el término βm no cambia (el volumen total de datos es el mismo).

Error común

En MPI_Scatter, sendcnt es por proceso (elementos del array / número de procesos), no el total. Y el recvbuf de Gather/Reduce solo importa en root.

En el examen…

Cuando el código usa un bucle de Send desde el maestro, di que es lineal $O(p\alpha)$ y que la colectiva equivalente cuesta $O(\alpha\log p)$. Es el argumento de la práctica 3: filas (colectivas) escala mejor que columnas (bucle de Send).

Código de clase (session2)

Bcast + Reduce

session2/ejemplo01-bcast-reduce.cpp

if (rank == 0) data = 5;
// 1. el maestro envía data a todos
MPI_Bcast(&data, 1, MPI_INT, 0, MPI_COMM_WORLD);
data *= rank;                                      // 2. cada uno modifica
MPI_Reduce(&data, &resultado, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
// 3. resultado (solo en el maestro) = 5·(0+1+…+(p−1))
if (rank == 0) cout << "resultado: " << resultado << endl;

Scatter + Gather

session2/ejemplo02-scatt-gath-array.cpp

int data_global[10 * size], data_local[10];
if (rank == 0)
    for (int i = 0; i < 10 * size; i++)
        data_global[i] = 2 * i + 1;
// 10 elementos POR proceso
MPI_Scatter(data_global, 10, MPI_INT, data_local, 10, MPI_INT, 0, MPI_COMM_WORLD);
for (int i = 0; i < 10; i++) data_local[i] = rank * rank;
MPI_Gather(data_local, 10, MPI_INT, data_global, 10, MPI_INT, 0, MPI_COMM_WORLD);

Allreduce

session2/ejemplo03-allreduce.cpp

// cada proceso aporta su rank; todos reciben la suma
MPI_Allreduce(&me, &sum, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);
printf("proceso %i: sum = %i\n", me, sum);   // todos imprimen p(p-1)/2

π (pi-reduce)

session2/pi-reduce/ejemplo03-PI-reduce.cpp

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
for (int i = (n / mpi_size * mpi_rank) + 1; i <= (n / mpi_size * (mpi_rank + 1)); ++i)
    local_sum += (4 / (1 + pow((i - 0.5) / n, 2)));
MPI_Reduce(&local_sum, &global_sum, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
// S(n) = O(n/(n/p)) = O(p), E(n) = O(1)

Pruébalo en Montecarlo π → Integración.

Medido: π con MPI_Reduce de np = 1 a 128

El mismo ejemplo03-PI-reduce.cpp se midió con N = 10² … 10⁶ iteraciones. Es la mejor evidencia de por qué la escalabilidad depende de N.

π con MPI_Reduce: tiempos medidos (np = 1 … 128)

Datos reales del benchmark de ejemplo03-PI-reduce.cpp para 5 tamaños N. ¿Cuándo conviene paralelizar?

TiempoSpeedupEficienciaFLOP/s

N=10²N=10³N=10⁴N=10⁵N=10⁶

N = 10³N = 10⁴N = 10⁵N = 10⁶

Carrera de tiempos para N =

10²10³10⁴10⁵10⁶

np=1

15.8 ms

np=2

12.7 ms

np=4

6.64 ms

np=8

4.39 ms

np=16

1.84 ms

np=32

1.3 ms

np=64

0.951 ms ★

np=128

1.11 ms

Para N = 10⁶ el mínimo está en np = 64 (S = 16.7). Con N pequeño el costo de MPI_Bcast/MPI_Reduce (latencia ~α log p) supera al cómputo O(N/p): más procesos = más lento. Con N grande el punto óptimo se desplaza a más procesos — la misma lección que N-Body y la isoeficiencia.

Ejercicio (U3.2, Ej. 5): promedio

Array de 1000 números aleatorios 0–100. Reparta con MPI_Scatter, cada proceso calcula su promedio, junte los promedios con MPI_Gather y el maestro calcula el promedio global. ¿Es correcto promediar los promedios? ¿Qué colectiva sería mejor?

Ver solución

Es correcto solo si todos los trozos tienen el mismo tamaño (1000 divisible por $p$); si no, hay que ponderar por el tamaño de cada trozo. Mejor aún: cada proceso calcula su suma local y se hace un único MPI_Reduce(MPI_SUM); el maestro divide entre 1000. Evita juntar $p$ valores en un array y el costo es $O(\log p)$ en árbol.

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. ¿Qué colectiva deja el resultado de la reducción en TODOS los procesos?

a) MPI_Reduceb) MPI_Gatherc) MPI_Allreduced) MPI_Bcast

2. MPI_Allgather equivale a…

a) Scatter + Gatherb) Gather + Bcastc) Reduce + Bcastd) Bcast + Scatter

3. En Scatter con 40 elementos y 4 procesos, sendcnt =

a) 40b) 10c) 4d) 160

4. Bcast en árbol vs lineal: pasos con $p=16$

a) 4 vs 15b) 16 vs 16c) 8 vs 15d) 4 vs 4

Fuente ·U3.2 Paralelismo Distribuido-MPI.pdf · session2/*.cpp · session2/pi-reduce/ejemplo03-PI-reduce.cpp · session2/pi-reduce/ej03_res.txt, ej03.plt · 05_Particionamiento.md §2