We have seen the problems that can arise when the workload is imbalanced in the first programming assignment. In particular, the reason that the speedup from naively adding additional threads to generate the Mandelbrot fractal was not linear was precisely because the workload was unevenly distributed amongst the threads. Once we fixed the issue by distributing work in an interleaved fashion as opposed to a blocked fashion, the workload was balanced, and therefore the speedup was effectively linear.

I'm trying to rederive the S = 0.2 that's written on this slide. What would be p be in this case? 4/5 since 4/5 of the program is not serial? What would the speedup factor s be in this case? 4?

By Amdahl's law, the speedup here is bound by 2.5. To derive this, we compute 1 / (s + (1-s)/p) = 1 / (0.2 + 0.8/4) = 1 / 0.4 = 2.5. So despite having four processors, our max speedup is 2.5x because 1/5 of the work is sequential. If we had 8 processors, the max speedup becomes around 3.33x. As p approaches infinity, the max speedup approaches 1 / 0.2 = 5. So no matter how many processors we throw at this program, we will never get a speedup higher than 5x.