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.
The only previous attempt at parallelizing a PQ for EM, that we could find in literature, was done in conjunction with a study of asynchronous pipelining in STXXL @cite_13 . They partially parallelized the sequence heap without touching the sequential PQ semantics. However, this gives only little opportunity for parallelization -- mostly for merging in groups with large external arrays.
@cite_13
2144022036
Large and fast hard disks for little money have enabled the processing of huge amounts of data on a single machine. For this purpose, the well-established STXXL library provides a framework for external memory algorithms with an easy-to-use interface. However, the clock speed of processors cannot keep up with the increasing bandwidth of parallel disks, making many algorithms actually compute-bound.