Improving the Data Locality of Work Stealing
Source: Vrije Universiteit Brussel
Fork/Join parallelism based on work stealing is becoming a widely used approach for parallelizing programs, yielding good and proven performance characteristics, while being relatively convenient to use. A known problem, however, is that randomized work stealing may suffer from suboptimal data locality over time. Current solutions for this issue rely on programmers defining worker affinity for tasks, or defining locales or places where tasks can be explicitly placed when they are generated. They thus add cognitive overhead. In this position paper, the authors propose to complement these existing solutions with a domain-specific approach: based on the observation that most parallel algorithms can be classified according to "Dwarfs", they suggest to include explicit support for such classes of algorithms on top of the basic Fork/Join operations.