Ley de Gustafson

LEY DE GUSTAFSON

La ley de Gustafson (también conocida como ley de Gustafson-Barsis) es una ley 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 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 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.

De acuerdo a la fórmula que vimos antes, la mejora de velocidad, o speedup está dada por

Speedup = 1 / (s + p / N)

Donde:

·         s es el tiempo en la parte serial

·         p es el tiempo que toma 1 procesador en la parte paralela del problema, y N es la cantidad de procesadores.

Gustafson notó que para un valor de s entre 0,4% y 0,8% obtenía valores de speedup de 1020 ó 1016, usando un hipercubo con 1024 procesadores.

Si hacen los cálculos verán que eso no se ajusta a lo predicho por la Ley de Amhdal (para s = 0,4% el valor speedup es = 1 / (0,004 + 0,996/1024) = 201,099).

Gustafson se dió cuenta que Amdahl asume que la parte paralelizable p es independiente del valor N, o sea, de la cantidad de procesadores, esto casi nunca se da, de acuerdo a Gustafson, en la práctica el tamaño del problema escala con la cantidad de procesadores.

Gustafson propuso una ley distinta para los problemas en que la parte paralela p’ depende linealmente de la cantidad de procesadores N.

Scaled Speedup = N + (1 - N ) s’