Notice that after this simple parallelization of step 1 of the program, most of the program's execution time is in the second step (the sequential step), even though this step is only half the total work performed.
ggm8
Thus, if we weren't able to find a way to parallelize this sequential step, we would eventually find ourselves unable to make much of a difference to the speedup of the program, since the gray bar would ultimately cause the sequential overhead to outweigh any number of processors we tried to add.
woohoo
Since 1/2 of the program is sequential, due to Amdahl's Law, the maximum speedup is at most 2.
paramecinm
That is why profiling is very important. I've seen many people try to optimize their program but it turns out what they are trying to speedup only takes a small proportion.
kapalani
Another way to think about why speedup is atmost 2 is by considering what is the speedup if we had infinitely many processors i.e. $$ lim_{p \rightarrow \infty} \frac{2n^2}{\frac{n^2}{p}+n^2} = 2$$
Notice that after this simple parallelization of step 1 of the program, most of the program's execution time is in the second step (the sequential step), even though this step is only half the total work performed.
Thus, if we weren't able to find a way to parallelize this sequential step, we would eventually find ourselves unable to make much of a difference to the speedup of the program, since the gray bar would ultimately cause the sequential overhead to outweigh any number of processors we tried to add.
Since 1/2 of the program is sequential, due to Amdahl's Law, the maximum speedup is at most 2.
That is why profiling is very important. I've seen many people try to optimize their program but it turns out what they are trying to speedup only takes a small proportion.
Another way to think about why speedup is atmost 2 is by considering what is the speedup if we had infinitely many processors i.e. $$ lim_{p \rightarrow \infty} \frac{2n^2}{\frac{n^2}{p}+n^2} = 2$$