Ley de Amdahl y de Gustafson: speedup, eficiencia y escalabilidad

Un programa tarda una hora. Si lo repartes entre 100 procesadores, ¿tardará 36 segundos? Casi nunca. Siempre queda una parte que no se puede repartir (leer los datos, combinar resultados, sincronizar), y esa parte acaba poniendo un techo a la aceleración. La ley de Amdahl calcula ese techo, y es la primera cuenta que hay que hacer antes de comprar más núcleos o de paralelizar un programa.

​

Lo que vas a aprender

• Cómo se modela el tiempo de un programa paralelo: cálculo y comunicaciones.
• Qué miden el speedup, la eficiencia, el coste y la sobrecarga.
• La ley de Amdahl y por qué la parte secuencial limita el speedup a $1/\alpha$.
• La ley de Gustafson-Barsis y la diferencia entre escalado fuerte y débil.
• Calcular el rendimiento teórico y el efectivo de un procesador real.
• Qué es la isoeficiencia y cuándo un algoritmo es escalable.

​

Cómo se usa el simulador

• La gráfica de speedup usa escala logarítmica en los dos ejes. La línea discontinua es el speedup lineal ($S = p$); la curva azul, Amdahl; la naranja, Gustafson; las curvas tenues, Amdahl con PF del 50 al 99 %.
• La gráfica de eficiencia muestra qué fracción del trabajo de los procesadores es útil.
• El reparto del tiempo es un diagrama de Gantt: la parte secuencial, la paralela, las comunicaciones y, rayado, el tiempo en que los procesadores están parados.
• Con comunicaciones, el panel indica el número de procesadores óptimo: a partir de él, el tiempo vuelve a subir.

​

Fundamentos teóricos

​

Tiempo de ejecución paralelo

El tiempo paralelo $T(n, p)$ es el que pasa desde que empieza el primer procesador hasta que termina el último. Depende de la talla $n$ y del número de procesadores $p$. En una primera aproximación es la suma del tiempo de cálculo y el de comunicaciones: $$T(n,p) \cong T_{ar}(n,p) + T_{co}(n,p)$$ El cálculo se cuenta en FLOPs (operaciones en coma flotante), cada una de duración $t_c$. Un mensaje de $L$ palabras entre dos procesos cuesta $$T_{co} = t_s + L\,t_w$$ donde $t_s$ es la latencia (lo que cuesta empezar a enviar) y $t_w$ el tiempo por palabra, la inversa del ancho de banda. Como $t_s \gg t_w$, es mejor enviar un mensaje grande que muchos pequeños.

​

Speedup, eficiencia, coste y sobrecarga

Como un algoritmo paralelo se puede simular en un solo procesador ejecutando sus pasos uno detrás de otro, $T(n) \le p\,T(n,p)$, y por tanto: $$S(n,p) \le p \qquad 0 \le E(n,p) \le 1$$

​

Ley de Amdahl

Se divide el tiempo secuencial en una parte no paralelizable $\alpha$ y una paralelizable $\beta$. Con $p$ procesadores solo se reparte la segunda: $$T(n) = \alpha + \beta \qquad T(n,p) = \alpha + \frac{\beta}{p}$$ Normalizando $\alpha + \beta = 1$ y llamando $PF = \beta$ a la fracción paralela: $$S(n,p) = \frac{1}{(1 - PF) + \dfrac{PF}{p}} = \frac{p}{(p-1)\,\alpha + 1}$$ Cuando $p \to \infty$, el término $PF/p$ desaparece y queda el techo de Amdahl: $$\lim_{p \to \infty} S(n,p) = \frac{1}{\alpha}$$ Consecuencias que se ven en el simulador:

• Con el tamaño del problema fijo (escalado fuerte o strong scaling), la eficiencia baja siempre al aumentar $p$.
• A partir de cierto número de procesadores no compensa añadir más: el speedup apenas sube y la eficiencia se desploma.
• Si además hay comunicaciones que crecen con $p$, el tiempo vuelve a subir: hay un número óptimo de procesadores.

​

Ley de Gustafson-Barsis

