Amdahls

Amdahl's Law is a formula used to estimate the maximum theoretical speedup of a task when part of the work can be parallelized. Named after Gene M. Amdahl, who described it in 1967 in the context of improving IBM mainframe performance, the law is widely applied in parallel computing to assess the potential benefits of multicore processors, clusters, and other parallel architectures.

The law states that if a fraction p of a program can be parallelized, and the remaining fraction (1 − p) must be executed serially, the overall speedup S with n processors is S = 1 / ((1 − p) + p / n). As the number of processors increases, the speedup is limited by the serial portion and approaches 1 / (1 − p). For example, if 60% of a task is parallelizable (p = 0.6), the theoretical maximum speedup with a very large number of processors is 1 / 0.4 = 2.5x.

In practice, actual speedups are lower due to overheads such as synchronization, communication, load balancing, and memory contention. Amdahl's Law assumes a fixed problem size; it does not account for the benefits of increasing problem size with more processors, a scenario addressed by Gustafson's law.

Usage notes: the law emphasizes reducing the serial portion and the importance of scalable parallel design. It remains a fundamental guideline in performance modeling, architectural design, and optimization discussions.