Problemas de examen resueltos

Teoría: Tema 1 - Evaluación de las prestaciones · Tema 2 - Diseño de algoritmos paralelos · Aula: Problemas de aula resueltos

Problema 28 (oct. 2025)

Producto de matrices $C = A \cdot B$ con $A, B, C \in \mathbb{R}^{n\times n}$, $T(n) = 2n^3 t_c$, memoria distribuida. Cada procesador tiene los mismos índices de $A$, $B$ y $C$. Allgather (recursive doubling): $T_{allgather} \cong \log(p)\,t_s + n\,t_w$.

1. Descomposición del dominio, centrada en la salida. Una tarea por elemento $C(i,j) = \sum_k A(i,k)\,B(k,j)$: $2n$ FLOPs.

2. Comunicaciones. La tarea $(i,j)$ tiene $A(i,j)$ y $B(i,j)$, pero necesita toda la fila $i$ de $A$ y toda la columna $j$ de $B$:

• allgather de $A$ entre las $n$ tareas de cada fila;
• allgather de $B$ entre las $n$ tareas de cada columna.

Comunicaciones globales (dentro de cada fila/columna), estáticas y regulares.

3. Agrupación por filas. Cada procesador tiene $n/p$ filas consecutivas de $A$, $B$ y $C$ ($p \le n$).

• La fila de $A$ ya es local: el allgather de $A$ desaparece (se ha agrupado en esa dirección).
• Para calcular sus filas de $C$ necesita toda $B$: un allgather de $B$ entre los $p$ procesadores, en el que cada uno aporta sus $n^2/p$ datos y todos acaban con los $n^2$.

4. Asignación: estática, un bloque de filas por procesador; balanceada porque todas las filas cuestan lo mismo.

Prestaciones:

Escalabilidad ($W = n^3$):

• $t_s$: $n^3 \propto K p\log p$ → $W \in \theta(p\log p)$.
• $t_w$: $n^3 \propto K p\,n^2 \Rightarrow n \propto Kp \Rightarrow W \in \theta(p^3)$.

Escalable, pero mal ($\theta(p^3)$). Además cada procesador guarda $B$ entera ($n^2$): la memoria no escala. Un agrupamiento 2D (bloques, tipo Cannon/SUMMA) reduce el volumen comunicado a $\approx n^2/\sqrt{p}$ por procesador.

Problema 27 (oct. 2024)

Gram-Schmidt modificado (MGS), $A, Q \in \mathbb{R}^{m\times n}$, $m \le n$. Solo líneas 7–14 de una iteración $i$: para cada columna $j > i$, $dtmp = Q(:,i)\cdot A(:,j)$ (producto escalar, $2m$) y $A(:,j) \mathrel{-}= dtmp\cdot Q(:,i)$ ($2m$). Llamo $c = n - i - 1$ al número de columnas pendientes.

Dato del enunciado (columnas, $p = n$, P2P no optimizado, iteración 0): $T \cong 4m\,t_c + p(t_s + m\,t_w)$. Es: la columna pivote envía $Q(:,i)$ ($m$ datos) a los demás uno a uno, y cada uno hace $4m$ FLOPs.

1. Columnas, iteración genérica, P2P optimizado. El dueño de la columna $i$ difunde $Q(:,i)$ a los $c$ procesadores con columnas pendientes en árbol (árbol binomial):

2. Grafo por filas ($p = m$), $m = 4$, $n = 5$, pivote en la columna 4. $P_k$ tiene la fila $k$ de $A$ y $Q$. Solo queda la columna 5.

• Cada $P_k$ tiene ya $Q(k,4)$ y $A(k,5)$: calcula el producto parcial $Q(k,4)\,A(k,5)$ (1 FLOP).
• $dtmp$ es la suma de los 4 parciales: una reducción, y además todos necesitan el resultado para actualizar su elemento. La mejor opción es un allreduce en hipercubo (reducción con réplica), sin fase de difusión aparte:

paso 1:  P1 <-> P2    P3 <-> P4    (intercambian parcial y suman)
paso 2:  P1 <-> P3    P2 <-> P4    (todos tienen dtmp)
final :  cada Pk:  A(k,5) = A(k,5) - dtmp*Q(k,4)    (2 FLOPs)
         P4 guarda R(4,5) = dtmp

