[Back]


Talks and Poster Presentations (with Proceedings-Entry):

J. Gruber, J. Träff, M. Wimmer:
"Brief Announcement: Benchmarking Concurrent Priority Queues";
Talk: 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), Asilomar State Beach, California, USA; 2016-07-11 - 2016-07-13; in: "Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016)", ACM, New York, NY, USA (2016), ISBN: 978-1-4503-4210-0; 361 - 362.



English abstract:
A number of concurrent, relaxed priority queues have recently been proposed and implemented. Results are commonly reported for a throughput benchmark that uses a uniform distribution of keys from a large integer range, a balanced mixture of operations, and mostly for single systems. We have conducted more extensive benchmarking of three recent, relaxed priority queues on four different types of systems with different key ranges and distributions. While we can show superior throughput and scalability for our own k-LSM priority queue for the uniform key distribution, the picture changes drastically for other distributions, both with respect to achieved throughput and relative merit of the priority queues. The throughput benchmark alone is thus not sufficient to characterize the performance of concurrent priority queues. Our priority queue, benchmark code and full set of results are publicly available to foster comparison.

Keywords:
Priority Queues, Concurrency, Relaxation, Benchmarking


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1145/2935764.2935803