T c o m m = f ( p ) ( α + x β ) T_{comm}=f(p)\,(\alpha+x\beta) T co mm = f ( p ) ( α + x β ) α \alpha α latencia (enviar un mensaje de tamaño 0), β \beta β x x x f ( p ) f(p) f ( p ) topología . Se comunica para: repartir datos desde el maestro, intercambiar entre procesos (p. ej. halos del suavizado) y reducir/recolectar al final.
Lineal (cada proceso tiene vecino anterior/posterior) Árbol binario Broadcast O ( p ( α + m β ) ) O(p(\alpha+m\beta)) O ( p ( α + m β )) p − 1 p-1 p − 1 ⌊ p / 2 ⌋ \lfloor p/2\rfloor ⌊ p /2 ⌋ O ( log p ( α + m β ) ) O(\log p\,(\alpha+m\beta)) O ( log p ( α + m β )) Scatter/Gather ( p − 1 ) ( α + β m / p ) = O ( α p + β m ) (p-1)(\alpha+\beta m/p)=O(\alpha p+\beta m) ( p − 1 ) ( α + β m / p ) = O ( α p + β m ) ∑ i = 0 log p − 1 ( α + β 2 i m p ) = α log p + β m ( 1 − 1 p ) \sum_{i=0}^{\log p-1}\left(\alpha+\beta2^i\frac mp\right)=\alpha\log p+\beta m\left(1-\frac1p\right) ∑ i = 0 l o g p − 1 ( α + β 2 i p m ) = α log p + β m ( 1 − p 1 )
Envío: O ( p ( α + n p β ) ) O(p(\alpha+\frac np\beta)) O ( p ( α + p n β )) O ( n / p ) O(n/p) O ( n / p ) O ( p ( α + β ) ) O(p(\alpha+\beta)) O ( p ( α + β )) O ( p ) O(p) O ( p )
T p ( n , p ) = O ( p α + ( n + p ) β + n / p ) T_p(n,p)=O\big(p\alpha+(n+p)\beta+n/p\big) T p ( n , p ) = O ( p α + ( n + p ) β + n / p )
Envío: O ( α log p + n p β ) O(\alpha\log p+\frac np\beta) O ( α log p + p n β ) O ( n / p ) O(n/p) O ( n / p ) O ( log p ( α + β + 1 ) ) O(\log p(\alpha+\beta+1)) O ( log p ( α + β + 1 ))
T p ( n , p ) = O ( n p + α log p + n p β ) T_p(n,p)=O\!\left(\frac np+\alpha\log p+\frac np\beta\right) T p ( n , p ) = O ( p n + α log p + p n β ) El span O ( log n ) O(\log n) O ( log n ) log p \log p log p
Si el enunciado dice «comunicación optimizada, f ( p ) = O ( log p ) f(p)=O(\log p) f ( p ) = O ( log p ) árbol . Siempre di el paradigma : PRAM = memoria compartida; si hay α y β, hay mensajes (distribuida).
Intensidad : cada píxel independiente ⇒ cada proceso trabaja su región sin comunicarse.Image warping (rotación): cada píxel de salida usa coordenadas rotadas + interpolación bilineal:
x ′ = ( x − c x ) cos θ + ( y − c y ) sin θ + c x y ′ = − ( x − c x ) sin θ + ( y − c y ) cos θ + c y x'=(x-c_x)\cos\theta+(y-c_y)\sin\theta+c_x\qquad y'=-(x-c_x)\sin\theta+(y-c_y)\cos\theta+c_y x ′ = ( x − c x ) cos θ + ( y − c y ) sin θ + c x y ′ = − ( x − c x ) sin θ + ( y − c y ) cos θ + c y
Imagen n × n n\times n n × n T s = O ( n 2 ) T_s=O(n^2) T s = O ( n 2 ) T p = O ( n 2 p + α log p + β n 2 p ) \;T_p=O\!\left(\frac{n^2}{p}+\alpha\log p+\beta\frac{n^2}{p}\right) T p = O ( p n 2 + α log p + β p n 2 ) memoria compartida (incl. GPU) es óptima .
Cada píxel itera z k + 1 = z k 2 + c z_{k+1}=z_k^2+c z k + 1 = z k 2 + c z 0 = 0 z_0=0 z 0 = 0 ∣ z ∣ > 2 |z|>2 ∣ z ∣ > 2 K m a x K_{max} K ma x
W = O ( n 2 K m a x ) T ∞ = O ( K m a x ) T p = O ( n 2 K m a x p + K m a x ) T c o m m = O ( log p ( α + β N 2 ) ) W=O(n^2K_{max})\qquad T_\infty=O(K_{max})\qquad T_p=O\!\left(\frac{n^2K_{max}}{p}+K_{max}\right)\qquad T_{comm}=O(\log p\,(\alpha+\beta N^2)) W = O ( n 2 K ma x ) T ∞ = O ( K ma x ) T p = O ( p n 2 K ma x + K ma x ) T co mm = O ( log p ( α + β N 2 )) Mandelbrot: balance de carga estático vs work pool Cada píxel itera z ← z² + c hasta |z| > 2 o K_max. Costo de una fila = suma de iteraciones de sus píxeles. Color = proceso dueño, brillo = iteraciones.
Estático: bloques de filas Estático: filas cíclicas Dinámico: work pool
p = 4 K_max = 300
Carga por proceso (iteraciones)P0 26200 P1 2.72e5 P2 2.90e5 P3 32900
T_s (Σ iteraciones) 6.21e5
T_p = máx. carga 2.90e5
S 2.14
E 0.535
desbalance máx/prom 1.87
Eficiencia vs p 0 0.2 0.4 0.6 0.8 1 2.5 5 7.5 10 12.5 15 p E
Con bloques, los procesos que reciben filas del interior del conjunto (K_max iteraciones por píxel) terminan mucho después: desbalance . El work pool lo corrige a cambio de overhead por tarea; con tareas muy chicas y overhead alto, el overhead domina.
«Cada proceso recibe la misma cantidad de píxeles ⇒ está balanceado». Falso : el costo por píxel varía de 1 a K m a x K_{max} K ma x estática desbalancea; el work pool (dinámico) balancea a cambio de T m s g T_{msg} T m s g T s c h e d T_{sched} T sc h e d K m a x = 10 5 K_{max}=10^5 K ma x = 1 0 5 p p p
Calcule W W W T ∞ T_\infty T ∞ n = 1000 n=1000 n = 1000 K m a x = 200 K_{max}=200 K ma x = 200 p = 100 p=100 p = 100
Ver solución W = n 2 K m a x = 10 6 ⋅ 200 = 2 × 10 8 W=n^2K_{max}=10^6\cdot200=2\times10^8 W = n 2 K ma x = 1 0 6 ⋅ 200 = 2 × 1 0 8 T ∞ = K m a x = 200 T_\infty=K_{max}=200 T ∞ = K ma x = 200 T p ≤ 2 × 10 8 100 + 200 = 2 000 200 T_p\le\frac{2\times10^8}{100}+200=2\,000\,200 T p ≤ 100 2 × 1 0 8 + 200 = 2 000 200 W / p W/p W / p p ≤ n 2 p\le n^2 p ≤ n 2 K m a x K_{max} K ma x T p = O ( n 2 / p ) T_p=O(n^2/p) T p = O ( n 2 / p ) O ( log p ( α + β N 2 ) ) O(\log p(\alpha+\beta N^2)) O ( log p ( α + β N 2 ))
Autoevaluación 0/4 correctas · 0 respondidas Reiniciar 1. Scatter en árbol binario cuesta…
a) O ( α p + β m ) O(\alpha p+\beta m) O ( α p + β m ) b) O ( α log p + β m ) O(\alpha\log p+\beta m) O ( α log p + β m ) c) O ( log p ( α + β ) ) O(\log p(\alpha+\beta)) O ( log p ( α + β )) d) O ( p β m ) O(p\beta m) O ( pβ m ) 2. ¿Qué término NO mejora el árbol en scatter/gather?
a) latencia b) β m \beta m β m (volumen) c) ambos d) ninguno 3. Para image warping se prefiere…
a) memoria distribuida b) memoria compartida/GPU c) topología lineal d) work pool
4. El work pool agrega overhead de…
a) T m s g T_{msg} T m s g y T s c h e d T_{sched} T sc h e d b) span c) memoria d) nada Fuente ·estudio/05_Particionamiento.md · U2.4-Diseño_en_paralelo-Particionamiento-Random.pdf · 08_Solvers (Arquetipo A)