Now, let B denote the fraction of the program that is strictly serial, and consider the following:
- B * T(1) is the time it takes to execute the parts of the program that are inherently sequential.
- T(1) - B * T(1) = (1 - B) * T(1) is the time it takes to execute the parts of the program that are parallelizable, with one processor:
- Then, (1 - B) * T(1) / N is the time it takes to execute these parts with N processors
- So, B * T(1) + (1 - B) * T(1) / N is the total time it takes to execute the whole program with N processors.
Coming back to the formula for the speedup quantity, we have the following:
This formula is actually a form of Amdahl's Law, used to estimate the speedup in a parallel program.