2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\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, 2020 at 22:53
  • $\begingroup$ I agree on that 100%. But how is the speedup linear to the number of cores ? $\endgroup$
    – Skyris
    Sep 23, 2020 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, 2020 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, 2020 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, 2020 at 23:00

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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