Previous | Next --- Slide 42 of 51
Back to Lecture Thumbnails
qqkk

1/(0.25+0.75/6) = 2.67 < 5

misaka-10032

Theoretically impossible on any machine: 1/0.25 = 4 < 5

efficiens

The parallelism can be bounded by Amdahl's law: speedup<= 1/(0.25 + (1-0.25/6)) = 2.67 <=5. You are right!

What about the I/O cost and memory stalls? If the original baseline is single threaded, with multicores and multithreads implementation we can actually achieve more than 5x speedup.

lol

I believe Renegade is right, it's possible to have > 4x speedup, but the intent of that question is probably not thinking superlinear effects.

bmperez

@Renegade @lol Amhdahl's law is a theoretical law; it is completely independent of the machine/architecture specific details, and any of the program's details. In this example, the serializable portion of the program is stated to be 25%. This means that 25% of the program will be executed on a single processor, so there will be no opportunity for a superlinear speedup for that part of the program.

You can get a superlinear speedup for the parallelizable portion, but in the limit this effect is irrelevant, because the execution time of the parallelizable portion becomes 0. Thus the maximum speedup remains:

$$\lim_{n \to \infty} \frac{1}{0.25 + \frac{1 - 0.25}{n}} = \frac{1}{0.25} = 4$$