I know after some reading Amdahl law is a embarrassingly parallel programming model. Embarrassingly parallel means there is no communication and tasks work independently. Am I to assume a parallel and a non parallel aspect of the program is embarrassingly parallel? If not, what makes it embarrassingly parallel?


Your terminology is incorrect. Amdahl's law is a way of estimating performance of a parallel program. It is not a "programming model". Amdahl's law says that if there is a computation, part of which is $M$ sequential (not parallelizable) instructions and part of which is $N$ instructions which could be parallelized, and you have $P$ processors, then the shortest computation time you can hope for is: $$ M + \frac{N}{P}. $$

So the speedup with $P$ processors is: $$ \frac{M+N}{M+\frac{N}{P}}. $$

Which, in the limit as $P \gg N$ goes to $$ \frac{M+N}{M} = 1 + \frac{N}{M}. $$

The takeaway message is simply that you shouldn't fool yourself. $N/M$ is much more important than $N/P$.

  • $\begingroup$ Why does this person say embarrassingly parallel task? cs.stackexchange.com/questions/24063/calculating-speed-up $\endgroup$
    – joker
    Apr 29 '14 at 15:29
  • $\begingroup$ What person? @YuvalFilmus? Presumably because none of us, including him, could understand what you were trying to ask. (Which is why we closed that question.) $\endgroup$ Apr 29 '14 at 15:58
  • 1
    $\begingroup$ "Estimating" is quite strong; at best, it gives an upper bound on performance increase by parallelisation and it's not very good at that. (For instance, the common case does completely disregard growing inputs which we usually consider in algorithmics. That a fixed computation can not be sped up arbitrarily using multiple processors is not very suprising, nor deep.) $\endgroup$
    – Raphael
    Apr 30 '14 at 11:53
  • $\begingroup$ I would have preferred using something like "units of work" rather than "instructions". (Also the formula can be used for estimating with other partial improvements, e.g., X feature reduces energy consumption of Y aspect by P factor and unmodified Y consumes N percent of the energy.) $\endgroup$ Apr 30 '14 at 14:20
  • $\begingroup$ @Raphael For such a simple calculation, it provides a useful estimate. The problem is not in the formula itself but in the simple model of parallel and non-parallel. It certainly works against naive intuitions (though common intuition for fractional improvements may not be as weak as intuitions dealing with probability and statistics, these intuitions do tend to be faulty). $\endgroup$ Apr 30 '14 at 14:32

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.