# Ley de Amdahl y Gustafson > Speedup, eficiencia, coste y sobrecarga de un programa paralelo según su fracción paralelizable y el número de procesadores. - Página interactiva: https://simulab.es/programacion/ley-de-amdahl - Asignatura: [Programación](https://simulab.es/programacion.md) - Niveles: [Universidad](https://simulab.es/universidad.md) - Gratis, en español y en el navegador, sin registro. ## 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. **Solución:** 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 - [Notación asintótica y recurrencias](https://simulab.es/programacion/notacion-asintotica.md): O, Ω y θ de dos costes con el límite del cociente, c y n₀ de la definición, y recurrencias de sustracción y división con su árbol de llamadas. - [Tablas hash](https://simulab.es/programacion/tablas-hash.md): Tabla cerrada con sondeo lineal o cuadrático y abierta con listas, en Java: colisiones, borrados, factor de carga y redimensionado. - [ArrayList y lista enlazada](https://simulab.es/programacion/listas.md): Las dos listas en Java paso a paso: capacidad y crecimiento, desplazamientos, recorrido de nodos y coste de cada operación. - [Árbol binario enhebrado](https://simulab.es/programacion/arbol-enhebrado.md): Hilos al sucesor y al predecesor en inorden, y recorrido del árbol en Java sin recursión ni pila. - [Memoria y punteros en C](https://simulab.es/programacion/punteros.md): Programas en C línea a línea con la pila, el montón y a dónde apunta cada puntero: paso por valor y por referencia, malloc y free. - [Recursión en C](https://simulab.es/programacion/recursion.md): Potencia, factorial, MCD, Fibonacci y suma de un vector: pila y árbol de llamadas, descenso y ascenso, y su versión iterativa. - [Divide y vencerás](https://simulab.es/programacion/divide-y-venceras.md): Máximo, suma, vector creciente y búsqueda binaria en C: el trozo de cada llamada, el árbol de subproblemas y su coste. - [Backtracking](https://simulab.es/programacion/backtracking.md): Mochila 0/1 y descomposición en sumandos en C: árbol de búsqueda con podas, todas las soluciones, una o la óptima. Más herramientas: [todas las de Simulab](https://simulab.es/llms.txt).