[{"department":[{"_id":"DaAl"},{"_id":"GradSch"}],"conference":{"start_date":"2023-02-25","location":"Montreal, QB, Canada","end_date":"2023-03-01","name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming"},"date_created":"2023-03-19T23:00:58Z","language":[{"iso":"eng"}],"_id":"12736","date_updated":"2023-03-20T07:57:27Z","title":"Unexpected scaling in path copying trees","publication_status":"published","page":"438-440","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","year":"2023","publication_identifier":{"isbn":["9798400700156"]},"abstract":[{"text":"Although a wide variety of handcrafted concurrent data structures have been proposed, there is considerable interest in universal approaches (Universal Constructions or UCs) for building concurrent data structures. UCs (semi-)automatically convert a sequential data structure into a concurrent one. The simplest approach uses locks [3, 6] that protect a sequential data structure and allow only one process to access it at a time. However, the resulting data structure is blocking. Most work on UCs instead focuses on obtaining non-blocking progress guarantees such as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et al.","lang":"eng"}],"status":"public","date_published":"2023-02-25T00:00:00Z","acknowledgement":"This work was supported by: the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Program grant: RGPIN-2019-04227, and the Canada Foundation for Innovation John R. Evans Leaders Fund (CFI-JELF) with equal support from the Ontario Research Fund CFI Leaders Opportunity Fund: 38512.","oa":1,"author":[{"last_name":"Aksenov","first_name":"Vitaly","full_name":"Aksenov, Vitaly"},{"full_name":"Brown, Trevor A","first_name":"Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87"},{"id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","last_name":"Fedorov","full_name":"Fedorov, Alexander","first_name":"Alexander"},{"first_name":"Ilya","full_name":"Kokorin, Ilya","last_name":"Kokorin"}],"month":"02","oa_version":"Published Version","publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","quality_controlled":"1","doi":"10.1145/3572848.3577512","citation":{"mla":"Aksenov, Vitaly, et al. “Unexpected Scaling in Path Copying Trees.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2023, pp. 438–40, doi:<a href=\"https://doi.org/10.1145/3572848.3577512\">10.1145/3572848.3577512</a>.","apa":"Aksenov, V., Brown, T. A., Fedorov, A., &#38; Kokorin, I. (2023). <i>Unexpected scaling in path copying trees</i>. <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 438–440). Montreal, QB, Canada: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3572848.3577512\">https://doi.org/10.1145/3572848.3577512</a>","ista":"Aksenov V, Brown TA, Fedorov A, Kokorin I. 2023. Unexpected scaling in path copying trees, Association for Computing Machinery,p.","chicago":"Aksenov, Vitaly, Trevor A Brown, Alexander Fedorov, and Ilya Kokorin. <i>Unexpected Scaling in Path Copying Trees</i>. <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3572848.3577512\">https://doi.org/10.1145/3572848.3577512</a>.","ieee":"V. Aksenov, T. A. Brown, A. Fedorov, and I. Kokorin, <i>Unexpected scaling in path copying trees</i>. Association for Computing Machinery, 2023, pp. 438–440.","short":"V. Aksenov, T.A. Brown, A. Fedorov, I. Kokorin, Unexpected Scaling in Path Copying Trees, Association for Computing Machinery, 2023.","ama":"Aksenov V, Brown TA, Fedorov A, Kokorin I. <i>Unexpected Scaling in Path Copying Trees</i>. Association for Computing Machinery; 2023:438-440. doi:<a href=\"https://doi.org/10.1145/3572848.3577512\">10.1145/3572848.3577512</a>"},"day":"25","type":"conference_poster","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3572848.3577512"}],"publisher":"Association for Computing Machinery"},{"language":[{"iso":"eng"}],"date_created":"2022-04-17T22:01:46Z","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"},"department":[{"_id":"DaAl"}],"title":"PathCAS: An efficient middle ground for concurrent search data structures","scopus_import":"1","tmp":{"short":"CC BY (4.0)","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)"},"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."}],"oa_version":"Published Version","quality_controlled":"1","doi":"10.1145/3503221.3508410","day":"02","type":"conference","citation":{"chicago":"Brown, Trevor A, William Sigouin, and Dan-Adrian Alistarh. “PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures.” In <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 385–99. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3503221.3508410\">https://doi.org/10.1145/3503221.3508410</a>.","apa":"Brown, T. A., Sigouin, W., &#38; Alistarh, D.-A. (2022). PathCAS: An efficient middle ground for concurrent search data structures. In <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 385–399). Seoul, Republic of Korea: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3503221.3508410\">https://doi.org/10.1145/3503221.3508410</a>","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.","ama":"Brown TA, Sigouin W, Alistarh D-A. PathCAS: An efficient middle ground for concurrent search data structures. In: <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery; 2022:385-399. doi:<a href=\"https://doi.org/10.1145/3503221.3508410\">10.1145/3503221.3508410</a>","ieee":"T. A. Brown, W. Sigouin, and D.-A. Alistarh, “PathCAS: An efficient middle ground for concurrent search data structures,” in <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 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.","mla":"Brown, Trevor A., et al. “PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures.” <i>Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2022, pp. 385–99, doi:<a href=\"https://doi.org/10.1145/3503221.3508410\">10.1145/3503221.3508410</a>."},"_id":"11181","publication_status":"published","date_updated":"2023-08-03T06:49:20Z","status":"public","ddc":["000"],"date_published":"2022-04-02T00:00:00Z","year":"2022","publication_identifier":{"isbn":["9781450392044"]},"article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","page":"385-399","oa":1,"isi":1,"external_id":{"isi":["000883318200027"]},"author":[{"first_name":"Trevor A","full_name":"Brown, Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","last_name":"Brown"},{"last_name":"Sigouin","full_name":"Sigouin, William","first_name":"William"},{"orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"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.","file":[{"file_id":"11731","creator":"dernst","date_updated":"2022-08-05T09:19:29Z","access_level":"open_access","file_name":"2022_PPoPP_Brown.pdf","date_created":"2022-08-05T09:19:29Z","checksum":"8ceea411fa133795cd4903529498eb6b","file_size":1128343,"success":1,"relation":"main_file","content_type":"application/pdf"}],"month":"04","publication":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","file_date_updated":"2022-08-05T09:19:29Z","publisher":"Association for Computing Machinery","has_accepted_license":"1"},{"publisher":"Association for Computing Machinery","citation":{"short":"D.-A. Alistarh, T.A. Brown, N. Singhal, in:, Annual ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, 2020, pp. 37–49.","ama":"Alistarh D-A, Brown TA, Singhal N. Memory tagging: Minimalist synchronization for scalable concurrent data structures. In: <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>. Association for Computing Machinery; 2020:37-49. doi:<a href=\"https://doi.org/10.1145/3350755.3400213\">10.1145/3350755.3400213</a>","ieee":"D.-A. Alistarh, T. A. Brown, and N. Singhal, “Memory tagging: Minimalist synchronization for scalable concurrent data structures,” in <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>, Virtual Event, United States, 2020, no. 7, pp. 37–49.","apa":"Alistarh, D.-A., Brown, T. A., &#38; Singhal, N. (2020). Memory tagging: Minimalist synchronization for scalable concurrent data structures. In <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 37–49). Virtual Event, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3350755.3400213\">https://doi.org/10.1145/3350755.3400213</a>","chicago":"Alistarh, Dan-Adrian, Trevor A Brown, and Nandini Singhal. “Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures.” In <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>, 37–49. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3350755.3400213\">https://doi.org/10.1145/3350755.3400213</a>.","ista":"Alistarh D-A, Brown TA, Singhal N. 2020. Memory tagging: Minimalist synchronization for scalable concurrent data structures. Annual ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 37–49.","mla":"Alistarh, Dan-Adrian, et al. “Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures.” <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>, no. 7, Association for Computing Machinery, 2020, pp. 37–49, doi:<a href=\"https://doi.org/10.1145/3350755.3400213\">10.1145/3350755.3400213</a>."},"type":"conference","day":"06","publication":"Annual ACM Symposium on Parallelism in Algorithms and Architectures","doi":"10.1145/3350755.3400213","quality_controlled":"1","month":"07","oa_version":"None","external_id":{"isi":["000744436200004"]},"author":[{"orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Trevor A","full_name":"Brown, Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","last_name":"Brown"},{"full_name":"Singhal, Nandini","first_name":"Nandini","last_name":"Singhal"}],"isi":1,"issue":"7","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"37-49","date_published":"2020-07-06T00:00:00Z","status":"public","year":"2020","publication_identifier":{"isbn":["9781450369350"]},"abstract":[{"lang":"eng","text":"There has been a significant amount of research on hardware and software support for efficient concurrent data structures; yet, the question of how to build correct, simple, and scalable data structures has not yet been definitively settled. In this paper, we revisit this question from a minimalist perspective, and ask: what is the smallest amount of synchronization required for correct and efficient concurrent search data structures, and how could this minimal synchronization support be provided in hardware?\r\n\r\nTo address these questions, we introduce memory tagging, a simple hardware mechanism which enables the programmer to \"tag\" a dynamic set of memory locations, at cache-line granularity, and later validate whether the memory has been concurrently modified, with the possibility of updating one of the underlying locations atomically if validation succeeds. We provide several examples showing that this mechanism can enable fast and arguably simple concurrent data structure designs, such as lists, binary search trees, balanced search trees, range queries, and Software Transactional Memory (STM) implementations. We provide an implementation of memory tags in the Graphite multi-core simulator, showing that the mechanism can be implemented entirely at the level of L1 cache, and that it can enable non-trivial speedups versus existing implementations of the above data structures."}],"date_updated":"2024-02-28T12:56:32Z","publication_status":"published","title":"Memory tagging: Minimalist synchronization for scalable concurrent data structures","scopus_import":"1","department":[{"_id":"DaAl"}],"_id":"8191","language":[{"iso":"eng"}],"date_created":"2020-08-02T22:00:58Z","conference":{"start_date":"2020-07-15","end_date":"2020-07-17","location":"Virtual Event, United States","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"}},{"quality_controlled":"1","publication":"Proceedings of the 2018 USENIX Annual Technical Conference","oa_version":"Published Version","month":"01","publisher":"USENIX Association","main_file_link":[{"open_access":"1","url":"https://www.usenix.org/system/files/conference/atc18/atc18-arbel-raviv.pdf"}],"type":"conference","day":"01","citation":{"mla":"Arbel-Raviv, Maya, et al. “Getting to the Root of Concurrent Binary Search Tree Performance.” <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>, USENIX Association, 2020, pp. 295–306.","ista":"Arbel-Raviv M, Brown TA, Morrison A. 2020. Getting to the root of concurrent binary search tree performance. Proceedings of the 2018 USENIX Annual Technical Conference. USENIX: Annual Technical Conference, 295–306.","chicago":"Arbel-Raviv, Maya, Trevor A Brown, and Adam Morrison. “Getting to the Root of Concurrent Binary Search Tree Performance.” In <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>, 295–306. USENIX Association, 2020.","apa":"Arbel-Raviv, M., Brown, T. A., &#38; Morrison, A. (2020). Getting to the root of concurrent binary search tree performance. In <i>Proceedings of the 2018 USENIX Annual Technical Conference</i> (pp. 295–306). Boston, MA, United States: USENIX Association.","short":"M. Arbel-Raviv, T.A. Brown, A. Morrison, in:, Proceedings of the 2018 USENIX Annual Technical Conference, USENIX Association, 2020, pp. 295–306.","ama":"Arbel-Raviv M, Brown TA, Morrison A. Getting to the root of concurrent binary search tree performance. In: <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>. USENIX Association; 2020:295-306.","ieee":"M. Arbel-Raviv, T. A. Brown, and A. Morrison, “Getting to the root of concurrent binary search tree performance,” in <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>, Boston, MA, United States, 2020, pp. 295–306."},"title":"Getting to the root of concurrent binary search tree performance","publication_status":"published","scopus_import":"1","date_updated":"2021-01-11T15:25:48Z","project":[{"_id":"26450934-B435-11E9-9278-68D0E5697425","name":"NSERC Postdoctoral fellowship"}],"_id":"7272","language":[{"iso":"eng"}],"conference":{"start_date":"2018-07-11","name":"USENIX: Annual Technical Conference","end_date":"2018-07-13","location":"Boston, MA, United States"},"date_created":"2020-01-14T07:27:08Z","department":[{"_id":"DaAl"}],"oa":1,"author":[{"first_name":"Maya","full_name":"Arbel-Raviv, Maya","last_name":"Arbel-Raviv"},{"full_name":"Brown, Trevor A","first_name":"Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Morrison, Adam","first_name":"Adam","last_name":"Morrison"}],"date_published":"2020-01-01T00:00:00Z","status":"public","ddc":["000"],"publication_identifier":{"isbn":["9781939133021"]},"year":"2020","abstract":[{"text":"Many systems rely on optimistic concurrent search trees for multi-core scalability. In principle, optimistic trees have a simple performance story: searches are read-only and so run in parallel, with writes to shared memory occurring only when modifying the data structure. However, this paper shows that in practice, obtaining the full performance benefits of optimistic search trees is not so simple.\r\n\r\nWe focus on optimistic binary search trees (BSTs) and perform a detailed performance analysis of 10 state-of-the-art BSTs on large scale x86-64 hardware, using both microbenchmarks and an in-memory database system. We find and explain significant unexpected performance differences between BSTs with similar tree structure and search implementations, which we trace to subtle performance-degrading interactions of BSTs with systems software and hardware subsystems. We further derive a prescriptive approach to avoid this performance degradation, as well as algorithmic insights on optimistic BST design. Our work underlines the gap between the theory and practice of multi-core performance, and calls for further research to help bridge this gap.","lang":"eng"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"295-306"},{"department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"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"},"date_created":"2020-04-05T22:00:49Z","title":"Non-blocking interpolation search trees with doubly-logarithmic running time","scopus_import":"1","abstract":[{"text":"Balanced search trees typically use key comparisons to guide their operations, and achieve logarithmic running time. By relying on numerical properties of the keys, interpolation search achieves lower search complexity and better performance. Although interpolation-based data structures were investigated in the past, their non-blocking concurrent variants have received very little attention so far.\r\nIn this paper, we propose the first non-blocking implementation of the classic interpolation search tree (IST) data structure. For arbitrary key distributions, the data structure ensures worst-case O(log n + p) amortized time for search, insertion and deletion traversals. When the input key distributions are smooth, lookups run in expected O(log log n + p) time, and insertion and deletion run in expected amortized O(log log n + p) time, where p is a bound on the number of threads. To improve the scalability of concurrent insertion and deletion, we propose a novel parallel rebuilding technique, which should be of independent interest.\r\nWe evaluate whether the theoretical improvements translate to practice by implementing the concurrent interpolation search tree, and benchmarking it on uniform and nonuniform key distributions, for dataset sizes in the millions to billions of keys. Relative to the state-of-the-art concurrent data structures, the concurrent interpolation search tree achieves performance improvements of up to 15% under high update rates, and of up to 50% under moderate update rates. Further, ISTs exhibit up to 2X less cache-misses, and consume 1.2 -- 2.6X less memory compared to the next best alternative on typical dataset sizes. We find that the results are surprisingly robust to distributional skew, which suggests that our data structure can be a promising alternative to classic concurrent search structures.","lang":"eng"}],"oa_version":"Published Version","quality_controlled":"1","doi":"10.1145/3332466.3374542","citation":{"mla":"Brown, Trevor A., et al. “Non-Blocking Interpolation Search Trees with Doubly-Logarithmic Running Time.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2020, pp. 276–91, doi:<a href=\"https://doi.org/10.1145/3332466.3374542\">10.1145/3332466.3374542</a>.","apa":"Brown, T. A., Prokopec, A., &#38; Alistarh, D.-A. (2020). Non-blocking interpolation search trees with doubly-logarithmic running time. In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 276–291). San Diego, CA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3332466.3374542\">https://doi.org/10.1145/3332466.3374542</a>","ista":"Brown TA, Prokopec A, Alistarh D-A. 2020. Non-blocking interpolation search trees with doubly-logarithmic running time. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPOPP: Principles and Practice of Parallel Programming, 276–291.","chicago":"Brown, Trevor A, Aleksandar Prokopec, and Dan-Adrian Alistarh. “Non-Blocking Interpolation Search Trees with Doubly-Logarithmic Running Time.” In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 276–91. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3332466.3374542\">https://doi.org/10.1145/3332466.3374542</a>.","ama":"Brown TA, Prokopec A, Alistarh D-A. Non-blocking interpolation search trees with doubly-logarithmic running time. In: <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery; 2020:276-291. doi:<a href=\"https://doi.org/10.1145/3332466.3374542\">10.1145/3332466.3374542</a>","ieee":"T. A. Brown, A. Prokopec, and D.-A. Alistarh, “Non-blocking interpolation search trees with doubly-logarithmic running time,” in <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, San Diego, CA, United States, 2020, pp. 276–291.","short":"T.A. Brown, A. Prokopec, D.-A. Alistarh, in:, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2020, pp. 276–291."},"day":"19","type":"conference","main_file_link":[{"url":"https://doi.org/10.1145/3332466.3374542","open_access":"1"}],"_id":"7636","date_updated":"2024-02-28T12:55:14Z","project":[{"name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"ec_funded":1,"publication_status":"published","article_processing_charge":"No","page":"276-291","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2020-02-19T00:00:00Z","status":"public","year":"2020","publication_identifier":{"isbn":["9781450368186"]},"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union Horizon 2020 research and innovation program, grant agreement No 805223, ERC Starting Grant ScaleML. We acknowledge the support of the Natural Sciences and\r\nEngineering Research Council of Canada (NSERC). ","author":[{"last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A","full_name":"Brown, Trevor A"},{"last_name":"Prokopec","first_name":"Aleksandar","full_name":"Prokopec, Aleksandar"},{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"}],"isi":1,"oa":1,"external_id":{"isi":["000564476500020"]},"month":"02","publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","publisher":"Association for Computing Machinery"},{"department":[{"_id":"DaAl"}],"date_created":"2018-12-11T11:44:33Z","conference":{"name":"Euro-Par: European Conference on Parallel Processing","location":"Turin, Italy","end_date":"2018-08-31","start_date":"2018-08-27"},"language":[{"iso":"eng"}],"alternative_title":["LNCS"],"scopus_import":"1","title":"Snapshot based synchronization: A fast replacement for Hand-over-Hand locking","volume":11014,"abstract":[{"text":"Concurrent accesses to shared data structures must be synchronized to avoid data races. Coarse-grained synchronization, which locks the entire data structure, is easy to implement but does not scale. Fine-grained synchronization can scale well, but can be hard to reason about. Hand-over-hand locking, in which operations are pipelined as they traverse the data structure, combines fine-grained synchronization with ease of use. However, the traditional implementation suffers from inherent overheads. This paper introduces snapshot-based synchronization (SBS), a novel hand-over-hand locking mechanism. SBS decouples the synchronization state from the data, significantly improving cache utilization. Further, it relies on guarantees provided by pipelining to minimize synchronization that requires cross-thread communication. Snapshot-based synchronization thus scales much better than traditional hand-over-hand locking, while maintaining the same ease of use.","lang":"eng"}],"intvolume":"     11014","oa_version":"Preprint","quality_controlled":"1","doi":"10.1007/978-3-319-96983-1_33","citation":{"mla":"Gilad, Eran, et al. <i>Snapshot Based Synchronization: A Fast Replacement for Hand-over-Hand Locking</i>. Vol. 11014, Springer, 2018, pp. 465–79, doi:<a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">10.1007/978-3-319-96983-1_33</a>.","short":"E. Gilad, T.A. Brown, M. Oskin, Y. Etsion, in:, Springer, 2018, pp. 465–479.","ieee":"E. Gilad, T. A. Brown, M. Oskin, and Y. Etsion, “Snapshot based synchronization: A fast replacement for Hand-over-Hand locking,” presented at the Euro-Par: European Conference on Parallel Processing, Turin, Italy, 2018, vol. 11014, pp. 465–479.","ama":"Gilad E, Brown TA, Oskin M, Etsion Y. Snapshot based synchronization: A fast replacement for Hand-over-Hand locking. In: Vol 11014. Springer; 2018:465-479. doi:<a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">10.1007/978-3-319-96983-1_33</a>","ista":"Gilad E, Brown TA, Oskin M, Etsion Y. 2018. Snapshot based synchronization: A fast replacement for Hand-over-Hand locking. Euro-Par: European Conference on Parallel Processing, LNCS, vol. 11014, 465–479.","chicago":"Gilad, Eran, Trevor A Brown, Mark Oskin, and Yoav Etsion. “Snapshot Based Synchronization: A Fast Replacement for Hand-over-Hand Locking,” 11014:465–79. Springer, 2018. <a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">https://doi.org/10.1007/978-3-319-96983-1_33</a>.","apa":"Gilad, E., Brown, T. A., Oskin, M., &#38; Etsion, Y. (2018). Snapshot based synchronization: A fast replacement for Hand-over-Hand locking (Vol. 11014, pp. 465–479). Presented at the Euro-Par: European Conference on Parallel Processing, Turin, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-319-96983-1_33\">https://doi.org/10.1007/978-3-319-96983-1_33</a>"},"day":"01","type":"conference","publist_id":"7969","_id":"85","project":[{"_id":"26450934-B435-11E9-9278-68D0E5697425","name":"NSERC Postdoctoral fellowship"}],"date_updated":"2023-09-18T09:32:36Z","publication_status":"published","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","page":"465 - 479","article_processing_charge":"No","year":"2018","publication_identifier":{"issn":["03029743"]},"ddc":["000"],"status":"public","date_published":"2018-08-01T00:00:00Z","acknowledgement":"Trevor Brown was supported in part by the ISF (grants 2005/17 & 1749/14) and by a NSERC post-doctoral fellowship.","isi":1,"oa":1,"external_id":{"isi":["000851042300031"]},"author":[{"last_name":"Gilad","full_name":"Gilad, Eran","first_name":"Eran"},{"full_name":"Brown, Trevor A","first_name":"Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","last_name":"Brown"},{"last_name":"Oskin","full_name":"Oskin, Mark","first_name":"Mark"},{"last_name":"Etsion","full_name":"Etsion, Yoav","first_name":"Yoav"}],"month":"08","file":[{"checksum":"13a3f250be8878405e791b53c19722ad","file_size":665372,"relation":"main_file","content_type":"application/pdf","creator":"dernst","date_updated":"2020-07-14T12:48:14Z","access_level":"open_access","file_id":"5954","file_name":"2018_Brown.pdf","date_created":"2019-02-12T07:40:40Z"}],"file_date_updated":"2020-07-14T12:48:14Z","publisher":"Springer","has_accepted_license":"1"},{"_id":"5963","arxiv":1,"publication_status":"published","date_updated":"2023-09-19T10:43:21Z","publication_identifier":{"isbn":["9781450357951"]},"year":"2018","date_published":"2018-07-23T00:00:00Z","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","page":"377-386","article_processing_charge":"No","isi":1,"oa":1,"author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"},{"first_name":"Trevor A","full_name":"Brown, Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","last_name":"Brown"},{"first_name":"Justin","full_name":"Kopinsky, Justin","last_name":"Kopinsky"},{"last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","first_name":"Giorgi"}],"external_id":{"isi":["000458186900048"],"arxiv":["1808.04155"]},"month":"07","publication":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC '18","publisher":"ACM Press","date_created":"2019-02-13T10:03:25Z","conference":{"start_date":"2018-07-23","location":"Egham, United Kingdom","end_date":"2018-07-27","name":"PODC: Principles of Distributed Computing"},"language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"scopus_import":"1","title":"Relaxed schedulers can efficiently parallelize iterative algorithms","abstract":[{"text":"There has been significant progress in understanding the parallelism inherent to iterative sequential algorithms: for many classic algorithms, the depth of the dependence structure is now well understood, and scheduling techniques have been developed to exploit this shallow dependence structure for efficient parallel implementations. A related, applied research strand has studied methods by which certain iterative task-based algorithms can be efficiently parallelized via relaxed concurrent priority schedulers. These allow for high concurrency when inserting and removing tasks, at the cost of executing superfluous work due to the relaxed semantics of the scheduler. In this work, we take a step towards unifying these two research directions, by showing that there exists a family of relaxed priority schedulers that can efficiently and deterministically execute classic iterative algorithms such as greedy maximal independent set (MIS) and matching. Our primary result shows that, given a randomized scheduler with an expected relaxation factor of k in terms of the maximum allowed priority inversions on a task, and any graph on n vertices, the scheduler is able to execute greedy MIS with only an additive factor of \\poly(k) expected additional iterations compared to an exact (but not scalable) scheduler. This counter-intuitive result demonstrates that the overhead of relaxation when computing MIS is not dependent on the input size or structure of the input graph. Experimental results show that this overhead can be clearly offset by the gain in performance due to the highly scalable scheduler. In sum, we present an efficient method to deterministically parallelize iterative sequential algorithms, with provable runtime guarantees in terms of the number of executed tasks to completion.","lang":"eng"}],"oa_version":"Preprint","quality_controlled":"1","doi":"10.1145/3212734.3212756","day":"23","type":"conference","citation":{"ista":"Alistarh D-A, Brown TA, Kopinsky J, Nadiradze G. 2018. Relaxed schedulers can efficiently parallelize iterative algorithms. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. PODC: Principles of Distributed Computing, 377–386.","apa":"Alistarh, D.-A., Brown, T. A., Kopinsky, J., &#38; Nadiradze, G. (2018). Relaxed schedulers can efficiently parallelize iterative algorithms. In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i> (pp. 377–386). Egham, United Kingdom: ACM Press. <a href=\"https://doi.org/10.1145/3212734.3212756\">https://doi.org/10.1145/3212734.3212756</a>","chicago":"Alistarh, Dan-Adrian, Trevor A Brown, Justin Kopinsky, and Giorgi Nadiradze. “Relaxed Schedulers Can Efficiently Parallelize Iterative Algorithms.” In <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, 377–86. ACM Press, 2018. <a href=\"https://doi.org/10.1145/3212734.3212756\">https://doi.org/10.1145/3212734.3212756</a>.","ama":"Alistarh D-A, Brown TA, Kopinsky J, Nadiradze G. Relaxed schedulers can efficiently parallelize iterative algorithms. In: <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>. ACM Press; 2018:377-386. doi:<a href=\"https://doi.org/10.1145/3212734.3212756\">10.1145/3212734.3212756</a>","ieee":"D.-A. Alistarh, T. A. Brown, J. Kopinsky, and G. Nadiradze, “Relaxed schedulers can efficiently parallelize iterative algorithms,” in <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, Egham, United Kingdom, 2018, pp. 377–386.","short":"D.-A. Alistarh, T.A. Brown, J. Kopinsky, G. Nadiradze, in:, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM Press, 2018, pp. 377–386.","mla":"Alistarh, Dan-Adrian, et al. “Relaxed Schedulers Can Efficiently Parallelize Iterative Algorithms.” <i>Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18</i>, ACM Press, 2018, pp. 377–86, doi:<a href=\"https://doi.org/10.1145/3212734.3212756\">10.1145/3212734.3212756</a>."},"main_file_link":[{"url":"https://arxiv.org/abs/1808.04155","open_access":"1"}]},{"isi":1,"author":[{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X"},{"last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A","full_name":"Brown, Trevor A"},{"last_name":"Kopinsky","first_name":"Justin","full_name":"Kopinsky, Justin"},{"last_name":"Li","first_name":"Jerry Z.","full_name":"Li, Jerry Z."},{"full_name":"Nadiradze, Giorgi","first_name":"Giorgi","last_name":"Nadiradze"}],"external_id":{"arxiv":["1804.01018"],"isi":["000545269600016"]},"oa":1,"article_processing_charge":"No","page":"133-142","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","date_published":"2018-07-16T00:00:00Z","year":"2018","publication_identifier":{"isbn":["9781450357999"]},"date_updated":"2023-09-19T10:44:13Z","publication_status":"published","arxiv":1,"_id":"5965","publisher":"ACM Press","publication":"Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA '18","month":"07","abstract":[{"lang":"eng","text":"Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications (\\citeNguyen13, gonzalez2012powergraph ). Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent data structures, such as the popular MultiQueue~\\citeMQ pattern for implementing relaxed priority queue data structures, for which no guarantees are known in the concurrent setting~\\citeAKLN17. Our main contribution is in showing for the first time that, under a set of analytic assumptions, a family of relaxed concurrent data structures, including variants of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter, provides strong probabilistic guarantees on the degree of relaxation with respect to the sequential specification, in arbitrary concurrent executions. We formalize these guarantees via a new correctness condition called distributional linearizability, tailored to concurrent implementations with randomized relaxations. Our result is based on a new analysis of an asynchronous variant of the classic power-of-two-choices load balancing algorithm, in which placement choices can be based on inconsistent, outdated information (this result may be of independent interest). We validate our results empirically, showing that the MultiCounter algorithm can implement scalable relaxed timestamps."}],"title":"Distributionally linearizable data structures","scopus_import":"1","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"conference":{"name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","location":"Vienna, Austria","end_date":"2018-07-18","start_date":"2018-07-16"},"date_created":"2019-02-13T10:17:19Z","main_file_link":[{"url":"https://arxiv.org/abs/1804.01018","open_access":"1"}],"related_material":{"record":[{"id":"10429","status":"public","relation":"dissertation_contains"}]},"citation":{"mla":"Alistarh, Dan-Adrian, et al. “Distributionally Linearizable Data Structures.” <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, ACM Press, 2018, pp. 133–42, doi:<a href=\"https://doi.org/10.1145/3210377.3210411\">10.1145/3210377.3210411</a>.","ista":"Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. 2018. Distributionally linearizable data structures. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18. SPAA: Symposium on Parallelism in Algorithms and Architectures, 133–142.","chicago":"Alistarh, Dan-Adrian, Trevor A Brown, Justin Kopinsky, Jerry Z. Li, and Giorgi Nadiradze. “Distributionally Linearizable Data Structures.” In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, 133–42. ACM Press, 2018. <a href=\"https://doi.org/10.1145/3210377.3210411\">https://doi.org/10.1145/3210377.3210411</a>.","apa":"Alistarh, D.-A., Brown, T. A., Kopinsky, J., Li, J. Z., &#38; Nadiradze, G. (2018). Distributionally linearizable data structures. In <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i> (pp. 133–142). Vienna, Austria: ACM Press. <a href=\"https://doi.org/10.1145/3210377.3210411\">https://doi.org/10.1145/3210377.3210411</a>","ama":"Alistarh D-A, Brown TA, Kopinsky J, Li JZ, Nadiradze G. Distributionally linearizable data structures. In: <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>. ACM Press; 2018:133-142. doi:<a href=\"https://doi.org/10.1145/3210377.3210411\">10.1145/3210377.3210411</a>","short":"D.-A. Alistarh, T.A. Brown, J. Kopinsky, J.Z. Li, G. Nadiradze, in:, Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18, ACM Press, 2018, pp. 133–142.","ieee":"D.-A. Alistarh, T. A. Brown, J. Kopinsky, J. Z. Li, and G. Nadiradze, “Distributionally linearizable data structures,” in <i>Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures  - SPAA ’18</i>, Vienna, Austria, 2018, pp. 133–142."},"day":"16","type":"conference","doi":"10.1145/3210377.3210411","quality_controlled":"1","oa_version":"Preprint"},{"_id":"397","publication_status":"published","date_updated":"2023-09-11T14:10:25Z","date_published":"2018-02-10T00:00:00Z","status":"public","publication_identifier":{"isbn":["978-1-4503-4982-6"]},"year":"2018","article_processing_charge":"No","page":"14 - 27","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Maya","full_name":"Arbel Raviv, Maya","last_name":"Arbel Raviv"},{"last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","first_name":"Trevor A","full_name":"Brown, Trevor A"}],"isi":1,"external_id":{"isi":["000446161100002"]},"month":"02","publisher":"ACM","language":[{"iso":"eng"}],"conference":{"location":"Vienna, Austria","end_date":"2018-02-28","name":"PPoPP: Principles and Practice of Parallel Programming","start_date":"2018-02-24"},"date_created":"2018-12-11T11:46:14Z","department":[{"_id":"DaAl"}],"title":"Harnessing epoch-based reclamation for efficient range queries","scopus_import":"1","alternative_title":["PPoPP"],"abstract":[{"text":"Concurrent sets with range query operations are highly desirable in applications such as in-memory databases. However, few set implementations offer range queries. Known techniques for augmenting data structures with range queries (or operations that can be used to build range queries) have numerous problems that limit their usefulness. For example, they impose high overhead or rely heavily on garbage collection. In this work, we show how to augment data structures with highly efficient range queries, without relying on garbage collection. We identify a property of epoch-based memory reclamation algorithms that makes them ideal for implementing range queries, and produce three algorithms, which use locks, transactional memory and lock-free techniques, respectively. Our algorithms are applicable to more data structures than previous work, and are shown to be highly efficient on a large scale Intel system. ","lang":"eng"}],"volume":53,"intvolume":"        53","issue":"1","oa_version":"None","doi":"10.1145/3178487.3178489","quality_controlled":"1","publist_id":"7430","day":"10","type":"conference","citation":{"mla":"Arbel Raviv, Maya, and Trevor A. Brown. <i>Harnessing Epoch-Based Reclamation for Efficient Range Queries</i>. Vol. 53, no. 1, ACM, 2018, pp. 14–27, doi:<a href=\"https://doi.org/10.1145/3178487.3178489\">10.1145/3178487.3178489</a>.","ama":"Arbel Raviv M, Brown TA. Harnessing epoch-based reclamation for efficient range queries. In: Vol 53. ACM; 2018:14-27. doi:<a href=\"https://doi.org/10.1145/3178487.3178489\">10.1145/3178487.3178489</a>","ieee":"M. Arbel Raviv and T. A. Brown, “Harnessing epoch-based reclamation for efficient range queries,” presented at the PPoPP: Principles and Practice of Parallel Programming, Vienna, Austria, 2018, vol. 53, no. 1, pp. 14–27.","short":"M. Arbel Raviv, T.A. Brown, in:, ACM, 2018, pp. 14–27.","apa":"Arbel Raviv, M., &#38; Brown, T. A. (2018). Harnessing epoch-based reclamation for efficient range queries (Vol. 53, pp. 14–27). Presented at the PPoPP: Principles and Practice of Parallel Programming, Vienna, Austria: ACM. <a href=\"https://doi.org/10.1145/3178487.3178489\">https://doi.org/10.1145/3178487.3178489</a>","ista":"Arbel Raviv M, Brown TA. 2018. Harnessing epoch-based reclamation for efficient range queries. PPoPP: Principles and Practice of Parallel Programming, PPoPP, vol. 53, 14–27.","chicago":"Arbel Raviv, Maya, and Trevor A Brown. “Harnessing Epoch-Based Reclamation for Efficient Range Queries,” 53:14–27. ACM, 2018. <a href=\"https://doi.org/10.1145/3178487.3178489\">https://doi.org/10.1145/3178487.3178489</a>."}}]