[{"oa_version":"Published Version","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."}],"month":"04","scopus_import":"1","file":[{"file_id":"11731","checksum":"8ceea411fa133795cd4903529498eb6b","success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2022-08-05T09:19:29Z","file_name":"2022_PPoPP_Brown.pdf","creator":"dernst","date_updated":"2022-08-05T09:19:29Z","file_size":1128343}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781450392044"]},"publication_status":"published","_id":"11181","status":"public","type":"conference","conference":{"name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming","start_date":"2022-04-02","end_date":"2022-04-06","location":"Seoul, Republic of Korea"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["000"],"date_updated":"2023-08-03T06:49:20Z","file_date_updated":"2022-08-05T09:19:29Z","department":[{"_id":"DaAl"}],"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.","quality_controlled":"1","publisher":"Association for Computing Machinery","oa":1,"day":"02","publication":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","has_accepted_license":"1","isi":1,"year":"2022","date_published":"2022-04-02T00:00:00Z","doi":"10.1145/3503221.3508410","date_created":"2022-04-17T22:01:46Z","page":"385-399","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"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.","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","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.","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.","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.","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."},"title":"PathCAS: An efficient middle ground for concurrent search data structures","author":[{"full_name":"Brown, Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A"},{"first_name":"William","last_name":"Sigouin","full_name":"Sigouin, William"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"}],"external_id":{"isi":["000883318200027"]},"article_processing_charge":"No"},{"oa":1,"publisher":"Association for Computing Machinery","quality_controlled":"1","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).","date_created":"2022-04-17T22:01:46Z","doi":"10.1145/3503221.3508432","date_published":"2022-04-02T00:00:00Z","page":"353-367","publication":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","day":"02","year":"2022","isi":1,"project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"title":"Multi-queues can be state-of-the-art priority schedulers","article_processing_charge":"No","external_id":{"isi":["000883318200025"],"arxiv":["2109.00657"]},"author":[{"full_name":"Postnikova, Anastasiia","last_name":"Postnikova","first_name":"Anastasiia"},{"id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita","full_name":"Koval, Nikita","last_name":"Koval"},{"full_name":"Nadiradze, Giorgi","last_name":"Nadiradze","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi"},{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"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.","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","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","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.","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.","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.","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."},"month":"04","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2109.00657","open_access":"1"}],"scopus_import":"1","oa_version":"Preprint","abstract":[{"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.","lang":"eng"}],"ec_funded":1,"related_material":{"record":[{"relation":"research_data","id":"13076","status":"public"}]},"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["9781450392044"]},"status":"public","conference":{"start_date":"2022-04-02","location":"Seoul, Republic of Korea","end_date":"2022-04-06","name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming"},"type":"conference","_id":"11180","department":[{"_id":"DaAl"}],"date_updated":"2023-08-03T06:48:35Z"}]