Amdahl's Law

Amdahl's Law is expressed as Speedup = 1 / (S + (P / N)), where:

• S is the fraction of the program that is inherently serial (cannot be parallelized).
• P is the fraction that can be parallelized (S + P = 1).
• N is the number of processors.

This formula calculates the maximum theoretical speedup. The serial fraction (S) acts as a bottleneck, limiting gains regardless of how many processors (N) are added. For example, if 90% of a task is parallelizable (P=0.9) and you have 10 processors, the speedup is 1 / (0.1 + (0.9/10)) = ~5.3x, not 10x.

The most critical insight from Amdahl's Law is the asymptotic limit on speedup. As the number of processors (N) approaches infinity, the speedup converges to 1 / S. This reveals an absolute ceiling.

• If S = 0.1 (10% serial), maximum speedup ≤ 10x.
• If S = 0.01 (1% serial), maximum speedup ≤ 100x.

This principle dictates hardware design and software architecture, emphasizing that optimizing the serial portion often yields greater returns than simply adding more cores. It's a primary driver for techniques like kernel fusion and pipeline parallelism to minimize serial overhead.

Amdahl's Law models strong scaling: measuring how fast a fixed total problem size can be solved by adding processors. It assumes the parallel portion scales perfectly, which is often unrealistic.

Its counterpart, Gustafson's Law, addresses weak scaling, where the problem size grows proportionally with the processor count. Gustafson's Law is often more representative of modern, data-intensive workloads (like training large models) where we scale the work with the resources.

Understanding which scaling model applies is crucial for performance analysis. Amdahl's Law provides the conservative, fundamental limit for a given task.

Amdahl's Law directly influences accelerator architecture:

• Emphasis on Reducing Serial Overhead: Hardware designs minimize fixed costs like kernel launch latency and data transfer (e.g., via unified memory).
• Justification for Specialized Units: Dedicated hardware for serial tasks (e.g., scheduling engines, DMA controllers) improves the 'S' term.
• Compiler Optimization Goal: Graph compilation and kernel fusion aim to transform serial operations into parallelizable ones or batch them to amortize overhead.
• Scheduling Strategy: Techniques like work stealing help balance loads, ensuring the parallel portion (P) is efficiently distributed, moving performance closer to the theoretical limit.

Amdahl's Law informs the choice of parallelism strategy for neural networks:

• Data Parallelism: Splits the batch across processors. Excellent speedup if batch size is large (large P), but has a serial synchronization cost (gradient averaging) that contributes to S.
• Model/Tensor Parallelism: Splits the model layers or operations. Reduces memory pressure but introduces serial communication dependencies between devices, increasing S.
• Pipeline Parallelism: Overlaps execution of different pipeline stages. Reduces idle time but has serial pipeline flush and bubble overhead.

The optimal strategy minimizes the effective S for a given model and hardware configuration.

While foundational, Amdahl's Law has assumptions that can be limiting:

• Fixed Problem Size: Assumes the total work is constant, which doesn't hold for weak scaling scenarios.
• Perfect Parallel Scaling: Assumes the parallel portion scales linearly with N, ignoring real-world overheads like communication and synchronization.
• Overhead-Free Serial Section: Assumes the serial section's runtime is constant, ignoring that synchronization and aggregation often scale with N.

Modern use treats 'S' as an effective serial fraction that includes these overheads. It remains the essential tool for performing a bottleneck analysis and setting realistic performance expectations for parallel systems.

Amdahl's Law establishes that serial code imposes a hard ceiling on parallel speedup. Even a small serial component, such as data loading, synchronization, or a non-parallelizable preprocessing step, drastically limits returns from adding more cores.

• Example: If 5% of a model's inference task is serial (S=0.05), the maximum theoretical speedup is 20x, regardless of how many NPU cores you use.
• This makes identifying and minimizing inherently sequential operations the primary optimization goal for NPU compiler engineers.

Launching a computational kernel on an NPU involves serial overhead: setting up DMA transfers, configuring tensor descriptors, and issuing commands. Amdahl's Law treats this as part of the serial fraction (S).

• For small, frequent operations (e.g., activating a small layer), this overhead can dominate, making parallel execution on many cores inefficient.
• Optimization focuses on kernel fusion (combining operations) to amortize launch overhead over more parallel work, effectively reducing S.

