Load Balancing Policies for Nested Fork-Join
Mia Reitz · 2021
Irregularity in parallel programs is often tackled by dynamic load balancing. Two well-known techniques, namely work sharing and work stealing, were recently combined into a hybrid scheme, which uses the former for shared-memory, and the latter for distributed-memory load balancing.Nested fork-join programs are an important type of task-based parallel programs, where tasks generate child tasks giving rise to an execution tree. The hybrid scheme was originally designed for a different task model. We transfer the hybrid scheme to nested fork-join programs, and compare different variants of the scheme, called load balancing policies. Experimental results show that the considered policies perform well for the used benchmarks with no significant difference between them.