Load Balancing in Parallel Computing is the algorithmic and runtime strategy for distributing work evenly across all processing elements — ensuring that no processor sits idle while others are overloaded, which is the single most common reason that parallel applications achieve only a fraction of their theoretical speedup, especially for irregular workloads where the computation per data element varies unpredictably.

Amdahl's Corollary for Load Imbalance

If P processors execute a parallel section but one processor has 20% more work than the average, all other P-1 processors wait during that 20% excess — the parallel efficiency drops to ~83% regardless of P. For irregular workloads (sparse matrix, adaptive mesh, graph algorithms), imbalances of 2-10x between processors are common without load balancing, reducing parallel efficiency below 50%.

Static Load Balancing

Work is distributed before execution begins, based on estimated computation cost:

• Block Partitioning: Divide N elements into P contiguous blocks of N/P. Optimal when each element has equal cost (regular arrays, dense matrix rows). Simple, zero runtime overhead, excellent locality.
• Cyclic Partitioning: Assign elements round-robin (element i → processor i mod P). Smooths out gradual imbalances (e.g., triangular matrix where row i has i nonzeros) but destroys locality.
• Block-Cyclic: Blocks of size B assigned cyclically. Balances load smoothness against locality. The standard for ScaLAPACK dense linear algebra.
• Weighted Partitioning: Assign elements with computational cost weights, partitioning so that total weight per processor is equal. Requires a priori cost estimation. Used for pre-partitioned mesh-based simulations.

Dynamic Load Balancing

Work is redistributed during execution based on observed progress:

• Centralized Queue: A global task queue feeds idle processors. Simple but the central queue becomes a bottleneck at high core counts.
• Work Stealing: Each processor maintains a local queue. Idle processors steal from random busy neighbors. Provably near-optimal for fork-join programs (Cilk bound: T = T₁/P + O(T∞)). Zero overhead when perfectly balanced (no stealing needed).
• Guided/Dynamic Scheduling (OpenMP): schedule(dynamic, chunk) assigns loop iterations in chunks to threads on demand. schedule(guided) starts with large chunks and decreases chunk size as the loop progresses — initially reduces overhead, then fine-tunes balance near the end.

Domain Decomposition Rebalancing

For long-running simulations (CFD, molecular dynamics), the computational load per spatial region changes over time (adaptive mesh refinement, particle migration). Periodic re-partitioning (Zoltan, ParMETIS) redistributes spatial domains across processors. The rebalancing cost (data migration) must be amortized against the improved balance — re-partition only when imbalance exceeds a threshold (e.g., 20%).

Load Balancing is the difference between theoretical and actual parallel performance — the discipline that ensures all processors finish at the same time, converting expensive parallel hardware from partially-utilized capacity into fully-engaged computing power.