Amdahl supone que el problema es siempre el mismo. Pero con una máquina más grande normalmente se resuelven problemas más grandes en el mismo tiempo. Si la parte secuencial $f_s = 1 - PF$ se mide en el programa paralelo y el resto crece con $p$, el speedup escalado es: $$S_G(W, p) = p - (p - 1)\,f_s$$ que crece casi linealmente con $p$. Las dos leyes no se contradicen: responden a preguntas distintas.

​

Rendimiento teórico y efectivo

El pico teórico (theoretical peak performance) en doble precisión de un procesador es: $$TPP_{dp} = \text{sockets} \times \text{núcleos por socket} \times \text{GHz} \times \frac{\text{FLOPs}}{\text{ciclo}}$$ Los FLOPs por ciclo dependen de las instrucciones vectoriales: 4 con SSE, 8 con AVX, 16 con AVX2 y FMA, 32 con AVX-512 y FMA. Es una cifra muy optimista: supone que todo el programa es paralelo. El rendimiento efectivo multiplica lo que da un solo núcleo por el speedup de Amdahl: $$Re_{dp} = S_{\text{Amdahl}}(PF, p) \times \text{GHz} \times \frac{\text{FLOPs}}{\text{ciclo}}$$ Una máquina con muchos núcleos lentos tiene un pico altísimo, pero se hunde en cuanto la fracción secuencial no es mínima.

​

Escalabilidad e isoeficiencia

Un algoritmo es escalable si puede mantener la eficiencia al aumentar $p$ haciendo crecer el problema. La función de isoeficiencia dice cuánto tiene que crecer el tamaño computacional $W$ con $p$. Partiendo de la sobrecarga: $$E = \frac{T(n)}{T(n) + T_0(n,p)} \quad\Longrightarrow\quad W = K\,T_0(W, p), \qquad K = \frac{E}{1-E}$$ Si $W$ se cancela al despejar, ningún tamaño compensa el crecimiento de $p$ y el algoritmo no escala.

​

Ejemplos resueltos

​

Experimenta con el simulador

​

Errores frecuentes

• Pensar que con $p$ procesadores se va $p$ veces más rápido. Solo si todo es paralelizable y no hay comunicaciones.
• Usar la fracción paralela donde va la secuencial. En Amdahl, el término que no se divide entre $p$ es $\alpha = 1 - PF$.
• Comparar con un secuencial malo. El speedup que mide la eficacia real se calcula con el mejor algoritmo secuencial conocido, no con el paralelo ejecutado en un procesador.
• Concluir a partir de una sola medida. “Con 12 procesadores el speedup fue 10,8” no dice qué pasará con 1000, ni con otra talla: hace falta un modelo.
• Leer Gustafson como una refutación de Amdahl. Cambian el tamaño del problema; con el tamaño fijo, Amdahl sigue valiendo.

​

Limitaciones del modelo

La ley de Amdahl supone que la parte paralela se reparte de forma perfecta y que no hay más costes. En la realidad:

• Hay desequilibrio de carga: unos procesadores acaban antes y esperan a los demás.
• Las comunicaciones y la sincronización crecen con $p$ y pueden hacer que el tiempo aumente.
• La memoria es compartida: varios núcleos compiten por el mismo ancho de banda.
• Al repartir los datos pueden caber en la caché y aparecer speedups superlineales.

El simulador incluye un coste de comunicaciones de reducción en árbol, $c\log_2 p$, para ver el efecto más importante. Aun así, el modelo sirve para lo que se pensó: dar una cota y decidir en el diseño.

​

Un poco de historia

Gene Amdahl, arquitecto de los IBM System/360, presentó su argumento en 1967 en una conferencia en la que defendía los procesadores únicos rápidos frente a los multiprocesadores. Durante dos décadas se usó como prueba de que el paralelismo masivo no tenía futuro. En 1988, John Gustafson y Edwin Barsis, en los laboratorios Sandia, obtuvieron speedups de más de 1000 con 1024 procesadores y explicaron por qué: con más procesadores se resuelven problemas más grandes, y la parte secuencial pesa cada vez menos. Hoy los superordenadores tienen millones de núcleos, y las dos leyes se enseñan juntas.

​

Preguntas frecuentes

​

Temas relacionados