Work-stealing with configurable scheduling strategies
Work-stealing with configurable scheduling strategies
复制标题
通过可配置的调度策略窃取工作
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
P. Tsigas
中科院分区：
文献类型：
--
作者：
Martin Wimmer;Daniel Cederman;J. Träff;P. Tsigas
工作窃取系统通常不知道它们正在调度的任务的性质。他们不知道也不考虑任务执行需要多长时间或者会产生多少个子任务。此外，任务执行顺序通常由底层任务存储数据结构决定，并且不能改变。因此，可以通过向调度系统提供有关特定任务及其首选执行顺序的信息来优化任务并行执行。
我们研究了工作窃取的概括，并引入了一个框架，使应用程序能够使用调度策略动态地提供有关特定任务性质的提示。策略可用于独立控制本地任务执行和窃取订单。与通常是全局范围的更传统的调度策略相比，策略允许对特定任务进行优化。策略是可组合的，并允许同时为应用程序的不同部分做出不同的、特定的调度选择。我们根据我们的战略框架实施了工作窃取系统。一系列基准展示了通过调度策略可以实现的有益效果。
Work-stealing systems are typically oblivious to the nature of the tasks they are scheduling. They do not know or take into account how long a task will take to execute or how many subtasks it will spawn. Moreover, task execution order is typically determined by an underlying task storage data structure, and cannot be changed. There are thus possibilities for optimizing task parallel executions by providing information on specific tasks and their preferred execution order to the scheduling system.
We investigate generalizations of work-stealing and introduce a framework enabling applications to dynamically provide hints on the nature of specific tasks using scheduling strategies. Strategies can be used to independently control both local task execution and steal order. Strategies allow optimizations on specific tasks, in contrast to more conventional scheduling policies that are typically global in scope. Strategies are composable and allow different, specific scheduling choices for different parts of an application simultaneously. We have implemented a work-stealing system based on our strategy framework. A series of benchmarks demonstrates beneficial effects that can be achieved with scheduling strategies.