Solución:
Ley de amdahl
Suponga que tiene un código secuencial y que una fracción f
de su cálculo se paraleliza y se ejecuta en N
unidades de procesamiento trabajando en paralelo, mientras que la fracción restante 1-f
no se puede mejorar, es decir, no se puede paralelizar. La ley de Amdahl establece que la aceleración lograda por la paralelización es
Ley de gustafson
El punto de vista de Amdahl se centra en un problema de cálculo de tamaño fijo, ya que trata con un código que requiere una cantidad fija de tiempo de cálculo secuencial. La objeción de Gustafson es que las máquinas masivamente paralelas permiten cálculos que antes eran inviables, ya que permiten cálculos en conjuntos de datos muy grandes en una cantidad fija de tiempo. En otras palabras, una plataforma paralela hace más que acelerar la ejecución de un código: permite lidiar con problemas mayores.
Suponga que tiene una aplicación que tarda un tiempo ts
para ser ejecutado en N
unidades de procesamiento. De ese tiempo de computación, una fracción (1-f)
debe ejecutarse secuencialmente. En consecuencia, esta aplicación se ejecutaría en una máquina completamente secuencial en un tiempo t
igual a
Si aumentamos el tamaño del problema, podemos aumentar el número de unidades de procesamiento para mantener la fracción de tiempo que el código se ejecuta en paralelo igual a f·ts
. En este caso, el tiempo de ejecución secuencial aumenta con N
que ahora se convierte en una medida del tamaño del problema. La aceleración se convierte en
La eficiencia sería entonces
de modo que la eficiencia tiende af para aumentar N
. La trampa de estas evaluaciones de eficiencia y aceleración bastante optimistas está relacionada con el hecho de que, a medida que aumenta el tamaño del problema, los costos de comunicación aumentarán, pero los aumentos en los costos de comunicación no se tienen en cuenta en la ley de Gustafson.
Referencias
G. Barlas, programación multinúcleo y GPU: un enfoque integrado, Morgan Kaufmann
MD Hill, MR Marty, Ley de Amdahl en la era multinúcleo, Computer, vol. 41, n. 7, págs. 33-38, julio de 2008.
GPGPU
Hay discusiones interesantes sobre la ley de Amdahl aplicada a las unidades de procesamiento de gráficos de propósito general, ver
Ley de Amdahl y GPU Ley de Amdahl para GPU ¿La ley de Amdahl también se acepta para GPU?
Estamos viendo el mismo problema desde diferentes perspectivas. La ley de Amdahl dice que si tiene, digamos, 100 CPU más, ¿cuánto más rápido puede resolver el mismo problema?
La ley de Gustafson dice que si una computadora en paralelo con 100 CPU puede resolver este problema en 30 minutos, ¿cuánto tiempo le tomaría a una computadora con solo UNA CPU de este tipo resolver el mismo problema?
La ley de Gustafson refleja mejor las situaciones. Por ejemplo, no podemos usar una PC de 20 años para jugar a la mayoría de los videojuegos de hoy porque son demasiado lentos.
Ley de amdahl
Generalmente, si una fracción f de un trabajo es imposible de dividir en partes paralelas, el conjunto solo se puede obtener 1 / f veces más rápido en paralelo. Esa es la ley de Amdahl.
Ley de gustafson
Generalmente, para p participantes, y una fracción f no paralelizable, el conjunto puede obtener p + (1 − p) f veces más rápido. Esa es la ley de Gustafson