Amdahl's Law vs. Gustafson

Attribute	Amdahl's Law	Gustafson
Originator	Gene Amdahl	John L. Gustafson
Focus	Limitations of parallel computing	Scalability of parallel computing
Formula	Speedup = 1 / [(1 - P) + (P / N)]	Speedup = S + (P * (N - S))
Parallelism	Emphasizes limiting factors of parallelism	Emphasizes increasing parallelism
Application	Used to analyze performance improvements in parallel computing	Used to analyze scalability of parallel algorithms

Introduction

Amdahl's Law and Gustafson's Law are two important concepts in the field of parallel computing. Both laws provide insights into how the speedup of a parallel program is affected by various factors. While Amdahl's Law focuses on the impact of serial portions of a program, Gustafson's Law takes into account the scalability of parallel programs. In this article, we will compare and contrast the attributes of Amdahl's Law and Gustafson's Law.

Amdahl's Law

Amdahl's Law, formulated by computer architect Gene Amdahl in 1967, provides a theoretical limit on the speedup that can be achieved by parallelizing a program. The law states that the speedup of a program is limited by the fraction of the program that must be executed sequentially. In other words, even if a program is parallelized to run faster on multiple processors, there will always be a portion of the program that cannot be parallelized and will limit the overall speedup.

One of the key attributes of Amdahl's Law is the notion of a fixed problem size. The law assumes that the problem size remains constant as the number of processors increases. This assumption may not always hold true in real-world scenarios where the problem size can vary. Additionally, Amdahl's Law is often criticized for oversimplifying the complexities of parallel computing by focusing solely on the impact of serial portions of a program.

• Amdahl's Law limits the speedup of a program based on the fraction of the program that must be executed sequentially.
• The law assumes a fixed problem size, which may not always hold true in practice.
• Amdahl's Law oversimplifies the complexities of parallel computing by focusing on serial portions of a program.

Gustafson's Law

Gustafson's Law, proposed by computer scientist John L. Gustafson in 1988, offers a different perspective on parallel computing compared to Amdahl's Law. Instead of focusing on the limitations imposed by serial portions of a program, Gustafson's Law emphasizes the scalability of parallel programs. The law states that as the problem size increases, the speedup of a parallel program can also increase, assuming that the amount of work that can be parallelized scales with the problem size.

One of the key attributes of Gustafson's Law is the recognition that the problem size can vary and that the speedup of a parallel program should be evaluated in the context of increasing problem sizes. This attribute makes Gustafson's Law more applicable to real-world scenarios where the size of the problem being solved can change. Additionally, Gustafson's Law provides a more optimistic view of parallel computing by focusing on the potential scalability of parallel programs.

• Gustafson's Law emphasizes the scalability of parallel programs as the problem size increases.
• The law recognizes that the problem size can vary and that the speedup of a parallel program should be evaluated in the context of increasing problem sizes.
• Gustafson's Law provides a more optimistic view of parallel computing by focusing on the potential scalability of parallel programs.

Comparison

When comparing Amdahl's Law and Gustafson's Law, it is important to consider their respective attributes and implications for parallel computing. Amdahl's Law highlights the impact of serial portions of a program on the overall speedup, while Gustafson's Law emphasizes the scalability of parallel programs with increasing problem sizes.

One key difference between the two laws is their focus. Amdahl's Law is concerned with the limitations imposed by serial portions of a program, while Gustafson's Law looks at the potential scalability of parallel programs. This difference in focus leads to contrasting perspectives on the speedup achievable through parallelization.

Another difference between Amdahl's Law and Gustafson's Law is their assumptions. Amdahl's Law assumes a fixed problem size, which may not always hold true in practice. On the other hand, Gustafson's Law recognizes that the problem size can vary and that the speedup of a parallel program should be evaluated in the context of increasing problem sizes.

• Amdahl's Law focuses on the limitations imposed by serial portions of a program, while Gustafson's Law emphasizes the scalability of parallel programs.
• Amdahl's Law assumes a fixed problem size, while Gustafson's Law recognizes that the problem size can vary.

Conclusion

In conclusion, Amdahl's Law and Gustafson's Law offer valuable insights into the performance of parallel programs. While Amdahl's Law highlights the impact of serial portions on speedup limitations, Gustafson's Law provides a more optimistic view by focusing on the scalability of parallel programs. Understanding the attributes and implications of both laws is essential for designing and optimizing parallel algorithms in the field of parallel computing.