Load Balancing Strategies

Load Balancing Strategies are techniques for distributing computational work across parallel processing elements to minimize idle time and maximize overall throughput — effective load balancing is critical because even a small imbalance can severely degrade parallel efficiency, with the slowest processor determining the total execution time.

Static Load Balancing:
- Block Partitioning: divide N work units evenly among P processors — processor i gets units [i×N/P, (i+1)×N/P) — simple and zero-overhead but assumes uniform work per unit
- Cyclic Partitioning: assign work unit i to processor i mod P — interleaves work assignments to average out non-uniform costs — effective when adjacent units have correlated costs (e.g., triangular matrix operations)
- Block-Cyclic: combine block and cyclic — assign blocks of B consecutive units in round-robin fashion — balances locality (block) with load distribution (cyclic), standard in ScaLAPACK for dense linear algebra
- Weighted Partitioning: assign work based on estimated costs — if work unit i costs w_i, partition so each processor receives approximately Σw_i/P total cost — requires accurate cost estimates

Dynamic Load Balancing:
- Centralized Work Queue: a master thread/process maintains a shared queue of work items — workers request items when idle — simple but the master can become a bottleneck at high worker counts (>64 workers)
- Distributed Work Queue: each processor maintains a local queue and uses work stealing when idle — eliminates the central bottleneck, scales to thousands of processors
- Chunk-Based Self-Scheduling: workers take chunks of work from a shared counter using atomic increment — chunk size trades granularity (small chunks → better balance) against overhead (fewer synchronization operations with larger chunks)
- Guided Self-Scheduling: chunk size decreases exponentially — initial chunks are N/P, each subsequent chunk is remaining_work/P — large initial chunks amortize overhead while small final chunks balance the tail

OpenMP Scheduling Strategies:
- schedule(static): iterations divided equally among threads at compile time — zero runtime overhead but no adaptability to non-uniform iteration costs
- schedule(dynamic, chunk): iterations assigned to threads on demand in chunks — balances irregular workloads but atomic counter access adds 50-200 ns per chunk
- schedule(guided, chunk): exponentially decreasing chunk sizes — first chunk is N/P iterations, subsequent chunks shrink toward minimum chunk size — balances between dynamic's adaptability and static's low overhead
- schedule(auto): implementation chooses the best strategy — may use profiling data from previous executions to select optimal scheduling

Task-Based Load Balancing:
- Task Decomposition: express computation as a DAG (directed acyclic graph) of tasks with dependencies — the runtime system schedules tasks to processors respecting dependencies
- Critical Path Scheduling: prioritize tasks on the longest path through the DAG — ensures that the critical path progresses even when other tasks are available
- Task Coarsening: merge fine-grained tasks to reduce scheduling overhead — a task should take at least 10-100 µs to amortize the ~1 µs scheduling cost
- Locality-Aware Scheduling: schedule tasks near their input data — reduces data movement cost, especially on NUMA systems where remote memory access is 2-3× slower than local

Domain Decomposition with Load Balancing:
- Adaptive Mesh Refinement (AMR): scientific simulations refine meshes non-uniformly — space-filling curves (Hilbert, Morton) reorder cells to maintain locality while enabling simple 1D partitioning
- Graph Partitioning: METIS/ParMETIS partition computational graphs to minimize communication while balancing load — edge weights represent communication volume, vertex weights represent computation cost
- Diffusive Load Balancing: processors exchange small amounts of work with neighbors iteratively until balance is achieved — converges slowly but requires only local communication
- Hierarchical Balancing: balance at the node level first (between NUMA domains), then at the global level (between nodes) — matches the hierarchical cost structure of modern supercomputers

Measuring and Diagnosing Imbalance:
- Load Imbalance Factor: (max_time - avg_time) / avg_time — a factor of 0.1 means 10% imbalance, wasting approximately 10% of total compute resources
- Parallel Efficiency: (sequential_time) / (P × parallel_time) — efficiency below 0.8 often indicates load imbalance as the primary bottleneck
- Profiling Tools: Intel VTune's threading analysis, NVIDIA Nsight Systems' timeline view, and Arm MAP visualize per-thread/per-process load — identify specific imbalance points in the execution

Load balancing is the difference between theoretical and actual parallel speedup — a perfectly parallelizable algorithm with 20% load imbalance across 1000 processors wastes 200 processor-equivalents of compute, making load balancing optimization one of the highest-impact improvements for large-scale parallel applications.