Previous | Next --- Slide 9 of 48
Back to Lecture Thumbnails
kayvonf

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$$