Tiempo secuencial normalizado a 1: f s f_s f s f p f_p f p f s + f p = 1 f_s+f_p=1 f s + f p = 1
Problema de tamaño fijo : ¿qué tan rápido lo resuelvo con p p p
T p = f s + f p p S = 1 f s + f p / p E = 1 p ( f s + 1 − f s p ) lim p → ∞ S = 1 f s T_p=f_s+\frac{f_p}{p}\qquad S=\frac{1}{f_s+f_p/p}\qquad E=\frac{1}{p\left(f_s+\frac{1-f_s}{p}\right)}\qquad \lim_{p\to\infty}S=\frac{1}{f_s} T p = f s + p f p S = f s + f p / p 1 E = p ( f s + p 1 − f s ) 1 p → ∞ lim S = f s 1 Si el 10 % es secuencial, nunca pasarás de 10× aunque uses un millón de núcleos.
El problema crece con p p p (trabajo por procesador ~constante):
T p = f s + f p T s = f s + p f p S = f s + p f p E = f s + p f p p T_p=f_s+f_p\qquad T_s=f_s+p\,f_p\qquad S=f_s+p\,f_p\qquad E=\frac{f_s+p\,f_p}{p} T p = f s + f p T s = f s + p f p S = f s + p f p E = p f s + p f p El speedup escala con p p p : no hay techo 1 / f s 1/f_s 1/ f s
Con n ∝ p n\propto p n ∝ p T s = f s + f p p α T_s=f_s+f_p p^\alpha T s = f s + f p p α T p = f s + f p p α − 1 T_p=f_s+f_p p^{\alpha-1} T p = f s + f p p α − 1
S = f s + f p p α f s + f p p α − 1 E = f s p − α + ( 1 − f s ) f s p 1 − α + ( 1 − f s ) S=\frac{f_s+f_p p^\alpha}{f_s+f_p p^{\alpha-1}}\qquad E=\frac{f_s p^{-\alpha}+(1-f_s)}{f_s p^{1-\alpha}+(1-f_s)} S = f s + f p p α − 1 f s + f p p α E = f s p 1 − α + ( 1 − f s ) f s p − α + ( 1 − f s ) α = 0 \alpha=0 α = 0 E = 1 f s p + ( 1 − f s ) E=\dfrac{1}{f_s p+(1-f_s)} E = f s p + ( 1 − f s ) 1 α = 1 \alpha=1 α = 1 E = f s p − 1 + ( 1 − f s ) E=f_s p^{-1}+(1-f_s) E = f s p − 1 + ( 1 − f s )
Carrera: 1 procesador vs p procesadores Rojo = parte secuencial (solo P0 trabaja, el resto espera); azul = parte paralelizable repartida.
Secuencial (1 procesador) Paralelo (4 procesadores) Tₛ 1
Tₚ 0.4
S 2.5
E 0.625
tope 1/f_s 5
T p = f s + f p p , S = 1 f s + f p / p T_p=f_s+\tfrac{f_p}{p},\ S=\tfrac{1}{f_s+f_p/p} T p = f s + p f p , S = f s + f p / p 1 . Con más procesadores la barra azul se encoge, pero la roja
no : S nunca pasa de 1/f_s.
Amdahl vs Gustafson Mueve la fracción secuencial y observa el techo de Amdahl frente al crecimiento lineal de Gustafson.
Amdahl S(p) 8.77
Amdahl E(p) 0.137
Límite 1/f_s 10
Gustafson S(p) 57.7
Gustafson E(p) 0.902
Speedup S(p) (ejes log)
1 10 100 1000 1 10 100 1000 p S 1/f_s = 10 p=64
Eficiencia E(p) = S/p 0 0.2 0.4 0.6 0.8 1 1 10 100 1000 p E p=64
Amdahl: S = 1 f s + f p p → p → ∞ 1 f s Gustafson: S = f s + p f p \text{Amdahl: } S=\frac{1}{f_s+\frac{f_p}{p}}\;\xrightarrow{p\to\infty}\;\frac{1}{f_s} \qquad \text{Gustafson: } S=f_s+p\,f_p Amdahl: S = f s + p f p 1 p → ∞ f s 1 Gustafson: S = f s + p f p
Identifica la palabra clave: «tamaño fijo», «mismo problema más rápido» ⇒ Amdahl . «Problema más grande», «más partículas», «n crece con p» ⇒ Gustafson . La escalabilidad (E constante al crecer n n n p p p no se puede describir con Amdahl.
Un algoritmo se paraleliza en 1000 procesos: (a) totalmente paralelizable, (b) 50 % paralelizable, (c) no paralelizable. Calcule S S S E E E α = 1 \alpha=1 α = 1
Ver solución
Caso Strong S S S Strong E E E Weak S S S Weak E E E (a) f p = 1 f_p=1 f p = 1 f p f p / p = p = 1000 \dfrac{f_p}{f_p/p}=p=1000 f p / p f p = p = 1000 1 f p p = p f_p p=p f p p = p 1 (b) f p = 0.5 f_p=0.5 f p = 0.5 1 0.5 + 0.5 / p = 2 p p + 1 ≈ 2 \dfrac{1}{0.5+0.5/p}=\dfrac{2p}{p+1}\approx2 0.5 + 0.5/ p 1 = p + 1 2 p ≈ 2 ≈ 0.002 \approx0.002 ≈ 0.002 f s + f p p = p + 1 2 ≈ 500 f_s+f_p p=\dfrac{p+1}{2}\approx500 f s + f p p = 2 p + 1 ≈ 500 ≈ 0.5 \approx0.5 ≈ 0.5 (c) f p = 0 f_p=0 f p = 0 1 1 / p 1/p 1/ p 1 1 / p 1/p 1/ p
(a) eficiencia constante: escalable en ambos casos. (b) con weak scaling sube mucho el speedup y la eficiencia: más escalable. (c) la eficiencia cae con p p p
Autoevaluación 0/4 correctas · 0 respondidas Reiniciar 1. f s = 0.05 f_s=0.05 f s = 0.05 . Speedup máximo según Amdahl: a) 5 b) 20 c) 95 d) ilimitado
2. Con Gustafson, f s = 0.1 f_s=0.1 f s = 0.1 , p = 100 p=100 p = 100 : S = S= S = a) 9.17 b) 90.1 c) 10 d) 100
3. Con Amdahl, f s = 0.1 f_s=0.1 f s = 0.1 , p = 100 p=100 p = 100 : S ≈ S\approx S ≈ a) 9.17 b) 90.1 c) 10 d) 100
4. ¿Por qué la eficiencia en strong scaling cae con más nodos y en weak se mantiene?
a) Porque en weak el problema crece y el trabajo por nodo se mantiene b) Porque weak usa menos comunicación por mensaje c) Por la ley de Brent d) No es cierto
Fuente ·estudio/03_Amdahl_Gustafson.md §2–3 · U2.1-Diseño_en_paralelo-performance.pdf · U3.5 Ejercicios de repaso.pdf (Ej. 5)