Why do Amdahl's law and Gustafson's law give us different speedups, when applied on the same task?

Question

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.

Answer 1

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.

Answer 2

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.