Imagínese esto: tiene prisa por preparar un banquete delicioso, pero está limitado por el tamaño de su cocina y la cantidad de manos a la obra. En el mundo de la computación paralela, la Ley de Amdahl y la Ley de Gustafson son las recetas confiables que necesita para optimizar su obra maestra culinaria. Son como los ingredientes secretos que han sazonado el rendimiento de las computadoras durante décadas, permitiéndonos disfrutar de velocidades de procesamiento cada vez más rápidas. Estos dos principios pueden ser el yin y el yang de la computación paralela, y han estado guiando a los magos expertos en tecnología en su búsqueda por conquistar el reino de los procesadores multinúcleo y la computación de alto rendimiento. Pero, ¿qué son las leyes de Amdahl y Gustafson y cómo ejercen su magia por separado o en conjunto? Siendo conscientes de la importancia de la programación paralela , hoy profundizaremos en las complejidades de estas leyes y descubriremos cómo pueden utilizarse como herramientas poderosas en manos de programadores expertos.

Tabla de contenido

• Ley de Amdahl: antecedentes

  – Aceleración máxima

  – Advertencias

• Ley de Gustafson: antecedentes

  – Aceleración escalada

  – Advertencias

• Escalado fuerte versus escalamiento débil

  – Pruebas de escala

  — Fuerte escalamiento

  — Escalado débil

• Conclusiones

Ley de Amdahl: antecedentes

Allá por el año 1967, en la Spring Joint Computer Conference, el Dr. Gene Amdahl, que estaba realizando algunos trabajos de magia informática en IBM, se reunió con otras tres personas conocedoras de la tecnología, incluido el cerebrito Daniel Slotnick, el genio detrás del funcionamiento interno de Illiac-IV. ¿Qué estaban haciendo, preguntas? Bueno, estaban debatiendo el futuro de la arquitectura informática. Durante esta conferencia, el Dr. Gene Amdahl expuso su opinión sobre los obstáculos que enfrenta el "enfoque multiprocesador" cuando se trata de problemas del mundo real y todas sus peculiaridades. Y adivinen qué, ¡hizo un gran reconocimiento al “enfoque de procesador único” para cuestiones de esa naturaleza!

Mientras estuvo en IBM, Amdahl se dio cuenta de que una parte sustancial del trabajo computacional estaba ocupada por lo que acertadamente denominó " manejo interno de gestión de datos ". Sostuvo firmemente que esta fracción en particular se había mantenido notablemente constante durante aproximadamente una década, devorando constantemente el 40% de las instrucciones ejecutadas en las series de producción.

¿Qué se incluye bajo el paraguas de este trabajo de “limpieza”? Abarca una amplia gama de tareas computacionales que, si bien son esenciales, no contribuyen directamente a la misión informática central. Dependiendo del algoritmo y la aplicación específicos, esto puede involucrar E/S de datos, preprocesamiento, administración de memoria, manejo de archivos y más. Esta coherencia sugiere que, para muchas aplicaciones, una parte sustancial del tiempo de procesamiento se dedica a estas tareas. Un cierto nivel de mantenimiento de la gestión de datos es casi inevitable y difícil de minimizar significativamente. Amdahl señala que esta sobrecarga parece secuencial, lo que significa que ocurre paso a paso y no es adecuada para técnicas de procesamiento paralelo.

"Una conclusión bastante obvia que se puede sacar en este punto es que el esfuerzo invertido en lograr altas tasas de procesamiento paralelo es en vano a menos que vaya acompañado de logros en tasas de procesamiento secuencial de casi la misma magnitud". - Dr. Gene Amdahl [1]