3. Tiempo, eficiencia, coste y sobrecarga (iteración genérica, $p = m$). El allreduce trabaja con vectores de $c$ valores (uno por columna pendiente):

Secuencial de la iteración: $4mc\,t_c$.

(El término en $t_c$ es cálculo redundante: el allreduce hace $m\log m$ sumas donde el secuencial hace $m$.)

4. Escalabilidad ($W = mc$, con $p = m$):

• $t_s$: $mc \propto K m\log m \Rightarrow c \propto \log p$ → crece como $\theta(p\log p)$.
• $t_w$ (y $t_c$): $mc \propto K m\log m\cdot c \Rightarrow 1 \propto K\log p$ → no escala: la eficiencia cae como $1/\log p$. La pérdida es lenta (logarítmica), pero no se compensa haciendo crecer el problema.

5. Algoritmo completo.

• Filas: todas las filas participan en todas las iteraciones (cada iteración toca las $m$ filas de las columnas pendientes): la carga está balanceada durante todo el algoritmo. Coste: un allreduce por iteración.
• Columnas: el procesador de la columna $j$ queda ocioso a partir de la iteración $j$. Con bloques consecutivos, los primeros procesadores acaban enseguida y la eficiencia global cae a $\approx 1/2$ (trabajo triangular). Arreglo: distribución cíclica de columnas.

Conclusión: por filas es mejor en equilibrio de carga; su límite es que solo admite $p \le m$ procesadores ($m \le n$, la dimensión pequeña).

Problema 26 (oct. 2023)

Mismo MGS. El bucle externo no se paraleliza.

1. Líneas 2–5: $\sqrt{\sum_j A(j,i)^2}$, la norma de una columna. Es una reducción (como el producto escalar). Estrategia: divide y vencerás en árbol (árbol binomial), $\theta(\log m)$.

Para las líneas 8–15 en una iteración $i$, con $c = n - i - 1$:

2. Tiempo secuencial:

3. Descomposición del dominio, centrada en los datos de salida: las columnas $A(:,j)$, $j > i$. A cada columna se le aplica la misma operación (producto escalar con $Q(:,i)$ y actualización) y las columnas son independientes entre sí; solo comparten la lectura de $Q(:,i)$.

4. Agrupar por columnas (bloques de columnas, $p \le c$). Así el producto escalar de cada columna es local (no hace falta ninguna reducción) y la única comunicación es difundir $Q(:,i)$ ($m$ datos) desde su dueño. Por filas habría una reducción por columna en cada iteración.

5. Tiempo paralelo (difusión en árbol):

6.

7. Escalabilidad ($W = mc$):

• $t_s$: $mc \propto Kp\log p$ → $\theta(p\log p)$.
• $t_w$: $mc \propto Kp\log p\cdot m \Rightarrow c \propto Kp\log p$ → creciendo el número de columnas, $W \in \theta(p\log p)$.

Escalabilidad buena (no óptima).

8. Algoritmo completo: sí hay pérdida. Las columnas $\le i$ ya están terminadas, así que con bloques consecutivos los procesadores de las primeras columnas se quedan sin trabajo y el último hace casi todo. Variante: distribución cíclica (o bloque-cíclica) de columnas, columna $j \to$ procesador $j \bmod p$. Así todos conservan $\approx c/p$ columnas activas en cada iteración.

Problema 25 (nov. 2022)

$A \in \mathbb{R}^{m\times n}$, $m \gg n$. Contar las filas cuya proyección $P(\text{fila}) = \sqrt{(c_1^2 + \dots + c_n^2)/n}$ es igual a $S_c$. Cuadrado, división, suma y raíz: 1 FLOP.

$T$ secuencial. Por fila: $n$ cuadrados + $(n-1)$ sumas + 1 división + 1 raíz + comparar/contar ≈ $2n + 2$:

1. Descomposición del dominio, por filas: cada fila es independiente. Se podría bajar a elemento, pero entonces cada fila exigiría su propia reducción; con $m \gg n$ hay concurrencia de sobra a nivel de fila.

2. Comunicaciones: solo al final, una reducción (suma) de los $m$ resultados 0/1. Global, en árbol.

