Extending a Work-Stealing Framework with Priorities and Weights
Ryusuke Nakashima, Hiroshi Yoritaka, Masahiro Yasugi, Tasuku Hiraishi, Seiji Umatani · 2019
This paper proposes priority-based and weight-based steal strategies for an idle worker (thief) to select a victim worker in work-stealing frameworks. Typical work-stealing frameworks employ uniformly random victim selection. We implemented the proposed strategies on a work-stealing framework called Tascell; Tascell programmers can let each worker estimate and declare the remaining work amount of its current task as a real number so that the enhanced Tascell framework can use declared values as priorities or weights. To reduce the total task division cost, the proposed strategies avoid stealing small tasks. With a priority-based strategy, a thief selects the victim that has the highest known priority at that time. With a weight-based non-uniformly random strategy, a thief uses the relative weights of victim candidates as their selection probabilities. The proposed selection strategies achieved superior performance compared to uniformly random selection. Our evaluation uses a parallel implementation of the ``highly serial'' version of the Barnes-Hut force calculation algorithm in a shared memory environment and five benchmark programs in a distributed memory environment.