# Linear Speedup and Amdahl's law

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.

• 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$. – Yuval Filmus Sep 23 '20 at 22:53
• I agree on that 100%. But how is the speedup linear to the number of cores ? – Skyris Sep 23 '20 at 22:56
• What you're suggesting I do, is simply plot $f(N) = t_A + t_B + t_C/N$, right? – Skyris Sep 23 '20 at 22:57
• That’s the meaning of linear speedup. You have N cores, the time drops by a factor of N. – Yuval Filmus Sep 23 '20 at 22:58
• Yes. Also, notice how Amdahl’s law is just a fancy name for the ratio of two quantities. – 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.