Gustafson

Gustafson's Law, also known as Gustafson's law of computation, is a principle in parallel computing that states that any sufficiently large problem can be efficiently parallelized. The law posits that as problem size increases, the amount of work that can be done in parallel also increases, allowing for a nearly constant execution time, even with a larger problem.

Unlike Amdahl's Law, which focuses on the fixed-size problem speedup achievable with parallelization, Gustafson's Law addresses the question of how much larger a problem can be solved in the same amount of time by using more processors. It essentially suggests that programmers tend to set the problem size to use the available resources.

The key difference between Gustafson's Law and Amdahl's Law lies in their assumptions. Amdahl's Law assumes a fixed problem size and calculates the maximum achievable speedup. Gustafson's Law, on the other hand, assumes a fixed execution time and calculates the maximum size of the problem that can be solved.

The formula representing Gustafson's Law is generally expressed as:

S(P) = P - α(P - 1)

Where:

• S(P) is the speedup achieved with P processors.
• P is the number of processors.
• α is the fraction of the code that is serial (cannot be parallelized).

This formula indicates that as the number of processors (P) increases, the achievable speedup is primarily limited by the serial portion of the code (α). However, unlike Amdahl's Law, Gustafson's Law emphasizes that the problem size can be scaled up to effectively utilize the increased processing power.

Gustafson's Law provides a more optimistic view of parallel processing than Amdahl's Law, particularly for applications where problem size can be easily scaled, such as scientific simulations and data analysis. It highlights the potential for solving larger, more complex problems by leveraging the power of parallel computing.