Data Structures for Task-based Priority Scheduling

Martin Wimmer, Daniel Cederman, Francesco Versaci, Jesper Larsson Traff, Philippas Tsigas
Faculty of Informatics, Vienna University of Technology, Favoritenstrasse 16, 1040 Vienna, Austria
arXiv:1312.2501 [cs.DC], (9 Dec 2013)


   author={Wimmer}, M. and {Cederman}, D. and {Versaci}, F. and {Larsson Tr{"a}ff}, J. and {Tsigas}, P.},

   title={"{Data Structures for Task-based Priority Scheduling}"},

   journal={ArXiv e-prints},




   keywords={Computer Science – Distributed, Parallel, and Cluster Computing},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   Source codes Source codes




Many task-parallel applications can benefit from attempting to execute tasks in a specific order, as for instance indicated by priorities associated with the tasks. We present three lock-free data structures for priority scheduling with different trade-offs on scalability and ordering guarantees. First we propose a basic extension to work-stealing that provides good scalability, but cannot provide any guarantees for task-ordering in-between threads. Next, we present a centralized priority data structure based on k-fifo queues, which provides strong (but still relaxed with regard to a sequential specification) guarantees. The parameter k allows to dynamically configure the trade-off between scalability and the required ordering guarantee. Third, and finally, we combine both data structures into a hybrid, k-priority data structure, which provides scalability similar to the work-stealing based approach for larger k, while giving strong ordering guarantees for smaller k. We argue for using the hybrid data structure as the best compromise for generic, priority-based task-scheduling. We analyze the behavior and trade-offs of our data structures in the context of a simple parallelization of Dijkstra’s single-source shortest path algorithm. Our theoretical analysis and simulations show that both the centralized and the hybrid k-priority based data structures can give strong guarantees on the useful work performed by the parallel Dijkstra algorithm. We support our results with experimental evidence on an 80-core Intel Xeon system.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: