Load Balancing Parallel
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.