3. Agrupar en bloques de $m/p$ filas consecutivas (sin partir filas). Cada procesador cuenta sus filas y al final hay una reducción de un escalar.

4. Asignación estática y balanceada (todas las filas cuestan igual). Supongo, como en el resto del boletín, que la matriz ya está repartida y que $S_c$ lo conocen todos.

Isoeficiencia: $W = mn \propto Kp\log p$ en los tres términos → $\theta(p\log p)$: muy buena. Es de coste óptimo mientras $p\log p \in O(mn)$.

Problema 24 (nov. 2022)

$A \in \mathbb{R}^{m\times n}$, $n > m$, 1 FLOP por elemento. En el grafo, cada elemento se comunica (en los dos sentidos) con 6 vecinos: arriba, abajo, izquierda, derecha y la diagonal principal (arriba-izquierda y abajo-derecha). $m, n$ divisibles por $p$, reparto y recogida gratis.

1. $T(m,n) = mn\,t_c$.

2. 1D por bloques de filas consecutivas (BFC): $m/p$ filas por procesador. La frontera con el bloque de arriba y con el de abajo es una fila. Los vecinos vertical y diagonal de la fila frontera están en la misma fila vecina (desplazados una posición), así que basta con enviar una fila de $\approx n$ datos a cada lado y recibir otra:

3. 1D por bloques de columnas consecutivas (BCC): $n/p$ columnas. Igual, pero las fronteras son columnas de $m$ datos (horizontal y diagonal caen en la misma columna vecina):

4. Relación superficie/volumen:

El volumen es el mismo y, como $n > m$, BCC tiene menos superficie. Se elige BCC. Además admite hasta $p = n$ procesadores, frente a $p = m$ de BFC.

5. Escalabilidad de BCC. $T_0 = 4p(t_s + m\,t_w)$, $W = mn$:

• $t_s$: $mn \propto Kp$ → $\theta(p)$, óptimo.
• $t_w$: $mn \propto Kp\,m \Rightarrow n \propto Kp$. Si el problema crece en $n$ (la dimensión larga) con $m$ fijo, $W = mn \in \theta(p)$: escalabilidad óptima. Si crecen las dos dimensiones a la vez ($m \propto n$), $W \in \theta(p^2)$.

Es escalable.

Problema 23 (nov. 2021)

$A \in \mathbb{R}^{n\times n}$. Se calcula un estadístico global (máximo, media…) con todos los elementos y luego cada elemento se actualiza con él. 1 FLOP por elemento en cada fase. Descomposición del dominio, una tarea por elemento ($p = n^2$).

1. $T(n) = n^2 t_c + n^2 t_c = 2n^2 t_c$.

2.1. Centralizado (cota $\ge T(n)$). Todas las tareas envían su valor a una; esta calcula el estadístico y lo devuelve una a una; cada tarea se actualiza:

Peor que el secuencial: toda la carga recae en una tarea.

2.2. Árbol sobre $n^2$ tareas (divide y vencerás): reducción en $\log n^2$ niveles y difusión en otros $\log n^2$:

2.3. Filas y columnas con réplica (hipercubo en cada dimensión). Primero un allreduce en cada fila ($\log n$ pasos, todas las filas a la vez): cada tarea tiene el estadístico de su fila. Luego un allreduce en cada columna ($\log n$ pasos): todas tienen el global. No hace falta difusión: se ha transformado el grafo de 2.2 replicando cálculo y comunicaciones.

Técnicas usadas: divide y vencerás (de 2.1 a 2.2) y replicación (de 2.2 a 2.3, que la reduce a la mitad).

Problema 22 (dic. 2020)

Este es también el problema 3 de aula. $A \in \mathbb{R}^{n\times n}$, $p$ ordenadores mono-core, comunicación interna gratis. En cada repetición hay que normalizar por filas.

1. Descomposición y comunicaciones. Descomposición del dominio, una tarea por elemento ($p = n^2$). Las filas son independientes entre sí. Dentro de cada fila hay una reducción y todos necesitan el resultado. Mejor modelo: allreduce en hipercubo dentro de cada fila (todas las filas a la vez):

2. Agrupación por bloques de filas ($n/p$ filas por ordenador, $p \le n$). Cada fila queda entera en un ordenador: cero comunicaciones (superficie 0). Por columnas habría que hacer un allreduce de un vector de $n$ sumas parciales en cada repetición.

