[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

M. Wimmer, J. Gruber, J. Träff, P. Tsigas:
"The Lock-Free k-LSM Relaxed Priority Queue";
Poster: 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015, San Francisco, CA, USA; 07.02.2015 - 11.02.2015; in: "Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015", A. Cohen, D. Grove (Hrg.); ACM, (2015), ISBN: 978-1-4503-3205-7; S. 277 - 278.



Kurzfassung englisch:
We present a new, concurrent, lock-free priority queue that relaxes the delete-min operation to allow deletion of any of the ρ smallest keys instead of only a minimal one, where ρ is a parameter that can be configured at runtime. It is built from a logarithmic number of sorted arrays, similar to log-structured merge-trees (LSM). For keys added and removed by the same thread the behavior is identical to a non-relaxed priority queue. We compare to state-of-the-art lock-free priority queues with both relaxed and non-relaxed semantics, showing high performance and good scalability of our approach.

Schlagworte:
Task-parallel programming, priority-queue, concurrent data structure relaxation, shared memory


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1145/2688500.2688547


Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.