En su artículo original [1], Amdahl añade que el ámbito de las tareas de “limpieza” es sólo la punta del iceberg respecto de los desafíos que enfrenta el enfoque “multiprocesador”. Con su impresionante experiencia como físico teórico capacitado y con un doctorado, Amdahl poseía un conocimiento profundo de los desafíos físicos del mundo real para los que fueron diseñadas las computadoras. Subraya muchas complicaciones, como límites irregulares, interiores no uniformes y dependencias espaciales y temporales de estados variables, todo lo cual presenta obstáculos formidables para el paradigma del "multiprocesador".

Por ejemplo, considere calcular la distribución de calor en una cuadrícula cartesiana 2D. En cualquier punto dado, la temperatura (T) depende de las temperaturas de los puntos vecinos. Cuando se emplea un modelo de computación paralela, es esencial comunicar estos valores con puntos adyacentes, que podrían almacenarse en procesadores separados. Estas cuestiones siguen siendo omnipresentes en los escenarios contemporáneos.

Afortunadamente, el ingenio colectivo de los expertos en computación ha dado como resultado numerosos métodos numéricos y técnicas de programación diseñadas para abordar estos intrincados desafíos de frente.

Ley de Amdahl: aceleración máxima

En su trabajo original, la formulación de Amdahl no profundizaba en ecuaciones matemáticas; Sólo en análisis posteriores se cuantificó la aceleración máxima.

La Ley de Amdahl se basa en el supuesto de que una fracción f del tiempo de ejecución de un programa en serie es idealmente paralelizable sin ninguna sobrecarga de comunicación o sincronización. La porción complementaria, representada como s = 1 − f, es completamente secuencial.

Así, si T es el tiempo de ejecución del programa secuencial, el tiempo de ejecución en p núcleos, T(p), viene dado por:

Speedup , que es la relación entre el tiempo de ejecución secuencial y el tiempo de ejecución en paralelo, da:

Por tanto, el límite superior de la aceleración se puede definir como:

Advertencias

A pesar de su simplicidad, la ley de Amdahl no está exenta de limitaciones. El modelo pasa por alto los cuellos de botella críticos del hardware, como el ancho de banda de la memoria, la latencia y las limitaciones de E/S. Tampoco tiene en cuenta los inconvenientes de rendimiento de la creación de subprocesos, la sincronización, la sobrecarga de comunicación y otros factores del mundo real. Lamentablemente, estos factores no contabilizados suelen tener un impacto perjudicial en el desempeño real.

La siguiente figura ilustra el impacto de la paralelización en la aceleración, según lo determinado por la ley de Amdahl. Está claro que, incluso con una fracción paralela sustancial del 95% y una amplia gama de procesadores, la aceleración máxima alcanzable se limita a alrededor de 20 veces. Llevar el porcentaje de paralelización al 99% y emplear una cantidad infinita de procesadores puede producir una impresionante aceleración de 100x, lo cual es prometedor.

Sin embargo, es fundamental reconocer que tener tantos procesadores es una rareza . A menudo trabajamos con un número mucho más modesto, como 64 o incluso menos.

Cuando aplicamos la ley de Amdahl a un programa que utiliza 64 procesadores (siendo f 95%), la velocidad máxima ronda 15,42x. ¡Es cierto que esta cifra no es muy prometedora!

Esta idea queda algo oscurecida por el límite empleado en esta expresión:

Este límite tiende a ocultar el hecho de que las cifras de velocidad son notablemente más bajas cuando consideramos números prácticos de procesadores en el mundo real.

No obstante, el inconveniente más importante de la ley de Amdahl radica en su suposición de que el tamaño del problema permanece constante cuando se utilizan más núcleos para ejecutar una aplicación.

Básicamente, se supone que la fracción paralelizable permanece sin cambios, independientemente del número de núcleos empleados. Esta limitación fue abordada y ampliada minuciosamente por John L. Gustafson , quien propuso una perspectiva modificada que ahora se conoce como ley de Gustafson . Sin embargo, a pesar de estos problemas y advertencias reconocidos, es esencial reconocer que la ley de Amdahl tiene sus propios méritos y ofrece información valiosa sobre las complejidades de la paralelización. La ley de Amdahl encuentra aplicación en forma de pruebas de escala fuertes , un tema que exploraremos más adelante.

