[{"page":"107-118","date_created":"2023-03-19T23:00:58Z","doi":"10.1145/3572848.3577481","date_published":"2023-02-25T00:00:00Z","year":"2023","publication_status":"published","publication_identifier":{"isbn":["9798400700156"]},"publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","language":[{"iso":"eng"}],"day":"25","oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2211.04986"}],"quality_controlled":"1","scopus_import":"1","publisher":"Association for Computing Machinery","month":"02","abstract":[{"lang":"eng","text":"Asynchronous programming has gained significant popularity over the last decade: support for this programming pattern is available in many popular languages via libraries and native language implementations, typically in the form of coroutines or the async/await construct. Instead of programming via shared memory, this concept assumes implicit synchronization through message passing. The key data structure enabling such communication is the rendezvous channel. Roughly, a rendezvous channel is a blocking queue of size zero, so both send(e) and receive() operations wait for each other, performing a rendezvous when they meet. To optimize the message passing pattern, channels are usually equipped with a fixed-size buffer, so sends do not suspend and put elements into the buffer until its capacity is exceeded. This primitive is known as a buffered channel.\r\n\r\nThis paper presents a fast and scalable algorithm for both rendezvous and buffered channels. Similarly to modern queues, our solution is based on an infinite array with two positional counters for send(e) and receive() operations, leveraging the unconditional Fetch-And-Add instruction to update them. Yet, the algorithm requires non-trivial modifications of this classic pattern, in order to support the full channel semantics, such as buffering and cancellation of waiting requests. We compare the performance of our solution to that of the Kotlin implementation, as well as against other academic proposals, showing up to 9.8× speedup. To showcase its expressiveness and performance, we also integrated the proposed algorithm into the standard Kotlin Coroutines library, replacing the previous channel implementations."}],"oa_version":"Preprint","external_id":{"arxiv":["2211.04986"]},"article_processing_charge":"No","author":[{"last_name":"Koval","full_name":"Koval, Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita"},{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"full_name":"Elizarov, Roman","last_name":"Elizarov","first_name":"Roman"}],"title":"Fast and scalable channels in Kotlin Coroutines","department":[{"_id":"DaAl"}],"date_updated":"2023-03-20T07:29:28Z","citation":{"chicago":"Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Fast and Scalable Channels in Kotlin Coroutines.” In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 107–18. Association for Computing Machinery, 2023. https://doi.org/10.1145/3572848.3577481.","ista":"Koval N, Alistarh D-A, Elizarov R. 2023. Fast and scalable channels in Kotlin Coroutines. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles and Practice of Parallel Programming, 107–118.","mla":"Koval, Nikita, et al. “Fast and Scalable Channels in Kotlin Coroutines.” Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2023, pp. 107–18, doi:10.1145/3572848.3577481.","ama":"Koval N, Alistarh D-A, Elizarov R. Fast and scalable channels in Kotlin Coroutines. In: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery; 2023:107-118. doi:10.1145/3572848.3577481","apa":"Koval, N., Alistarh, D.-A., & Elizarov, R. (2023). Fast and scalable channels in Kotlin Coroutines. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp. 107–118). Montreal, QC, Canada: Association for Computing Machinery. https://doi.org/10.1145/3572848.3577481","short":"N. Koval, D.-A. Alistarh, R. Elizarov, in:, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2023, pp. 107–118.","ieee":"N. Koval, D.-A. Alistarh, and R. Elizarov, “Fast and scalable channels in Kotlin Coroutines,” in Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Montreal, QC, Canada, 2023, pp. 107–118."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2023-02-25","location":"Montreal, QC, Canada","end_date":"2023-03-01","name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming"},"type":"conference","status":"public","_id":"12735"},{"article_number":"116","title":"CQS: A formally-verified framework for fair and abortable synchronization","article_processing_charge":"No","author":[{"id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita","full_name":"Koval, Nikita","last_name":"Koval"},{"full_name":"Khalanskiy, Dmitry","last_name":"Khalanskiy","first_name":"Dmitry"},{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Koval, Nikita, et al. “CQS: A Formally-Verified Framework for Fair and Abortable Synchronization.” Proceedings of the ACM on Programming Languages, vol. 7, 116, Association for Computing Machinery , 2023, doi:10.1145/3591230.","ieee":"N. Koval, D. Khalanskiy, and D.-A. Alistarh, “CQS: A formally-verified framework for fair and abortable synchronization,” Proceedings of the ACM on Programming Languages, vol. 7. Association for Computing Machinery , 2023.","short":"N. Koval, D. Khalanskiy, D.-A. Alistarh, Proceedings of the ACM on Programming Languages 7 (2023).","apa":"Koval, N., Khalanskiy, D., & Alistarh, D.-A. (2023). CQS: A formally-verified framework for fair and abortable synchronization. Proceedings of the ACM on Programming Languages. Association for Computing Machinery . https://doi.org/10.1145/3591230","ama":"Koval N, Khalanskiy D, Alistarh D-A. CQS: A formally-verified framework for fair and abortable synchronization. Proceedings of the ACM on Programming Languages. 2023;7. doi:10.1145/3591230","chicago":"Koval, Nikita, Dmitry Khalanskiy, and Dan-Adrian Alistarh. “CQS: A Formally-Verified Framework for Fair and Abortable Synchronization.” Proceedings of the ACM on Programming Languages. Association for Computing Machinery , 2023. https://doi.org/10.1145/3591230.","ista":"Koval N, Khalanskiy D, Alistarh D-A. 2023. CQS: A formally-verified framework for fair and abortable synchronization. Proceedings of the ACM on Programming Languages. 7, 116."},"oa":1,"publisher":"Association for Computing Machinery ","quality_controlled":"1","date_created":"2023-07-02T22:00:43Z","doi":"10.1145/3591230","date_published":"2023-06-06T00:00:00Z","publication":"Proceedings of the ACM on Programming Languages","day":"06","year":"2023","has_accepted_license":"1","status":"public","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)"},"type":"journal_article","article_type":"original","_id":"13179","department":[{"_id":"DaAl"}],"file_date_updated":"2023-07-03T13:09:39Z","ddc":["000"],"date_updated":"2023-07-17T08:43:19Z","intvolume":" 7","month":"06","scopus_import":"1","oa_version":"Published Version","abstract":[{"lang":"eng","text":"Writing concurrent code that is both correct and efficient is notoriously difficult. Thus, programmers often prefer to use synchronization abstractions, which render code simpler and easier to reason about. Despite a wealth of work on this topic, there is still a gap between the rich semantics provided by synchronization abstractions in modern programming languages—specifically, fair FIFO ordering of synchronization requests and support for abortable operations—and frameworks for implementing it correctly and efficiently. Supporting such semantics is critical given the rising popularity of constructs for asynchronous programming, such as coroutines, which abort frequently and are cheaper to suspend and resume compared to native threads.\r\n\r\nThis paper introduces a new framework called CancellableQueueSynchronizer (CQS), which enables simple yet efficient implementations of a wide range of fair and abortable synchronization primitives: mutexes, semaphores, barriers, count-down latches, and blocking pools. Our main contribution is algorithmic, as implementing both fairness and abortability efficiently at this level of generality is non-trivial. Importantly, all our algorithms, including the CQS framework and the primitives built on top of it, come with formal proofs in the Iris framework for Coq for many of their properties. These proofs are modular, so it is easy to show correctness for new primitives implemented on top of CQS. From a practical perspective, implementation of CQS for native threads on the JVM improves throughput by up to two orders of magnitude over Java’s AbstractQueuedSynchronizer, the only practical abstraction offering similar semantics. Further, we successfully integrated CQS as a core component of the popular Kotlin Coroutines library, validating the framework’s practical impact and expressiveness in a real-world environment. In sum, CancellableQueueSynchronizer is the first framework to combine expressiveness with formal guarantees and solid practical performance. Our approach should be extensible to other languages and families of synchronization primitives."}],"volume":7,"language":[{"iso":"eng"}],"file":[{"success":1,"file_id":"13187","checksum":"5dba6e73f0ed79adbdae14d165bc2f68","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2023_ACMProgram.Lang._Koval.pdf","date_created":"2023-07-03T13:09:39Z","file_size":1266773,"date_updated":"2023-07-03T13:09:39Z","creator":"alisjak"}],"publication_status":"published","publication_identifier":{"eissn":["2475-1421"]}},{"department":[{"_id":"DaAl"},{"_id":"GradSch"}],"file_date_updated":"2023-09-06T08:16:25Z","date_updated":"2024-02-27T07:46:52Z","ddc":["000"],"type":"conference","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)"},"conference":{"name":"CAV: Computer Aided Verification","start_date":"2023-07-17","end_date":"2023-07-22","location":"Paris, France"},"status":"public","_id":"14260","volume":13964,"related_material":{"record":[{"status":"public","id":"14995","relation":"research_data"}]},"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031377051"],"issn":["0302-9743"]},"publication_status":"published","file":[{"creator":"dernst","file_size":421408,"date_updated":"2023-09-06T08:16:25Z","file_name":"2023_LNCS_Koval.pdf","date_created":"2023-09-06T08:16:25Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"checksum":"c346016393123a0a2338ad4d976f61bc","file_id":"14275"}],"language":[{"iso":"eng"}],"alternative_title":["LNCS"],"scopus_import":"1","month":"07","intvolume":" 13964","abstract":[{"text":"This paper presents Lincheck, a new practical and user-friendly framework for testing concurrent algorithms on the Java Virtual Machine (JVM). Lincheck provides a simple and declarative way to write concurrent tests: instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. The framework automatically generates a set of concurrent scenarios, examines them using stress-testing or bounded model checking, and verifies that the results of each invocation are correct. Notably, if an error is detected via model checking, Lincheck provides an easy-to-follow trace to reproduce it, significantly simplifying the bug investigation.\r\n\r\nTo the best of our knowledge, Lincheck is the first production-ready tool on the JVM that offers such a simple way of writing concurrent tests, without requiring special skills or expertise. We successfully integrated Lincheck in the development process of several large projects, such as Kotlin Coroutines, and identified new bugs in popular concurrency libraries, such as a race in Java’s standard ConcurrentLinkedDeque and a liveliness bug in Java’s AbstractQueuedSynchronizer framework, which is used in most of the synchronization primitives. We believe that Lincheck can significantly improve the quality and productivity of concurrent algorithms research and development and become the state-of-the-art tool for checking their correctness.","lang":"eng"}],"oa_version":"Published Version","author":[{"full_name":"Koval, Nikita","last_name":"Koval","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Fedorov, Alexander","last_name":"Fedorov","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","first_name":"Alexander"},{"last_name":"Sokolova","full_name":"Sokolova, Maria","first_name":"Maria"},{"last_name":"Tsitelov","full_name":"Tsitelov, Dmitry","first_name":"Dmitry"},{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"article_processing_charge":"Yes (in subscription journal)","title":"Lincheck: A practical framework for testing concurrent data structures on JVM","citation":{"short":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, D.-A. Alistarh, in:, 35th International Conference on Computer Aided Verification , Springer Nature, 2023, pp. 156–169.","ieee":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, and D.-A. Alistarh, “Lincheck: A practical framework for testing concurrent data structures on JVM,” in 35th International Conference on Computer Aided Verification , Paris, France, 2023, vol. 13964, pp. 156–169.","ama":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. Lincheck: A practical framework for testing concurrent data structures on JVM. In: 35th International Conference on Computer Aided Verification . Vol 13964. Springer Nature; 2023:156-169. doi:10.1007/978-3-031-37706-8_8","apa":"Koval, N., Fedorov, A., Sokolova, M., Tsitelov, D., & Alistarh, D.-A. (2023). Lincheck: A practical framework for testing concurrent data structures on JVM. In 35th International Conference on Computer Aided Verification (Vol. 13964, pp. 156–169). Paris, France: Springer Nature. https://doi.org/10.1007/978-3-031-37706-8_8","mla":"Koval, Nikita, et al. “Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM.” 35th International Conference on Computer Aided Verification , vol. 13964, Springer Nature, 2023, pp. 156–69, doi:10.1007/978-3-031-37706-8_8.","ista":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. 2023. Lincheck: A practical framework for testing concurrent data structures on JVM. 35th International Conference on Computer Aided Verification . CAV: Computer Aided Verification, LNCS, vol. 13964, 156–169.","chicago":"Koval, Nikita, Alexander Fedorov, Maria Sokolova, Dmitry Tsitelov, and Dan-Adrian Alistarh. “Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM.” In 35th International Conference on Computer Aided Verification , 13964:156–69. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-37706-8_8."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"156-169","date_published":"2023-07-17T00:00:00Z","doi":"10.1007/978-3-031-37706-8_8","date_created":"2023-09-03T22:01:16Z","has_accepted_license":"1","year":"2023","day":"17","publication":"35th International Conference on Computer Aided Verification ","quality_controlled":"1","publisher":"Springer Nature","oa":1},{"day":"28","year":"2023","date_created":"2024-02-14T15:14:13Z","doi":"10.5281/ZENODO.7877757","related_material":{"record":[{"relation":"used_in_publication","id":"14260","status":"public"}]},"date_published":"2023-04-28T00:00:00Z","oa_version":"Published Version","abstract":[{"lang":"eng","text":"Lincheck is a new practical and user-friendly framework for testing concurrent data structures on the Java Virtual Machine (JVM). It provides a simple and declarative way to write concurrent tests. Instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. \r\nThe artifact presents a collection of Lincheck tests that discover new bugs in popular libraries and implementations from the concurrency literature -- they are listed in Table 1, Section 3. To evaluate the performance of Lincheck analysis, the collection of tests also includes those which check correct data structures and, thus, always succeed. Similarly to Table 2, Section 3, the experiments demonstrate the reasonable time to perform a test. Finally, Lincheck provides user-friendly output with an easy-to-follow trace to reproduce a detected error, significantly simplifying further investigation."}],"month":"04","main_file_link":[{"open_access":"1","url":"https://doi.org/10.5281/zenodo.7877757"}],"oa":1,"publisher":"Zenodo","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"date_updated":"2024-02-27T07:46:52Z","citation":{"ista":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. 2023. Lincheck: A practical framework for testing concurrent data structures on JVM, Zenodo, 10.5281/ZENODO.7877757.","chicago":"Koval, Nikita, Alexander Fedorov, Maria Sokolova, Dmitry Tsitelov, and Dan-Adrian Alistarh. “Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM.” Zenodo, 2023. https://doi.org/10.5281/ZENODO.7877757.","apa":"Koval, N., Fedorov, A., Sokolova, M., Tsitelov, D., & Alistarh, D.-A. (2023). Lincheck: A practical framework for testing concurrent data structures on JVM. Zenodo. https://doi.org/10.5281/ZENODO.7877757","ama":"Koval N, Fedorov A, Sokolova M, Tsitelov D, Alistarh D-A. Lincheck: A practical framework for testing concurrent data structures on JVM. 2023. doi:10.5281/ZENODO.7877757","ieee":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, and D.-A. Alistarh, “Lincheck: A practical framework for testing concurrent data structures on JVM.” Zenodo, 2023.","short":"N. Koval, A. Fedorov, M. Sokolova, D. Tsitelov, D.-A. Alistarh, (2023).","mla":"Koval, Nikita, et al. Lincheck: A Practical Framework for Testing Concurrent Data Structures on JVM. Zenodo, 2023, doi:10.5281/ZENODO.7877757."},"department":[{"_id":"DaAl"}],"title":"Lincheck: A practical framework for testing concurrent data structures on JVM","article_processing_charge":"No","author":[{"full_name":"Koval, Nikita","last_name":"Koval","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita"},{"last_name":"Fedorov","full_name":"Fedorov, Alexander","id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","first_name":"Alexander"},{"full_name":"Sokolova, Maria","last_name":"Sokolova","first_name":"Maria"},{"full_name":"Tsitelov, Dmitry","last_name":"Tsitelov","first_name":"Dmitry"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"}],"_id":"14995","status":"public","type":"research_data_reference"},{"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"}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2109.00657"}],"month":"04","publication_identifier":{"isbn":["9781450392044"]},"publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","id":"13076","relation":"research_data"}]},"ec_funded":1,"_id":"11180","type":"conference","conference":{"start_date":"2022-04-02","end_date":"2022-04-06","location":"Seoul, Republic of Korea","name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming"},"status":"public","date_updated":"2023-08-03T06:48:35Z","department":[{"_id":"DaAl"}],"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).","publisher":"Association for Computing Machinery","quality_controlled":"1","oa":1,"isi":1,"year":"2022","day":"02","publication":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","page":"353-367","date_published":"2022-04-02T00:00:00Z","doi":"10.1145/3503221.3508432","date_created":"2022-04-17T22:01:46Z","project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"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."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"last_name":"Postnikova","full_name":"Postnikova, Anastasiia","first_name":"Anastasiia"},{"full_name":"Koval, Nikita","last_name":"Koval","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"},{"id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"}],"article_processing_charge":"No","external_id":{"isi":["000883318200025"],"arxiv":["2109.00657"]},"title":"Multi-queues can be state-of-the-art priority schedulers"},{"abstract":[{"text":"The source code for replicating experiments presented in the paper.\r\n\r\nThe implementation of the designed priority schedulers can be found in Galois-2.2.1/include/Galois/WorkList/:\r\nStealingMultiQueue.h is the StealingMultiQueue.\r\nMQOptimized/ contains MQ Optimized variants.\r\n\r\nWe provide images that contain all the dependencies and datasets. Images can be pulled from npostnikova/mq-based-schedulers repository, or downloaded from Zenodo. See readme for more detail.","lang":"eng"}],"oa_version":"Published Version","oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.5281/zenodo.5813846"}],"publisher":"Zenodo","month":"01","year":"2022","day":"03","date_created":"2023-05-23T17:05:40Z","related_material":{"link":[{"url":"https://github.com/npostnikova/mq-based-schedulers/tree/v1.1","relation":"software"}],"record":[{"relation":"used_in_publication","id":"11180","status":"public"}]},"doi":"10.5281/ZENODO.5733408","date_published":"2022-01-03T00:00:00Z","_id":"13076","type":"research_data_reference","status":"public","date_updated":"2023-08-03T06:48:34Z","citation":{"chicago":"Postnikova, Anastasiia, Nikita Koval, Giorgi Nadiradze, and Dan-Adrian Alistarh. “Multi-Queues Can Be State-of-the-Art Priority Schedulers.” Zenodo, 2022. https://doi.org/10.5281/ZENODO.5733408.","ista":"Postnikova A, Koval N, Nadiradze G, Alistarh D-A. 2022. Multi-queues can be state-of-the-art priority schedulers, Zenodo, 10.5281/ZENODO.5733408.","mla":"Postnikova, Anastasiia, et al. Multi-Queues Can Be State-of-the-Art Priority Schedulers. Zenodo, 2022, doi:10.5281/ZENODO.5733408.","ama":"Postnikova A, Koval N, Nadiradze G, Alistarh D-A. Multi-queues can be state-of-the-art priority schedulers. 2022. doi:10.5281/ZENODO.5733408","apa":"Postnikova, A., Koval, N., Nadiradze, G., & Alistarh, D.-A. (2022). Multi-queues can be state-of-the-art priority schedulers. Zenodo. https://doi.org/10.5281/ZENODO.5733408","short":"A. Postnikova, N. Koval, G. Nadiradze, D.-A. Alistarh, (2022).","ieee":"A. Postnikova, N. Koval, G. Nadiradze, and D.-A. Alistarh, “Multi-queues can be state-of-the-art priority schedulers.” Zenodo, 2022."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"article_processing_charge":"No","author":[{"last_name":"Postnikova","full_name":"Postnikova, Anastasiia","first_name":"Anastasiia"},{"last_name":"Koval","full_name":"Koval, Nikita","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","full_name":"Nadiradze, Giorgi","last_name":"Nadiradze"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"}],"title":"Multi-queues can be state-of-the-art priority schedulers","department":[{"_id":"DaAl"}]},{"license":"https://creativecommons.org/licenses/by/3.0/","volume":153,"publication_status":"published","publication_identifier":{"isbn":["9783959771337"],"issn":["18688969"]},"language":[{"iso":"eng"}],"file":[{"file_id":"7609","checksum":"d66f07ecb609d9f02433e39f80a447e9","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2020-03-23T09:22:48Z","file_name":"2019_LIPIcs_Alistarh.pdf","creator":"dernst","date_updated":"2020-07-14T12:48:01Z","file_size":13074131}],"alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 153","month":"02","abstract":[{"lang":"eng","text":"Union-Find (or Disjoint-Set Union) is one of the fundamental problems in computer science; it has been well-studied from both theoretical and practical perspectives in the sequential case. Recently, there has been mounting interest in analyzing this problem in the concurrent scenario, and several asymptotically-efficient algorithms have been proposed. Yet, to date, there is very little known about the practical performance of concurrent Union-Find. This work addresses this gap. We evaluate and analyze the performance of several concurrent Union-Find algorithms and optimization strategies across a wide range of platforms (Intel, AMD, and ARM) and workloads (social, random, and road networks, as well as integrations into more complex algorithms). We first observe that, due to the limited computational cost, the number of induced cache misses is the critical determining factor for the performance of existing algorithms. We introduce new techniques to reduce this cost by storing node priorities implicitly and by using plain reads and writes in a way that does not affect the correctness of the algorithms. Finally, we show that Union-Find implementations are an interesting application for Transactional Memory (TM): one of the fastest algorithm variants we discovered is a sequential one that uses coarse-grained locking with the lock elision optimization to reduce synchronization cost and increase scalability. "}],"oa_version":"Published Version","department":[{"_id":"DaAl"}],"file_date_updated":"2020-07-14T12:48:01Z","date_updated":"2023-02-23T13:12:12Z","ddc":["000"],"conference":{"start_date":"2019-12-17","end_date":"2019-12-19","location":"Neuchatal, Switzerland","name":"OPODIS: International Conference on Principles of Distributed Systems"},"tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"type":"conference","status":"public","_id":"7605","page":"15:1-15:16","date_created":"2020-03-22T23:00:46Z","date_published":"2020-02-01T00:00:00Z","doi":"10.4230/LIPIcs.OPODIS.2019.15","year":"2020","has_accepted_license":"1","publication":"23rd International Conference on Principles of Distributed Systems","day":"01","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","external_id":{"arxiv":["1911.06347"]},"article_processing_charge":"No","author":[{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"full_name":"Fedorov, Alexander","last_name":"Fedorov","first_name":"Alexander"},{"last_name":"Koval","full_name":"Koval, Nikita","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"}],"title":"In search of the fastest concurrent union-find algorithm","citation":{"ama":"Alistarh D-A, Fedorov A, Koval N. In search of the fastest concurrent union-find algorithm. In: 23rd International Conference on Principles of Distributed Systems. Vol 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:15:1-15:16. doi:10.4230/LIPIcs.OPODIS.2019.15","apa":"Alistarh, D.-A., Fedorov, A., & Koval, N. (2020). In search of the fastest concurrent union-find algorithm. In 23rd International Conference on Principles of Distributed Systems (Vol. 153, p. 15:1-15:16). Neuchatal, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2019.15","ieee":"D.-A. Alistarh, A. Fedorov, and N. Koval, “In search of the fastest concurrent union-find algorithm,” in 23rd International Conference on Principles of Distributed Systems, Neuchatal, Switzerland, 2020, vol. 153, p. 15:1-15:16.","short":"D.-A. Alistarh, A. Fedorov, N. Koval, in:, 23rd International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 15:1-15:16.","mla":"Alistarh, Dan-Adrian, et al. “In Search of the Fastest Concurrent Union-Find Algorithm.” 23rd International Conference on Principles of Distributed Systems, vol. 153, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 15:1-15:16, doi:10.4230/LIPIcs.OPODIS.2019.15.","ista":"Alistarh D-A, Fedorov A, Koval N. 2020. In search of the fastest concurrent union-find algorithm. 23rd International Conference on Principles of Distributed Systems. OPODIS: International Conference on Principles of Distributed Systems, LIPIcs, vol. 153, 15:1-15:16.","chicago":"Alistarh, Dan-Adrian, Alexander Fedorov, and Nikita Koval. “In Search of the Fastest Concurrent Union-Find Algorithm.” In 23rd International Conference on Principles of Distributed Systems, 153:15:1-15:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.OPODIS.2019.15."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"abstract":[{"text":"Concurrent programming can be notoriously complex and error-prone. Programming bugs can arise from a variety of sources, such as operation re-reordering, or incomplete understanding of the memory model. A variety of formal and model checking methods have been developed to address this fundamental difficulty. While technically interesting, existing academic methods are still hard to apply to the large codebases typical of industrial deployments, which limits their practical impact.","lang":"eng"}],"oa_version":"None","scopus_import":"1","publisher":"Association for Computing Machinery","quality_controlled":"1","month":"02","year":"2020","publication_status":"published","publication_identifier":{"isbn":["9781450368186"]},"publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP","language":[{"iso":"eng"}],"day":"19","page":"423-424","date_created":"2020-04-05T22:00:48Z","doi":"10.1145/3332466.3374503","date_published":"2020-02-19T00:00:00Z","_id":"7635","conference":{"name":"PPOPP: Principles and Practice of Parallel Programming","location":"San Diego, CA, United States","end_date":"2020-02-26","start_date":"2020-02-22"},"type":"conference","status":"public","citation":{"short":"N. Koval, M. Sokolova, A. Fedorov, D.-A. Alistarh, D. Tsitelov, in:, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, Association for Computing Machinery, 2020, pp. 423–424.","ieee":"N. Koval, M. Sokolova, A. Fedorov, D.-A. Alistarh, and D. Tsitelov, “Testing concurrency on the JVM with Lincheck,” in Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, San Diego, CA, United States, 2020, pp. 423–424.","apa":"Koval, N., Sokolova, M., Fedorov, A., Alistarh, D.-A., & Tsitelov, D. (2020). Testing concurrency on the JVM with Lincheck. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP (pp. 423–424). San Diego, CA, United States: Association for Computing Machinery. https://doi.org/10.1145/3332466.3374503","ama":"Koval N, Sokolova M, Fedorov A, Alistarh D-A, Tsitelov D. Testing concurrency on the JVM with Lincheck. In: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP. Association for Computing Machinery; 2020:423-424. doi:10.1145/3332466.3374503","mla":"Koval, Nikita, et al. “Testing Concurrency on the JVM with Lincheck.” Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, Association for Computing Machinery, 2020, pp. 423–24, doi:10.1145/3332466.3374503.","ista":"Koval N, Sokolova M, Fedorov A, Alistarh D-A, Tsitelov D. 2020. Testing concurrency on the JVM with Lincheck. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP. PPOPP: Principles and Practice of Parallel Programming, 423–424.","chicago":"Koval, Nikita, Mariia Sokolova, Alexander Fedorov, Dan-Adrian Alistarh, and Dmitry Tsitelov. “Testing Concurrency on the JVM with Lincheck.” In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, 423–24. Association for Computing Machinery, 2020. https://doi.org/10.1145/3332466.3374503."},"date_updated":"2024-02-28T12:53:46Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","author":[{"last_name":"Koval","full_name":"Koval, Nikita","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"},{"id":"26217AE4-77FF-11EA-8101-AD24D49E41F4","first_name":"Mariia","full_name":"Sokolova, Mariia","last_name":"Sokolova"},{"first_name":"Alexander","last_name":"Fedorov","full_name":"Fedorov, Alexander"},{"full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tsitelov, Dmitry","last_name":"Tsitelov","first_name":"Dmitry"}],"title":"Testing concurrency on the JVM with Lincheck","department":[{"_id":"DaAl"}]},{"month":"02","quality_controlled":"1","publisher":"ACM Press","oa_version":"None","abstract":[{"lang":"eng","text":"Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) [1] and actor [2] models, which share data via explicit communication. Rendezvous channelis the common abstraction for communication between several processes, where senders and receivers perform a rendezvous handshake as a part of their protocol (senders wait for receivers and vice versa). Additionally to this, channels support the select expression. In this work, we present the first efficient lock-free channel algorithm, and compare it against Go [3] and Kotlin [4] baseline implementations."}],"date_created":"2019-05-24T10:09:12Z","doi":"10.1145/3293883.3297000","date_published":"2019-02-01T00:00:00Z","page":"417-418","publication":"Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming","language":[{"iso":"eng"}],"day":"01","publication_status":"published","year":"2019","publication_identifier":{"isbn":["9781450362252"]},"isi":1,"status":"public","conference":{"name":"PPoPP: Principles and Practice of Parallel Programming","location":"Washington, NY, United States","end_date":"2019-02-20","start_date":"2019-02-16"},"type":"conference_poster","_id":"6485","title":"Lock-free channels for programming via communicating sequential processes","department":[{"_id":"DaAl"}],"article_processing_charge":"No","external_id":{"isi":["000587604600044"]},"author":[{"full_name":"Koval, Nikita","last_name":"Koval","first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"},{"first_name":"Roman","last_name":"Elizarov","full_name":"Elizarov, Roman"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. Lock-Free Channels for Programming via Communicating Sequential Processes. Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. ACM Press, 2019. https://doi.org/10.1145/3293883.3297000.","ista":"Koval N, Alistarh D-A, Elizarov R. 2019. Lock-free channels for programming via communicating sequential processes, ACM Press,p.","mla":"Koval, Nikita, et al. “Lock-Free Channels for Programming via Communicating Sequential Processes.” Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, ACM Press, 2019, pp. 417–18, doi:10.1145/3293883.3297000.","short":"N. Koval, D.-A. Alistarh, R. Elizarov, Lock-Free Channels for Programming via Communicating Sequential Processes, ACM Press, 2019.","ieee":"N. Koval, D.-A. Alistarh, and R. Elizarov, Lock-free channels for programming via communicating sequential processes. ACM Press, 2019, pp. 417–418.","apa":"Koval, N., Alistarh, D.-A., & Elizarov, R. (2019). Lock-free channels for programming via communicating sequential processes. Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming (pp. 417–418). Washington, NY, United States: ACM Press. https://doi.org/10.1145/3293883.3297000","ama":"Koval N, Alistarh D-A, Elizarov R. Lock-Free Channels for Programming via Communicating Sequential Processes. ACM Press; 2019:417-418. doi:10.1145/3293883.3297000"},"date_updated":"2023-08-25T10:41:20Z"},{"date_updated":"2023-09-06T14:53:59Z","department":[{"_id":"DaAl"}],"_id":"7228","status":"public","type":"conference","conference":{"start_date":"2019-08-26","location":"Göttingen, Germany","end_date":"2019-08-30","name":"Euro-Par: European Conference on Parallel Processing"},"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0302-9743"],"isbn":["978-3-0302-9399-4"],"eissn":["1611-3349"]},"publication_status":"published","volume":11725,"oa_version":"None","abstract":[{"lang":"eng","text":"Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) and actor models, which share data via explicit communication. These models have been known for almost half a century, and have recently had started to gain significant traction among modern programming languages. The common abstraction for communication between several processes is the channel. Although channels are similar to producer-consumer data structures, they have different semantics and support additional operations, such as the select expression. Despite their growing popularity, most known implementations of channels use lock-based data structures and can be rather inefficient.\r\n\r\nIn this paper, we present the first efficient lock-free algorithm for implementing a communication channel for CSP programming. We provide implementations and experimental results in the Kotlin and Go programming languages. Our new algorithm outperforms existing implementations on many workloads, while providing non-blocking progress guarantee. Our design can serve as an example of how to construct general communication data structures for CSP and actor models. "}],"month":"08","intvolume":" 11725","alternative_title":["LNCS"],"scopus_import":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"apa":"Koval, N., Alistarh, D.-A., & Elizarov, R. (2019). Scalable FIFO channels for programming via communicating sequential processes. In 25th Anniversary of Euro-Par (Vol. 11725, pp. 317–333). Göttingen, Germany: Springer Nature. https://doi.org/10.1007/978-3-030-29400-7_23","ama":"Koval N, Alistarh D-A, Elizarov R. Scalable FIFO channels for programming via communicating sequential processes. In: 25th Anniversary of Euro-Par. Vol 11725. Springer Nature; 2019:317-333. doi:10.1007/978-3-030-29400-7_23","ieee":"N. Koval, D.-A. Alistarh, and R. Elizarov, “Scalable FIFO channels for programming via communicating sequential processes,” in 25th Anniversary of Euro-Par, Göttingen, Germany, 2019, vol. 11725, pp. 317–333.","short":"N. Koval, D.-A. Alistarh, R. Elizarov, in:, 25th Anniversary of Euro-Par, Springer Nature, 2019, pp. 317–333.","mla":"Koval, Nikita, et al. “Scalable FIFO Channels for Programming via Communicating Sequential Processes.” 25th Anniversary of Euro-Par, vol. 11725, Springer Nature, 2019, pp. 317–33, doi:10.1007/978-3-030-29400-7_23.","ista":"Koval N, Alistarh D-A, Elizarov R. 2019. Scalable FIFO channels for programming via communicating sequential processes. 25th Anniversary of Euro-Par. Euro-Par: European Conference on Parallel Processing, LNCS, vol. 11725, 317–333.","chicago":"Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. “Scalable FIFO Channels for Programming via Communicating Sequential Processes.” In 25th Anniversary of Euro-Par, 11725:317–33. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-29400-7_23."},"title":"Scalable FIFO channels for programming via communicating sequential processes","author":[{"id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita","full_name":"Koval, Nikita","last_name":"Koval"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"first_name":"Roman","last_name":"Elizarov","full_name":"Elizarov, Roman"}],"article_processing_charge":"No","external_id":{"isi":["000851061400023"]},"day":"13","publication":"25th Anniversary of Euro-Par","isi":1,"year":"2019","date_published":"2019-08-13T00:00:00Z","doi":"10.1007/978-3-030-29400-7_23","date_created":"2020-01-05T23:00:46Z","page":"317-333","publisher":"Springer Nature","quality_controlled":"1"},{"year":"2019","isi":1,"publication":"31st ACM Symposium on Parallelism in Algorithms and Architectures","day":"01","page":"145-154","date_created":"2019-07-24T08:59:36Z","date_published":"2019-06-01T00:00:00Z","doi":"10.1145/3323165.3323201","oa":1,"quality_controlled":"1","publisher":"ACM Press","citation":{"mla":"Alistarh, Dan-Adrian, et al. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, 2019, pp. 145–54, doi:10.1145/3323165.3323201.","apa":"Alistarh, D.-A., Nadiradze, G., & Koval, N. (2019). Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In 31st ACM Symposium on Parallelism in Algorithms and Architectures (pp. 145–154). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3323165.3323201","ama":"Alistarh D-A, Nadiradze G, Koval N. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In: 31st ACM Symposium on Parallelism in Algorithms and Architectures. ACM Press; 2019:145-154. doi:10.1145/3323165.3323201","short":"D.-A. Alistarh, G. Nadiradze, N. Koval, in:, 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, 2019, pp. 145–154.","ieee":"D.-A. Alistarh, G. Nadiradze, and N. Koval, “Efficiency guarantees for parallel incremental algorithms under relaxed schedulers,” in 31st ACM Symposium on Parallelism in Algorithms and Architectures, Phoenix, AZ, United States, 2019, pp. 145–154.","chicago":"Alistarh, Dan-Adrian, Giorgi Nadiradze, and Nikita Koval. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” In 31st ACM Symposium on Parallelism in Algorithms and Architectures, 145–54. ACM Press, 2019. https://doi.org/10.1145/3323165.3323201.","ista":"Alistarh D-A, Nadiradze G, Koval N. 2019. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. 31st ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 145–154."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","external_id":{"arxiv":["2003.09363"],"isi":["000507618500018"]},"author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","orcid":"0000-0001-5634-0731"},{"last_name":"Koval","full_name":"Koval, Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita"}],"title":"Efficiency guarantees for parallel incremental algorithms under relaxed schedulers","project":[{"grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","publication_identifier":{"isbn":["9781450361842"]},"language":[{"iso":"eng"}],"ec_funded":1,"related_material":{"record":[{"id":"10429","status":"public","relation":"dissertation_contains"}]},"abstract":[{"text":"Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2003.09363"}],"scopus_import":"1","month":"06","date_updated":"2023-09-07T13:31:39Z","department":[{"_id":"DaAl"}],"_id":"6673","conference":{"start_date":"2019-06-22","location":"Phoenix, AZ, United States","end_date":"2019-06-24","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"},"type":"conference","status":"public"}]