Tarea 3

Ley de Gustafson

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 procesadores, ya que con mayor número de procesadores se pueden abordar problemas de mayores dimensiones. Por ello, la ley de Gustafson se refiere al crecimiento del volumen de cálculo necesario para resolver un problema. Como veremos a continuación, 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.

La razón de que cierto tipo de problemas adquieran gran volumen de cálculo es la disminución del tamaño de la malla de cálculo o también el aumento la extensión espacio-temporal del problema. Esto hace que el número de puntos aumente de forma cúbica respecto al grado de disminución en la malla, si el problema es tridimensional. Hay muchos problemas en que, además de las tres dimensiones del espacio, también interviene el tiempo, por lo que el aumento del volumen de cálculo es todavía mayor. 

Evidentemente, esto afecta, en general, a la parte paralelizable del problema y no a su parte secuencial, o al menos no en la misma medida. Si suponemos que el número de procesadores crece indefinidamente de la misma forma que las dimensiones del problema tendremos que

1.2

Siendo s y p, respectivamente, las partes secuencial y paralela del problema antes de ser aumentado en relación al número de  procesadores (por ejemplo, incrementando el número de puntos de la malla). Con estas premisas, podremos calcular ahora la ganancia de velocidad para esta nueva situación (la parte paralela del problema ha crecido en la misma proporción que el número de procesadores). Para calcular la ganancia de velocidad supondremos que el tiempo que se tardaría en ejecutar el programa (ya incrementado) en un monoprocesador es:

y en un sistema paralelo sería:

Por tanto, la ganancia en velocidad vendrá dada por:

 1.13

que, teniendo en cuenta la definición de la fracción no paralelizable dada por 1.8, se podrá escribir como

 1.14

En la figura 1.3 puede verse la representación de la ecuación 1.14 para sistemas con diferente número de procesadores. Podría pensarse que hay una aparente contradicción entre las leyes de Amdahl y Gustafson. Esto no es así debido a que las premisas de ambas leyes son distintas: la ley de Amdahl se refiere a procesos con un volumen de cálculo fijo mientras que la ley de Gustafson se refiere a problemas cuyo volumen de cálculo puede aumentar según el número de procesadores (esto se suele denominar escalado del problema). Afortunadamente, esta última situación es más cercana a la realidad.

Fuente:  http://www.infor.uva.es/~bastida/Arquitecturas%20Avanzadas/General.pdf