I'm having trouble understanding and solving the problem.

Suppose we have a program which is composed of 3 portions A, B and C and that each portion takes $t_A$, $t_B$ and $t_C$ respectively to run on a single-core CPU.

Assume that $t_A$ < $t_B$ < $t_C$

Assume we parallelize only the portion C of the code and that we run the whole program on a cluster that has up to $N$ cores. The speedup we achieve is linear to the number of cores.

I have to plot the execution time vs the number of cores

What I don't understand is, how can you have a linear speedup ? I've tried playing around with Amdahl's formula to find a way to have a linear speedup to the number of cores. I might be mistaken, but I've realized that this is only possible if the speedup is equal to the number of cores (so I don't understand how you can achieve a linear speedup).

If you could explain this to me, that would be very helpful, thank you.

  • $\begingroup$ I suggest forgetting for a minute about Amdahl's formula. If we parallelize $C$ perfectly, then its running time drops from $t_C$ to $t_C/N$. Therefore the total running time drops from $t_A+t_B+t_C$ to $t_A+t_B+t_C/N$. $\endgroup$ – Yuval Filmus Sep 23 '20 at 22:53
  • $\begingroup$ I agree on that 100%. But how is the speedup linear to the number of cores ? $\endgroup$ – Skyris Sep 23 '20 at 22:56
  • $\begingroup$ What you're suggesting I do, is simply plot $f(N) = t_A + t_B + t_C/N $, right? $\endgroup$ – Skyris Sep 23 '20 at 22:57
  • $\begingroup$ That’s the meaning of linear speedup. You have N cores, the time drops by a factor of N. $\endgroup$ – Yuval Filmus Sep 23 '20 at 22:58
  • $\begingroup$ Yes. Also, notice how Amdahl’s law is just a fancy name for the ratio of two quantities. $\endgroup$ – Yuval Filmus Sep 23 '20 at 23:00

The phrase

The speedup we achieve is linear to the number of cores.

refers only to the C portion of the program. Therefore the running time on $N$ cores is

$$ t_A + t_B + \frac{t_C}{N}. $$

The speedup is

$$ \frac{t_A + t_B + t_C}{t_A + t_B + t_C/N} = \frac{1}{\frac{t_A + t_B + t_C/N}{t_A+t_B+t_C}} = \frac{1}{\frac{t_A+t_B}{t_A+t_B+t_C}+\frac{1}{N} \frac{t_C}{t_A+t_B+t_C}}. $$ This is 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.