Ley de Gustafson

La ley de Gustafson (también conocida como ley de Gustafson-Barsis)^[1] es una ley en ciencia de la computación que establece que cualquier problema suficientemente grande puede ser eficientemente paralelizado. La ley de Gustafson está muy ligada a la ley de Amdahl, que pone límite a la mejora 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 ofrece un nuevo punto de vista y así una visión positiva de las ventajas del procesamiento paralelo. El estadounidense John L. Gustafson enunció por primera vez la ley que lleva su nombre en 1988.

$S(P)=P-\alpha \cdot (P-1)$

donde P es el número de procesadores, S es el speedup, y $\alpha$ la parte no paralelizable del proceso.

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. 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.

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. 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.

Derivación de la ley de Gustafson editar

El tiempo de ejecución de un programa en una computadora paralela es descompuesto en:

$(a+b)$

donde $a$ es el tiempo secuencial y $b$ es el tiempo paralelo, en cualquiera de los P procesadores.

La suposición clave de Gustafson y Barsis es que la cantidad total de trabajo a realizar en paralelo varía linealmente con el número de procesadores. La implicación práctica es que un procesador capaz de procesar más de la carga de procesamiento asignada a este, puede ejecutar en paralelo otras tareas generalmente similares. Esto implica que b, el tiempo de procesamiento en paralelo por proceso, debe ser fijo mientras P varía. El tiempo correspondiente para el procesamiento secuencial es:

$a+P\cdot b.$

El speedup (aceleramiento) es, en concordancia:

$(a+P\cdot b)/(a+b).$

Definiendo

$\alpha =a/(a+b)$

como la fracción secuencial del tiempo de ejecución en paralelo, obtenemos

$S(P)=\alpha +P\cdot (1-\alpha )=P-\alpha \cdot (P-1).$

Por consiguiente, si $\alpha$ es pequeño, el aceleramiento es aproximadamente P, como es deseado. Incluso se puede dar el caso en que $\alpha$ disminuya mientras P junto con el tamaño del problema aumente; si esto se cumple, S se aproxima a P monótonamente con el crecimiento de P.

De esta forma, la Ley de Gustafson aparenta rescatar el procesamiento en paralelo de la Ley de Amdahl. Está basada en la idea de que si el tamaño de un problema puede crecer monotónicamente con P, entonces la fracción secuencial de la carga de trabajo no representará la parte dominante de dicha carga. Esto es posible haciendo la mayoría de las asignaciones de trabajo contenibles dentro del ámbito de procesamiento de un solo procesador; de aquí que un solo procesador pueda servir para múltiples asignaciones, mientras que una asignación no debe expandirse a más de un procesador. Esta es también la regla para proyectos en sitios de trabajo, teniendo muchos proyectos por sitio, pero solo un sitio por proyecto.

Metáfora de la conducción editar

La ley de Amdahl aproximadamente sugiere:

Supongamos que un auto está viajando entre dos ciudades que se encuentran a 60 millas de distancia, y ya ha estado una hora viajando la mitad de la distancia a 30 millas por hora. Sin importar cuán rápido viaje la mitad restante es imposible alcanzar una velocidad promedio de 90 millas por hora antes de terminar el recorrido. Debido a que ya le ha tomado 1 hora y ha de recorrer 60 millas; aunque viaje infinitamente rápido solo alcanzaría una velocidad promedio de 60 millas por hora.

La ley de Gustafson aproximadamente enuncia:

Supongamos que un auto ha estado viajando algún tiempo a 90 millas por hora. Teniendo distancia y tiempo suficiente para viajar, la velocidad promedio del auto podría alcanzar eventualmente las 90 millas por hora, sin importar cuánto o a qué velocidad haya viajado. Por ejemplo, si el auto demoró una hora viajando a 30 millas por hora, podría alcanzar las 90 millas por hora de velocidad promedio conduciendo a 120 millas por hora durante 2 horas, o a 150 millas por hora durante una hora, etc.

Aplicaciones editar

Aplicaciones en la investigación editar

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.

Aplicaciones cotidianas en sistemas computacionales editar

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.

Limitaciones editar

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 del paralelismo.

Los algoritmos no lineales dificultan la utilización de las ventajas del paralelismo expuestas por la ley de Gustafson. Snyder^[2] muestra que un algoritmo O(N³) 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 puede traer una relativamente pequeña ventaja sobre la solución original; sin embargo en la práctica han ocurrido mejoras considerables.

Hill and Marty^[3] 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^[4] 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.

Véase también editar

Ley de Amdahl

Referencias editar

↑ Reevaluating Amdahl's Law, John L. Gustafson, Communications of the ACM, volumen 31 (mayo 1988)
↑ Type Architectures, Shared Memory, and The Corrolary of Modest Potential, Lawrence Snyder, Ann. Rev. Comput. Sci. 1986. 1:289-317.
↑ Amdahl's Law in the Multicore Era, Mark D. Hill and Michael R. Marty, IEEE Computer, vol. 41, pp. 33–38, July 2008. Also UW CS-TR-2007-1593, April 2007.
↑ Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era Archivado el 10 de octubre de 2012 en Wayback Machine., Dong Hyuk Woo and Hsien-Hsin S. Lee, IEEE Computer, vol. 41, No. 12, pp.24-31, December 2008.

Datos: Q1276790

[reevaluating-amdahl-1] Reevaluating Amdahl's Law, John L. Gustafson, Communications of the ACM, volumen 31 (mayo 1988)

[Snyder1986-2] Type Architectures, Shared Memory, and The Corrolary of Modest Potential, Lawrence Snyder, Ann. Rev. Comput. Sci. 1986. 1:289-317.

[Hill&Marty2008-3] Amdahl's Law in the Multicore Era, Mark D. Hill and Michael R. Marty, IEEE Computer, vol. 41, pp. 33–38, July 2008. Also UW CS-TR-2007-1593, April 2007.

[Woo&Lee2008-4] Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era Archivado el 10 de octubre de 2012 en Wayback Machine., Dong Hyuk Woo and Hsien-Hsin S. Lee, IEEE Computer, vol. 41, No. 12, pp.24-31, December 2008.

[1]

[2]

[3]

[4]