Ley de Gustafson: antecedentes

Mientras trabajaba en los sistemas informáticos masivamente paralelos de los Laboratorios Nacionales Sandia, el Dr. John L. Gustafson y su equipo obtuvieron factores de aceleración impresionantes para tres aplicaciones diferentes en un hipercubo de 1024 procesadores. La fracción del código de serie correspondió al 0,4-0,8%.

“… hemos logrado los factores de aceleración en un hipercubo de 1024 procesadores que creemos que no tienen precedentes: 1021 para el análisis de tensión del haz usando gradientes conjugados, 1020 para la simulación de ondas de superficie desconcertadas usando diferencias finitas explícitas y 1016 para el flujo de fluido inestable usando corrección de flujo. transporte." — Dr. John L. Gustafson [2]

Vimos claramente en la última sección que según la ley de Amdahl, la velocidad máxima alcanzable para una gran cantidad de procesadores es 1/s. Entonces, ¿cómo se puede lograr esta desconcertante aceleración de 1021x?

Gustafson [2] destacó que la expresión matemática tiene una suposición sutil, implicando que la variable f no está relacionada con p . Sin embargo, este escenario rara vez es la realidad que encontramos. En escenarios del mundo real, normalmente no tomamos un problema de tamaño fijo y lo ejecutamos en diferentes números de procesadores, excepto quizás en el entorno controlado de la investigación académica. En cambio, en aplicaciones prácticas, el tamaño del problema tiende a escalar junto con la cantidad de procesadores.

Cuando hay procesadores más potentes disponibles, los usuarios se adaptan ampliando la complejidad del problema para aprovechar al máximo las capacidades mejoradas. Pueden ajustar aspectos como la resolución de la cuadrícula, el número de pasos de tiempo, la complejidad del operador de diferencia y otros parámetros para garantizar que el programa se pueda ejecutar en el período de tiempo deseado.

Según Gustafson, a menudo es más realista suponer que, en la práctica, el tiempo de ejecución permanece relativamente constante que el tamaño del problema.

Gustafson notó que la fracción paralela o vectorial de un programa crece en proporción al tamaño del problema. Elementos como el inicio del vector, la carga del programa, los cuellos de botella en serie y las operaciones de E/S, que en conjunto contribuyen al componente s del tiempo de ejecución del programa, generalmente permanecen relativamente constantes y no muestran un crecimiento significativo con el tamaño del problema.

Gustafson llevó el argumento más allá al enfatizar que en escenarios donde duplicamos los grados de libertad en una simulación física, a menudo es esencial duplicar correspondientemente el número de procesadores. Como estimación preliminar, el volumen de trabajo que se puede distribuir efectivamente en paralelo tiende a crecer linealmente con el número de procesadores.

En su examen en profundidad de las tres aplicaciones mencionadas, Gustafson y sus colegas descubrieron que el componente paralelo mostraba factores de escala de aproximadamente 1023,9969, 1023,9965 y 1023,9965.

Ley de Gustafson: aceleración escalada

La suposición de Gustafson radica en considerar el tiempo de ejecución normalizado en p núcleos, que suma (1 − f) + f , lo que da como resultado un valor total de 1. Según esta lógica, si (1 − f) + f significa el tiempo de ejecución en p núcleos , entonces el tiempo de ejecución en un solo núcleo se puede expresar como (1 − f) + p*f . En consecuencia, la aceleración, a la que Gustafson denominó “ aceleración escalada ”, se puede calcular de la siguiente manera:

Cuando aplicamos la ley de Gustafson a un programa que utiliza 64 procesadores (siendo f 95%), la aceleración prevista es 60,85x (en comparación con 15,42x con la ley de Amdahl). Ahora estamos hablando😉

Las siguientes figuras resaltan las diferencias entre las dos leyes.

