Ley de Gustafson
| ||||||
Ley de Gustafson. También conocida como Ley de Gustafson-Barsis, es una ley en ciencia de la computación que establece que cualquier problema suficientemente grande puede ser eficientemente paralelizado, ofrece un nuevo punto de vista y así una visión positiva de las ventajas del procesamiento paralelo. John L. Gustafson enunció por primera vez la ley que lleva su nombre en 1988.
Precedente
La ley de Gustafson está muy ligada a la Ley de Amdahl, que pone límite a la aceleración que se puede obtener gracias a la paralelización, dado un conjunto de datos de tamaño fijo, ofreciendo así una visión pesimista del procesamiento paralelo. Por el contrario la ley de Gustafson aborda las limitaciones de la Ley de Amdahl, la cual no escala la disponibilidad del poder de cómputo a medida que el número de máquinas aumenta.
Propuesta
La ley de Gustafson propone que los programadores establezcan el tamaño de los problemas para utilizar el equipamiento disponible en su solución en un tiempo práctico. Por consiguiente, si existe equipamiento más rápido disponible, mayores problemas se pondrán resolver en el mismo tiempo.
Impacto
El impacto de la ley de Gustafson fue el cambio de dirección de los objetivos de investigación hacia la selección o reformulación de problemas a fin de que fuera posible la solución de mayores problemas en el mismo intervalo de tiempo. En particular la ley redefine la eficiencia como una necesidad para minimizar la parte secuencial de un programa, incluso si esto incrementa la cantidad total de cálculos.
Formula
S ( P ) = P - α . ( P - 1 )
donde P es el número de procesadores, S es el speedup (aceleración), y α la parte no paralelizable del proceso. La Ley de Amdahl se basa en una carga de trabajo o tamaño de entrada prefijados. Esto implica que la parte secuencial de un programa no cambia con respecto al número de procesadores de la máquina, sin embargo, la parte paralelizable es uniformemente distribuida en el número de procesadores
Aplicaciones
La ley de Amdahl presupone que los requerimientos de cómputo se mantendrán invariables, dado el incremento del poder de procesamiento. En otras palabras, el análisis de la misma cantidad de datos toma menos tiempo dado más poder de cómputo. Gustafson, por otra parte, argumenta que más poder de cómputo causará que los datos sean analizados más profunda y cuidadosamente: pixel por pixel o unidad por unidad, en lugar de ser analizados a gran escala. Donde no sería posible o práctico simular el impacto de una detonación nuclear en todas las construcciones, autos y sus contenidos (incluyendo muebles, accesorios, etc.) debido a que tales cálculos tomarían más tiempo del disponible para dar una respuesta, el incremento del poder de cómputo incita a los investigadores a añadir más datos para simular más variables, brindado resultados más precisos.
La Ley de Amdahl presenta una limitación en, por ejemplo, la capacidad de los núcleos múltiples de reducir el tiempo que toma a una computadora iniciar su sistema operativo y estar lista para el uso. Asumiendo que el proceso de iniciado fuera mayormente paralelizado, cuadruplicando el poder de cómputo en un sistema que toma un minuto para cargar, podría cargar en solo 15 segundos. Pero mayor paralelización fallaría eventualmente en hacer el inicio más rápido, si alguna parte del proceso de inicio fuera esencialmente secuencial.
La ley de Gustafson argumenta que un aumento cuádruple del poder de cómputo conllevaría a un incremento similar en las capacidades del sistema. Si un minuto de tiempo de inicio de un sistema es aceptable para la mayoría de los usuarios, entonces esto es un punto de inicio desde donde incrementar las funcionalidades y características del sistema. El tiempo de inicio del sistema operativo se mantendrá igual, o sea un minuto, pero el nuevo sistema incluirá mejores características gráficas y funcionalidades para el usuario.
La ley de Gustafson (1988) viene a compensar el pesimismo dejado por la Ley de Amdahl. Ésta se refería a problemas con volumen de cálculo fijo en que se aumenta el número de procesadores. Sin embargo, en la práctica, el volumen del problema no es independiente del número de rocesadores, ya que con mayor número de procesadores se pueden abordar problemas de mayores dimensiones. Por ello, la ley de Gustafson se refiere al recimiento del volumen de cálculo necesario para resolver un problema. En la mayoría de los casos, cuando el volumen del problema crece, lo hace sólo en su parte paralela, no en su parte secuencial. Ello hace que el cuello de botella secuencial tienda a cero cuando el volumen del problema aumenta.
Limitaciones
Algunos problemas no tienen fundamentalmente grandes cantidades de datos. Por ejemplo, procesar un dato por ciudadano del mundo crece un bajo por ciento anualmente. El punto principal de la ley de Gustafson es que tales problemas no son los que más pueden explotar las ventajas de la Programación paralela paralelismo. Los algoritmos no lineales dificultan la utilización de las ventajas del paralelismo expuestas por la ley de Gustafson. Snyder muestra que un algoritmo O(N3) mediante la duplicación de la concurrencia solo permite el aumento de un 26% de la cantidad de datos. Por consiguiente, mientras sea posible ocupar grandemente la concurrencia, hacerlo pude traer una relativamente pequeña ventaja sobre la solución original; sin embargo en la práctica han ocurrido mejoras considerables.
Hill and Marty enfatiza además que métodos de acelerar la ejecución secuencial todavía son necesarios, incluso para máquinas con núcleos múltiples. Ellos señalan que métodos localmente ineficientes pueden ser globalmente eficientes cuando reducen la fase secuencial. Adicionalmente, Woo and Lee estudia la implicación de energía y poder en procesadores futuros de múltiples núcleos basados en la Ley de Amdahl, mostrando que un procesador multinúcleo asimétrico puede alcanzar la mayor eficiencia energética posible mediante la activación del número óptimo de núcleos dado que la cantidad de paralelismo es conocida antes de la ejecución.