3. Escalabilidad: $T_0 = 0$ → la eficiencia es 1 para cualquier $p \le n$: escalable. Como mucho hay $p = n$ ordenadores, así que para usar más hace falta $W = n^2 \ge p^2$ (igual que "columnas" en el problema 2 de aula).

Problema 21 (oct. 2020)

1. Qué hace: normaliza cada columna de $M$ dividiéndola por la suma de sus elementos.

2. Por columna, $n$ sumas + $n$ divisiones: $T(n) = 2n^2 t_c$.

3. Por columnas ($n/p$ columnas completas): en a) cada uno tiene ya sus sumas completas, así que pasa directamente a c). Sin comunicaciones:

4. Por filas ($n/p$ filas):

• a) sumas parciales de las $n$ columnas con sus filas: $\frac{n^2}{p}t_c$ → vector de $n$.
• b) el gestor recibe los $p$ vectores uno detrás de otro: $p(t_s + n\,t_w)$; los fusiona sumándolos: $\approx p\,n\,t_c$; y los reenvía a los $p$: $p(t_s + n\,t_w)$.
• c) dividir sus elementos: $\frac{n^2}{p}t_c$.

5.

6. El mejor es por columnas: la dependencia (la suma) va a lo largo de la columna, así que agrupando por columnas queda dentro de cada procesador. $E = 1$ siempre, frente a $E_{fil} < 1$, que además decrece con $p$.

7. Columnas: $T_0 = 0$ → escalable (con el límite $p \le n$, así que $W \ge p^2$). Para comparar, en filas: $T_0 = 2p^2(t_s + n\,t_w) + p^2 n\,t_c$; con $W = n^2$, el término $t_s$ da $\theta(p^2)$ y los términos $t_w$ y $t_c$ dan $n^2 \propto p^2 n \Rightarrow n \propto p^2 \Rightarrow W \in \theta(p^4)$.

Problema 20 (dic. 2019)

Matriz $N \times M$ ($N > M$), $k$ iteraciones:

4 FLOPs por elemento (1 producto, 2 sumas, 1 división): $T = 4kNM\,t_c$.

1. Descomposición del dominio: una tarea por elemento. Fronteras con padding.

2. Comunicaciones: locales, estáticas, regulares. Cada tarea solo depende de sus dos vecinos en diagonal: 2 envíos + 2 recepciones por iteración.

3. Agrupación por diagonales: cero comunicaciones. Las diagonales tienen longitudes distintas, así que hay que juntarlas para equilibrar. Con $N = 5$, $M = 4$ hay 8 diagonales de longitudes $1, 2, 3, 4, 4, 3, 2, 1$ (20 elementos). Con $p = 4$: $\{4,1\}, \{4,1\}, \{3,2\}, \{3,2\}$, 5 elementos cada uno: perfectamente balanceado.

Por comparación, por bloques de filas habría que intercambiar una fila de $M$ datos con cada vecino ($4(t_s + M\,t_w)$ por iteración), y por columnas una de $N$ (peor, porque $N > M$). El inconveniente de las diagonales es que el almacenamiento no es contiguo (hay que reorganizar la matriz por diagonales).

Problema 19 (oct. 2019)

Entrada $n \times n$. Paso 1: $W$ cúbica ($n^3$) que produce un vector de $n$. Paso 2: cuadrático ($n^2$) sobre el vector. Un equipo no puede hacer dos P2P a la vez.

A. $T(n) = (n^3 + n^2)\,t_c \approx n^3 t_c$.

B. Comunicaciones del intercambio (cada uno tiene $n/p$ y todos deben acabar con $n$):

1. Todos a uno y uno a todos: recoger $(p-1)$ trozos en serie, $(p-1)(t_s + \frac{n}{p}t_w) \approx p\,t_s + n\,t_w$; difundir el vector entero a $p-1$ en serie, $(p-1)(t_s + n\,t_w) \approx p\,t_s + p\,n\,t_w$. Total $\approx 2p\,t_s + p\,n\,t_w$.
2. Todos con todos: se organiza en $p-1$ rondas de parejas. En cada ronda cada equipo envía y recibe un trozo (2 P2P, no simultáneas): $(p-1)\cdot 2(t_s + \frac{n}{p}t_w) \approx 2p\,t_s + 2n\,t_w$.

