load balancing parallel

**Load Balancing in Parallel Computing** is the **resource allocation discipline that distributes computational work evenly across available processors — preventing the scenario where some processors finish early and sit idle while others remain overloaded, which directly wastes parallel resources and limits speedup to the pace of the slowest processor regardless of how many total processors are available**. **Why Load Imbalance Kills Performance** If 1000 processors each take 1 second but one processor takes 10 seconds, the parallel execution time is 10 seconds — 10x worse than the perfectly balanced case. The efficiency drops from 100% to 10%. In Amdahl's terms, the imbalance creates a serial bottleneck proportional to the slowest processor's excess work. **Static Load Balancing** Work is divided before execution based on known or estimated cost: - **Block Partitioning**: Divide N work items into P equal contiguous chunks. Simple but assumes uniform cost per item. - **Cyclic Partitioning**: Assign items to processors in round-robin fashion (item i → processor i % P). Distributes irregular work more evenly than block when cost varies smoothly. - **Weighted Partitioning**: Use a cost model to assign different amounts of work to each processor. Requires accurate cost estimation. Used in mesh-based simulations where element computation cost is known from element type. - **Graph Partitioning (METIS, ParMETIS)**: For mesh-based parallel computations, partition the computational mesh into P subdomains that minimize inter-partition communication while equalizing computation per partition. **Dynamic Load Balancing** Work is redistributed during execution based on actual runtime costs: - **Work Stealing**: Each processor maintains a local work queue (deque). When a processor's queue is empty, it "steals" work from another processor's queue (typically from the opposite end to minimize contention). Intel TBB, Cilk, and Java ForkJoinPool implement work stealing. Advantages: fully automatic, adapts to unpredictable work variation. Overhead: ~100 ns per steal operation. - **Centralized Work Queue**: A global queue distributes work on demand. Each processor dequeues the next chunk when idle. Simple but the queue becomes a contention bottleneck at high processor counts (>64 processors). - **Work Sharing**: Overloaded processors proactively push excess work to underloaded neighbors. Less common than work stealing because it requires knowing who is underloaded. **Granularity Tradeoff** Finer-grained work units enable better balance (more opportunities to redistribute) but increase scheduling overhead. The optimal granularity balances the cost of scheduling against the cost of imbalance — typically 1000-10000 work units per processor provides excellent balance with negligible overhead. Load Balancing is **the efficiency enforcer of parallel computing** — ensuring that the parallel speedup you paid for in hardware is actually realized by keeping every processor productively busy until the very last computation completes.