Al duplicar o cuadruplicar el número de procesadores y núcleos, es fácil esperar que el programa termine el doble o el cuádruple de rápido. Sin embargo, al ejecutarlo, la mejora que se percibe suele ser mucho menor de lo esperado. La ley de Amdahl (Amdahl’s Law) recoge precisamente esta idea de que la parte que no puede repartirse para ejecutarse en paralelo limita la velocidad del conjunto.
En términos sencillos, la ley de Amdahl establece que, cuando solo se mejora o se ejecuta en paralelo una parte de una tarea, el tramo en serie que queda intacto determina el límite superior del factor de aceleración total. El informático Gene Amdahl desarrolló esta idea en su artículo «Validez del enfoque de un solo procesador para lograr capacidades de cómputo a gran escala» (Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities), que presentó en la Conferencia Conjunta de Informática de Primavera de la AFIPS en 1967.
En este material veremos, por orden, qué significa el factor de aceleración en la ley de Amdahl y cómo la fracción en serie determina su límite superior. Después examinaremos analogías cotidianas, como la cocina y las líneas de montaje, y la realidad de los sistemas multinúcleo, para terminar con las diferencias respecto a la ley de Gustafson y cómo aplicar ambas.
El límite del paralelismo según la ley de Amdahl
Qué significan el factor de aceleración y el tramo en serie
La ley de Amdahl nació como un principio general que permite determinar cuánto mejora el rendimiento global al mejorar una parte de un sistema. Hoy se utiliza principalmente para predecir el factor de aceleración teórico en la computación paralela. La clave para estimar cuánto puede acelerarse la tarea en su conjunto es distinguir la parte que puede repartirse para ejecutarse en paralelo de la que necesariamente debe ejecutarse en secuencia.
Si p es la fracción del tiempo total de ejecución que puede repartirse para ejecutarse en paralelo y N es el número de procesadores (o núcleos), el factor de aceleración teórico se obtiene dividiendo 1 entre ((1-p) + p/N). Si expresamos lo mismo en función de la fracción en serie s, el factor de aceleración se obtiene dividiendo 1 entre (s + (1-s)/N). A medida que aumenta N, disminuye la influencia del tramo paralelo, pero la fracción en serie s permanece constante. Incluso si el número de procesadores aumenta indefinidamente, el factor de aceleración no puede superar 1/s.
- El factor de aceleración (Speedup) es el cociente entre el tiempo de ejecución antes de la mejora y el tiempo de ejecución después de la mejora.
- La fracción en serie (Serial Fraction) es la proporción del tiempo que debe procesarse en secuencia porque el trabajo correspondiente no puede repartirse para ejecutarse simultáneamente.
- La fracción paralela (Parallel Fraction) es la proporción del tiempo correspondiente al trabajo que puede repartirse entre varios procesadores y ejecutarse simultáneamente.
Por qué se nota tan poco la mejora al añadir núcleos
La fórmula por sí sola puede parecer abstracta. Los límites que suelen citarse ayudan a entenderla de forma intuitiva. Si solo la mitad de la tarea puede repartirse para ejecutarse en paralelo, el factor de aceleración total será como máximo de dos, por muchos núcleos que se añadan. Incluso si el 95 por ciento puede ejecutarse en paralelo, el factor teórico tiene un límite de veinte. Esto se debe a que el 5 por ciento restante, que se ejecuta en serie, limita la velocidad total.
(1) Los rendimientos decrecientes aparecen pronto
Si la fracción en serie se mantiene constante, las ganancias son cada vez menores al pasar de 2 a 4 y luego a 8 núcleos. Una vez que se ha acortado el tramo paralelo, el tramo en serie se convierte en el cuello de botella.
(2) La comunicación y la sincronización también se comportan casi como tramos en serie
En la práctica, repartir el trabajo entre núcleos exige tiempo para reunir los resultados, aplicar bloqueos y mantener la coherencia de la memoria. Este coste queda fuera del supuesto de «paralelismo perfecto» de la fórmula, por lo que el factor de aceleración que se percibe suele ser inferior al teórico.
(3) Un cuello de botella de una sola línea limita el conjunto
Incluso un fragmento breve de código en serie, como la lectura de archivos, la inicialización o la suma final, reduce considerablemente el límite superior si representa una proporción apreciable del tiempo. Por eso, al diseñar sistemas con CPU multinúcleo y aceleración por GPU, conviene preguntarse primero «¿qué queda en serie?» y después «¿qué se va a paralelizar?».
Analogías cotidianas con la cocina y las líneas de montaje
La misma estructura que describe la ley de Amdahl aparece fuera de la informática. Pensemos en preparar una cena para diez invitados. Cortar y saltear las verduras lleva menos tiempo si hay más personas ayudando, pero el tiempo de horneado se mantiene aunque haya mucha gente. Si el horno es el tramo en serie, ese tramo limita el tiempo total de preparación de la cena por muchas manos que se sumen.
En una línea de montaje de una fábrica ocurre algo parecido. Aunque se ensamblen piezas al mismo tiempo en varias estaciones, si la inspección final o el embalaje se realizan en una sola línea, el ritmo de esa línea determina la velocidad del conjunto. En una reunión también puede repartirse la búsqueda de información, pero es difícil alcanzar en paralelo el acuerdo único que permite tomar una decisión.
Qué observar en la vida cotidiana
- El cuello de botella (Bottleneck) es el tramo en serie más lento y determina el ritmo de todo el proceso.
- El trabajo paralelizable (Parallel Work) es la parte que puede realizarse simultáneamente y de forma independiente.
- En la coordinación (Coordination), el coste de reunir los resultados y ajustar el orden de las operaciones también reduce la velocidad que se percibe.
Cómo interpretar la ley de Amdahl junto con la ley de Gustafson
La ley de Amdahl muestra el límite superior al añadir procesadores «manteniendo fijo el tamaño del problema». La ley de Gustafson (Gustafson’s Law), que John Gustafson formuló en torno a 1988, adopta la perspectiva de ampliar también el problema al añadir procesadores para realizar una tarea mayor en el mismo tiempo. Terminar antes una tarea de tamaño fijo y ejecutar una simulación más precisa dentro del mismo plazo son objetivos que plantean preguntas distintas.
(1) La ley de Amdahl es especialmente útil para problemas de tamaño fijo
Si el objetivo es terminar «más rápido» con los mismos datos y la misma resolución, lo fundamental es reducir la fracción en serie. Entre las decisiones de diseño que responden a este objetivo están cambiar el algoritmo, reducir las operaciones de I/O y eliminar las sincronizaciones innecesarias.
(2) La ley de Gustafson ayuda cuando se amplía la escala
En problemas como los cálculos meteorológicos y científicos, donde pueden ampliarse las mallas o aumentarse las muestras, cuantos más núcleos hay, mayor es la cantidad de trabajo que puede procesarse en paralelo, lo que puede aumentar el beneficio efectivo.
(3) Cómo conciliar ambas leyes
Las dos fórmulas describen escenarios distintos según «qué se mantiene fijo y qué se amplía», de modo que cada una es válida en su escenario. Al desarrollar un producto, primero se decide si el objetivo es reducir la latencia o aumentar la capacidad de procesamiento y la escala. Después se aplica la perspectiva que corresponda.
Antes de formarse expectativas a partir del número de núcleos anunciado, es importante medir qué tramos de nuestro trabajo siguen ejecutándose en serie. El éxito de la paralelización depende más de cuánto se reduzca el tiempo que no puede repartirse que de cuántos núcleos se compren.
La ley de Amdahl establece que, aunque se mejore la parte que puede repartirse para ejecutarse en paralelo, la proporción del tramo en serie determina el límite superior del factor de aceleración total. Localizar y acortar los tramos en serie que actúan como cuellos de botella incide de forma más directa en el límite de rendimiento que añadir núcleos.
Medir primero el tiempo que no puede repartirse, antes de considerar el número de procesadores, es el primer paso para aplicar la ley de Amdahl en la práctica.
