Ley de Amdahl

Fórmula en la arquitectura informática

La aceleración teórica de la latencia (mediante una reducción de la latencia, es decir: la latencia como métrica es el tiempo transcurrido entre una entrada y una salida en un sistema) de la ejecución de un programa en función del número de procesadores que lo ejecutan, según la ley de Amdahl. La aceleración está limitada por la parte serial del programa. Por ejemplo, si el 95% del programa se puede paralelizar, la aceleración máxima teórica utilizando computación paralela sería 20 veces.

En arquitectura de computadoras , la ley de Amdahl (o argumento de Amdahl ^[1] ) es una fórmula que da la aceleración teórica en latencia de la ejecución de una tarea con una carga de trabajo fija que se puede esperar de un sistema cuyos recursos se mejoran.

La ley puede resumirse así:

"La mejora general del rendimiento obtenida al optimizar una sola parte de un sistema está limitada por la fracción de tiempo en que se utiliza realmente la parte mejorada". ^[2]

Lleva el nombre del científico informático Gene Amdahl y se presentó en la Conferencia informática conjunta de primavera de la Federación Estadounidense de Sociedades de Procesamiento de Información (AFIPS) en 1967.

La ley de Amdahl se utiliza a menudo en computación paralela para predecir la aceleración teórica cuando se utilizan varios procesadores. Por ejemplo, si un programa necesita 20 horas para completarse utilizando un solo hilo, y una parte de una hora del programa no se puede paralelizar, entonces solo se pueden paralelizar las 19 horas restantes ( p = 0,95 ) de tiempo de ejecución. Por lo tanto, independientemente de cuántos hilos se dediquen a una ejecución paralelizada de este programa, el tiempo mínimo de ejecución siempre es más de 1 hora. Por lo tanto, la aceleración teórica es, como máximo, 20 veces el rendimiento de un solo hilo . ${\displaystyle \left({\dfrac {1}{1-p}}=20\right)}$

La Ley de Escalabilidad Universal (LSU), desarrollada por Neil J. Gunther , extiende la ley de Amdahl y tiene en cuenta la sobrecarga adicional debida a la comunicación entre procesos. La LSU cuantifica la escalabilidad en función de parámetros como la contención y la coherencia. ^[3]

Definición

La ley de Amdahl se puede formular de la siguiente manera: ^[4]

${\displaystyle S_{\text{latency}}(s)={\frac {1}{(1-p)+{\frac {p}{s}}}}}$

dónde

• La _latencia es la aceleración teórica de la ejecución de toda la tarea;
• s es la aceleración de la parte de la tarea que se beneficia de los recursos mejorados del sistema;
• p es la proporción del tiempo de ejecución que originalmente ocupaba la parte que se beneficiaba de los recursos mejorados.

Además,

${\displaystyle {\begin{cases}S_{\text{latency}}(s)\leq {\dfrac {1}{1-p}}\\[8pt]\lim \limits _{s\to \infty }S_{\text{latency}}(s)={\dfrac {1}{1-p}}.\end{cases}}}$

muestra que la aceleración teórica de la ejecución de toda la tarea aumenta con la mejora de los recursos del sistema y que, independientemente de la magnitud de la mejora, la aceleración teórica siempre está limitada por la parte de la tarea que no puede beneficiarse de la mejora.

La ley de Amdahl se aplica únicamente a los casos en los que el tamaño del problema es fijo. En la práctica, a medida que se dispone de más recursos informáticos, estos tienden a utilizarse en problemas más grandes (conjuntos de datos más grandes), y el tiempo dedicado a la parte paralelizable suele crecer mucho más rápido que el trabajo inherentemente serial. En este caso, la ley de Gustafson ofrece una evaluación menos pesimista y más realista del rendimiento paralelo. ^[5]

Derivación

Una tarea ejecutada por un sistema cuyos recursos se mejoran en comparación con un sistema similar inicial se puede dividir en dos partes:

• una parte que no se beneficia de la mejora de los recursos del sistema;
• una parte que se beneficia de la mejora de los recursos del sistema.

Un ejemplo es un programa informático que procesa archivos. Una parte de ese programa puede escanear el directorio del disco y crear una lista de archivos internamente en la memoria. Después de eso, otra parte del programa pasa cada archivo a un hilo separado para su procesamiento. La parte que escanea el directorio y crea la lista de archivos no se puede acelerar en una computadora paralela, pero la parte que procesa los archivos sí.

