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.
In the 1990s, many PPQs were developed for the PRAM. Pinotti and Pucci proposed @math -bandwidth-heaps @cite_1 , which store @math sorted items in a heap node, and allow bulk insertion and extraction of @math items by sorting and merging using an @math -processor CREW-PRAM. Similarly, Deo and Prasad describe a parallel heap @cite_15 , which allows insertion and extractions of @math items with @math processors by using more advanced PRAM algorithms. @cite_10 extend these ideas to allow of @math arbitrary elements in @math time and @math work on an EREW-PRAM. Sanders @cite_25 developed a randomized PPQ for @math distributed memory machines, where each processor keeps a set of local elements and insertions are randomly distributed among the processors. The PPQ's operation retrieves the @math globally smallest elements, one per processor, using an exchange algorithm with probabilistic time guarantees.
@cite_10 @cite_15 @cite_1 @cite_25
2003969379 1967362387 2003898228
We present a parallel priority queue that supports the following operations in constant time:parallel insertionof a sequence of elements ordered according to key,parallel decrease keyfor a sequence of elements ordered according to key,deletion of the minimum key element, anddeletion of an arbitrary element. Our data structure is the first to support multi-insertion and multi-decrease key in constant time. The priority queue can be implemented on the EREW PRAM and can perform any sequence ofnoperations inO(n) time andO(mlogn) work,mbeing the total number of keyes inserted and or updated. A main application is a parallel implementation of Dijkstra's algorithm for the single-source shortest path problem, which runs inO(n) time andO(mlogn) work on a CREW PRAM on graphs withnvertices andmedges. This is a logarithmic factor improvement in the running time compared with previous approaches. We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of θ(p) highest priority items and insertions of θ(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n. We present simple randomized algorithms for parallel priority queues on distributed memory machines. Inserting O(n) elements or deleting the O(n) out ofmsmallest elements usingnprocessors requires O(Tcoll+ log(m n)) amortized time with high probability whereTcollbounds the time for performing prefix sums and randomized routing. The memory requirement is bounded by (m n)(1 +o(1)) + O(logn) whp. These bounds are an improvement over the best previously known algorithms for many interconnection networks and even matches the speed of the best known PRAM algorithms. Generalizations for accessing thek?nsmallest elements are even more efficient. A portable implementation using MPI demonstrates that our approach is already useful for medium scale parallelism. Two parallel selection algorithms for randomly placed data are a spin-off. One runs in time O(Tcoll) with high probability, beating a lower bound for the worst case. The other requires only a single reduction operation.