Strong Scaling

The core premise of strong scaling analysis is that the total computational workload remains constant. As processors are added from P to N*P, the goal is to solve the identical problem faster, not a larger one. This contrasts with weak scaling, where the problem size per processor is kept constant.

• Example: Running a fixed neural network inference (e.g., ResNet-50 on a 224x224 image) on 1, 2, 4, and 8 NPU cores.

Performance is quantified by speedup (S) and parallel efficiency (E).

• Speedup: S(P) = T(1) / T(P), where T(1) is runtime on 1 processor and T(P) is runtime on P processors. Linear (ideal) speedup is S(P) = P.
• Parallel Efficiency: E(P) = S(P) / P. An efficiency of 1.0 (or 100%) indicates perfect linear scaling. Efficiency below 1.0 reveals overhead.

These metrics directly expose the scalability ceiling of an algorithm and hardware architecture.

Amdahl's Law provides the theoretical limit for strong scaling. It states that if a fraction α of a program is strictly serial, the maximum speedup is bounded by 1/α, regardless of the number of processors.

• Formula: S_max(P) ≤ 1 / (α + (1-α)/P)
• Implication: Even a small serial component (e.g., 5% I/O, initialization, non-parallelizable ops) severely limits maximum speedup. For α=0.05, S_max ≤ 20x even with infinite processors.

Adding processors introduces overhead that reduces efficiency:

• Inter-processor Communication: Time spent moving data (activations, gradients, parameters) between cores or memory hierarchies.
• Synchronization Costs: Delays from barriers and locks ensuring correct execution order.
• Load Imbalance: Idle time when some processors finish their assigned sub-tasks before others.

These costs often increase super-linearly with processor count, causing efficiency to drop.

As more cores work on the same problem, they often contend for shared resources, primarily memory bandwidth. Simultaneous requests to shared caches or DRAM can saturate available bandwidth, creating a bottleneck.

• NUMA Effects: In Non-Uniform Memory Access systems, accessing remote memory incurs higher latency.
• Cache Coherence Traffic: Maintaining consistency across private caches generates additional communication. This limits strong scaling even for compute-bound kernels when memory access patterns are not optimized.

Strong scaling is the primary goal for real-time inference tasks where a fixed model must produce a result within a strict deadline. Adding more NPU cores directly reduces the time-to-first-token or end-to-end latency.

• Examples: Autonomous vehicle perception, live video analysis, and high-frequency trading models.
• Constraint: Efficiency drops as core count increases due to Amdahl's Law, which limits speedup based on the serial fraction of the workload (e.g., data loading, final aggregation).

For user-facing applications processing individual requests (batch size = 1), strong scaling is essential. The workload cannot be enlarged via weak scaling; performance hinges solely on distributing the fixed computation across cores.

• NPU Challenge: Requires efficient partitioning of a single inference graph (e.g., a transformer layer) across multiple cores using model or tensor parallelism.
• Goal: Minimize idle cores and communication overhead to achieve near-linear speedup for the single request.

Amdahl's Law mathematically defines the limit of strong scaling: Speedup = 1 / (S + P/N), where S is the serial fraction, P is the parallelizable fraction, and N is the number of processors.

• Implication: Even a small serial component (e.g., 5% of runtime from data marshaling or a non-parallelizable activation function) caps maximum speedup. With 100 cores, a 5% serial fraction limits speedup to 20x, not 100x.
• NPU Design Impact: Drives architectural focus on minimizing serial operations and accelerating data movement between cores.

A key compiler technique to improve strong scaling is kernel fusion, which merges multiple small, sequential operations into a single, larger kernel.

• Benefit: Reduces the launch overhead and intermediate memory transfers that constitute the serial fraction (S) in Amdahl's Law.
• Example: Fusing a layer normalization, GeLU activation, and residual addition in a transformer block into one monolithic kernel executed across many cores, minimizing synchronization points.

As more cores work on the same problem, synchronization costs (e.g., barriers) and memory contention become dominant scaling limiters.

