A Lock-Free Priority Queue Design Based On Multi-Dimensional Linked Lists

Keywords

Concurrent Data Structure; Lock-freedom; Multi-dimensional List; Priority Queue; Skiplist

Abstract

The throughput of concurrent priority queues is pivotal to multiprocessor applications such as discrete event simulation, best-first search and task scheduling. Existing lock-free priority queues are mostly based on skiplists, which probabilistically create shortcuts in an ordered list for fast insertion of elements. The use of skiplists eliminates the need of global rebalancing in balanced search trees and ensures logarithmic sequential search time on average, but the worst-case performance is linear with respect to the input size. In this paper, we propose a quiescently consistent lock-free priority queue based on a multi-dimensional list that guarantees worst-case search time of O(\log N) for key universe of size N. The novel multi-dimensional list (MDList) is composed of nodes that contain multiple links to child nodes arranged by their dimensionality. The insertion operation works by first injectively mapping the scalar key to a high-dimensional vector, then uniquely locating the target position by using the vector as coordinates. Nodes in MDList are ordered by their coordinate prefixes and the ordering property of the data structure is readily maintained during insertion without rebalancing nor randomization. In our experimental evaluation using a micro-benchmark, our priority queue achieves an average of 50 percent speedup over the state of the art approaches under high concurrency.

Publication Date

3-1-2016

Publication Title

IEEE Transactions on Parallel and Distributed Systems

Volume

27

Issue

3

Number of Pages

613-626

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/TPDS.2015.2419651

Socpus ID

84962621226 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84962621226

This document is currently not available here.

Share

COinS