0
$\begingroup$

I read that if $\alpha$ is the fraction of the code that cannot be made parallel then it is desirable that $\alpha < \frac 1 p$ where $p$ is the number of processors.

Why is it the case?

The speed-up is $S(p) = \frac{T_1}{T_p} = \frac{p}{1+(p-1)\alpha}$

$\endgroup$
2
  • $\begingroup$ Write down the formula for the speedup. $\endgroup$
    – user16034
    Oct 28, 2022 at 20:28
  • $\begingroup$ @YvesDaoust done $\endgroup$ Oct 28, 2022 at 21:21

2 Answers 2

1
$\begingroup$

When $\alpha=\dfrac1p$, the speedup is $$\dfrac{p^2}{2p-1}\sim50\%\,p$$ so the processors are well utilized.

$\endgroup$
2
  • $\begingroup$ Why are the processors well utilized if $S(p) = \frac 1 2 p$? $\endgroup$ Oct 29, 2022 at 12:55
  • $\begingroup$ @user1868607: this is arbitrary. $\endgroup$
    – user16034
    Oct 29, 2022 at 13:05
0
$\begingroup$

An example: You have 10 processors, and 1000 items that can be handled by any processor. So you let any processor handle 100 items, and you are finished after 100 time units. With a single processor, that processor would have to do all thousand tasks and take 1000 time units, 10 times more.

Now you have another kind of task y. Y can only be handled by one processor at a time. If you have 100 of these tasks, you give them to 1 processor which takes 100 time units. Meanwhile the other nine processors do 900 of the other task. So you’ll need another ten time units for 100 tasks and finally you finish 1100 tasks after 110 time units. 10 times faster.

Now assume you have 200 tasks y. You give them to one processor which takes 200 units. The other nine processors finish their 1000 tasks in 112 time units and then do nothing. It takes you 200 time units to do 1200 tasks, so your gain went down from 10 to 6.

So as long as task y takes only a fraction of 1/p of all work, you still get the speed up. Above that your speed up goes down.

PS. The "speed-up" formula seems to assume that "non-parallelizable" means all other processors need to be idle. That is rarely the case. Unless told otherwise I would always assume that "parallelizable" code can run simultaneously on the p-1 other processors.

$\endgroup$

Your Answer

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

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