Método de Foster (PCAM)

Ian Foster (Designing and Building Parallel Programs, 1995). Dos abstracciones:

• Task = programa + memoria local + puertos de entrada/salida.
• Channel = cola de mensajes que conecta la salida de un task con la entrada de otro: define la dependencia.

Definición

En el modelo task/channel el envío es asíncrono y el recibo es síncrono (bloquea). Propiedades deseables: performance, independencia (el resultado no depende de dónde corre), modularidad y determinismo.

Los 4 pasos

1. Particionar — dividir datos y tareas en muchas primitive tasks.
   • Descomposición del dominio: divide la data (la más grande / más accedida) y luego asigna tareas.
   • Descomposición funcional: divide la tarea y luego decide qué data usa cada pieza.
   • Reglas: #tareas ≥ un orden de magnitud mayor que #procesos; tareas de tamaño parecido; #tareas crece con $n$.
2. Comunicar — definir canales (es overhead: no existe en la versión secuencial). Local (pocos vecinos) o global. Buscar comunicación balanceada y concurrente.
3. Aglomerar — agrupar tareas para bajar overhead (las que se comunican mucho, las que no pueden ser concurrentes, pares envío/recibo) y garantizar escalabilidad.
4. Mapear — asignar tareas a procesos: maximizar utilización y minimizar comunicación. Balanceo estático (distribución fija) o dinámico (número variable de tareas por proceso).

Foster paso a paso: P → C → A → M

Compara aglomerar por franjas de filas vs bloques 2D: mismo cómputo, distinta comunicación.

malla N = 8procesos p = 4

Franjas de filasBloques 2D (2×2)

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

etapa 0/4

Inicio

Problema: stencil de 5 puntos sobre una malla N×N (cada celda se actualiza con sus 4 vecinos).

tareas—

canales—

carga por proceso—

frontera (filas / bloques)24 / 16

En el examen…

Escribe los 4 pasos con nombre y di explícitamente cuántas tareas y cuántos canales quedan después de cada uno. Es lo que puntúa (ver el ejemplo del modelo climático en repaso U3.5).

Error común

Confundir aglomeración con mapeo. Aglomerar = decidir el tamaño de las tareas (agrupar); mapear = decidir en qué procesador corre cada tarea.

Ejemplo resuelto: suma de $n=10^{12}$ números

Datos: una suma = $10^{-9}$ s; envío/recibo $10^{-8}$ s/Byte; cada proceso puede sumar a lo más $10^9$ números.

Propuesta 1: lineal

• P: suma de a pares → $10^{12}-1$ tareas primitivas.
• C: $10^{12}-2$ canales (topología lineal).
• A: $10^5$ números por tarea → $10^7$ canales.
• M: cada proceso suma $10^9$ números → $10^3$ canales.

$$T_s=10^{12}\cdot10^{-9}=1000\text{ s}\qquad T_p=10^9\cdot10^{-9}+10^3\cdot10^{-9}+10^3\cdot8\cdot10^{-8}\approx1.00008\text{ s}$$

Propuesta 2: árbol

Misma P/C/A/M en cantidad final, pero topología de árbol binario: el camino crítico tiene $\log_2 10^3\approx10$ saltos en vez de $10^3$.

$$T_p=10^9\cdot10^{-9}+10\cdot10^{-9}+10\cdot8\cdot10^{-8}\approx1.0000008\text{ s}$$

Conclusión: el mapeo final no cambia, pero la topología sí afecta el tiempo; aquí la diferencia es mínima porque el problema es compute bound (domina el término de cómputo $10^9\cdot10^{-9}=1$ s).

Ejercicio (PD01 2026-II, Ej. 1): suavizado

Aplique Foster al suavizado de un array de $n$ píxeles con $t$ iteraciones: $U_i^t=\dfrac{U_{i-1}^{t-1}+U_i^{t-1}+U_{i+1}^{t-1}}{3}$. Cada proceso puede manejar a lo más 4 MB; cada píxel es un float. (1.1) Pasos de Foster. (1.2) Fronteras del dominio y de subdominios. (1.3) $T_s$, $T_p$ con $10^{-9}$ s/op y $10^{-8}$ s/Byte.

Antes de ver la solución, mira el algoritmo funcionando: cada iteración intercambia los bordes entre vecinos (halo) y luego calcula localmente.