El tiempo de ejecución de toda la tarea antes de la mejora de los recursos del sistema se denota como . Incluye el tiempo de ejecución de la parte que no se beneficiaría de la mejora de los recursos y el tiempo de ejecución de la que se beneficiaría de ella. La fracción del tiempo de ejecución de la tarea que se beneficiaría de la mejora de los recursos se denota por . El relativo a la parte que no se beneficiaría de ella es por tanto . Entonces: ${\displaystyle T}$ ${\displaystyle p}$ ${\displaystyle 1-p}$

${\displaystyle T=(1-p)T+pT.}$

Es la ejecución de la parte que se beneficia de la mejora de los recursos la que se acelera por el factor posterior a la mejora de los recursos. En consecuencia, el tiempo de ejecución de la parte que no se beneficia de ella permanece igual, mientras que el de la parte que se beneficia de ella pasa a ser: ${\displaystyle s}$

${\displaystyle {\frac {p}{s}}T.}$

El tiempo teórico de ejecución de toda la tarea después de la mejora de los recursos es entonces: ${\displaystyle T(s)}$

${\displaystyle T(s)=(1-p)T+{\frac {p}{s}}T.}$

La ley de Amdahl proporciona la aceleración teórica en latencia de la ejecución de toda la tarea con una carga de trabajo fija ${\displaystyle W}$ , lo que da como resultado

${\displaystyle S_{\text{latency}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1}{1-p+{\frac {p}{s}}}}.}$

Programas paralelos

Si el 30% del tiempo de ejecución puede ser objeto de una mejora, p será 0,3; si la mejora hace que la parte afectada sea el doble de rápida, s será 2. La ley de Amdahl establece que la mejora global de la aplicación de la mejora será:

${\displaystyle S_{\text{latency}}={\frac {1}{1-p+{\frac {p}{s}}}}={\frac {1}{1-0.3+{\frac {0.3}{2}}}}=1.18.}$

Por ejemplo, supongamos que se nos da una tarea en serie que se divide en cuatro partes consecutivas, cuyos porcentajes de tiempo de ejecución son p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23 y p 4 = 0,48 respectivamente. Luego se nos dice que la primera parte no se acelera, por lo que s 1 = 1 , mientras que la segunda parte se acelera 5 veces, por lo que s 2 = 5 , la tercera parte se acelera 20 veces, por lo que s 3 = 20 , y la cuarta parte se acelera 1,6 veces, por lo que s 4 = 1,6 . Al utilizar la ley de Amdahl, la aceleración total es

${\displaystyle S_{\text{latency}}={\frac {1}{{\frac {p1}{s1}}+{\frac {p2}{s2}}+{\frac {p3}{s3}}+{\frac {p4}{s4}}}}={\frac {1}{{\frac {0.11}{1}}+{\frac {0.18}{5}}+{\frac {0.23}{20}}+{\frac {0.48}{1.6}}}}=2.19.}$

Observe cómo la aceleración de 5 y 20 veces en la 2.ª y 3.ª parte respectivamente no tiene mucho efecto en la aceleración general cuando la 4.ª parte (48 % del tiempo de ejecución) se acelera solo 1,6 veces.

Programas en serie

Supongamos que una tarea tiene dos partes independientes, A y B. La parte B requiere aproximadamente el 25 % del tiempo de todo el cálculo. Si se trabaja muy duro, se puede hacer que esta parte sea 5 veces más rápida, pero esto reduce el tiempo de todo el cálculo solo ligeramente. Por el contrario, es posible que se necesite realizar menos trabajo para que la parte A funcione el doble de rápido. Esto hará que el cálculo sea mucho más rápido que si se optimiza la parte B , aunque la aceleración de la parte B sea mayor en términos de la relación (5 veces frente a 2 veces).

Por ejemplo, con un programa serial en dos partes A y B para el cual T _A = 3 s y T _B = 1 s ,

• Si se hace que la parte B funcione 5 veces más rápido, es decir s = 5 y p = T _B /( T _A + T _B ) = 0,25 , entonces $${\displaystyle S_{\text{latency}}={\frac {1}{1-0.25+{\frac {0.25}{5}}}}=1.25;}$$
• Si se hace que la parte A corra 2 veces más rápido, es decir s = 2 y p = T _A /( T _A + T _B ) = 0,75 , entonces $${\displaystyle S_{\text{latency}}={\frac {1}{1-0.75+{\frac {0.75}{2}}}}=1.60.}$$