Moving data between system memory and the NPU's high-bandwidth memory (HBM) is often a serialized operation. Amdahl's Law frames this data transfer time as a non-parallelizable component.

• Memory-bound workloads see limited benefit from more compute cores if the data pipeline cannot keep them fed.
• Techniques like double-buffering (overlapping compute with data transfer) and optimizing for data locality are direct responses to this law, aiming to hide serial memory latency within parallel computation.

Operations that require global synchronization—such as batch normalization layers that compute mean and variance across all cores—introduce serial segments. Each synchronization point is a sequential bottleneck.

• In pipeline-parallel execution across NPU cores, the slowest stage (the critical path) determines throughput, a direct manifestation of Amdahl's Law.
• Hardware-aware model optimization seeks to minimize or eliminate synchronization points, or to use asynchronous execution patterns where possible.

Amdahl's Law guides the design of NPU-friendly neural networks. Architectures with massive, homogeneous parallel operations (like large matrix multiplications in transformers) have a very small S, enabling near-linear scaling on many-core NPUs.

• Conversely, models with many small, sequential, or data-dependent branches (e.g., certain recurrent or control-flow-heavy networks) have a large S, making them poor candidates for massive NPU acceleration.
• This law justifies the industry shift towards attention-based models for hardware efficiency.

Amdahl's Law directly explains the difference between strong and weak scaling in distributed training.

• Strong Scaling (fixed problem size): Adding more GPUs/NPUs to train the same batch size hits Amdahl's limit quickly due to fixed overheads like gradient synchronization (all-reduce).
• Weak Scaling (increasing problem size): Increasing batch size with processor count keeps the per-processor work constant. Success here depends on the serial fraction not growing with problem size—a key challenge for optimizer and communication overhead.

Strong scaling measures how the execution time of a fixed-size problem decreases as more processors are added. The goal is to solve the same total workload faster. It is the scenario directly modeled by Amdahl's Law, which shows that the serial fraction of the program ultimately limits the maximum achievable speedup, regardless of the number of processors. For example, a simulation with a 10% serial component has a maximum theoretical speedup of 10x, even with infinite processors.

Weak scaling measures how the total amount of work a system can handle increases as more processors are added, while keeping the problem size per processor constant. This model, formalized by Gustafson's Law, is often more relevant for large-scale scientific computing where researchers want to solve larger, more complex problems. It argues that the serial portion often remains fixed or grows slowly, allowing efficiency to be maintained as the system scales. For instance, doubling processors to model a weather system with twice the resolution.

The critical path is the longest sequence of dependent tasks in a parallel task graph from start to finish. It determines the absolute minimum possible execution time (makespan) for the entire computation. Optimizing parallel performance requires identifying and shortening this path. Amdahl's Law implicitly identifies the serial portion of a program as an irreducible critical path—a chain of operations that cannot be parallelized, thus setting a hard lower bound on execution time regardless of other optimizations.

A task graph is a directed acyclic graph (DAG) that models a parallel computation. Nodes represent tasks (units of work), and edges represent data or control dependencies. This abstraction is fundamental for scheduling and analyzing parallelism. The structure of the task graph reveals opportunities for concurrency and inherent serial constraints. Amdahl's Law can be viewed as analyzing a simple two-part task graph: a large parallelizable section followed by a small, strictly sequential section that creates a bottleneck.

Synchronization overhead encompasses the time and resources spent coordinating parallel threads or processes, including operations like barriers, locks, and atomic updates. This overhead is a key practical factor that reduces real-world speedup below Amdahl's theoretical limit. Even perfectly parallelizable code requires synchronization for correctness, introducing serialized sections and communication latency not accounted for in the basic law. Techniques like lock-free algorithms and careful granularity design aim to minimize this overhead.

Gustafson's Law (1988) provides a complementary perspective to Amdahl's Law. It states that given a fixed time budget, larger problems can be solved by scaling both the parallel and serial work. It models weak scaling scenarios, arguing that the serial fraction becomes less significant as the total problem size grows. While Amdahl's Law pessimistically focuses on speeding up a fixed problem, Gustafson's Law optimistically focuses on solving bigger problems within the same time, often aligning better with real-world high-performance computing goals.