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.
Recently, interest has arisen in PPQs @cite_5 @cite_11 @cite_21 , since the performance of concurrent PQs does not scale with the higher number of processors available in newer machines. Instead of returning smallest item(s), relaxed PPQs return smallest items, and the quality of the relaxed PPQs is measured by both performance and the introduced errors. Bulk-parallel PQs can be viewed as synchronous relaxed PQs with simple and clear semantics.
@cite_5 @cite_21 @cite_11
2082679906 2132473764 1802414416
There is a trade-off between performance and correctness in implementing concurrent data structures. Better performance may be achieved at the expense of relaxing correctness, by redefining the semantics of data structures. We address such a redefinition of data structure semantics and present a systematic and formal framework for obtaining new data structures by quantitatively relaxing existing ones. We view a data structure as a sequential specification S containing all "legal" sequences over an alphabet of method calls. Relaxing the data structure corresponds to defining a distance from any sequence over the alphabet to the sequential specification: the k-relaxed sequential specification contains all sequences over the alphabet within distance k from the original specification. In contrast to other existing work, our relaxations are semantic (distance in terms of data structure states). As an instantiation of our framework, we present two simple yet generic relaxation schemes, called out-of-order and stuttering relaxation, along with several ways of computing distances. We show that the out-of-order relaxation, when further instantiated to stacks, queues, and priority queues, amounts to tolerating bounded out-of-order behavior, which cannot be captured by a purely syntactic relaxation (distance in terms of sequence manipulation, e.g. edit distance). We give concurrent implementations of relaxed data structures and demonstrate that bounded relaxations provide the means for trading correctness for performance in a controlled way. The relaxations are monotonic which further highlights the trade-off: increasing k increases the number of permitted sequences, which as we demonstrate can lead to better performance. Finally, since a relaxed stack or queue also implements a pool, we actually have new concurrent pool implementations that outperform the state-of-the-art ones. High-performance concurrent priority queues are essential for applications such as task scheduling and discrete event simulation. Unfortunately, even the best performing implementations do not scale past a number of threads in the single digits. This is because of the sequential bottleneck in accessing the elements at the head of the queue in order to perform a DeleteMin operation. In this paper, we present the SprayList, a scalable priority queue with relaxed ordering semantics. Starting from a non-blocking SkipList, the main innovation behind our design is that the DeleteMin operations avoid a sequential bottleneck by spraying'' themselves onto the head of the SkipList list in a coordinated fashion. The spraying is implemented using a carefully designed random walk, so that DeleteMin returns an element among the first O(p log^3 p) in the list, with high probability, where p is the number of threads. We prove that the running time of a DeleteMin operation is O(log^3 p), with high probability, independent of the size of the list. Our experiments show that the relaxed semantics allow the data structure to scale for high thread counts, comparable to a classic unordered SkipList. Furthermore, we observe that, for reasonably parallel workloads, the scalability benefits of relaxation considerably outweigh the additional work due to out-of-order execution. AbstractPriority queues with parallel access are an attractive data structure for ap-plications like prioritized online scheduling, discrete event simulation, or branch-and-bound. However, a classical priority queue constitutes a severe bottleneck inthis context, leading to very small throughput. Hence, there has been signi cantinterest in concurrent priority queues with a somewhat relaxed semantics wheredeleted elements only need to be close to the minimum. In this paper we presenta very simple approach based on multiple sequential priority queues. It turns outto outperform previous more complicated data structures while at the same timeimproving the quality of the returned elements. 1 Introduction Priority queues are a fundamental data structure with many applications. Priority queuesmanage a set of elements and support the operations for inserting elements and deletingthe smallest element (deleteMin). Whenever we have to dynamically reorder operationsperformed by an algorithm, priority queues can turn out to be useful. Examples includegraph algorithms for shortest paths and minimum spanning trees, discrete event simu-lation, best rst branch-and-bound, and other best rst heuristics. In particular, manysuccessful job scheduling algorithms are of that type. The latter application was the start-ing point for this work focusing on scheduling of jobs with priorities in data managementsystems to support quality of service guarantees (Service Level Agreements).On modern parallel hardware, we often have the situation that p parallel threads(or PEs for processing elements) want to access the priority queue concurrently. This