Question

If a program has 5% code that is fundamentally sequential, what is the maximal speed-up if you parallelize it with unlimited number of parallel processors?

1) 5
2) 10
3) 20
4) 40

Answer 1

According to Amdahl's Law, the maximum speed-up with 5% sequential code and unlimited processors is 20.

Step-by-step explanation:

If a program has 5% code that is fundamentally sequential, then according to Amdahl's Law, the maximum speed-up achievable by parallelizing the program is determined by the amount of code that cannot be parallelized. Given that 5% of the program must remain sequential, 95% can be parallelized.

Amdahl's Law gives us the following formula for maximum speed-up: Speed-up = 1 / (S + (1-S)/P), where S represents the fraction of the program that is sequential (0.05 in this case for 5%), and P is the number of processors.

In an ideal case with an unlimited number of processors, P approaches infinity, making (1-S)/P approach 0.

Thus, the maximum speed-up approaches 1/S, which would be 1/0.05 or 20.