Ley de Gustafson

En arquitectura informática , la ley de Gustafson (o ley de Gustafson-Barsis ^[1] ) proporciona la aceleración en el tiempo de ejecución de una tarea que teóricamente se beneficia de la computación paralela , utilizando una ejecución hipotética de la tarea en una máquina de un solo núcleo como línea de base. En otras palabras, es la "desaceleración" teórica de una tarea ya paralelizada si se ejecuta en una máquina en serie. Recibe su nombre en honor al científico informático John L. Gustafson y su colega Edwin H. Barsis, y se presentó en el artículo Reevaluating Amdahl's Law en 1988. ^[2]

Gustafson estimó la aceleración de un programa obtenida mediante el uso de computación paralela de la siguiente manera: ${\estilo de visualización S}$

$${\displaystyle {\begin{aligned}S&=s+p\times N\\&=s+(1-s)\times N\\&=N+(1-N)\times s\end{aligned}}}$$

dónde

• ${\estilo de visualización S}$es la aceleración teórica del programa con paralelismo (aceleración escalada ^[2] );
• ${\estilo de visualización N}$es el número de procesadores;
• ${\estilo de visualización s}$y son las fracciones de tiempo empleadas en la ejecución de las partes seriales y las partes paralelas del programa, respectivamente, en el sistema paralelo , donde .${\estilo de visualización p}$${\estilo de visualización s+p=1}$

Alternativamente, se puede expresar utilizando : ${\estilo de visualización S}$${\estilo de visualización p}$

$${\displaystyle {\begin{aligned}S&=(1-p)+p\times N\\&=1+(N-1)\times p\end{aligned}}}$$

La ley de Gustafson aborda las deficiencias de la ley de Amdahl , que se basa en el supuesto de un tamaño fijo del problema , es decir, de una carga de trabajo de ejecución que no cambia con respecto a la mejora de los recursos. La ley de Gustafson, en cambio, propone que los programadores tienden a aumentar el tamaño de los problemas para aprovechar al máximo la potencia de cálculo que queda disponible a medida que mejoran los recursos. ^[2]

Gustafson y sus colegas observaron además, a partir de sus cargas de trabajo, que el tiempo para la parte serial normalmente no crece a medida que el problema y la escala del sistema, ^[2] es decir, es fijo. Esto da un modelo lineal entre el número de procesadores y la aceleración con pendiente , como se muestra en la figura anterior (que utiliza diferentes notaciones: para y para ). Además, escala linealmente con en lugar de exponencialmente en la Ley de Amdahl. ^[2] Con estas observaciones, Gustafson "esperaba extender [su] éxito [en computación paralela] a una gama más amplia de aplicaciones e incluso valores mayores para ". ^[2]${\estilo de visualización s}$${\estilo de visualización N}$${\estilo de visualización S}$${\estilo de visualización 1-s}$${\estilo de visualización P}$${\estilo de visualización N}$${\estilo de visualización a}$${\estilo de visualización s}$${\estilo de visualización S}$${\estilo de visualización s}$${\estilo de visualización N}$

El impacto de la ley de Gustafson fue cambiar ^{[ cita requerida ]} los objetivos de investigación para seleccionar o reformular problemas de modo que fuera posible resolver un problema más grande en la misma cantidad de tiempo. En cierto modo, la ley redefine la eficiencia, debido a la posibilidad de que las limitaciones impuestas por la parte secuencial de un programa se puedan contrarrestar aumentando la cantidad total de cómputo.

El tiempo de ejecución de un programa que se ejecuta en un sistema paralelo se puede dividir en dos partes:

• una parte que no se beneficia del aumento del número de procesadores (parte serie);
• una parte que se beneficia del creciente número de procesadores (parte paralela).

Ejemplo. Un programa informático que procesa archivos del 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í.

Sin pérdida de generalidad, sea . el tiempo total de ejecución en el sistema paralelo . Denote el tiempo en serie como y el tiempo en paralelo como , donde . Denote el número de procesadores como . ${\estilo de visualización T=1}$${\estilo de visualización s}$${\estilo de visualización p}$${\estilo de visualización s+p=1}$${\estilo de visualización N}$

Hipotéticamente, al ejecutar el programa en un sistema serial (solo un procesador), la parte serial aún demora , mientras que la parte paralela ahora demora . El tiempo de ejecución en el sistema serial es: ${\estilo de visualización s}$${\estilo de visualización Np}$

