panthema / 2015 / 0402-A-Bulk-Parallel-Priority-Queue-in-External-Memory-with-STXXL
Two figures from the technical report

A Bulk-Parallel Priority Queue in External Memory with STXXL

Posted on 2015-04-03 14:54 by Timo Bingmann at Permlink with 0 Comments. Tags: #research #stxxl

Today, our technical report on "A Bulk-Parallel Priority Queue in External Memory with STXXL" is now available on arXiv as 1504.00545 or locally: 1504.00545v1.pdf 1504.00545v1.pdf with source 1504.00545v1.tar.gz 1504.00545v1.tar.gz (130 KiB). A big thanks goes to Thomas Keh for the hard work he did in his bachelor thesis, and to Peter Sanders for all the insights into priority queues. The technical report is an extended version of our paper that will appear at the 14th International Symposium on Experimental Algorithms - SEA 2015.

Download 1504.00545v1.pdf

The bulk-parallel priority queue is current available in the development repository of STXXL on Github.

On 2015-06-29, Thomas Keh presented the PPQ at SEA'15 in Paris.


We propose the design and an implementation of a bulk-parallel external memory priority queue to take advantage of both shared-memory parallelism and high external memory transfer speeds to parallel disks. To achieve higher performance by decoupling item insertions and extractions, we offer two parallelization interfaces: one using "bulk" sequences, the other by defining "limit" items. In the design, we discuss how to parallelize insertions using multiple heaps, and how to calculate a dynamic prediction sequence to prefetch blocks and apply parallel multiway merge for extraction. Our experimental results show that in the selected benchmarks the priority queue reaches 75% of the full parallel I/O bandwidth of rotational disks and and 65% of SSDs, or the speed of sorting in external memory when bounded by computation.

Post Comment
E-Mail or Homepage:

URLs (http://...) are displayed, e-mails are hidden and used for Gravatar.

Many common HTML elements are allowed in the text, but no CSS style.