La mejor es la 2: el mismo término en $t_s$, pero en $t_w$ mueve $2n$ datos por equipo frente a $p\,n$.

C. (paso 2 también repartido de forma balanceada)

D.

E. Isoeficiencia ($W = n^3$):

• $t_s$: $n^3 \propto Kp^2$ → $\theta(p^2)$.
• $t_w$: $n^3 \propto Kp\,n \Rightarrow n \propto \sqrt{p} \Rightarrow W \in \theta(p^{3/2})$.

Escalable, no óptimo: domina $\theta(p^2)$ por las latencias. Con la alternativa 1 el término $t_w$ sería $p^2 n$ y daría $\theta(p^3)$.

Problema 18 (dic. 2019): CUDA, coalescencia

Kernel con 1 bloque de 32 hilos; el hilo $x$ recorre la fila $x$:

<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (</span><span style="color: var(--shiki-token-keyword)">int</span><span style="color: var(--shiki-color-text)"> i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">N; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">)</span></span>
<span><span style="color: var(--shiki-color-text)">  </span><span style="color: var(--shiki-token-keyword)">if</span><span style="color: var(--shiki-color-text)"> (M[</span><span style="color: var(--shiki-token-constant)">threadIdx</span><span style="color: var(--shiki-token-punctuation)">.</span><span style="color: var(--shiki-color-text)">x</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">N </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> i] </span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)"> FPA) M[</span><span style="color: var(--shiki-token-constant)">threadIdx</span><span style="color: var(--shiki-token-punctuation)">.</span><span style="color: var(--shiki-color-text)">x</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">N </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> i] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0.0</span><span style="color: var(--shiki-color-text)">;</span></span>
<span></span>

1. No es coalescente. En la iteración $i$, el hilo 0 accede a $M[i]$, el 1 a $M[N + i]$, el 2 a $M[2N + i]$… Hilos consecutivos acceden a posiciones separadas $N$ elementos (stride $N$): cada acceso del warp cae en un segmento de memoria distinto. Con $M$ de 4×4 (row-major) y 4 hilos, en la iteración 0 se leen las posiciones 0, 4, 8, 12.

2. Versión coalescente: que cada hilo recorra una columna, para que en cada iteración los hilos consecutivos lean posiciones consecutivas:

<span><span style="color: var(--shiki-color-text)">__global__ </span><span style="color: var(--shiki-token-keyword)">void</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">Caso2</span><span style="color: var(--shiki-color-text)">(</span><span style="color: var(--shiki-token-keyword)">double</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">M</span><span style="color: var(--shiki-token-punctuation)">,</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-keyword)">const</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-keyword)">double</span><span style="color: var(--shiki-color-text)"> FPA</span><span style="color: var(--shiki-token-punctuation)">,</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-keyword)">const</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-keyword)">int</span><span style="color: var(--shiki-color-text)"> N) {</span></span>
<span><span style="color: var(--shiki-color-text)">  </span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (</span><span style="color: var(--shiki-token-keyword)">int</span><span style="color: var(--shiki-color-text)"> i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">N; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">)</span></span>
<span><span style="color: var(--shiki-color-text)">    </span><span style="color: var(--shiki-token-keyword)">if</span><span style="color: var(--shiki-color-text)"> (M[i</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">N </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">threadIdx</span><span style="color: var(--shiki-token-punctuation)">.</span><span style="color: var(--shiki-color-text)">x] </span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)"> FPA) M[i</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">N </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">threadIdx</span><span style="color: var(--shiki-token-punctuation)">.</span><span style="color: var(--shiki-color-text)">x] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0.0</span><span style="color: var(--shiki-color-text)">;</span></span>
<span><span style="color: var(--shiki-color-text)">}</span></span>
<span></span>

En la iteración $i$ los 4 hilos acceden a $4i, 4i+1, 4i+2, 4i+3$: una sola transacción.

Problema 17 (jun. 2019)

$A, B, C$ complejas $m \times n$ ($m > n$); en cada iteración $C_{ij} \mathrel{+}= A_{ij} \oplus B_{ij}$ y se repite hasta que el error, calculado sobre la parte real de $C$, sea $< \varepsilon$. $p$ procesadores en línea o en malla 2D. $k$ iteraciones.

