Ley de Amdahl: aceleración y eficiencia

La ley de Amdahl, formulada por el arquitecto de computadoras Gene Amdahl en 1967, describe la aceleración teórica que se puede lograr al paralelizar un cálculo en múltiples procesadores. Es uno de los principios más importantes y citados en computación paralela porque establece un límite superior estricto a las mejoras de rendimiento que pueden aportar más procesadores, sin importar cuántos añadas. La ley parte de una observación sencilla: cualquier programa real consta de dos partes. Una es inherentemente serial y debe ejecutarse secuencialmente porque cada paso depende del resultado del anterior. La otra es paralelizable y puede dividirse en tareas independientes para ejecutarse al mismo tiempo en varios procesadores. La ley de Amdahl formaliza la relación entre estas dos partes. La fórmula es: S(n) = 1 / (p + (1 − p) / n), donde S es la aceleración, p es la fracción del programa que debe ejecutarse en serie (entre 0 y 1), n es el número de procesadores y (1 − p) es la fracción paralelizable. A medida que n tiende a infinito, el término (1 − p) / n se aproxima a cero y la aceleración se acerca a 1/p, la aceleración teórica máxima. Ese máximo está determinado por completo por la fracción serial y no puede superarse por muchos procesadores que se añadan. Las implicaciones son importantes. Si el 10% de un programa debe ejecutarse en serie (p = 0.1), la aceleración máxima es 1/0.1 = 10×, sin importar cuántos procesadores uses. Si el 20% es serial, el máximo es 5×. Si el 50% es serial, el máximo es solo 2×. Añadir más procesadores a partir de cierto punto produce rendimientos decrecientes porque la parte serial se convierte en el cuello de botella; a veces esto se llama el “techo de Amdahl”. Veamos un ejemplo concreto: un programa tarda 3,600 segundos en un solo núcleo, con un 80% del trabajo paralelizable (p = 0.2). Con 8 procesadores, la aceleración es S(8) = 1 / (0.2 + 0.8/8) = 1 / (0.2 + 0.1) = 1 / 0.3 = 3.33×. El tiempo paralelo es 3600 / 3.33 = 1080 segundos. Con 16 procesadores, S(16) = 1 / (0.2 + 0.8/16) = 1 / (0.2 + 0.05) = 4×, y el tiempo baja a 900 segundos. Duplicar de 8 a 16 procesadores solo mejora el rendimiento un 20% porque el 20% serial domina. La eficiencia paralela es la aceleración dividida por el número de procesadores, expresada como porcentaje: E = S(n)/n × 100%. Mide qué tan bien se aprovecha cada procesador adicional. Una eficiencia perfecta (100%) significaría que cada procesador se utiliza por completo, un ideal teórico. En la práctica, la eficiencia cae al añadir más procesadores porque la fracción serial desperdicia tiempo de CPU. Cuando la eficiencia baja del 50%, añadir más procesadores cuesta más en hardware de lo que ahorra en tiempo. La ley de Amdahl asume que la fracción serial p permanece constante independientemente del tamaño del problema. La ley de Gustafson (1988) ofrece una perspectiva complementaria: para problemas más grandes, una mayor fracción del trabajo se vuelve paralelizable y la eficiencia se mantiene más alta al aumentar el número de procesadores. Juntas, ambas leyes ofrecen una visión completa del escalado paralelo: la ley de Amdahl es pesimista pero describe con precisión el escenario de tamaño fijo, mientras que la ley de Gustafson es optimista y se aplica cuando el tamaño del problema crece con el número de procesadores. Entre las aplicaciones prácticas de la ley de Amdahl están el diseño de arquitecturas CPU y GPU, la provisión de recursos en la nube, el análisis de algoritmos para computación de alto rendimiento y la estimación del retorno de invertir en más procesadores para un sistema existente. Identificar y reducir la fracción serial de un cálculo —mediante mejores algoritmos, menor sobrecarga de sincronización o rediseño de estructuras de datos— es la forma más eficaz de elevar el techo de Amdahl.