The SprayList: a scalable relaxed priority queue
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 access...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/101058 https://orcid.org/0000-0003-2062-0998 https://orcid.org/0000-0002-9937-0049 https://orcid.org/0000-0002-4552-2414 |
| _version_ | 1811076304523493376 |
|---|---|
| author | Alistarh, Dan Kopinsky, Justin Li, Jerry Zheng Shavit, Nir N. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Alistarh, Dan Kopinsky, Justin Li, Jerry Zheng Shavit, Nir N. |
| author_sort | Alistarh, Dan |
| collection | MIT |
| description | 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[superscript 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[superscript 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. |
| first_indexed | 2024-09-23T10:19:33Z |
| format | Article |
| id | mit-1721.1/101058 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:19:33Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1010582022-09-26T17:14:49Z The SprayList: a scalable relaxed priority queue Alistarh, Dan Kopinsky, Justin Li, Jerry Zheng Shavit, Nir N. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kopinsky, Justin Li, Jerry Zheng Shavit, Nir N. 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[superscript 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[superscript 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. National Science Foundation (U.S.) (Grant CCF-1217921) National Science Foundation (U.S.) (Grant CCF-1301926) National Science Foundation (U.S.) (Grant IIS-1447786) United States. Dept. of Energy (Grant ER26116/DE-SC0008923) Oracle Corporation Intel Corporation 2016-02-02T13:02:12Z 2016-02-02T13:02:12Z 2015-02 Article http://purl.org/eprint/type/ConferencePaper 9781450332057 http://hdl.handle.net/1721.1/101058 Dan Alistarh, Justin Kopinsky, Jerry Li, and Nir Shavit. 2015. The SprayList: a scalable relaxed priority queue. SIGPLAN Not. 50, 8 (January 2015), 11-20. https://orcid.org/0000-0003-2062-0998 https://orcid.org/0000-0002-9937-0049 https://orcid.org/0000-0002-4552-2414 en_US http://dx.doi.org/10.1145/2688500.2688523 Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2015) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Alistarh, Dan Kopinsky, Justin Li, Jerry Zheng Shavit, Nir N. The SprayList: a scalable relaxed priority queue |
| title | The SprayList: a scalable relaxed priority queue |
| title_full | The SprayList: a scalable relaxed priority queue |
| title_fullStr | The SprayList: a scalable relaxed priority queue |
| title_full_unstemmed | The SprayList: a scalable relaxed priority queue |
| title_short | The SprayList: a scalable relaxed priority queue |
| title_sort | spraylist a scalable relaxed priority queue |
| url | http://hdl.handle.net/1721.1/101058 https://orcid.org/0000-0003-2062-0998 https://orcid.org/0000-0002-9937-0049 https://orcid.org/0000-0002-4552-2414 |
| work_keys_str_mv | AT alistarhdan thespraylistascalablerelaxedpriorityqueue AT kopinskyjustin thespraylistascalablerelaxedpriorityqueue AT lijerryzheng thespraylistascalablerelaxedpriorityqueue AT shavitnirn thespraylistascalablerelaxedpriorityqueue AT alistarhdan spraylistascalablerelaxedpriorityqueue AT kopinskyjustin spraylistascalablerelaxedpriorityqueue AT lijerryzheng spraylistascalablerelaxedpriorityqueue AT shavitnirn spraylistascalablerelaxedpriorityqueue |