CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Data structures for task-based priority scheduling

M. Wimmer ; F. Versaci ; J.L. Träff ; Daniel Cederman (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers)) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) )
Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP (0362-1340). Vol. 49 (2014), 8, p. 379-380.
[Konferensbidrag, refereegranskat]

We present three lock-free data structures for priority task scheduling: a priority work-stealing one, a centralized one with ρ-relaxed semantics, and a hybrid one combining both concepts. With the single-source shortest path (SSSP) problem as example, we show how the different approaches affect the prioritization and provide upper bounds on the number of examined nodes. We argue that priority task scheduling allows for an intuitive and easy way to parallelize the SSSP problem, notoriously a hard task. Experimental evidence supports the good scalability of the resulting algorithm. The larger aim of this work is to understand the trade-offs between scalability and priority guarantees in task scheduling systems. We show that ρ-relaxation is a valuable technique for improving the first, while still allowing semantic constraints to be satisfied: the lock-free, hybrid κ-priority data structure can scale as well as work-stealing, while still providing strong priority scheduling guarantees, which depend on the parameter κ. Our theoretical results open up possibilities for even more scalable data structures by adopting a weaker form of ρ-relaxation, which still enables the semantic constraints to be respected.

Nyckelord: κ-priority data structure , Parallel single-source shortest paths , Priority scheduling , Task-parallelism , Work-stealing



Denna post skapades 2014-04-17. Senast ändrad 2016-05-10.
CPL Pubid: 196874

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)