Efficient Work-Stealing Strategies for Fine-Grain Task Parallelism

Herein, we describe extended work-stealing strategies for Stack Threads/MP, in which thieves steal from the bottom of a victim´s logical stack not just the bottommost task but multiple chained tasks. These new strategies offer two advantages: reducing the total cost of stealing tasks and reducing the total idle time. In addition, these strategies attempt to preserve the sequential execution order of tasks in the chain. We evaluated these extended work-stealing strategies by using the unbalanced tree search (UTS) benchmark and could demonstrate its advantages over the original work-stealing strategy and other OpenMP task implementations and Cilk implementation as well. Extended work-stealing strategies exhibit significant improvement with respect to the UTS benchmark, even if the task is very fine-grain and non-uniform.