  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.