$${\displaystyle T'=s+Np}$$ Usando como base, la aceleración para el sistema paralelo es: ${\estilo de visualización T'}$

$${\displaystyle S={\frac {T'}{T}}={\frac {s+Np}{s+p}}={\frac {s+Np}{1}}=s+Np}$$

Sustituyendo o , se pueden derivar varias formas de la sección anterior. ${\displaystyle p=1-s}$${\estilo de visualización s=1-p}$

La ley de Amdahl presupone que los requisitos de computación se mantendrán invariables si se aumenta la capacidad de procesamiento. En otras palabras, un análisis de los mismos datos llevará menos tiempo si se dispone de más capacidad de procesamiento.

Gustafson, por su parte, sostiene que una mayor potencia de cálculo hará que los datos se analicen de forma más cuidadosa y completa: píxel por píxel o unidad por unidad, en lugar de a mayor escala. Si bien no habría sido posible o práctico simular el impacto de una detonación nuclear en cada edificio, coche y sus contenidos (incluidos los muebles, la resistencia de la estructura, etc.) porque un cálculo de ese tipo habría llevado más tiempo del que había disponible para proporcionar una respuesta, el aumento de la potencia de cálculo impulsará a los investigadores a añadir más datos para simular de forma más completa más variables, lo que dará un resultado más preciso.

La Ley de Amdahl revela una limitación, por ejemplo, en la capacidad de múltiples núcleos para reducir el tiempo que tarda un ordenador en arrancar su sistema operativo y estar listo para su uso. Suponiendo que el proceso de arranque fuera en su mayor parte paralelo, cuadruplicar la potencia de cálculo en un sistema que tardaba un minuto en cargarse podría reducir el tiempo de arranque a poco más de quince segundos. Pero una paralelización cada vez mayor acabaría por no conseguir que el arranque fuese más rápido, si alguna parte del proceso de arranque fuese inherentemente secuencial.

La ley de Gustafson sostiene que un aumento cuádruple de la potencia de cálculo conduciría, en cambio, a un aumento similar de las expectativas sobre lo que el sistema será capaz de hacer. Si el tiempo de carga de un minuto es aceptable para la mayoría de los usuarios, entonces ese es un punto de partida para aumentar las características y funciones del sistema. El tiempo que se tarda en arrancar el sistema operativo será el mismo, es decir, un minuto, pero el nuevo sistema incluiría más funciones gráficas o de fácil manejo.

Algunos problemas no requieren conjuntos de datos fundamentalmente mayores. Por ejemplo, el procesamiento de un punto de datos por ciudadano del mundo aumenta solo un pequeño porcentaje al año. El punto principal de la ley de Gustafson es que es poco probable que esos problemas sean las aplicaciones más fructíferas del paralelismo.

A los algoritmos con tiempos de ejecución no lineales puede resultarles difícil aprovechar el paralelismo "expuesto" por la ley de Gustafson. Snyder ^[3] señala que un algoritmo significa que duplicar la concurrencia da como resultado solo un aumento de alrededor del 26% en el tamaño del problema. Por lo tanto, si bien puede ser posible ocupar una gran concurrencia, hacerlo puede traer pocas ventajas sobre la solución original, menos concurrente; sin embargo, en la práctica, aún se han producido mejoras considerables. $Estilo de visualización O(N^{3})}$

Hill y Marty ^[4] también destacan que aún se necesitan métodos para acelerar la ejecución secuencial, incluso para máquinas multinúcleo. Señalan que los métodos localmente ineficientes pueden ser globalmente eficientes cuando reducen la fase secuencial. Además, Woo y Lee ^[5] estudiaron la implicación de la energía y la potencia en los futuros procesadores multinúcleo basándose en la ley de Amdahl, mostrando que un procesador multinúcleo asimétrico puede lograr la mejor eficiencia energética posible activando un número óptimo de núcleos dado que se conoce la cantidad de paralelismo antes de la ejecución.

Al-hayanni, Rafiev et al. han desarrollado nuevos modelos de aceleración y consumo de energía basados ​​en una representación general de la heterogeneidad del núcleo, 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. ^{[6] [7]}

• Paralelismo escalable
• Ley de Parkinson
• Paradoja de Jevons