Advertencias

Las perspectivas de Amdahl y Gustafson ofrecen distintos puntos de vista sobre la paralelización, cada uno con sus propios supuestos.

La ley de Amdahl supone que la cantidad de trabajo que se puede paralelizar es constante e independiente del número de procesadores, lo que la hace muy pesimista. La perspectiva de Gustafson, que supone que la cantidad de trabajo que se puede paralelizar crece linealmente con el número de núcleos, es sin duda práctica para muchos escenarios. Sin embargo, a veces puede resultar demasiado optimista.

Las aplicaciones del mundo real frecuentemente encuentran restricciones que pueden limitar esta escalabilidad lineal. Por ejemplo, a medida que aumenta el número de núcleos, pueden producirse rendimientos decrecientes debido a las complejidades del procesamiento paralelo, las dependencias de datos y los gastos generales de comunicación. Además, las limitaciones del hardware prácticamente limitan el número de núcleos que pueden integrarse eficazmente en un solo chip. Es posible que la ley de Gustafson no siempre tenga en cuenta estos intrincados desafíos del mundo real, por lo que es necesario considerar las salvedades que afectan su aplicabilidad.

La eficacia de la ley de Gustafson también puede depender de la naturaleza de la aplicación misma. Si bien algunas aplicaciones se prestan naturalmente a la escalabilidad lineal con un número de núcleos cada vez mayor, otras pueden estabilizarse mucho antes debido a limitaciones inherentes o a la naturaleza del problema. Se deben tener en cuenta las complejidades de la programación y el potencial de rendimientos decrecientes al considerar la viabilidad de la escalabilidad lineal en aplicaciones prácticas.

En esencia, si bien ofrece una perspectiva más optimista sobre la paralelización, la ley de Gustafson debe aplicarse con un conocimiento profundo de la aplicación, las limitaciones del hardware y las complejidades de la programación paralela para alinearse con las complejidades del mundo real de la informática moderna.

Escalado fuerte versus escalamiento débil

En esencia, la escalabilidad se refiere a la capacidad de un sistema o aplicación para gestionar de manera eficiente mayores cargas de trabajo a medida que aumenta su tamaño.

En informática, ya sea hardware o software, la escalabilidad denota la capacidad de mejorar la potencia computacional aumentando los recursos disponibles.

En el contexto de los clústeres de informática de alto rendimiento (HPC), lograr la escalabilidad es fundamental; significa la capacidad de ampliar sin problemas la capacidad general del sistema mediante la integración de componentes de hardware adicionales. En cuanto al software, la escalabilidad suele ser sinónimo de eficiencia de paralelización , lo que representa la relación entre la aceleración real obtenida y la aceleración ideal que se puede lograr al emplear un número específico de procesadores. Esta métrica ofrece información sobre la eficacia con la que el software puede aprovechar el procesamiento paralelo para mejorar el rendimiento.

Pruebas de escala

En el proceso de desarrollo típico de aplicaciones grandes, a menudo no resulta práctico comenzar las pruebas con el tamaño completo del problema y el número máximo de procesadores desde el principio. Este enfoque implica tiempos de espera prolongados y una utilización excesiva de recursos. Por lo tanto, una estrategia más pragmática implica inicialmente reducir estos factores, lo que acelera la fase de prueba y permite una estimación más precisa de los recursos necesarios para la eventual ejecución a gran escala, lo que ayuda en la planificación de recursos.

Las pruebas de escalabilidad sirven como medio para evaluar qué tan bien una aplicación puede adaptarse a diferentes tamaños de problemas y diferentes conteos de procesadores, asegurando un rendimiento óptimo.

Es importante tener en cuenta que las pruebas de escalabilidad no examinan la funcionalidad o corrección general de la aplicación; su enfoque principal es el rendimiento y la eficiencia a medida que se ajustan los recursos computacionales.

