An efficient work-stealing scheduler for task dependency graph

Chun-Xun Lin, Tsung-Wei Huang, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

19 Citations (Scopus)

Abstract

Work-stealing is a key component of many parallel task graph libraries such as Intel Threading Building Blocks (TBB) FlowGraph, Microsoft Task Parallel Library (TPL) Batch.Net, Cpp-Taskflow, and Nabbit. However, designing a correct and effective work-stealing scheduler is a notoriously difficult job, due to subtle implementation details of concurrency controls and decentralized coordination between threads. This problem becomes even more challenging when striving for optimal thread usage in handling parallel workloads with complex task graphs. As a result, we introduce in this paper an effective work-stealing scheduler for execution of task dependency graphs. Our scheduler adopts a simple and efficient strategy to adapt the number of working threads to available task parallelism at any time during the graph execution. Our strategy is provably good in preventing resource underutilization and simultaneously minimizing resource waste when tasks are scarce. We have evaluated our scheduler on both micro-benchmarks and a real-world circuit timing analysis workload, and demonstrated promising results over existing methods in terms of runtime, energy efficiency, and throughput.

Original languageEnglish
Title of host publicationProceedings of The IEEE 26th International Conference on Parallel and Distributed Systems, ICPADS 2020
PublisherIEEE Computer Society
Pages64-71
Number of pages8
ISBN (Electronic)9781728190747
ISBN (Print)9781728183824
DOIs
Publication statusPublished - 2 Dec 2020
Event26th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2020 - Virtual, Hong Kong
Duration: 2 Dec 20204 Dec 2020
https://ieeexplore.ieee.org/xpl/conhome/9359105/proceeding (Conference proceedings )

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume2020-December
ISSN (Print)1521-9097
ISSN (Electronic)2690-5965

Conference

Conference26th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2020
Country/TerritoryHong Kong
CityVirtual
Period2/12/204/12/20
Internet address

Scopus Subject Areas

  • Hardware and Architecture

User-Defined Keywords

  • task dependency graph
  • work stealing
  • parallel computing
  • scheduling
  • multithreading

Fingerprint

Dive into the research topics of 'An efficient work-stealing scheduler for task dependency graph'. Together they form a unique fingerprint.

Cite this