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?
1 Answer
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$– jokerCommented Apr 29, 2014 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$ Commented Apr 29, 2014 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$– RaphaelCommented Apr 30, 2014 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$– user4577Commented Apr 30, 2014 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$– user4577Commented Apr 30, 2014 at 14:32