Document Open Access Logo

A Heap-Based Concurrent Priority Queue with Mutable Priorities for Faster Parallel Algorithms

Authors Orr Tamir, Adam Morrison, Noam Rinetzky

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.15.pdf
  • Filesize: 0.79 MB
  • 16 pages

Document Identifiers

Author Details

Orr Tamir
Adam Morrison
Noam Rinetzky

Cite As Get BibTex

Orr Tamir, Adam Morrison, and Noam Rinetzky. A Heap-Based Concurrent Priority Queue with Mutable Priorities for Faster Parallel Algorithms. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.15

Abstract

Existing concurrent priority queues do not allow to update the priority of an element after its insertion. As a result, algorithms that need this functionality, such as Dijkstra's single source shortest path algorithm, resort to cumbersome and inefficient workarounds. We report on a heap-based concurrent priority queue which allows to change the priority of an element after its insertion. We show that the enriched interface allows to express Dijkstra's algorithm in a more natural way, and that its implementation, using our concurrent priority queue, outperform existing algorithms.

Subject Classification

Keywords
  • priority queues
  • concurrent data structures
  • Dijkstra's single-source shortest path algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dan Alistarh, Justin Kopinsky, Jerry Li, and Nir Shavit. The SprayList: A Scalable Relaxed Priority Queue. In PPoPP, 2015. Google Scholar
  2. Irina Calciu, Hammurabi Mendes, and Maurice Herlihy. The Adaptive Priority Queue with Elimination and Combining. In DISC, 2014. Google Scholar
  3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 3rd edition, 2009. Google Scholar
  4. Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient smt solver. In TACAS, 2008. Google Scholar
  5. E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1):269-271, December 1959. Google Scholar
  6. 9th DIMACS implementation challenge. URL: http://www.dis.uniroma1.it/challenge9/download.shtml.
  7. Michael L. Fredman and Robert Endre Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. JACM, 34(3):596-615, July 1987. Google Scholar
  8. Richard M. Fujimoto. Parallel discrete event simulation. CACM, 33(10):30-53, 1990. URL: http://dx.doi.org/10.1145/84537.84545.
  9. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., 2008. Google Scholar
  10. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: a correctness condition for concurrent objects. TOPLAS, 12:463-492, July 1990. Google Scholar
  11. Galen C. Hunt, Maged M. Michael, Srinivasan Parthasarathy, and Michael L. Scott. An Efficient Algorithm for Concurrent Priority Queue Heaps. IPL, 60(3):151-157, 1996. Google Scholar
  12. Richard Jones, Antony Hosking, and Eliot Moss. The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman &Hall/CRC, 1st edition, 2011. Google Scholar
  13. Zvi M. Kedem and Abraham Silberschatz. A characterization of database graphs admitting a simple locking protocol. Acta Informatica, 16, 1981. Google Scholar
  14. Justin Kopinsky. SprayList SSSP benchmark. https://github.com/jkopinsky/SprayList/blob/master/sssp.c, 2015.
  15. Jonatan Lindén and Bengt Jonsson. A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention. In OPODIS, 2013. Google Scholar
  16. Yujie Liu and Michael Spear. Mounds: Array-Based Concurrent Priority Queues. In ICPP, 2012. Google Scholar
  17. Itay Lotan and Nir Shavit. Skiplist-Based Concurrent Priority Queues. In IPDPS, 2000. Google Scholar
  18. Paul E. McKenney and John D. Slingwine. Read-copy update: using execution history to solve concurrency problems. In PDCS, 1998. Google Scholar
  19. Maged M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Trans. Parallel Distrib. Syst., 2004. Google Scholar
  20. Donald Nguyen, Andrew Lenharth, and Keshav Pingali. A Lightweight Infrastructure for Graph Analytics. In SOSP, 2013. Google Scholar
  21. R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6):1389-1401, 1957. URL: http://dx.doi.org/10.1002/j.1538-7305.1957.tb01515.x.
  22. William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees. CACM, 33(6):668-676, June 1990. Google Scholar
  23. Hamza Rihani, Peter Sanders, and Roman Dementiev. Brief Announcement: MultiQueues: Simple Relaxed Concurrent Priority Queues. In SPAA, 2015. Google Scholar
  24. Nir Shavit and Asaph Zemach. Scalable Concurrent Priority Queue Algorithms. In PODC, 1999. Google Scholar
  25. Håkan Sundell and Philippas Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. JPDC, 65(5):609-627, 2005. Google Scholar
  26. Martin Wimmer, Jakob Gruber, Jesper Larsson Träff, and Philippas Tsigas. The Lock-free k-LSM Relaxed Priority Queue. In PPoPP, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact