[{"type":"conference","abstract":[{"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.","lang":"eng"}],"issue":"7","title":"Memory tagging: Minimalist synchronization for scalable concurrent data structures","status":"public","publication_status":"published","publisher":"Association for Computing Machinery","department":[{"_id":"DaAl"}],"year":"2020","_id":"8191","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2020-08-02T22:00:58Z","date_updated":"2024-02-28T12:56:32Z","oa_version":"None","author":[{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Brown, Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","last_name":"Brown","first_name":"Trevor A"},{"first_name":"Nandini","last_name":"Singhal","full_name":"Singhal, Nandini"}],"scopus_import":"1","month":"07","day":"06","article_processing_charge":"No","publication_identifier":{"isbn":["9781450369350"]},"isi":1,"quality_controlled":"1","page":"37-49","publication":"Annual ACM Symposium on Parallelism in Algorithms and Architectures","citation":{"mla":"Alistarh, Dan-Adrian, et al. “Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures.” Annual ACM Symposium on Parallelism in Algorithms and Architectures, no. 7, Association for Computing Machinery, 2020, pp. 37–49, doi:10.1145/3350755.3400213.","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.","chicago":"Alistarh, Dan-Adrian, Trevor A Brown, and Nandini Singhal. “Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures.” In Annual ACM Symposium on Parallelism in Algorithms and Architectures, 37–49. Association for Computing Machinery, 2020. https://doi.org/10.1145/3350755.3400213.","ama":"Alistarh D-A, Brown TA, Singhal N. Memory tagging: Minimalist synchronization for scalable concurrent data structures. In: Annual ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery; 2020:37-49. doi:10.1145/3350755.3400213","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.","apa":"Alistarh, D.-A., Brown, T. A., & Singhal, N. (2020). Memory tagging: Minimalist synchronization for scalable concurrent data structures. In Annual ACM Symposium on Parallelism in Algorithms and Architectures (pp. 37–49). Virtual Event, United States: Association for Computing Machinery. https://doi.org/10.1145/3350755.3400213","ieee":"D.-A. Alistarh, T. A. Brown, and N. Singhal, “Memory tagging: Minimalist synchronization for scalable concurrent data structures,” in Annual ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, United States, 2020, no. 7, pp. 37–49."},"external_id":{"isi":["000744436200004"]},"language":[{"iso":"eng"}],"conference":{"location":"Virtual Event, United States","start_date":"2020-07-15","end_date":"2020-07-17","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"},"date_published":"2020-07-06T00:00:00Z","doi":"10.1145/3350755.3400213"},{"_id":"7635","year":"2020","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Association for Computing Machinery","department":[{"_id":"DaAl"}],"status":"public","publication_status":"published","title":"Testing concurrency on the JVM with Lincheck","author":[{"full_name":"Koval, Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","last_name":"Koval","first_name":"Nikita"},{"id":"26217AE4-77FF-11EA-8101-AD24D49E41F4","first_name":"Mariia","last_name":"Sokolova","full_name":"Sokolova, Mariia"},{"full_name":"Fedorov, Alexander","first_name":"Alexander","last_name":"Fedorov"},{"orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Dmitry","last_name":"Tsitelov","full_name":"Tsitelov, Dmitry"}],"oa_version":"None","date_created":"2020-04-05T22:00:48Z","date_updated":"2024-02-28T12:53:46Z","type":"conference","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"}],"citation":{"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","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.","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","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.","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.","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.","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."},"publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP","page":"423-424","quality_controlled":"1","date_published":"2020-02-19T00:00:00Z","doi":"10.1145/3332466.3374503","conference":{"name":"PPOPP: Principles and Practice of Parallel Programming","location":"San Diego, CA, United States","start_date":"2020-02-22","end_date":"2020-02-26"},"language":[{"iso":"eng"}],"scopus_import":"1","publication_identifier":{"isbn":["9781450368186"]},"article_processing_charge":"No","month":"02","day":"19"},{"type":"conference","abstract":[{"text":"We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We explain why this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.","lang":"eng"}],"_id":"8383","year":"2020","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"DaAl"}],"publisher":"Association for Computing Machinery","status":"public","publication_status":"published","title":"Brief Announcement: Why Extension-Based Proofs Fail","author":[{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Aspnes, James","first_name":"James","last_name":"Aspnes"},{"last_name":"Ellen","first_name":"Faith","full_name":"Ellen, Faith"},{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"},{"first_name":"Leqi","last_name":"Zhu","full_name":"Zhu, Leqi"}],"oa_version":"None","date_updated":"2024-02-28T12:54:19Z","date_created":"2020-09-13T22:01:18Z","scopus_import":"1","article_processing_charge":"No","publication_identifier":{"isbn":["9781450375825"]},"month":"07","day":"31","citation":{"mla":"Alistarh, Dan-Adrian, et al. “Brief Announcement: Why Extension-Based Proofs Fail.” Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 54–56, doi:10.1145/3382734.3405743.","short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 54–56.","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Brief Announcement: Why Extension-Based Proofs Fail.” In Proceedings of the 39th Symposium on Principles of Distributed Computing, 54–56. Association for Computing Machinery, 2020. https://doi.org/10.1145/3382734.3405743.","ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Brief Announcement: Why Extension-Based Proofs Fail. In: Proceedings of the 39th Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2020:54-56. doi:10.1145/3382734.3405743","ista":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2020. Brief Announcement: Why Extension-Based Proofs Fail. Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 54–56.","apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2020). Brief Announcement: Why Extension-Based Proofs Fail. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 54–56). Virtual, Italy: Association for Computing Machinery. https://doi.org/10.1145/3382734.3405743","ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Brief Announcement: Why Extension-Based Proofs Fail,” in Proceedings of the 39th Symposium on Principles of Distributed Computing, Virtual, Italy, 2020, pp. 54–56."},"publication":"Proceedings of the 39th Symposium on Principles of Distributed Computing","page":"54-56","quality_controlled":"1","date_published":"2020-07-31T00:00:00Z","doi":"10.1145/3382734.3405743","conference":{"name":"PODC: Principles of Distributed Computing","end_date":"2020-08-07","location":"Virtual, Italy","start_date":"2020-08-03"},"language":[{"iso":"eng"}]},{"type":"journal_article","issue":"4","abstract":[{"text":"We present a method for animating yarn-level cloth effects using a thin-shell solver. We accomplish this through numerical homogenization: we first use a large number of yarn-level simulations to build a model of the potential energy density of the cloth, and then use this energy density function to compute forces in a thin shell simulator. We model several yarn-based materials, including both woven and knitted fabrics. Our model faithfully reproduces expected effects like the stiffness of woven fabrics, and the highly deformable nature and anisotropy of knitted fabrics. Our approach does not require any real-world experiments nor measurements; because the method is based entirely on simulations, it can generate entirely new material models quickly, without the need for testing apparatuses or human intervention. We provide data-driven models of several woven and knitted fabrics, which can be used for efficient simulation with an off-the-shelf cloth solver.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"8385","intvolume":" 39","title":"Homogenized yarn-level cloth","status":"public","ddc":["000"],"file":[{"file_id":"8794","relation":"main_file","date_updated":"2020-11-23T09:01:22Z","date_created":"2020-11-23T09:01:22Z","success":1,"checksum":"cf4c1d361c3196c4bd424520a5588205","file_name":"2020_hylc_submitted.pdf","access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_size":38922662}],"oa_version":"Submitted Version","scopus_import":"1","has_accepted_license":"1","article_processing_charge":"No","day":"08","citation":{"chicago":"Sperl, Georg, Rahul Narain, and Chris Wojtan. “Homogenized Yarn-Level Cloth.” ACM Transactions on Graphics. Association for Computing Machinery, 2020. https://doi.org/10.1145/3386569.3392412.","mla":"Sperl, Georg, et al. “Homogenized Yarn-Level Cloth.” ACM Transactions on Graphics, vol. 39, no. 4, 48, Association for Computing Machinery, 2020, doi:10.1145/3386569.3392412.","short":"G. Sperl, R. Narain, C. Wojtan, ACM Transactions on Graphics 39 (2020).","ista":"Sperl G, Narain R, Wojtan C. 2020. Homogenized yarn-level cloth. ACM Transactions on Graphics. 39(4), 48.","apa":"Sperl, G., Narain, R., & Wojtan, C. (2020). Homogenized yarn-level cloth. ACM Transactions on Graphics. Association for Computing Machinery. https://doi.org/10.1145/3386569.3392412","ieee":"G. Sperl, R. Narain, and C. Wojtan, “Homogenized yarn-level cloth,” ACM Transactions on Graphics, vol. 39, no. 4. Association for Computing Machinery, 2020.","ama":"Sperl G, Narain R, Wojtan C. Homogenized yarn-level cloth. ACM Transactions on Graphics. 2020;39(4). doi:10.1145/3386569.3392412"},"publication":"ACM Transactions on Graphics","article_type":"original","date_published":"2020-07-08T00:00:00Z","article_number":"48","ec_funded":1,"file_date_updated":"2020-11-23T09:01:22Z","acknowledgement":"We wish to thank the anonymous reviewers and the members of the Visual Computing Group at IST Austria for their valuable feedback. We also thank the creators of the Berkeley Garment Library [de Joya et al. 2012] for providing garment meshes, [Krishnamurthy and Levoy 1996] and [Turk and Levoy 1994] for the armadillo and bunny meshes, the creators of libWetCloth [Fei et al. 2018] for their implementation of discrete elastic rod forces, and Tomáš Skřivan for\r\ninspiring discussions and help with Mathematica code generation. This research was supported by the Scientific Service Units (SSU) of IST Austria through resources provided by Scientific Computing. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 638176. Rahul Narain is supported by a Pankaj Gupta Young Faculty Fellowship and a gift from Adobe Inc.","year":"2020","publisher":"Association for Computing Machinery","department":[{"_id":"ChWo"}],"publication_status":"published","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"12358"}]},"author":[{"last_name":"Sperl","first_name":"Georg","id":"4DD40360-F248-11E8-B48F-1D18A9856A87","full_name":"Sperl, Georg"},{"last_name":"Narain","first_name":"Rahul","full_name":"Narain, Rahul"},{"full_name":"Wojtan, Christopher J","first_name":"Christopher J","last_name":"Wojtan","id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6646-5546"}],"volume":39,"date_created":"2020-09-13T22:01:18Z","date_updated":"2024-02-28T12:57:47Z","publication_identifier":{"eissn":["15577368"],"issn":["07300301"]},"month":"07","oa":1,"main_file_link":[{"url":"https://doi.org/10.1145/3386569.3392412","open_access":"1"}],"external_id":{"isi":["000583700300021"]},"project":[{"name":"Efficient Simulation of Natural Phenomena at Extremely Large Scales","call_identifier":"H2020","grant_number":"638176","_id":"2533E772-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","isi":1,"doi":"10.1145/3386569.3392412","language":[{"iso":"eng"}],"acknowledged_ssus":[{"_id":"ScienComp"}]},{"article_number":"204905","ec_funded":1,"year":"2020","publication_status":"published","publisher":"AIP Publishing","department":[{"_id":"MiLe"}],"author":[{"last_name":"Pȩkalski","first_name":"J.","full_name":"Pȩkalski, J."},{"id":"48C55298-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1106-4419","first_name":"Wojciech","last_name":"Rzadkowski","full_name":"Rzadkowski, Wojciech"},{"full_name":"Panagiotopoulos, A. Z.","last_name":"Panagiotopoulos","first_name":"A. Z."}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10759"}]},"date_updated":"2024-02-28T13:00:28Z","date_created":"2020-06-14T22:00:49Z","volume":152,"month":"05","publication_identifier":{"eissn":["10897690"]},"external_id":{"arxiv":["2002.07294"],"isi":["000537900300001"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1063/5.0005194"}],"oa":1,"quality_controlled":"1","isi":1,"project":[{"name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385"}],"doi":"10.1063/5.0005194","language":[{"iso":"eng"}],"type":"journal_article","abstract":[{"lang":"eng","text":"When short-range attractions are combined with long-range repulsions in colloidal particle systems, complex microphases can emerge. Here, we study a system of isotropic particles, which can form lamellar structures or a disordered fluid phase when temperature is varied. We show that, at equilibrium, the lamellar structure crystallizes, while out of equilibrium, the system forms a variety of structures at different shear rates and temperatures above melting. The shear-induced ordering is analyzed by means of principal component analysis and artificial neural networks, which are applied to data of reduced dimensionality. Our results reveal the possibility of inducing ordering by shear, potentially providing a feasible route to the fabrication of ordered lamellar structures from isotropic particles."}],"issue":"20","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7956","title":"Shear-induced ordering in systems with competing interactions: A machine learning study","status":"public","intvolume":" 152","oa_version":"Published Version","scopus_import":"1","day":"29","article_processing_charge":"No","publication":"The Journal of chemical physics","citation":{"apa":"Pȩkalski, J., Rzadkowski, W., & Panagiotopoulos, A. Z. (2020). Shear-induced ordering in systems with competing interactions: A machine learning study. The Journal of Chemical Physics. AIP Publishing. https://doi.org/10.1063/5.0005194","ieee":"J. Pȩkalski, W. Rzadkowski, and A. Z. Panagiotopoulos, “Shear-induced ordering in systems with competing interactions: A machine learning study,” The Journal of chemical physics, vol. 152, no. 20. AIP Publishing, 2020.","ista":"Pȩkalski J, Rzadkowski W, Panagiotopoulos AZ. 2020. Shear-induced ordering in systems with competing interactions: A machine learning study. The Journal of chemical physics. 152(20), 204905.","ama":"Pȩkalski J, Rzadkowski W, Panagiotopoulos AZ. Shear-induced ordering in systems with competing interactions: A machine learning study. The Journal of chemical physics. 2020;152(20). doi:10.1063/5.0005194","chicago":"Pȩkalski, J., Wojciech Rzadkowski, and A. Z. Panagiotopoulos. “Shear-Induced Ordering in Systems with Competing Interactions: A Machine Learning Study.” The Journal of Chemical Physics. AIP Publishing, 2020. https://doi.org/10.1063/5.0005194.","short":"J. Pȩkalski, W. Rzadkowski, A.Z. Panagiotopoulos, The Journal of Chemical Physics 152 (2020).","mla":"Pȩkalski, J., et al. “Shear-Induced Ordering in Systems with Competing Interactions: A Machine Learning Study.” The Journal of Chemical Physics, vol. 152, no. 20, 204905, AIP Publishing, 2020, doi:10.1063/5.0005194."},"article_type":"original","date_published":"2020-05-29T00:00:00Z"}]