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.
External memory PQs are a well-established field, and one can choose from different I O optimal designs. The older theoretical designs @cite_24 involve complex buffering of insertion and deletion to reach optimal @math amortized I O complexity, and the hidden constants are high. By using buffered multiway merging of pre-sorted EM lists @cite_23 , the theoretical algorithms were soon simplified. In 1999, @cite_3 carried out an experimental study of PQs in EM that resulted in two very practical external memory PQ designs.
@cite_24 @cite_3 @cite_23
2088116875 2138648789
We present a technique for designing external memory data structures that support batched operations I O efficiently. We show how the technique can be used to develop external versions of a search tree, a priority queue, and a segment tree, and give examples of how these structures can be used to develop I O-efficient algorithms. The developed algorithms are either extremely simple or straightforward generalizations of known internal memory algorithms—given the developed external data structures. In this paper we compare the performance of eight different priority queue implementations: four of them are explicitly designed to work in an external-memory setting, the others are standard internal-memory queues available in the LEDA library [Mehlhorn and Naher 1999]. Two of the external-memory priority queues are obtained by engineering known internal-memory priority queues with the aim of achieving effective performance on external storage devices (i.e., Radix heaps [ 1990] and array heaps [Thorup 1996]). Our experimental framework includes some simple tests, like random sequences of insert or delete-minimum operations, as well as more advanced tests consisting of intermixed sequences of update operations and "application driven" update sequences originated by simulations of Dijkstra's algorithm on large graph instances. Our variegate spectrum of experimental results gives a good picture of the features of these priority queues, thus being helpful to anyone interested in the use of such data structures on very large data sets.