Ley de Gustafson

es una ley en ciencia de la computación que establece que cualquier problema suficientemente grande puede ser eficientemente paralelizado.está muy ligada a la Ley de Amdahl

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

donde P es el número de procesadores, S es el speedup, y 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.

Derivación de la Ley de Gustafson
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 Barisis 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.

Comentarios

Publicar un comentario

Entradas populares