Configurable Strategies for Work-stealing

Work-stealing systems are typically oblivious to the nature of the tasks theyare scheduling. For instance, they do not know or take into account how long atask will take to execute or how many subtasks it will spawn. Moreover, theactual task execution order is typically determined by the underlying taskstorage data structure, and cannot be changed. There are thus possibilities foroptimizing task parallel executions by providing information on specific tasksand their preferred execution order to the scheduling system. We introduce scheduling strategies to enable applications to dynamicallyprovide hints to the task-scheduling system on the nature of specific tasks.Scheduling strategies can be used to independently control both local taskexecution order as well as steal order. In contrast to conventional schedulingpolicies that are normally global in scope, strategies allow the scheduler toapply optimizations on individual tasks. This flexibility greatly improvescomposability as it allows the scheduler to apply different, specificscheduling choices for different parts of applications simultaneously. Wepresent a number of benchmarks that highlight diverse, beneficial effects thatcan be achieved with scheduling strategies. Some benchmarks (branch-and-bound,single-source shortest path) show that prioritization of tasks can reduce thetotal amount of work compared to standard work-stealing execution order. Forother benchmarks (triangle strip generation) qualitatively better results canbe achieved in shorter time. Other optimizations, such as dynamic merging oftasks or stealing of half the work, instead of half the tasks, are also shownto improve performance. Composability is demonstrated by examples that combinedifferent strategies, both within the same kernel (prefix sum) as well as whenscheduling multiple kernels (prefix sum and unbalanced tree search)