Práctica: matriz × vector

PD03, Ej. 2: $x=A\,v$ con $A$ de $N\times N$. P0 tiene $A$ y $v$, reparte por bloques de filas o de columnas, envía $v$ y obtiene $x$. $W(N)=\Theta(N^2)$ en ambos: toda la diferencia de escalabilidad está en el overhead.

Filas (colectivas)

practica_3_ofi/ejercicio02_row.cpp (núcleo)

MPI_Bcast(v, N, MPI_LONG_LONG, 0, MPI_COMM_WORLD);
MPI_Scatter(A, elem_proc, MPI_INT, local_A, elem_proc, MPI_INT, 0, MPI_COMM_WORLD);

for (i = 0; i < fil_proc; i++) {          // fil_proc = N / size
    local_x[i] = 0;
    for (j = 0; j < N; j++)
        local_x[i] += local_A[i * N + j] * v[j];
}

MPI_Gather(local_x, fil_proc, MPI_LONG_LONG, x, fil_proc, MPI_LONG_LONG, 0, MPI_COMM_WORLD);

Columnas (Send + vector)

practica_3_ofi/ejercicio02_col.cpp (núcleo)

MPI_Type_vector(N, col_proc, N, MPI_LONG_LONG, &coltype);   // bloque de columnas
MPI_Type_commit(&coltype);

if (rank == 0) {
    for (dest = 1; dest < size; dest++) {                      // p-1 envíos secuenciales
        MPI_Send(&A[dest * col_proc], 1, coltype, dest, 0, MPI_COMM_WORLD);
        MPI_Send(&v[dest * col_proc], col_proc, MPI_LONG_LONG, dest, 1, MPI_COMM_WORLD);
    }
} else {
    MPI_Recv(local_A, N * col_proc, MPI_LONG_LONG, 0, 0, MPI_COMM_WORLD, &status);
    MPI_Recv(local_v, col_proc, MPI_LONG_LONG, 0, 1, MPI_COMM_WORLD, &status);
}

for (i = 0; i < N; i++) {                  // x parcial de largo N
    partial_x[i] = 0;
    for (j = 0; j < col_proc; j++)
        partial_x[i] += local_A[i * col_proc + j] * local_v[j];
}
MPI_Reduce(partial_x, x, N, MPI_LONG_LONG, MPI_SUM, 0, MPI_COMM_WORLD);

Matriz × vector: filas vs columnas vs bloques

A de N×N (aquí N=8) repartida entre p procesos. Color = proceso dueño de la celda.

filascolumnasbloques

p=2p=4p=8p=16

Fase	filas
Distribuir A	MPI_Scatter de N/p filas contiguas
Distribuir v	MPI_Bcast de v completo (N)
Cómputo	N/p productos punto de largo N
Resultado	MPI_Gather de N/p elementos de x

v[j] necesario por: todos

Modelo teórico del examen (arquetipo B)

$T_p^{filas}=\gamma\frac{n^2}{p}+\alpha\log p+\beta n\qquad T_p^{bloques}=\gamma\frac{n^2}{p}+2\alpha\log\sqrt p+\beta\frac{n}{\sqrt p}$

n = 1e3γ = 1e-9α = 1e-6β = 1e-8

Eficiencia teórica E(p)

filasbloques

Granularidad G = T_comp / T_comm

filasbloques

Bloques: denominador de G más chico ⇒ mayor granularidad. Escalabilidad (oficial): filas $n\propto p$; bloques $n\propto\sqrt{p\log p}$ ⇒ bloques necesita menos crecimiento de n para mantener E: más escalable.

Datos medidos (practica_3_ofi, laptop, p = 1…10)

Filas (Bcast + Scatter/Gather)

N=240N=360N=480N=600

Columnas (Send + vector + Reduce)

N=240N=360N=480N=600

p	filas, N=5040 (s)			columnas, N=5040 (s)
	T_ej	T_comp	T_comm	T_ej	T_comp	T_comm
2	0.0374	0.0109	0.0265	0.102	0.0117	0.0496
4	0.0496	0.0104	0.0391	0.118	0.0134	0.0593
6	0.0568	0.00946	0.0471	0.157	0.0114	0.0899
8	0.0654	0.00839	0.0568	0.168	0.00968	0.092
10	0.0719	0.00744	0.0642	0.174	0.0093	0.0964

