Wikipedia says about Gustafsons's law that:

It may even be the case that $\alpha$ diminishes as $P$ (together with the problem size) increases.

I'm not understanding how $\alpha$ can ever change given it's definition:

$$ \alpha= a / (a + b)$$

I thought that $a$ and $b$ are constants independent of the problem size.

What am I missing?


First I suggest you to read the original article "Reevaluating Amdahl's Law" (CACM'1988) by John L. Gustafson when you have difficulty with the wiki article. Notice that I will use the notations from the original article: $s$ for serial time; $p$ for parallel time; $N$ for number of processors.

In the original article, the author mentioned that Amdahl's Law is based on an unrealistic assumption that "$p$ is independent of $N$", where $p$ is the amount of time spent (by a serial processor) on parts of the program that can be done in parallel.

Then, the author pointed out two key observations:

  1. In practice, the problem size scales with the number of processors.
  2. As a first approximation, we have found that it is the parallel or vector part of a program that scales with the problem size.

More explicitly, times for vector startup, program loading, serial bottlenecks and I/O that make up the $s$ (serial) component of the run do not grow with problem size; however, the amount of work that can be done in parallel varies linearly with the number of processors.

As a result, as $N$ (the number of processors; together with the problem size) increases, the portion of parallel time ($p$) increases according to the two observations given above, and the portion ($\alpha$) of serial time ($s$) diminishes (in most/common cases).

  • 2
    $\begingroup$ In other words, $a$ and $b$ are not constants, but sequences $a_n$ and $b_n$ and hopefully $a_n \in o(b_n)$. $\endgroup$
    – Raphael
    Feb 5 '15 at 16:11

The easiest way to understand it is to realize that the Percentage of serial work is a function of the problem size - it's not a simple constant value independent of problem size.

If the beginning of a parallel job requires $1000$ instructions of setup no matter what the problem size, yet we can keep feeding it larger problem instances, then the percentage of serial work effectively goes to zero.

Imagine that the amount of serial work is $\mathcal{O}(n \log n)$, but the size of parallelizable work is $\mathcal{O}(n \times n)$. This might match up with getting ready to process an $n \times n$ matrix on $n$ processors. Eventually, the amount of serial work is negligible compared to the parallelizable work.

I have gone through the process of deriving Gustafson's law from Amdahl's law. It's just an algebraic re-arrangement of the original statement of Amdahl's law.


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.