Secuencial. Por elemento: producto complejo (6) + suma compleja (2) = 8 FLOPs. Error: sumar las partes reales ($mn$), cuadrado, raíz y división ($\approx$ 3). Por iteración $\approx 9mn$:

Diseño. La actualización de cada elemento es independiente (sin vecinos). La única dependencia global es el error: una reducción de un escalar cuyo resultado necesitan todos para decidir si siguen. Es decir, un allreduce de 1 dato por iteración. Como no hay comunicación entre vecinos, la forma de los bloques da igual para el volumen de datos. Lo que importa es cuántos saltos cuesta el allreduce en cada topología.

Se elige la malla 2D con bloques 2D (las dimensiones son divisibles por $\sqrt{p}$). Con $m = 4$, $n = 3$: 12 tareas en una malla, cada una con su bloque.

Escalabilidad ($W = kmn$):

• Línea: $T_0 \approx 2kp^2(t_s + t_w)$ → $W \in \theta(p^2)$.
• Malla: $T_0 \approx 4kp\sqrt{p}(t_s + t_w)$ → $W \in \theta(p^{3/2})$. Mejor.

Problema 16 (may. 2019)

$C_{ij} = A_{ij} \oplus B_{ij}$ (producto complejo, 6 FLOPs), una sola vez: $T = 6mn\,t_c$.

No hay ninguna dependencia entre elementos: cualquier particionado 1D o 2D da

si no se cuenta la distribución. Escalable hasta $p = mn$. La eficiencia escalada es la recta $E_{sca} = 1$.

Lo que decide de verdad es el reparto y la recogida, si se cuentan: desde un nodo, P2P en serie, hay que enviar $A$ y $B$ ($2mn$ complejos = $4mn$ reales) y recoger $C$ ($2mn$ reales): $\approx 2p\,t_s + 6mn\,t_w$. Entonces $T_0 \ni 6p\,mn\,t_w$ → $mn \propto Kp\,mn \Rightarrow$ no escala. En una malla 2D se puede distribuir por filas de la malla y luego por columnas en paralelo (en $\approx 2\sqrt{p}$ etapas), lo que reduce el término de latencia.

Problema 15 (dic. 2018)

Filtro del problema 14 en un ordenador: CPU con $p$ núcleos ($t_c$) y una GPU $S$ veces más potente que la CPU (entera). $t_s$, $t_w$: comunicaciones CPU/GPU.

1. Reparto proporcional a la potencia: $x + Sx = N^2 \Rightarrow$ CPU $\frac{N^2}{S+1}$, GPU $\frac{S\,N^2}{S+1}$, en bloques de filas. Así las dos terminan a la vez.

2.

• CPU paralela: $T_{CPU} = \dfrac{K N^2 R^2}{p}t_c$.
• Heterogénea: cargar en la GPU su parte, $K$ iteraciones de cálculo (equilibradas), intercambiar en cada iteración las $\frac{R-1}{2}$ filas frontera entre CPU y GPU, y descargar:

3. Con $K = 1$, $t_c = t_s = t_w = 1$, $p = R$ y carga/descarga gratis: con una sola iteración el halo viaja con la carga inicial (gratis), así que

Cualquier GPU ($S > 0$) compensa, con ganancia $S + 1$. La decisión deja de ser trivial en cuanto la transferencia cuesta: con carga/descarga de coste $2(1 + \frac{S N^2}{S+1})$ hace falta $S(N^2(R-2) - 2) > 2$, es decir, $R > 2$ y $S > \dfrac{2}{N^2(R-2) - 2}$.

Problema 14 (dic. 2018)

Filtro gaussiano $K$ veces, imagen $N\times N$, máscara $R \times R$ (sin separabilidad), $R^2$ FLOPs por píxel. Reparto/recogida gratis. Radio $r = \frac{R-1}{2}$.

1. $T(N) = K N^2 R^2 t_c$.

2. Descomposición del dominio, un píxel por tarea ($p = N^2$). Cada tarea necesita los $R^2 - 1$ vecinos de su ventana (con $R = 3$, $N = 5$: los 8 vecinos de cada píxel; los bordes usan padding). Comunicaciones locales, estáticas, regulares, síncronas.