Por lo tanto, hacer que la parte A funcione dos veces más rápido es mejor que hacer que la parte B funcione cinco veces más rápido. El porcentaje de mejora en la velocidad se puede calcular como

${\displaystyle {\text{percentage improvement}}=100\left(1-{\frac {1}{S_{\text{latency}}}}\right).}$

• Mejorar la parte A en un factor de 2 aumentará la velocidad general del programa en un factor de 1,60, lo que lo hace un 37,5 % más rápido que el cálculo original.
• Sin embargo, mejorar la parte B en un factor de 5, lo que presumiblemente requiere más esfuerzo, logrará un factor de aceleración general de solo 1,25, lo que la hace un 20% más rápida.

Optimización de la parte secuencial de programas paralelos

Si la parte no paralelizable se optimiza por un factor de , entonces ${\displaystyle O}$

${\displaystyle T(O,s)=(1-p){\frac {T}{O}}+{\frac {p}{s}}T.}$

De la ley de Amdahl se deduce que la aceleración debida al paralelismo viene dada por

${\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}.}$

Cuando , tenemos , lo que significa que la aceleración se mide con respecto al tiempo de ejecución después de que se optimiza la parte no paralelizable. ${\displaystyle s=1}$ ${\displaystyle S_{\text{latency}}(O,s)=1}$

Cuando , ${\displaystyle s=\infty }$

${\displaystyle S_{\text{latency}}(O,\infty )={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}=1+{\frac {p}{1-p}}O.}$

Si , y , entonces: ${\displaystyle 1-p=0.4}$ ${\displaystyle O=2}$ ${\displaystyle s=5}$

${\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {{0.4}{\frac {1}{2}}+0.6}{{\frac {0.4}{2}}+{\frac {0.6}{5}}}}=2.5.}$

Transformar partes secuenciales de programas paralelos en paralelizables

A continuación, consideramos el caso en el que la parte no paralelizable se reduce por un factor de , y la parte paralelizable se incrementa correspondientemente. Entonces ${\displaystyle O'}$

${\displaystyle T'(O',s)={\frac {1-p}{O'}}T+\left(1-{\frac {1-p}{O'}}\right){\frac {T}{s}}.}$

De la ley de Amdahl se deduce que la aceleración debida al paralelismo viene dada por

${\displaystyle S'_{\text{latency}}(O',s)={\frac {T'(O')}{T'(O',s)}}={\frac {1}{{\frac {1-p}{O'}}+\left(1-{\frac {1-p}{O'}}\right){\frac {1}{s}}}}.}$

Relación con la ley de rendimientos decrecientes

La ley de Amdahl se confunde a menudo con la ley de rendimientos decrecientes , mientras que solo un caso especial de aplicación de la ley de Amdahl demuestra la ley de rendimientos decrecientes. Si uno elige de manera óptima (en términos de la aceleración lograda) lo que se debe mejorar, entonces verá mejoras decrecientes monótonamente a medida que uno mejora. Sin embargo, si uno elige de manera no óptima, después de mejorar un componente subóptimo y pasar a mejorar un componente más óptimo, puede ver un aumento en el rendimiento. Tenga en cuenta que a menudo es racional mejorar un sistema en un orden que es "no óptimo" en este sentido, dado que algunas mejoras son más difíciles o requieren un mayor tiempo de desarrollo que otras.

La ley de Amdahl representa la ley de rendimientos decrecientes si se considera qué tipo de rendimiento se obtiene al agregar más procesadores a una máquina, si se ejecuta un cálculo de tamaño fijo que utilizará todos los procesadores disponibles en su capacidad. Cada nuevo procesador agregado al sistema agregará menos potencia utilizable que el anterior. Cada vez que se duplica el número de procesadores, la tasa de aceleración disminuirá, ya que el rendimiento total se acerca al límite de 1/(1 −  p ).

Este análisis no tiene en cuenta otros posibles cuellos de botella, como el ancho de banda de la memoria y el ancho de banda de E/S. Si estos recursos no se escalan con la cantidad de procesadores, entonces simplemente agregar procesadores proporciona retornos aún más bajos.

Una implicación de la ley de Amdahl es que para acelerar aplicaciones reales que tienen partes en serie y en paralelo, se requieren técnicas de computación heterogéneas . ^[6] Existen nuevos modelos de aceleración y consumo de energía basados ​​en una representación más general de la heterogeneidad, denominada heterogeneidad de forma normal, que admiten una amplia gama de arquitecturas heterogéneas de múltiples núcleos. Estos métodos de modelado tienen como objetivo predecir la eficiencia energética y los rangos de rendimiento del sistema, y ​​facilitan la investigación y el desarrollo a nivel de hardware y software del sistema. ^{[7] [8]}

Véase también

• Ley de Gustafson
• Ley universal de escalabilidad computacional
• Análisis de algoritmos paralelos
• Método de la ruta crítica
• Ley de Moore

Referencias

1. Rodgers, David P. (junio de 1985). "Mejoras en el diseño de sistemas multiprocesadores". ACM Sigarch Computer Architecture News . 13 (3). Nueva York, NY, EE. UU.: ACM : 225–231 [p. 226]. doi :10.1145/327070.327215. ISBN 0-8186-0634-7. ISSN  0163-5964. S2CID  7083878.
2. Reddy, Martin (2011). Diseño de API para C++ . Burlington, Massachusetts : Morgan Kaufmann Publishers . pág. 210. doi :10.1016/C2010-0-65832-9. ISBN . 978-0-12-385003-4. OCLC  666246330  .​
3. Gunther, Neil (2007). Planificación de la capacidad de guerrilla: un enfoque táctico para la planificación de aplicaciones y servicios altamente escalables . ISBN 978-3540261384.
4. Bryant, Randal E .; David, O'Hallaron (2016), Sistemas informáticos: la perspectiva de un programador (3.ª ed.), Pearson Education, pág. 58, ISBN 978-1-488-67207-1
5. McCool, Michael; Reinders, James; Robison, Arch (2013). Programación paralela estructurada: patrones para computación eficiente . Elsevier. pág. 61. ISBN 978-0-12-415993-8.
6. Hill, Mark D.; Marty, Michael R. (2008). "La ley de Amdahl en la era multinúcleo". Computer . 41 (7): 33–38. CiteSeerX 10.1.1.221.8635 . doi :10.1109/MC.2008.209. 
7. Rafiev, Ashur; Al-Hayanni, Mohammed AN; Xia, Fei; Shafik, Rishad; Romanovsky, Alexander; Yakovlev, Alex (1 de julio de 2018). "Modelos de aceleración y escalado de potencia para sistemas heterogéneos de múltiples núcleos". IEEE Transactions on Multi-Scale Computing Systems . 4 (3): 436–449. doi :10.1109/TMSCS.2018.2791531. ISSN  2332-7766. S2CID  52287374.
8. Al-hayanni, Mohammed A. Noaman; Xia, Fei; Rafiev, Ashur; Romanovsky, Alexander; Shafik, Rishad; Yakovlev, Alex (julio de 2020). "Ley de Amdahl en el contexto de sistemas heterogéneos de múltiples núcleos: una encuesta". IET Computers & Digital Techniques . 14 (4): 133–148. doi : 10.1049/iet-cdt.2018.5220 . ISSN  1751-8601. S2CID  214415079.

Lectura adicional

• Amdahl, Gene M. (1967). "Validez del enfoque de procesador único para lograr capacidades de computación a gran escala" (PDF) . Actas de la conferencia AFIPS (30): 483–485. doi :10.1145/1465482.1465560. S2CID  195607370.

Enlaces externos

• Gene M. Amdahl (1989), Entrevista de historia oral con Gene M. Amdahl , Instituto Charles Babbage , Universidad de Minnesota, hdl :11299/104341Amdahl habla de su trabajo de posgrado en la Universidad de Wisconsin y de su diseño de WISC . Habla de su papel en el diseño de varias computadoras para IBM, incluidas STRETCH , IBM 701 e IBM 704. Habla de su trabajo con Nathaniel Rochester y de la gestión del proceso de diseño por parte de IBM. Menciona su trabajo con Ramo-Wooldridge , Aeronutronic y Computer Sciences Corporation .
• "Ley de Amdahl" de Joel F. Klein, Wolfram Demonstrations Project (2007)
• La Ley de Amdahl en la era de los núcleos múltiples (julio de 2008)