panthema / 2015 / 0629-SEA-Conference-Talk-Bulk-Parallel-Priority-Queue
First slide of the talk showing priority queues at the airport

Presentation of Parallel Priority Queue at the Conference SEA'2015

Posted on 2015-06-30 17:11 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ talk stxxl

We are very glad to have been given the opportunity to present our work on bulk-parallel priority queues for external memory at the 14th International Symposium on Experimental Algorithms (SEA 2015) in Paris. Our paper is in the proceedings and also available here: paper-SEA15-Bulk-Parallel-Priority-Queue.pdf paper-SEA15-Bulk-Parallel-Priority-Queue.pdf

The talk was given by Thomas Keh, and the slides of the presentation are available online: 2015-06-29 A Bulk-Parallel Priority Queue in External Memory with STXXL.pdf 2015-06-29 A Bulk-Parallel Priority Queue in External Memory with STXXL.pdf. The implementation is available in the current master branch of STXXL at github.

Download 2015-06-29 A Bulk-Parallel Priority Queue in External Memory with STXXL.pdf


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 64% of the full parallel I/O bandwidth of SSDs and 49% of rotational disks, 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.