• Contention: Multiple cores reading/writing to shared caches or global memory create bottlenecks, stalling parallel execution.
• NPU Mitigation: Employ hierarchical synchronization and design memory subsystems (e.g., high-bandwidth on-chip SRAM) to sustain data feeds to many concurrent cores.

While weak scaling (increasing batch size with processors) is common for training, strong scaling is applied to reduce time-per-epoch for a fixed dataset.

• Use Case: Hyperparameter search or rapid prototyping, where completing more experiments in less wall-clock time is valuable.
• Trade-off: Strong scaling for training hits gradient synchronization bottlenecks faster. Techniques like 1-bit Adam or compressed communication are used to mitigate this.

Weak scaling measures how the total problem size a system can solve increases as more processors are added, while keeping the problem size per processor constant. The goal is to solve a larger problem in the same amount of time.

• Contrast with Strong Scaling: Strong scaling fixes the total problem size; weak scaling increases it proportionally with resources.
• Gustafson's Law: This principle formalizes weak scaling, arguing that in practice, scientists want to solve larger, more complex problems as computing power increases, not just the same problem faster.
• Example: Doubling the grid resolution of a climate simulation and also doubling the number of processors to maintain the same time-to-solution is weak scaling.

Amdahl's Law is the fundamental formula that defines the theoretical limit of strong scaling speedup. It states that the maximum speedup of a program is limited by its serial fraction.

• Formula: Speedup = 1 / (S + P/N), where S is the serial fraction, P is the parallelizable fraction (S+P=1), and N is the number of processors.
• Strong Scaling Implication: It quantifies the diminishing returns of adding more processors. If 10% of a program is serial, the maximum speedup is 10x, regardless of how many processors are used.
• Critical Path: The serial portion forms the critical path that cannot be shortened through parallelism.

Parallel overhead encompasses all the extra computation and resource consumption required to manage parallelism, which directly opposes perfect strong scaling.

• Key Components:
  • Communication: Time spent transferring data between processors (e.g., over a network or interconnect).
  • Synchronization: Time spent at barriers or using mutexes to coordinate threads.
  • Load Imbalance: Idle time on some processors because work was not divided evenly.
  • Task Management: Cost of spawning, scheduling, and destroying threads or processes.
• Impact on Scaling: As more processors are added for a fixed problem, overhead often increases, reducing efficiency.

Data parallelism is the most common programming model for achieving strong scaling. The same operation (kernel) is applied concurrently to different subsets (shards) of a dataset.

• Mechanism: The global dataset is partitioned (e.g., batch splitting in deep learning). Each processor executes the same computational kernel on its local partition.
• Strong Scaling Fit: Ideal for embarrassingly parallel problems where partitions are independent. Scaling efficiency depends on the cost of redistributing/aggregating results.
• Contrast with Model Parallelism: Data parallelism replicates the entire model; model parallelism splits the model itself across devices.

Scalability is the broader capability of a system to handle increasing workloads by adding resources. Strong scaling is one specific measure of it.

• Strong Scalability: Measures time-to-solution for a fixed workload.
• Weak Scalability: Measures workload handled for a fixed time-to-solution.
• Horizontal vs. Vertical: Strong scaling is often associated with horizontal scaling (adding more nodes), though vertical scaling (adding power to a single node) can also improve it for a limited time.
• System Bottlenecks: Poor strong scaling exposes bottlenecks like serial sections, memory bandwidth limits, or network latency.

Parallel efficiency is the metric used to quantify how effectively additional processors are utilized in a strong scaling experiment.

• Calculation: Efficiency = (Speedup / Number of Processors) * 100%, or (T1 / (N * TN)) * 100%, where T1 is runtime on 1 processor and TN is runtime on N processors.
• Perfect Strong Scaling: 100% efficiency means doubling processors halves the runtime exactly.
• Real-World Target: Efficiency above 70-80% is often considered good for strong scaling on non-trivial problems. Efficiency inevitably declines as N increases, due to Amdahl's Law and increasing parallel overhead.