En la computación paralela se emplean ampliamente dos pruebas de escala estándar, fuerte y débil .

Escalamiento fuerte

Un escalamiento fuerte implica aumentar la cantidad de procesadores manteniendo constante el tamaño del problema. Este enfoque reduce la carga de trabajo por procesador, lo cual es particularmente valioso para aplicaciones de larga duración que requieren un uso intensivo de la CPU. El objetivo principal de un escalamiento sólido es identificar una configuración que ofrezca tiempos de ejecución razonables y al mismo tiempo mantenga los costos de recursos dentro de un rango manejable.

El escalamiento fuerte está anclado en la ley de Amdahl, donde el tamaño del problema permanece fijo mientras aumenta el número de elementos de procesamiento. Esta metodología suele justificarse para programas con cargas de trabajo sustanciales vinculadas a la CPU.

El objetivo final de un escalamiento sólido es localizar el "punto ideal" óptimo que permita completar los cálculos dentro de un plazo razonable, y al mismo tiempo minimizar el desperdicio de ciclos de procesamiento debido a la sobrecarga paralela.

En un escalamiento fuerte, se considera que un programa escala linealmente si la aceleración, en términos de unidades de trabajo completadas por unidad de tiempo, se alinea con la cantidad de elementos de procesamiento empleados (N). De manera similar, la aceleración puede ser sublineal o incluso superlineal, dependiendo de cómo escala con la cantidad de procesadores.

Finalmente, intenté realizar pruebas de escala sólida en uno de mis códigos. Fluidchen-EM es un solucionador de dinámica de fluidos computacional capaz de resolver muchos problemas de dinámica de fluidos. Los siguientes resultados corresponden a la simulación de la cavidad impulsada por la tapa . Se visualiza la velocidad en la marca de tiempo final (después de la convergencia) y se calcula el tiempo de ejecución. Fluidchen-EM utiliza MPI para distribuir el dominio computacional en procesadores iproc*jproc .

Nota : Los resultados se ejecutaron en mi computadora personal y todos los núcleos corresponden a un solo procesador. ¡Los resultados pueden variar si la simulación se ejecuta en una máquina mejor y más grande!

El dominio computacional se divide en un total de puntos de cuadrícula imax*jmax .

iproc: número de procesadores en la dirección x

jproc: número de procesadores en la dirección y

Como se muestra en la figura, el tiempo de ejecución disminuye drásticamente a medida que el número de procesadores se duplica de 1 a 2. Sin embargo, la aceleración no es tan dramática para la siguiente duplicación de procesadores de 2 a 4, e incluso comienza a saturarse para aumentos adicionales. en el número de procesadores. Sin embargo, los resultados fueron compilados en un procesador de ocho núcleos, por lo que estos resultados pueden cambiar si la ejecución se realiza en una máquina más grande y potente.

Escalado débil

En el escalado débil, la cantidad de procesadores y el tamaño del problema aumentan, manteniendo una carga de trabajo constante por procesador. La escala débil se alinea con la ley de Gustafson, donde la aceleración escalada se calcula en función de la carga de trabajo de un tamaño de problema escalado, a diferencia de la ley de Amdahl, que se centra en un tamaño de problema fijo.

El tamaño del problema asignado a cada elemento de procesamiento permanece constante, lo que permite que elementos adicionales resuelvan colectivamente un problema general más grande, que puede exceder la capacidad de memoria de un solo nodo.

El escalado débil justifica aplicaciones con requisitos sustanciales de memoria o recursos (aquellos vinculados a la memoria) que necesitan más memoria de la que un solo nodo puede proporcionar. Estas aplicaciones suelen exhibir un escalamiento eficiente ya que sus estrategias de acceso a la memoria priorizan los nodos cercanos, lo que las hace adecuadas para un mayor número de núcleos.

En el caso de un escalado débil, la escalabilidad lineal se logra cuando el tiempo de ejecución permanece constante a medida que la carga de trabajo aumenta en proporción directa al número de procesadores.

