1
$\begingroup$

I am given a task, where exactly 50% of the work is parallelizable. When applying Amdahl's law to calculate speedup when using 2 processing units instead of one, I get a different result than the one I get when calculating the same speedup using Gustafson's law. I don't understand why is that.

$\endgroup$
6
  • $\begingroup$ What are answers in both cases? $\endgroup$
    – Vladislav
    Mar 20 '20 at 23:31
  • $\begingroup$ With amdahl's law I get a speedup of 1.33 and with gustafson's it's 1.5 $\endgroup$
    – AlexH
    Mar 21 '20 at 0:38
  • $\begingroup$ with 4 processing units it's an even bigger difference, with amdahl's it's 1.6 and with gustafson's it's 2.5 $\endgroup$
    – AlexH
    Mar 21 '20 at 0:39
  • $\begingroup$ Something is wrong then - if only 50% of the work is parallelizable, an infinite number of processors cannot get the time below 50% of the original. $\endgroup$
    – gnasher729
    Mar 21 '20 at 15:20
  • $\begingroup$ No, there is nothing wrong. The speedup (for Amdahl) and the scaled speedups (i.e., the speedup when the problem is scaled for Gustafson) are indeed correct. The scaled speedup goes down linearly (with slope -$p$) as $s$ grows. This is much less pessimistic than in the fixed-size speedup case, where Amdahl's law suggests that the speedup goes down like 1/$f$ as $f$ grows. $\endgroup$ Mar 21 '20 at 18:25
5
$\begingroup$

The reason is that Amdahl's law and Gustafson's law refer to two very different situations.

In particular, Amdahl's law applies to those cases in which the problem size is fixed, e.g. you need to process a static dataset or an image of given dimensions. The law treats the problem size as being a constant (size constrained model), and clearly shows how the execution time decreases as the number of processors increases. This law can be applied to any system, not just to parallel systems; it is a very general statement about any improvement in a system, i.e., no matter how much one improves one part of a system, the improvement in the overall performance is bounded by $1/f$, where $f$ is the fraction of the original time spent in parts of the system one does not improve. This model, fixing the amount of data per processor, usually provides the highest efficiency possible (this is commonly referred to as strong scaling).

On the other hand, rather than assuming that the problem size is fixed, it is just as valid to assume that the parallel execution time is fixed. This is exactly what the Gustafson's law does: as the parallel system size is increased (i.e. the number of processors $p$ is increased), the problem size is increased to maintain constant parallel execution time (weak scaling). Therefore, this is a time constrained model. So, the important difference is that the scaled speedup of Gustafson starts with a big problem on a big ($p$ processors) machine and looks back toward the one-processor case and asks how long it would have taken to execute, whilst Amdahl's law starts with a problem on the one-processor machine, and asks how long it might take on a many-processor parallel machine. Gustafson simply noted that there were lots of problems that seemed to run well on lots of processors: they computed for a great deal of time $(1-s)$ using all the processors, and not all that long $(s)$ in a serial fashion. So he derived the scaled speedup formula to help explain that.

Does this contradict Amdahl's law? No, of course. Amdahl works when you are given a fixed size input and you want to understand how fast you can process in parallel that input. Gustafson works when you can increase the problem size and you want to solve larger problems in the same amount of time. For instance scientist are actually interested to solving larger instances of problems, or want to increase the complexity of a model to gain better accuracy.

$\endgroup$
1
  • $\begingroup$ Thank you very much! :) $\endgroup$
    – AlexH
    Mar 21 '20 at 14:58
0
$\begingroup$

It seems that the "50%" in Gustafson's law means that 50% of the time, tasks are being run in parallel. For example with 100 tasks and four processors, running 20 tasks on a single processor in 20 time units, then 80 tasks running on four processors also in 20 time units, gets called "50%" but it means "the processors are running parallelizable tasks 50% of the time". Amdahl's law would call the exact same situation "80% of tasks are parallelizable".

So it seems that someone really messed up what they are calling things.

$\endgroup$
1
  • $\begingroup$ See both my answer and my comments to your comment to the OP question. You need to fully understand the difference between the $f$ in Amdahl and the $s$ in Gustafson. Then, you may easily understand why Gustafson scaled speedup is, in general, better than Amdahl speedup. $\endgroup$ Mar 21 '20 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.