An Efficient Work-Stealing Scheduler for Task Dependency Graph
An Efficient Work-Stealing Scheduler for Task Dependency Graph
复制标题
DOI：
10.1109/icpads51040.2020.00018
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Chun-Xun Lin;Tsung-Wei Huang;Martin D. F. Wong
中科院分区：
文献类型：
--
作者：
Chun-Xun Lin;Tsung-Wei Huang;Martin D. F. Wong
窃取工作是许多并行任务图库的关键组成部分，例如英特尔螺纹构建块（TBB）Flowgraph，Microsoft Task Parallel Library（TPL）批处理.NET .NET，CPP-TASKFLOW和NABBIT。但是，设计正确且有效的工作策划调整器是一项艰巨的工作，这是一项艰巨的工作，由于螺纹之间的并发控制和分散协调的细微实施细节。在使用复杂的任务图处理并行工作负载时，在努力进行最佳线程使用时，这个问题变得更加具有挑战性。结果，我们在本文中介绍了一个有效的工作策划调度程序，用于执行任务依赖图。我们的调度程序采用了一种简单有效的策略，以在图表执行过程中的任何时候调整工作线程的数量到可用的任务并行性。事实证明，我们的策略在防止资源不足和同时最大程度地减少资源浪费时非常好。我们已经在微基准和现实世界的电路正时分析工作量上评估了调度程序，并在运行时，能源效率和吞吐量方面证明了对现有方法的有希望的结果。
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.