Title: MultiQueues: Simpler, Faster, and Better Relaxed Concurrent Priority Queues
Abstract: 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
Publication Year: 2014
Publication Date: 2014-11-05
Language: en
Type: preprint
Access and Citation
Cited By Count: 11
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot