ley de amdahl

Fórmula en arquitectura informática.

La aceleración teórica de la latencia (a través de 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 usando computación paralela sería 20 veces.

En arquitectura informática , la ley de Amdahl (o argumento de Amdahl ^[1] ) es una fórmula que proporciona 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. Afirma que "la mejora general del rendimiento obtenida al optimizar una sola parte de un sistema está limitada por la fracción de tiempo que realmente se utiliza 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 la 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 subproceso y una parte del programa de una hora no se puede paralelizar, entonces solo se pueden paralelizar las 19 horas restantes ( p = 0,95 ) del tiempo de ejecución. Por lo tanto, independientemente de cuántos subprocesos se dediquen a la ejecución en paralelo de este programa, el tiempo mínimo de ejecución es siempre superior a 1 hora. Por lo tanto, la aceleración teórica es, como máximo, 20 veces el rendimiento de un solo subproceso . ${\displaystyle \left({\dfrac {1}{1-p}}=20\right)}$

Definición

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

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

dónde

• _{La latencia} S 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 la mejora de los recursos del sistema;
• p es la proporción del tiempo de ejecución que ocupaba originalmente la parte que se beneficia 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 sólo en los casos en que el tamaño del problema es fijo. En la práctica, a medida que hay más recursos informáticos disponibles, tienden a usarse en problemas más grandes (conjuntos de datos más grandes) y el tiempo dedicado a la parte paralelizable a menudo crece mucho más rápido que el trabajo inherentemente en serie. En este caso, la ley de Gustafson ofrece una evaluación menos pesimista y más realista del desempeño paralelo. ^[4]

Derivación

Una tarea ejecutada por un sistema cuyos recursos 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 sí 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 . Por tanto, la relativa a la parte que no se beneficiaría de él es . 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 que es acelerada por el factor posterior a la mejora de los recursos. En consecuencia, el tiempo de ejecución de la parte que no se beneficia sigue siendo el mismo, mientras que la parte que se beneficia pasa a ser: ${\displaystyle s}$

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

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

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

La ley de Amdahl da 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 produce

${\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 aceleración, p será 0,3; si la mejora hace que la parte afectada sea dos veces más rápida, s será 2. La ley de Amdahl establece que la velocidad general de 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 nos dan 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 está acelerada, 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 general 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 segunda y tercera parte respectivamente no tiene mucho efecto en la aceleración general cuando la cuarta parte (48% del tiempo de ejecución) se acelera solo 1,6 veces.

Programas en serie

Suponga que una tarea tiene dos partes independientes , A y B. La parte B requiere aproximadamente el 25% del tiempo de todo el cálculo. Trabajando muy duro, uno puede ser capaz de hacer esta parte 5 veces más rápido, pero esto reduce sólo ligeramente el tiempo de todo el cálculo. Por el contrario, es posible que sea necesario 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 optimizando la parte B , aunque la aceleración de la parte B es mayor en términos de relación (5 veces versus 2 veces).

Por ejemplo, con un programa en serie 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 corra 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 se ejecute 2 veces más rápido es mejor que hacer que la parte B se ejecute 5 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 sólo 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 está 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 optimizar 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 en un factor de y la parte paralelizable aumenta 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 está 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 a menudo se combina con la ley de rendimientos decrecientes , mientras que sólo 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 monótonamente decrecientes a medida que mejora. Sin embargo, si uno elige no de manera óptima, después de mejorar un componente subóptimo y pasar a mejorar un componente más óptimo, se puede ver un aumento en el rendimiento. Tenga en cuenta que a menudo es racional mejorar un sistema en un orden que no es "óptimo" en este sentido, dado que algunas mejoras son más difíciles o requieren más tiempo de desarrollo que otras.

La ley de Amdahl representa la ley de los 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 a su capacidad. Cada nuevo procesador agregado al sistema agregará menos energía utilizable que el anterior. Cada vez que se duplica el número de procesadores, la relación de aceleración disminuirá, a medida que el rendimiento total se acerca al límite de 1/(1 −  p ).

Este análisis ignora 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 aumentan con la cantidad de procesadores, entonces simplemente agregar procesadores proporciona retornos aún menores.

Una implicación de la ley de Amdahl es que para acelerar aplicaciones reales que tienen porciones tanto en serie como en paralelo, se requieren técnicas informáticas heterogéneas . ^[5] 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 muchos núcleos. Estos métodos de modelado tienen como objetivo predecir la eficiencia energética del sistema y los rangos de rendimiento, y facilitan la investigación y el desarrollo a nivel de hardware y software del sistema. ^{[6] [7]}

Ver también

• ley de gustafson
• Ley universal de escalabilidad computacional
• Análisis de algoritmos paralelos.
• Método del camino crítico
• ley de moore

Referencias

1. Rodgers, David P. (junio de 1985). "Mejoras en el diseño de sistemas multiprocesador". Noticias de arquitectura informática de ACM Sigarch . 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, Martín (2011). Diseño de API para C++ . Burlington, Massachusetts : Editores Morgan Kaufmann . pag. 210. doi :10.1016/C2010-0-65832-9. ISBN 978-0-12-385003-4. LCCN  2010039601. OCLC  666246330.
3. 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
4. McCool, Michael; Reinders, James; Robinson, arco (2013). Programación paralela estructurada: patrones para una computación eficiente . Elsevier. pag. 61.ISBN​ 978-0-12-415993-8.
5. Colina, Mark D.; Marty, Michael R. (2008). "Ley de Amdahl en la era multinúcleo". Computadora . 41 (7): 33–38. CiteSeerX 10.1.1.221.8635 . doi :10.1109/MC.2008.209. 
6. Rafiev, Ashur; Al-Hayanni, Mohammed AN; Xia, Fei; Shafik, Rishad; Romanovsky, Alejandro; Yakovlev, Alex (1 de julio de 2018). "Modelos de aceleración y escalamiento de potencia para sistemas heterogéneos de muchos núcleos". Transacciones IEEE en sistemas informáticos multiescala . 4 (3): 436–449. doi :10.1109/TMSCS.2018.2791531. ISSN  2332-7766. S2CID  52287374.
7. Al-hayanni, Mohammed A. Noaman; Xia, Fei; Rafiev, Ashur; Romanovsky, Alejandro; Shafik, Rishad; Yakovlev, Alex (julio de 2020). "La ley de Amdahl en el contexto de sistemas heterogéneos de muchos núcleos: una encuesta". Computadoras IET y técnicas digitales . 14 (4): 133-148. doi : 10.1049/iet-cdt.2018.5220 . ISSN  1751-8601. S2CID  214415079.

Otras lecturas

• Amdahl, Gene M. (1967). "Validez del enfoque de procesador único para lograr capacidades informáticas a gran escala" (PDF) . Actas de la conferencia de 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/104341. Amdahl analiza su trabajo de posgrado en la Universidad de Wisconsin y su diseño de WISC . Analiza 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 la gestión del proceso de diseño de IBM. Menciona trabajos con Ramo-Wooldridge , Aeronutronic y Computer Sciences Corporation.
• "Ley de Amdahl" de Joel F. Klein, Proyecto de demostraciones Wolfram (2007)
• Ley de Amdahl en la era multinúcleo (julio de 2008)