La mayoría de los programas que adoptan este modo exhiben una escala favorable a recuentos de núcleos más altos, particularmente aquellos que emplean patrones de comunicación con el vecino más cercano, ya que su sobrecarga de comunicación permanece relativamente consistente independientemente de la cantidad de procesos utilizados. Las excepciones a esta tendencia incluyen algoritmos que dependen en gran medida de patrones de comunicación global.

Finalmente, realicé las pruebas de escala débil usando Fluidchen-EM . Los siguientes resultados corresponden a la simulación de la convección de Rayleigh-Bénard . Nuevamente, se visualiza la velocidad en la marca de tiempo final (después de la convergencia) y se calcula el tiempo de ejecución. Fluidchen-EM utiliza MPI para distribuir el dominio computacional en procesadores iproc*jproc .

Nota: Los resultados se ejecutaron en mi computadora personal y todos los núcleos corresponden a un solo procesador. ¡Los resultados pueden variar si la simulación se ejecuta en una máquina mejor y más grande!

El dominio computacional se divide en un total de puntos de cuadrícula imax*jmax .

iproc: número de procesadores en la dirección x

jproc: número de procesadores en la dirección y

imax: número de puntos de la cuadrícula a lo largo del canal

jmax: número de puntos de la cuadrícula a lo largo de la altura del canal

xlength: longitud del canal

ylength: altura del canal

Como se ilustra en la figura anterior, el tiempo de ejecución muestra un aumento con el crecimiento tanto del tamaño del problema como del número de procesadores. Este comportamiento se puede atribuir a varios factores. Como todos los núcleos residen en un solo procesador, a medida que el tamaño del problema se expande y se utilizan más procesadores, una parte del tiempo de procesamiento se consume en la configuración de la comunicación MPI (Interfaz de paso de mensajes). Además, el mayor tamaño del problema requiere un mayor intercambio de datos entre los núcleos, amplificando la latencia de la comunicación debido al ancho de banda finito de la red de comunicación.

Por lo tanto, los resultados de estas pruebas proporcionan información crucial sobre la paralelización del problema.

Conclusión

La selección entre la Ley de Gustafson y la Ley de Amdahl en la paralelización de algoritmos depende de la adaptabilidad de la carga de trabajo de cálculo. La Ley de Gustafson es adecuada cuando un algoritmo puede ajustar dinámicamente la cantidad de cálculo para igualar la paralelización disponible. Por el contrario, la Ley de Amdahl es más adecuada cuando la carga de cálculo es fija y no puede alterarse significativamente mediante la paralelización. En escenarios del mundo real, adaptar un algoritmo para la paralelización a menudo implica cierto grado de modificación del cálculo, y ambas leyes sirven como puntos de referencia valiosos, ofreciendo límites superiores e inferiores en la aceleración prevista. La elección entre ellos depende del alcance de los cambios computacionales introducidos durante la paralelización, lo que permite una evaluación integral de las posibles ganancias de aceleración.

Lectura sugerida

[1] Validez del enfoque de procesador único para lograr capacidades informáticas a gran escala, reimpreso de las actas de la conferencia AFIPS, vol. 30 (Atlantic City, Nueva Jersey, 18-20 de abril), AFIPS Press, Reston, Va., 1967, págs. 483-485, cuando el Dr. Amdahl estaba en International Business Machines Corporation, Sunnyvale, California | Revistas y revistas IEEE | Exploración IEEE

[2] Reevaluación de la ley de Amdahl | Comunicaciones de la ACM

[3] Durganshu/Fluidchen-EM

[4] La ley de Amdahl para predecir el futuro de los multinúcleos se considera perjudicial (tu-berlin.de)

[5] Escalado: HPC Wiki (hpc-wiki.info)

[6] Amdahl contra gustafson por r1parks - Infogram

Foto destacada de Marc Sendra Martorell en Unsplash