Simulab
Programación · Paralela

Ley de Amdahl

Cuánto se acelera un programa con p procesadores, y por qué la parte secuencial pone un techo.

Preguntar a la IA

Speedup S(p)

ejes en escala logarítmica
14166425610241416642561024pSlineal: S = p50 %75 %90 %95 %99 %1/α = 10
━ Amdahl (tamaño fijo)━ Gustafson (tamaño escalado)┅ linealcurvas tenues: PF = 50, 75, 90, 95 y 99 %

Eficiencia E(p) = S / p

141664256102400.20.40.60.81p

Reparto del tiempo

T(n) = 1
1 proc.T(n)16 proc.T(n,p) = 0.156secuencial αparalela PF/pinactivo (sobrecarga)

Programa y máquina

El modelo es T(n, p) = α + PF/p, con T(n) = α + PF = 1.

Speedup S6.4
Eficiencia E40 %
Tiempo T(n,p)0.156
Coste C = p·T2.5
Sobrecarga T₀1.5
LÍMITE 1/α10
Gustafson S_G14.5
S / límite64 %

Con 10 % de código secuencial nunca pasarás de S = 10, por muchos procesadores que uses. Con p = 16 ya tienes el 64 % de ese límite, y más de la mitad del tiempo de los procesadores se pierde.

Gustafson responde a otra pregunta: si el problema crece con la máquina y el tiempo se mantiene, con p = 16 se hace 14.5 veces más trabajo.

Rendimiento efectivo

2 × 6 cores · 1,7 GHz · 16 FLOPs/ciclo (doble precisión)

TPP_dp326.4 GFLOPS
Re_dp con PF = 90 %155.4 GFLOPS

Re = S(PF, p = 12) × GHz × FLOPs/ciclo: el rendimiento de un core multiplicado por el speedup de Amdahl. Se aprovecha el 47.6 % del pico teórico.

Qué es y cómo se usa

La ley de Amdahl dice cuánto se puede acelerar un programa al repartirlo entre p procesadores. Si una fracción α del tiempo es secuencial y el resto (PF = 1 − α) se reparte perfectamente, el speedup es S = 1 / ((1 − PF) + PF/p), y nunca pasa de 1/α por muchos procesadores que se añadan.

El simulador dibuja el speedup y la eficiencia E = S/p en escala logarítmica, y un diagrama de Gantt con la parte secuencial, la paralela y el tiempo en que los procesadores están parados, que es la sobrecarga. Se puede añadir un coste de comunicación que crece con log₂ p para ver cómo el tiempo acaba subiendo.

La ley de Gustafson-Barsis responde a otra pregunta: si el problema crece con la máquina, el speedup escalado es S = p − (p − 1)·α. También se calcula el rendimiento efectivo de varios procesadores reales a partir de su pico teórico.

Ejemplo resuelto

Un programa es paralelizable al 90 %. ¿Qué speedup se consigue con 16 procesadores? ¿Y cuál es el máximo?

  1. Fracción secuencial: α = 1 − 0,9 = 0,1.
  2. S = 1 / (0,1 + 0,9/16) = 1 / 0,15625 = 6,4.
  3. Eficiencia: E = 6,4 / 16 = 0,4, es decir, el 40 %.
  4. Límite cuando p → ∞: S ≤ 1/α = 10.

S = 6,4 con 16 procesadores, y nunca más de 10

Preguntas frecuentes

¿Por qué la eficiencia baja al añadir procesadores?

Porque la parte secuencial no se reparte: mientras un procesador la ejecuta, los demás esperan. Cuantos más procesadores hay, más tiempo parado se acumula y menor es la fracción de trabajo útil.

¿Se contradicen Amdahl y Gustafson?

No. Amdahl mantiene fijo el tamaño del problema (strong scaling) y Gustafson lo hace crecer con el número de procesadores para mantener el tiempo (weak scaling). Son dos preguntas distintas.

¿Puede el speedup ser mayor que p?

En el modelo, no: S ≤ p. En la práctica a veces sale superlineal, normalmente porque el algoritmo secuencial no era el mejor o porque al repartir los datos caben en la caché.

¿Qué es la sobrecarga?

El tiempo que los procesadores consumen entre todos por encima del secuencial: T₀ = p·T(n, p) − T(n). En el diagrama es el área en que los procesadores están parados o comunicándose.

Herramientas relacionadas