> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.
# Ley de Amdahl y de Gustafson: speedup, eficiencia y escalabilidad
> Speedup y eficiencia de un programa paralelo explicados: tiempo paralelo, coste y sobrecarga, ley de Amdahl, ley de Gustafson-Barsis, rendimiento efectivo e isoeficiencia, con ejemplos resueltos.
Cambia la fracción paralelizable y el número de procesadores y mira el speedup, la eficiencia y el tiempo perdido.
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
| Control | Qué hace | Rango |
| - | - | - |
| **PF · fracción paralelizable** | Parte del tiempo secuencial que se puede repartir. El resto, $\alpha = 1 - PF$, es secuencial | 0 – 100 % |
| **p · procesadores** | Número de procesadores | 1 – 1024 |
| **Comunicaciones** | Coste de cada paso de una reducción en árbol, en fracción del tiempo secuencial. Se suma $\log_2 p$ veces | 0 – 2 % |
| **Procesador** | Procesadores reales para el rendimiento efectivo | — |
* 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.
La configuración se guarda en el enlace de la página: útil para comparar casos en clase.
## 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
| Magnitud | Fórmula | Qué mide |
| - | - | - |
| **Speedup** | $S(n,p) = \dfrac{T(n)}{T(n,p)}$ | Cuántas veces más rápido va el paralelo |
| **Eficiencia** | $E(n,p) = \dfrac{S(n,p)}{p}$ | Fracción del trabajo de los procesadores que es útil |
| **Coste** | $C(n,p) = p\,T(n,p)$ | Tiempo de procesador gastado entre todos |
| **Sobrecarga** | $T_0(n,p) = C(n,p) - T(n)$ | Tiempo gastado de más respecto al secuencial |
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
$$
| Speedup | Nombre | Causa |
| - | - | - |
| $S = p$ | Lineal | Todos trabajan a la vez, sin comunicaciones ni esperas |
| $S \lt p$ | Sublineal | Dependencias, partes secuenciales, comunicaciones: el caso normal |
| $S \gt p$ | Superlineal | El secuencial no era el mejor, o efectos de la caché al repartir los datos |
### 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}
$$
| Paralelizable | Speedup máximo |
| - | - |
| 50 % | 2 |
| 75 % | 4 |
| 90 % | 10 |
| 95 % | 20 |
| 99 % | 100 |
Con un 10 % de código secuencial, ni un millón de procesadores dan más de 10 veces de aceleración. Para acelerar de verdad hay que **reducir la parte secuencial**, no añadir procesadores.
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$.
| | Amdahl | Gustafson |
| - | - | - |
| Pregunta | ¿Cuánto se acelera un problema de **tamaño fijo**? | ¿Cuánto **más grande** puede ser el problema en el mismo tiempo? |
| Escalado | Fuerte (*strong scaling*) | Débil (*weak scaling*) |
| Speedup con $p \to \infty$ | Acotado por $1/\alpha$ | Crece sin límite |
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}
$$
| Isoeficiencia | Escalabilidad |
| - | - |
| $W \in \theta(p)$ | Óptima |
| $W \in \theta(p \log p)$ | Buena |
| $W \in \theta(p^2)$ | Peor |
| $W \in \theta(p^3)$ | Mala: el problema tiene que crecer muy deprisa |
Si $W$ se cancela al despejar, ningún tamaño compensa el crecimiento de $p$ y el algoritmo **no escala**.
## Ejemplos resueltos
Un programa es paralelizable al 90 %. Calcula el speedup y la eficiencia con 16 procesadores, y el speedup máximo.
**Speedup:** $S = \dfrac{1}{0{,}1 + 0{,}9/16} = \dfrac{1}{0{,}15625} = 6{,}4$.
**Eficiencia:** $E = 6{,}4/16 = 0{,}4$. El 60 % del tiempo de los procesadores se pierde.
**Máximo:** $S \lt 1/0{,}1 = 10$. Con 16 procesadores ya se tiene el 64 % del máximo; con 1024, el speedup es 9,91.
Cuatro tareas independientes de coste 50 y una final de coste 20 que depende de las cuatro. En secuencial, $T(n) = 4 \cdot 50 + 20 = 220$.
| $p$ | $T(n,p)$ | $C = p\,T$ | $T_0$ | $S$ | $E$ |
| - | - | - | - | - | - |
| 2 | $100 + 20 = 120$ | 240 | 20 | 1,83 | 0,92 |
| 3 | $100 + 20 = 120$ | 360 | 140 | 1,83 | 0,61 |
| 4 | $50 + 20 = 70$ | 280 | 60 | 3,14 | 0,79 |
| 5 | $50 + 20 = 70$ | 350 | 130 | 3,14 | 0,63 |
Con 3 procesadores, una tarea de 50 necesita una segunda ronda y no se gana nada. A partir de 4 el tiempo ya no baja y la eficiencia cae: **no compensa usar más de 4 procesadores**.
Sumar $n$ números con $p = n/2$ procesadores: cada paso suma parejas y se hacen $\log_2 n$ pasos, cada uno con una suma y una comunicación.
* $T(n) \cong n\,t_c$ y $T(n,p) \cong 2\log_2 n\; t_c$.
* $S = \dfrac{n}{2\log_2 n}$ y $E = \dfrac{1}{\log_2 n}$.
* Coste: $C = n\,t_c\log_2 n$, que crece más que $T(n) = n\,t_c$. **No es de coste óptimo.**
Con menos procesadores, cada uno suma primero $n/p$ números y luego se reduce en árbol: $T(n,p) \cong (n/p + 2\log_2 p)\,t_c$. Si $p \ll n$, domina $n/p$ y la eficiencia se acerca a 1.
Xeon E5-2603 v4: 2 sockets de 6 núcleos a 1,7 GHz, con AVX2 + FMA (16 FLOPs/ciclo).
**Pico teórico:** $TPP_{dp} = 2 \times 6 \times 1{,}7 \times 16 = 326{,}4$ GFLOPS.
**Con PF = 0,99 y p = 12:** $S = \dfrac{1}{0{,}01 + 0{,}99/12} = 10{,}81$, y $Re_{dp} = 10{,}81 \times 1{,}7 \times 16 = 294{,}1$ GFLOPS.
**Con PF = 0,90:** $S = 5{,}71$ y $Re_{dp} = 155{,}4$ GFLOPS, menos de la mitad del pico.
Un programa paralelo pasa el 5 % de su tiempo en la parte secuencial, con 64 procesadores. ¿Qué speedup escalado consigue?
$S_G = 64 - 63 \cdot 0{,}05 = 60{,}85$
Con Amdahl, el mismo 5 % daría como mucho $S = 20$. La diferencia es la pregunta: Gustafson mide cuánto trabajo más se hace en el mismo tiempo.
## Experimenta con el simulador
Con PF = 90 %, sube $p$ hasta 1024. ¿A qué valor se acerca el speedup? Repite con 99 %: ¿cuántos procesadores hacen falta para llegar a la mitad del techo?
Mira el diagrama de Gantt con 4, 16 y 128 procesadores. ¿Qué parte del tiempo total es la secuencial en cada caso? ¿Y el área rayada?
Pon un coste de comunicación de 0,5 %. ¿Cuál es ahora el número óptimo de procesadores? ¿Qué le pasa al speedup si pasas de ese número?
Con PF = 95 %, compara las dos curvas con 32 y con 1024 procesadores. ¿Cuál se parece más al speedup lineal? ¿Por qué no se contradicen?
Elige el EPYC 7413 y baja PF del 99 % al 75 %. ¿Qué porcentaje del pico teórico se aprovecha en cada caso? Compáralo con el i3-2100.
## 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
Con un perfilador: se mide cuánto tiempo pasa el programa secuencial en cada parte y cuáles se pueden repartir. También se puede despejar de Amdahl a partir de dos medidas: si con $p$ procesadores se obtiene $S$, entonces $PF = \dfrac{1 - 1/S}{1 - 1/p}$.
Porque la eficiencia es $S/p$. Si al duplicar los procesadores el speedup sube menos del doble, cada procesador aprovecha menos su tiempo.
Que su coste $p\,T(n,p)$ es proporcional al tiempo del mejor secuencial. Entonces la sobrecarga no crece más deprisa que el trabajo útil y la eficiencia se mantiene acotada por debajo.
Depende de la fracción paralelizable. Con programas casi totalmente paralelos (gráficos, álgebra lineal), ganan muchos núcleos lentos, como en las GPU. Con una parte secuencial apreciable, Amdahl favorece pocos núcleos rápidos.
Sí, y con más fuerza: una GPU tiene miles de núcleos, así que la parte que se queda en la CPU y las copias de memoria entre ambas limitan enseguida el speedup.
## Temas relacionados
Las herramientas para analizar el coste que aquí se amplían a $p$ procesadores.
Algoritmos que se reparten de forma natural entre procesadores.
Medir el coste de un algoritmo de forma experimental.
This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.