Suavizado 1D con intercambio de halo (PD01)

$U_i^{t}=\tfrac13\left(U_{i-1}^{t-1}+U_i^{t-1}+U_{i+1}^{t-1}\right)$ · cada iteración: ① intercambio de celdas fantasma entre vecinos → ② cómputo local.

pixels n = 24procesos p = 4iteraciones t = 6

EscalónPicoRuido

Borde: pixel fantasma (réplica)Borde: fórmula reducida (÷2)

⏮︎◀︎▶︎ Play▶︎⏭︎

0.5×1×2×4×

fase 0/12

iteración0/6

mensajes / iteración6

ops / proceso / iter.≈ 18

¿igual al secuencial?sí ✓

Con los datos del PD01 ($t_c=10^{-9}$, $t_w=10^{-8}$ s/B) y, por ejemplo, $n=10^7,\ t=10^3$: $T_s=3nt\,t_c$ = 30 s, $T_p=t\left[3\tfrac{n}{p}t_c+8t_w\right]$ = 7.5 s ⇒ S = 4, E = 1.
El halo es O(1) por proceso (2 floats) mientras el cómputo es O(n/p): la razón comunicación/cómputo baja al crecer n/p.

Ver solución (1.1 Foster)

• Partición: descomposición de dominio; tarea primitiva = un valor $U_i^t$ ⇒ malla $n\times t$ (cada fila depende de la anterior).
• Comunicación: cada $(i,t)$ necesita 3 valores de $t-1$: patrón local tipo stencil 1D, sin comunicación global.
• Aglomeración: bloques contiguos de $s$ píxeles por proceso; solo se comunican los bordes (halo). Límite de memoria: $s_{max}=\dfrac{4\,\text{MB}}{4\,\text{B}}=2^{20}$ píxeles.
• Mapeo: $p=\lceil n/s\rceil$ procesos en topología lineal: $P_k$ solo habla con $P_{k-1}$ y $P_{k+1}$.

Ver solución (1.2 fronteras)

• Frontera del dominio ($i=1$, $i=n$): celda fantasma replicada ($U_0=U_1$, $U_{n+1}=U_n$) o promedio de solo 2 valores.
• Frontera de subdominios: intercambio de halo en cada iteración: enviar el píxel de borde al vecino y recibir el suyo en una celda auxiliar. Los procesos extremos solo intercambian con un lado.

Ver solución (1.3 T_s, T_p y métricas)

3 operaciones por píxel (2 sumas + 1 división):

$$T_s=3\,n\,t\,t_c\qquad T_p=t\left[3\frac np t_c+8\,t_w\right]$$

(cada proceso intercambia 1 float = 4 B con 2 vecinos por iteración). Métricas derivadas:

$$S=\frac{3n\,t_c}{3\frac np t_c+8t_w}\qquad E=\frac{3n\,t_c}{3n\,t_c+8p\,t_w}\qquad T_o=pT_p-T_s=8\,p\,t\,t_w$$

Isoeficiencia: $3ntt_c=K\cdot8ptt_w\Rightarrow n=\dfrac{8Kt_w}{3t_c}\,p=O(p)$ — lineal, muy escalable. Ejemplo $n=2^{22}$, $t=100$, $p=4$: $T_s=1.258$ s, $T_p=0.3146$ s, $S\approx3.9999$, $E\approx0.99997$.

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. ¿En qué paso de Foster decides que cada proceso reciba un bloque de $n/p$ píxeles contiguos?

a) Particiónb) Comunicaciónc) Aglomeraciónd) Mapeo

2. ¿Cuántas tareas primitivas conviene tener respecto a los procesos?

a) Igual númerob) Al menos un orden de magnitud másc) La mitadd) Exactamente $\log p$

3. En la suma de $10^{12}$ números, ¿por qué el árbol casi no mejora $T_p$?

a) Porque tiene más canalesb) Porque el problema es compute boundc) Porque el árbol es EREWd) Porque β es grande

4. En el modelo task/channel…

a) envío y recibo son síncronosb) envío asíncrono, recibo síncronoc) envío síncrono, recibo asíncronod) ambos asíncronos

Fuente ·estudio/01_Flynn_Foster.md §2–5 · PD01-Ejercicio1-Resolucion.md · CS4052-PD01-S02.pdf · U1.2-Fundamentos-Foster_Flynn-apuntes.pdf