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
1993681722 1967362387 1992754027 2142561263
This paper introduces the Parallel Priority Queue (PPQ) abstract data type. A PPQ stores a set of integer-valued items andprovides operations such as insertion of n new items or deletion of the n smallest ones. Algorithms for realizing PPQ operations on an n-processor CREW-PRAM are based on two new data structures, the n-Bandwidth-Heap (n.-H) and the n-Bandwidth-Leftist-Heap (n-L), that are obtained as extensions of the well-known sequential binary-heap and leftist-heap, respectively. Using these structures, it is shown that insertion of n new items in a PPQ of m elements can be performed in parallel time O(h +log n), where h = log(m n), while deletion of the n smallest items can be performed in time O(h+ log log n). 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. Load balanced parallel radix sort solved the load imbalance problem present in parallel radix sort. By redistributing the keys in each round of radix, each processor has exactly the same number of keys, thereby reducing the overall sorting time. Load balanced radix sort is currently known as the fastest internal sorting method for distributed-memory multiprocessors. However, as the computation time is balanced, the communication time emerges as the bottleneck of the overall sorting performance due to key redistribution. We present in this report a new parallel radix sorter that solves the communication problem of balanced radix sort, called partitioned parallel radix sort. The new method reduces the communication time by eliminating the redistribution steps. The keys are first sorted in a top-down fashion (left-to-right as opposed to right-to-left) by using some most significant bits. Once the keys are localized to each processor, the rest of sorting is confined within each processor, hence eliminating the need for global redistribution of keys. It enables well balanced communication and computation across processors. The proposed method has been implemented in three different distributed-memory platforms, including IBM SP2, Cray T3E, and PC Cluster. Experimental results with various key distributions indicate that partitioned parallel radix sort indeed shows significant improvements over balanced radix sort. IBM SP2 shows 13 to 30 improvement while Cray SGI T3E does 20 to 100 in execution time. PC cluster shows over 2.4-fold improvement in execution time. We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log*n) time andn2 logn processors. We generalize this to obtain anO (logn log*n)-time algorithm usingnd logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.