En arquitectura informática , la ley de Amdahl (o el 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. Lleva el nombre del científico informático Gene Amdahl y se presentó en la Conferencia Conjunta de Computación AFIPS Spring en 1967.
La ley de Amdahl se usa a menudo en computación paralela para predecir la aceleración teórica cuando se usan múltiples procesadores. Por ejemplo, si un programa necesita 20 horas para completarse usando un solo subproceso, pero una porción de una hora del programa no se puede paralelizar, por lo tanto, solo se pueden paralelizar las 19 horas restantes ( p = 0.95 ) de tiempo de ejecución, entonces independientemente de cuántos subprocesos se dedican a una ejecución paralelizada de este programa, el tiempo mínimo de ejecución no puede ser inferior a una hora. Por lo tanto, la aceleración teórica se limita a un máximo de 20 veces el rendimiento de un solo hilo,.
Definición
La ley de Amdahl se puede formular de la siguiente manera: [2]
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 la mejora de los recursos del sistema;
- p es la proporción del tiempo de ejecución que ocupó originalmente la parte que se benefició de la mejora de los recursos.
Además,
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 solo a los casos en los que se soluciona el tamaño del problema. En la práctica, a medida que se dispone de más recursos informáticos, tienden a utilizarse 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 da una evaluación menos pesimista y más realista del desempeño paralelo. [3]
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 de computadora que procesa archivos desde un disco. 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. Por lo tanto, el relativo a la parte que no se beneficiaría de él es. Luego:
Es la ejecución de la parte que se beneficia de la mejora de los recursos que se acelera por el factor después de 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 se convierte en:
El tiempo de ejecución teórico de toda la tarea después de la mejora de los recursos es entonces:
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., cuyos rendimientos
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 aceleración general de la aplicación de la mejora será:
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. Entonces se nos dice que la primera parte no se acelera, entonces s 1 = 1 , mientras que la segunda parte se acelera 5 veces, entonces s 2 = 5 , la tercera parte se acelera 20 veces, entonces s 3 = 20 , y la cuarta parte se acelera 1,6 veces, por lo que s 4 = 1,6 . Al usar la ley de Amdahl, la aceleración general es
Observe cómo la aceleración de 5 veces y 20 veces en la segunda y tercera partes, 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
Por ejemplo, con un programa de serie en dos partes A y B para que T A = 3 s y T B = 1 s ,
- si parte B se hace para correr 5 veces más rápido, es decir s = 5 y P = T B / ( T A + T B ) = 0,25 , entonces
- si parte A se hace para ejecutar 2 veces más rápido, es decir s = 2 y p = T A / ( T A + T B ) = 0,75 , entonces
Por lo tanto, hacer que la parte A corra 2 veces más rápido es mejor que hacer que la parte B corra 5 veces más rápido. El porcentaje de mejora en la velocidad se puede calcular como
- 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 lo hace un 20% más rápido.
Optimización de la parte secuencial de programas paralelos
Si la parte no paralelizable se optimiza en un factor de , luego
De la ley de Amdahl se deduce que la aceleración debida al paralelismo viene dada por
Cuándo , 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.
Cuándo ,
Si , y , luego:
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. Luego
De la ley de Amdahl se deduce que la aceleración debida al paralelismo viene dada por
La derivación anterior está de acuerdo con el análisis de Jakob Jenkov del tiempo de ejecución frente al compromiso de aceleración. [4]
Relación con la ley de rendimientos decrecientes
La ley de Amdahl a menudo se combina 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 que disminuyen monótonamente a medida que se 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, 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 rendimientos decrecientes si al considerar qué tipo de rendimiento se obtiene al agregar más procesadores a una máquina, si uno está ejecutando 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á, ya 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 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 las aplicaciones reales que tienen partes en serie y en paralelo, se requieren técnicas de computación heterogéneas . [5]
Ver también
Referencias
- ^ Rodgers, David P. (junio de 1985). "Mejoras en el diseño de sistemas multiprocesador". ACM SIGARCH Computer Architecture News . Nueva York, NY, EE.UU .: ACM . 13 (3): 225–231 [pág. 226]. doi : 10.1145 / 327070.327215 . ISBN 0-8186-0634-7. ISSN 0163-5964 .
- ^ Bryant, Randal E .; David, O'Hallaron (2016), Computer Systems: A Programmer's Perspective (3 ed.), Pearson Education, p. 58, ISBN 978-1-488-67207-1
- ^ McCool, Michael; Reinders, James; Robison, Arco (2013). Programación paralela estructurada: patrones para una computación eficiente . Elsevier. pag. 61. ISBN 978-0-12-415993-8.
- ^ http://tutorials.jenkov.com/java-concurrency/amdahls-law.html
- ^ Hill, Mark D .; Marty, Michael R. (2008). "Ley de Amdahl en la era multinúcleo". Computadora . 41 (7): 33–38. doi : 10.1109 / MC.2008.209 .
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 AFIPS (30): 483–485. doi : 10.1145 / 1465482.1465560 .
enlaces externos
- "Programación paralela: ¿Cuándo es inaplicable la ley de Amdahl?" . 2011-06-25. Archivado desde el original el 14 de abril de 2013 . Consultado el 26 de junio de 2011 .
- 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 de IBM del proceso de diseño. Menciona trabajo con Ramo-Wooldridge , Aeronutronic y Computer Sciences Corporation
- Ley de Amdahl: no todas las mejoras de rendimiento son iguales (2007)
- "Ley de Amdahl" por Joel F. Klein, Proyecto de demostraciones Wolfram (2007)
- Ley de Amdahl en la era multinúcleo (julio de 2008)
- ¡Qué diablos! Qué es el paralelismo, de todos modos? (Charles Leiserson, mayo de 2008)
- Evaluación de la función Intel Core i7 Turbo Boost , por James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat y Alexandra Fedorova (2009)
- Cálculo de la aceleración de programas paralelos en función del número de hilos , por George Popov, Valeri Mladenov y Nikos Mastorakis (enero de 2010)
- Danny Hillis - Demostrando que la ley de Amdahl es incorrecta, video grabado en octubre de 2016