E(p=10): filas 0.058 → 0.184 al pasar de N=240 a 600 (mejora con N); columnas 0.048 → 0.030 (no mejora). Con N fijo el tiempo total crece con p: el problema es communication-bound en este rango (T_comm ≫ T_comp).

Análisis (de analisis_escalabilidad.md)

Esquema	$T_o(N,p)$	Isoeficiencia	$E(p=10)$: $N=240\to600$
Filas	$\Theta(p\log p)$ (colectivas en árbol)	$N=\Theta(\sqrt{p\log p})$	$0.058\to0.184$ (mejora)
Columnas	$\Theta(p)+\Theta(N^2)$ (bucle de Send en P0)	no hay favorable	$0.048\to0.030$ (no mejora)

En columnas, P0 mueve $\Theta(N^2)$ datos él solo: una fracción serial al estilo Amdahl del mismo orden que el trabajo, que no se diluye al crecer $N$. En filas, la fracción serial efectiva $\frac{\Theta(p\log p)}{\Theta(N^2)+\Theta(p\log p)}\to0$ (estilo Gustafson).

Medición

Con $N\le600$ los tiempos son de milisegundos, cerca de la resolución del reloj: algunos speedups > 1 en filas son ruido, no superlinealidad. La tendencia general no cambia.

En el examen…

Con $N=5040$ fijo el tiempo total crece con $p$ (communication-bound, sin óptimo interno de $p$): respuesta de manual para «¿punto óptimo de procesos?» ⇒ el menor $p$ probado. Y siempre relaciona: granularidad (cómputo/comunicación), overhead y escalabilidad.

Ejercicio (PD02 2025-II, Ej. 2 — arquetipo B)

$T_p^{filas}=\gamma\frac{n^2}{p}+\alpha\log p+\beta n$ y $T_p^{bloques}=\gamma\frac{n^2}{p}+2\alpha\log\sqrt p+\beta\frac{n}{\sqrt p}$. (a) ¿Cuál tiene mayor granularidad? (b) Condición de escalabilidad. (c) ¿Cuál es más escalable?

Ver solución

(a) $G_{filas}=\dfrac{n^2}{p(n+\log p)}$, $\;G_{bloques}=\dfrac{n^2}{p\left(\frac{n}{\sqrt p}+2\log\sqrt p\right)}$. Bloques tiene el denominador más chico ⇒ mayor granularidad ⇒ menor overhead de comunicación.

(b) Filas: $n\propto p$. Bloques: $n\propto\sqrt{p\log p}$.

(c) Bloques es más escalable. Solución oficial: con filas, al duplicar $n$ se obtiene $p_2=2p_1$; con bloques se obtiene otra relación, «lo que lo hace más escalable, ya que cuando $n$ crece se requieren menos procesos para mantener la eficiencia constante». Dicho de otra forma: para un mismo $p$, bloques necesita un $n$ mucho menor ($\sqrt{p\log p}\ll p$) para sostener la misma eficiencia.

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. En la partición por filas, ¿qué recibe cada proceso de $v$?

a) nadab) solo su tramoc) todo $v$ (Bcast)d) una columna

2. En columnas, el resultado se combina con…

a) Gather de $N/p$ elementosb) Reduce(SUM) de $N$ elementosc) Bcastd) Allgather

3. Según los datos medidos, al pasar de N=240 a N=600 con p=10, la eficiencia en filas…

a) bajab) sube (0.058 → 0.184)c) no cambiad) llega a 1

4. ¿Por qué columnas no mejora con $N$?

a) por el Reduceb) P0 envía $\Theta(N^2)$ datos secuencialmente: overhead del orden del trabajoc) por el tipo vectord) por el caché

Fuente ·practica_3_ofi/ejercicio02_row.cpp · practica_3_ofi/ejercicio02_col.cpp · practica_3_ofi/executed/eficiencia_resultados.csv · resultados_5040.csv · executed/analisis_escalabilidad.md · executed/informe_2_3.md · previos/2025-II PD02 S01/S02 (Ej. 2)