Work-stealing Strategies That Consider Work Amount and Hierarchy

DOI Web Site 1 Citations 19 References Open Access
  • Nakashima Ryusuke
    Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology
  • Yasugi Masahiro
    Department of Computer Science and Networks, Kyushu Institute of Technology
  • Yoritaka Hiroshi
    Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology
  • Hiraishi Tasuku
    Academic Center for Computing and Media Studies, Kyoto University
  • Umatani Seiji
    Department of Information Sciences, Faculty of Science, Kanagawa University

Abstract

<p>This paper proposes work-stealing strategies for an idle worker (thief) to select a victim worker. These strategies avoid small tasks being stolen to reduce the total task-division cost. We implemented these strategies on a work-stealing framework called Tascell. First, we propose new types of priority- and weight-based steal strategies. Programmers can let each worker estimate and declare, as a real number, the amount of remaining work required to complete its current task so that declared values are used as “priorities” or “weights”. 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. Second, we propose work-stealing strategies to alleviate excessive intra-node work stealing and excessive “steal backs” (or leapfroggings); for example, we allow workers to steal tasks from external nodes with some frequency even if work remains inside the current node. 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.</p>

Journal

Citations (1)*help

See more

References(19)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top