---
_id: '11180'
abstract:
- lang: eng
text: "Designing and implementing efficient parallel priority schedulers is an active
research area. An intriguing proposed design is the Multi-Queue: given n threads
and m ≥ n distinct priority queues, task insertions are performed uniformly at
random, while, to delete, a thread picks two queues uniformly at random, and removes
the observed task of higher priority. This approach scales well, and has probabilistic
rank guarantees: roughly, the rank of each task removed, relative to remaining
tasks in all other queues, is O (m) in expectation. Yet, the performance of this
pattern is below that of well-engineered schedulers, which eschew theoretical
guarantees for practical efficiency.\r\n\r\nWe investigate whether it is possible
to design and implement a Multi-Queue-based task scheduler that is both highly-efficient
and has analytical guarantees. We propose a new variant called the Stealing Multi-Queue
(SMQ), a cache-efficient variant of the Multi-Queue, which leverages both queue
affinity---each thread has a local queue, from which tasks are usually removed;
but, with some probability, threads also attempt to steal higher-priority tasks
from the other queues---and task batching, that is, the processing of several
tasks in a single insert / remove step. These ideas are well-known for task scheduling
without priorities; our theoretical contribution is showing that, despite relaxations,
this design can still provide rank guarantees, which in turn implies bounds on
total work performed. We provide a general SMQ implementation which can surpass
state-of-the-art schedulers such as OBIM and PMOD in terms of performance on popular
graph-processing benchmarks. Notably, the performance improvement comes mainly
from the superior rank guarantees provided by our scheduler, confirming that analytically-reasoned
approaches can still provide performance improvements for priority task scheduling."
acknowledgement: We would like to thank the anonymous reviewers for their useful comments.
This project has received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (grant agreement
No 805223 ScaleML).
article_processing_charge: No
arxiv: 1
author:
- first_name: Anastasiia
full_name: Postnikova, Anastasiia
last_name: Postnikova
- first_name: Nikita
full_name: Koval, Nikita
id: 2F4DB10C-F248-11E8-B48F-1D18A9856A87
last_name: Koval
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Postnikova A, Koval N, Nadiradze G, Alistarh D-A. Multi-queues can be state-of-the-art
priority schedulers. In: Proceedings of the 27th ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming. Association for Computing Machinery;
2022:353-367. doi:10.1145/3503221.3508432'
apa: 'Postnikova, A., Koval, N., Nadiradze, G., & Alistarh, D.-A. (2022). Multi-queues
can be state-of-the-art priority schedulers. In Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp.
353–367). Seoul, Republic of Korea: Association for Computing Machinery. https://doi.org/10.1145/3503221.3508432'
chicago: Postnikova, Anastasiia, Nikita Koval, Giorgi Nadiradze, and Dan-Adrian
Alistarh. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” In Proceedings
of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
353–67. Association for Computing Machinery, 2022. https://doi.org/10.1145/3503221.3508432.
ieee: A. Postnikova, N. Koval, G. Nadiradze, and D.-A. Alistarh, “Multi-queues can
be state-of-the-art priority schedulers,” in Proceedings of the 27th ACM SIGPLAN
Symposium on Principles and Practice of Parallel Programming, Seoul, Republic
of Korea, 2022, pp. 353–367.
ista: 'Postnikova A, Koval N, Nadiradze G, Alistarh D-A. 2022. Multi-queues can
be state-of-the-art priority schedulers. Proceedings of the 27th ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles
and Practice of Parallel Programming, 353–367.'
mla: Postnikova, Anastasiia, et al. “Multi-Queues Can Be State-of-the-Art Priority
Schedulers.” Proceedings of the 27th ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming, Association for Computing Machinery, 2022,
pp. 353–67, doi:10.1145/3503221.3508432.
short: A. Postnikova, N. Koval, G. Nadiradze, D.-A. Alistarh, in:, Proceedings of
the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
Association for Computing Machinery, 2022, pp. 353–367.
conference:
end_date: 2022-04-06
location: Seoul, Republic of Korea
name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
start_date: 2022-04-02
date_created: 2022-04-17T22:01:46Z
date_published: 2022-04-02T00:00:00Z
date_updated: 2023-08-03T06:48:35Z
day: '02'
department:
- _id: DaAl
doi: 10.1145/3503221.3508432
ec_funded: 1
external_id:
arxiv:
- '2109.00657'
isi:
- '000883318200025'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2109.00657'
month: '04'
oa: 1
oa_version: Preprint
page: 353-367
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice
of Parallel Programming
publication_identifier:
isbn:
- '9781450392044'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '13076'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Multi-queues can be state-of-the-art priority schedulers
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2022'
...
---
_id: '11181'
abstract:
- lang: eng
text: 'To maximize the performance of concurrent data structures, researchers have
often turned to highly complex fine-grained techniques, resulting in efficient
and elegant algorithms, which can however be often difficult to understand and
prove correct. While simpler techniques exist, such as transactional memory, they
can have limited performance or portability relative to their fine-grained counterparts.
Approaches at both ends of this complexity-performance spectrum have been extensively
explored, but relatively less is known about the middle ground: approaches that
are willing to sacrifice some performance for simplicity, while remaining competitive
with state-of-the-art handcrafted designs. In this paper, we explore this middle
ground, and present PathCAS, a primitive that combines ideas from multi-word CAS
(KCAS) and transactional memory approaches, while carefully avoiding overhead.
We show how PathCAS can be used to implement efficient search data structures
relatively simply, using an internal binary search tree as an example, then extending
this to an AVL tree. Our best implementations outperform many handcrafted search
trees: in search-heavy workloads, it rivals the BCCO tree [5], the fastest known
concurrent binary tree in terms of search performance [3]. Our results suggest
that PathCAS can yield concurrent data structures that are relatively easy to
build and prove correct, while offering surprisingly high performance.'
acknowledgement: "This work was supported by: the Natural Sciences and Engineering
Research Council of Canada (NSERC) Collaborative Research and Development grant:
CRDPJ 539431-19, the\r\nCanada Foundation for Innovation John R. Evans Leaders Fund
with equal support from the Ontario Research Fund CFI Leaders Opportunity Fund:
38512, Waterloo Huawei Joint Innovation Lab project “Scalable Infrastructure for
Next Generation Data Management Systems”, NSERC Discovery Launch Supplement: DGECR-2019-00048,
NSERC Discovery\r\nProgram under the grants: RGPIN-2019-04227 and RGPIN04512-2018,
and the University of Waterloo. We would also like to thank the reviewers for their
insightful comments."
article_processing_charge: No
author:
- first_name: Trevor A
full_name: Brown, Trevor A
id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
last_name: Brown
- first_name: William
full_name: Sigouin, William
last_name: Sigouin
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Brown TA, Sigouin W, Alistarh D-A. PathCAS: An efficient middle ground for
concurrent search data structures. In: Proceedings of the 27th ACM SIGPLAN
Symposium on Principles and Practice of Parallel Programming. Association
for Computing Machinery; 2022:385-399. doi:10.1145/3503221.3508410'
apa: 'Brown, T. A., Sigouin, W., & Alistarh, D.-A. (2022). PathCAS: An efficient
middle ground for concurrent search data structures. In Proceedings of the
27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
(pp. 385–399). Seoul, Republic of Korea: Association for Computing Machinery.
https://doi.org/10.1145/3503221.3508410'
chicago: 'Brown, Trevor A, William Sigouin, and Dan-Adrian Alistarh. “PathCAS: An
Efficient Middle Ground for Concurrent Search Data Structures.” In Proceedings
of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,
385–99. Association for Computing Machinery, 2022. https://doi.org/10.1145/3503221.3508410.'
ieee: 'T. A. Brown, W. Sigouin, and D.-A. Alistarh, “PathCAS: An efficient middle
ground for concurrent search data structures,” in Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming, Seoul,
Republic of Korea, 2022, pp. 385–399.'
ista: 'Brown TA, Sigouin W, Alistarh D-A. 2022. PathCAS: An efficient middle ground
for concurrent search data structures. Proceedings of the 27th ACM SIGPLAN Symposium
on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles
and Practice of Parallel Programming, 385–399.'
mla: 'Brown, Trevor A., et al. “PathCAS: An Efficient Middle Ground for Concurrent
Search Data Structures.” Proceedings of the 27th ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming, Association for Computing Machinery,
2022, pp. 385–99, doi:10.1145/3503221.3508410.'
short: T.A. Brown, W. Sigouin, D.-A. Alistarh, in:, Proceedings of the 27th ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association
for Computing Machinery, 2022, pp. 385–399.
conference:
end_date: 2022-04-06
location: Seoul, Republic of Korea
name: 'PPoPP: Sympopsium on Principles and Practice of Parallel Programming'
start_date: 2022-04-02
date_created: 2022-04-17T22:01:46Z
date_published: 2022-04-02T00:00:00Z
date_updated: 2023-08-03T06:49:20Z
day: '02'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3503221.3508410
external_id:
isi:
- '000883318200027'
file:
- access_level: open_access
checksum: 8ceea411fa133795cd4903529498eb6b
content_type: application/pdf
creator: dernst
date_created: 2022-08-05T09:19:29Z
date_updated: 2022-08-05T09:19:29Z
file_id: '11731'
file_name: 2022_PPoPP_Brown.pdf
file_size: 1128343
relation: main_file
success: 1
file_date_updated: 2022-08-05T09:19:29Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 385-399
publication: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice
of Parallel Programming
publication_identifier:
isbn:
- '9781450392044'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'PathCAS: An efficient middle ground for concurrent search data structures'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2022'
...