3. Agrupamientos 1D:

• Bloques de filas: $N/p$ filas. Se intercambian $r$ filas con el bloque de arriba y con el de abajo: $T = K\left(\frac{N^2R^2}{p}t_c + 4(t_s + rN\,t_w)\right)$.
• Bloques de columnas: por simetría (imagen cuadrada, máscara simétrica) sale exactamente lo mismo.

Analíticamente son equivalentes. En la práctica, con almacenamiento row-major, las filas son mejores: el halo es contiguo y se envía sin empaquetar.

Escalabilidad: $T_0 = 4Kp(t_s + rN\,t_w)$; $t_s$ da $\theta(p)$ y $t_w$: $N^2 \propto KpN \Rightarrow W \in \theta(p^2)$. Además $p \le N/r$.

Problema 13 (oct. 2018)

$T(n) = n^2 t_c$. Un ordenador central que no calcula y $p$ de cálculo: $p/2$ de tipo A (1 núcleo) y $p/2$ de tipo B (2 núcleos), todos con $t_c$. Solo hay comunicación en el reparto inicial.

1. Reparto óptimo = proporcional a la potencia. Si A recibe $x$, B recibe $2x$:

Así todos tardan $\frac{2n^2}{3p}t_c$.

2. El central envía en serie $p$ mensajes que suman $n^2$ datos: $p\,t_s + n^2 t_w$. El último en recibir empieza a calcular al final:

Hay $\frac{p}{2} + p = \frac{3p}{2}$ núcleos de cálculo; los uso como recursos para coste y eficiencia:

3. $t_s$: $n^2 \propto Kp^2$ → $\theta(p^2)$. $t_w$: $n^2 \propto Kp\,n^2 \Rightarrow 1 \propto Kp$ → no escalable.

4. Gustafson–Barsis: la parte secuencial (el reparto, $\propto n^2 t_w$) crece igual que el trabajo, así que la fracción secuencial no disminuye al agrandar el problema:

Según Gustafson, el algoritmo no escala: agrandar el problema no compensa.

Problema 12

Es el ejemplo de clase del clúster CPU + GPU (GPU 9×). Está resuelto en Tema 1, sistemas heterogéneos. Resultado: no escala por el término $t_w$ del reparto.

Problema 11

Filtro gaussiano 1D, máscara 3, en el eje vertical de $M \in \mathbb{R}^{m\times n}$, $R$ veces. Clúster de $p$ ordenadores con CPU mono-core y GPU 19× la CPU.

1. Descomposición del dominio, un elemento por tarea. Cada elemento depende de arriba y abajo. $T = R\,mn\,t_c$. Con $mn$ ordenadores: $T = R\big(4(t_s + t_w) + t_c\big)$.

2. Agrupar por bloques de columnas: las dependencias son verticales, así que cada columna las contiene todas y no hay comunicaciones. Almacenamiento column-major (columnas contiguas). A cada ordenador le tocan $n/p$ columnas, es decir, $\frac{mn}{p}$ elementos.

3. Un ordenador. Secuencial: $R\frac{mn}{p}t_c$. Heterogéneo: CPU $\frac{1}{20}$ de sus columnas y GPU $\frac{19}{20}$. Al ser columnas independientes, no hay halo entre CPU y GPU:

4. Con CPU/GPU gratis y sin comunicación entre ordenadores: $T = \dfrac{R\,mn}{20p}t_c$. Equivale a $20p$ CPUs sin sobrecarga: escalable (hasta $p = n$). Si se contara el reparto desde un nodo en serie ($\approx 2p\,t_s + 2mn\,t_w$), el término $p\,mn\,t_w$ de $T_0$ lo haría no escalable.

Problema 10

Igual que el 11 pero el filtro va en el eje horizontal y cada ordenador tiene CPU de $k$ núcleos y GPU 9× la CPU:

• Dependencias horizontales → agrupar por bloques de filas, almacenamiento row-major, $\frac{mn}{p}$ elementos por ordenador, sin comunicaciones.
• En cada ordenador: CPU $\frac{1}{10}$ (repartido entre sus $k$ núcleos) y GPU $\frac{9}{10}$, sin halo entre ellas.