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.