{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:46Z","timestamp":1750220326894,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SIDA\/Bright Project under the Makerere-Sweden bilateral research programme 2015-2020","award":["317"],"award-info":[{"award-number":["317"]}]},{"name":"The Swedish Foundation for International Cooperation in Research and Higher Education (STINT)","award":["SG2021-8934"],"award-info":[{"award-number":["SG2021-8934"]}]},{"name":"The Swedish Research Council (VR)","award":["2021-05443"],"award-info":[{"award-number":["2021-05443"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538578","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"333-344","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Performance Analysis and Modelling of Concurrent Multi-access Data Structures"],"prefix":"10.1145","author":[{"given":"Adones","family":"Rukundo","sequence":"first","affiliation":[{"name":"Chalmers University of Technology, Gothenburg, Sweden"}]},{"given":"Aras","family":"Atalar","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, Gothenburg, Sweden"}]},{"given":"Philippas","family":"Tsigas","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, Gothenburg, Sweden"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1885276.1885295"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17653-1_29"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210411"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212756"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087810"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858788.2688523"},{"key":"e_1_3_2_1_7_1","volume-title":"DISC 2015, Tokyo, Japan, October 7--9, 2015, Proceedings (Lecture Notes in Computer Science","volume":"355","author":"Atalar Aras","year":"2015","unstructured":"Aras Atalar , Paul Renaud-Goud , and Philippas Tsigas . 2015 . Analyzing the Performance of Lock-Free Data Structures: A Conflict-Based Model. In Distributed Computing - 29th International Symposium , DISC 2015, Tokyo, Japan, October 7--9, 2015, Proceedings (Lecture Notes in Computer Science , Vol. 9363), Yoram Moses (Ed.). Springer, 341-- 355 . https:\/\/doi.org\/10.1007\/978--3--662--48653--5_23 10.1007\/978--3--662--48653--5_23 Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas. 2015. Analyzing the Performance of Lock-Free Data Structures: A Conflict-Based Model. In Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7--9, 2015, Proceedings (Lecture Notes in Computer Science, Vol. 9363), Yoram Moses (Ed.). Springer, 341--355. https:\/\/doi.org\/10.1007\/978--3--662--48653--5_23"},{"key":"e_1_3_2_1_8_1","first-page":"1","article-title":"Laws of Order","volume":"46","author":"Attiya Hagit","year":"2011","unstructured":"Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kuznetsov , Maged M. Michael , and Martin Vechev . 2011 . Laws of Order : Expensive Synchronization in Concurrent Algorithms Cannot Be Eliminated. SIGPLAN Not. 46 , 1 (Jan. 2011), 487--498. https:\/\/doi.org\/10.1145\/1925844.1926442 10.1145\/1925844.1926442 Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov, Maged M. Michael, and Martin Vechev. 2011. Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot Be Eliminated. SIGPLAN Not. 46, 1 (Jan. 2011), 487--498. https:\/\/doi.org\/10.1145\/1925844.1926442","journal-title":"Expensive Synchronization in Concurrent Algorithms Cannot Be Eliminated. SIGPLAN Not."},{"volume-title":"Principles of Distributed Systems, Antonio Fern\u00e0ndez Anta","author":"Bar-Nissan Gal","key":"e_1_3_2_1_9_1","unstructured":"Gal Bar-Nissan , Danny Hendler , and Adi Suissa . 2011. A Dynamic Elimination- Combining Stack Algorithm . In Principles of Distributed Systems, Antonio Fern\u00e0ndez Anta , Giuseppe Lipari, and Matthieu Roy (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 544--561. Gal Bar-Nissan, Danny Hendler, and Adi Suissa. 2011. A Dynamic Elimination- Combining Stack Algorithm. In Principles of Distributed Systems, Antonio Fern\u00e0ndez Anta, Giuseppe Lipari, and Matthieu Roy (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 544--561."},{"volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing","author":"Ben-David Naama","key":"e_1_3_2_1_10_1","unstructured":"Naama Ben-David and Guy E. Blelloch . 2017. Analyzing Contention and Backoff in Asynchronous Shared Memory . In Proceedings of the ACM Symposium on Principles of Distributed Computing ( Washington, DC, USA) (PODC '17). ACM, New York, NY, USA, 53--62. https:\/\/doi.org\/10.1145\/3087801.3087828 10.1145\/3087801.3087828 Naama Ben-David and Guy E. Blelloch. 2017. Analyzing Contention and Backoff in Asynchronous Shared Memory. In Proceedings of the ACM Symposium on Principles of Distributed Computing (Washington, DC, USA) (PODC '17). ACM, New York, NY, USA, 53--62. https:\/\/doi.org\/10.1145\/3087801.3087828"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-5316(96)00045-4"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.91"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.127442"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522714"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/268999.269000"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/08072646X"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979427491"},{"key":"e_1_3_2_1_18_1","volume-title":"Local Linearizability for Concurrent Container-Type Data Structures. In 27th International Conference on Concurrency Theory, CONCUR 2016","volume":"15","author":"Haas Andreas","year":"2016","unstructured":"Andreas Haas , Thomas A. Henzinger , Andreas Holzer , Christoph M. Kirsch , Michael Lippautz , Hannes Payer , Ali Sezgin , Ana Sokolova , and Helmut Veith . 2016 . Local Linearizability for Concurrent Container-Type Data Structures. In 27th International Conference on Concurrency Theory, CONCUR 2016 , August 23 --26 , 2016, Qu\u00e9bec City, Canada (LIPIcs, Vol. 59), Jos\u00e9e Desharnais and Radha Jagadeesan (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 6:1--6: 15 . https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2016.6 10.4230\/LIPIcs.CONCUR.2016.6 Andreas Haas, Thomas A. Henzinger, Andreas Holzer, Christoph M. Kirsch, Michael Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, and Helmut Veith. 2016. Local Linearizability for Concurrent Container-Type Data Structures. In 27th International Conference on Concurrency Theory, CONCUR 2016, August 23--26, 2016, Qu\u00e9bec City, Canada (LIPIcs, Vol. 59), Jos\u00e9e Desharnais and Radha Jagadeesan (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 6:1--6:15. https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2016.6"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2482767.2482789"},{"volume-title":"Proceedings of the 42Nd Annual IEEE\/ACM International Symposium on Microarchitecture","author":"Hackenberg Daniel","key":"e_1_3_2_1_20_1","unstructured":"Daniel Hackenberg , Daniel Molka , and Wolfgang E. Nagel . 2009. Comparing Cache Architectures and Coherency Protocols on x86--64 Multicore SMP Systems . In Proceedings of the 42Nd Annual IEEE\/ACM International Symposium on Microarchitecture ( New York, New York) (MICRO 42). ACM, New York, NY, USA, 413--422. https:\/\/doi.org\/10.1145\/1669112.1669165 10.1145\/1669112.1669165 Daniel Hackenberg, Daniel Molka, and Wolfgang E. Nagel. 2009. Comparing Cache Architectures and Coherency Protocols on x86--64 Multicore SMP Systems. In Proceedings of the 42Nd Annual IEEE\/ACM International Symposium on Microarchitecture (New York, New York) (MICRO 42). ACM, New York, NY, USA, 413--422. https:\/\/doi.org\/10.1145\/1669112.1669165"},{"volume-title":"Proceedings of the 42nd Annual IEEE\/ACM International Symposium on Microarchitecture","author":"Hackenberg Daniel","key":"e_1_3_2_1_21_1","unstructured":"Daniel Hackenberg , Daniel Molka , and Wolfgang E. Nagel . 2009. Comparing Cache Architectures and Coherency Protocols on X86--64 Multicore SMP Systems . In Proceedings of the 42nd Annual IEEE\/ACM International Symposium on Microarchitecture ( New York, New York) (MICRO 42). ACM, New York, NY, USA, 413--422. https:\/\/doi.org\/10.1145\/1669112.1669165 10.1145\/1669112.1669165 Daniel Hackenberg, Daniel Molka, and Wolfgang E. Nagel. 2009. Comparing Cache Architectures and Coherency Protocols on X86--64 Multicore SMP Systems. In Proceedings of the 42nd Annual IEEE\/ACM International Symposium on Microarchitecture (New York, New York) (MICRO 42). ACM, New York, NY, USA, 413--422. https:\/\/doi.org\/10.1145\/1669112.1669165"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_30"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.08.011"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2480359.2429109"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3337821.3337901"},{"volume-title":"Intel 64 and IA-32 Architectures Optimization Reference Manual","author":"Intel Corporation 2014.","key":"e_1_3_2_1_26_1","unstructured":"Intel Corporation 2014. Intel 64 and IA-32 Architectures Optimization Reference Manual . Intel Corporation . Intel Corporation 2014. Intel 64 and IA-32 Architectures Optimization Reference Manual. Intel Corporation."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198079"},{"key":"e_1_3_2_1_28_1","volume-title":"Advances in Parallel Computing","volume":"13","author":"Juckeland G.","unstructured":"G. Juckeland , S. B\u00f6rner , M. Kluge , S. K\u00f6lling , W.E. Nagel , S. Pfl\u00fcger , H. R\u00f6ding , S. Seidl , T. William , and R. Wloch . 2004. BenchIT - Performance measurement and comparison for scientific applications. In Parallel Computing, G.R. Joubert, W.E. Nagel, F.J. Peters, and W.V. Walter (Eds.) . Advances in Parallel Computing , Vol. 13 . North-Holland, 501--508. https:\/\/doi.org\/10.1016\/S0927--5452(04)80064--9 10.1016\/S0927--5452(04)80064--9 G. Juckeland, S. B\u00f6rner, M. Kluge, S. K\u00f6lling, W.E. Nagel, S. Pfl\u00fcger, H. R\u00f6ding, S. Seidl, T. William, and R. Wloch. 2004. BenchIT - Performance measurement and comparison for scientific applications. In Parallel Computing, G.R. Joubert, W.E. Nagel, F.J. Peters, and W.V. Walter (Eds.). Advances in Parallel Computing, Vol. 13. North-Holland, 501--508. https:\/\/doi.org\/10.1016\/S0927--5452(04)80064--9"},{"key":"e_1_3_2_1_29_1","volume-title":"Cache Coherence Protocol and Memory Performance of the Intel Haswell-EP Architecture. In 44th International Conference on Parallel Processing, ICPP 2015","author":"Molka Daniel","year":"2015","unstructured":"Daniel Molka , Daniel Hackenberg , Robert Sch\u00f6ne , and Wolfgang E. Nagel . 2015 . Cache Coherence Protocol and Memory Performance of the Intel Haswell-EP Architecture. In 44th International Conference on Parallel Processing, ICPP 2015 , Beijing, China, September 1--4 , 2015 . IEEE Computer Society, 739--748. https:\/\/doi.org\/10.1109\/ICPP.2015.83 10.1109\/ICPP.2015.83 Daniel Molka, Daniel Hackenberg, Robert Sch\u00f6ne, and Wolfgang E. Nagel. 2015. Cache Coherence Protocol and Memory Performance of the Intel Haswell-EP Architecture. In 44th International Conference on Parallel Processing, ICPP 2015, Beijing, China, September 1--4, 2015. IEEE Computer Society, 739--748. https:\/\/doi.org\/10.1109\/ICPP.2015.83"},{"key":"e_1_3_2_1_30_1","volume-title":"Capability Models for Manycore Memory Systems: A Case-Study with Xeon Phi KNL. In 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017","author":"Ramos Sabela","year":"2017","unstructured":"Sabela Ramos and Torsten Hoefler . 2017 . Capability Models for Manycore Memory Systems: A Case-Study with Xeon Phi KNL. In 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017 , Orlando, FL, USA, May 29 - June 2, 2017. IEEE Computer Society, 297--306. https:\/\/doi.org\/10.1109\/IPDPS.2017.30 10.1109\/IPDPS.2017.30 Sabela Ramos and Torsten Hoefler. 2017. Capability Models for Manycore Memory Systems: A Case-Study with Xeon Phi KNL. In 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017, Orlando, FL, USA, May 29 - June 2, 2017. IEEE Computer Society, 297--306. https:\/\/doi.org\/10.1109\/IPDPS.2017.30"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755616"},{"key":"e_1_3_2_1_32_1","volume-title":"33rd International Symposium on Distributed Computing, DISC 2019","volume":"15","author":"Rukundo Adones","year":"2019","unstructured":"Adones Rukundo , Aras Atalar , and Philippas Tsigas . 2019 . Monotonically Relaxing Concurrent Data-Structure Semantics for Increasing Performance: An Efficient 2D Design Framework . In 33rd International Symposium on Distributed Computing, DISC 2019 , October 14 --18 , 2019, Budapest, Hungary (LIPIcs, Vol. 146), Jukka Suomela (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 31:1--31: 15 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2019.31 10.4230\/LIPIcs.DISC.2019.31 Adones Rukundo, Aras Atalar, and Philippas Tsigas. 2019. Monotonically Relaxing Concurrent Data-Structure Semantics for Increasing Performance: An Efficient 2D Design Framework. In 33rd International Symposium on Distributed Computing, DISC 2019, October 14--18, 2019, Budapest, Hungary (LIPIcs, Vol. 146), Jukka Suomela (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 31:1--31:15. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2019.31"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370816.2370861"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.24"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1897852.1897873"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/215399.215419"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1621"},{"key":"e_1_3_2_1_38_1","volume-title":"SSS 2017, Boston, MA, USA, November 5--8, 2017, Proceedings (Lecture Notes in Computer Science","volume":"156","author":"Talmage Edward","unstructured":"Edward Talmage and Jennifer L. Welch . 2017. Relaxed Data Types as Consistency Conditions. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium , SSS 2017, Boston, MA, USA, November 5--8, 2017, Proceedings (Lecture Notes in Computer Science , Vol. 10616), Paul G. Spirakis and Philippas Tsigas (Eds.). Springer, 142-- 156 . https:\/\/doi.org\/10.1007\/978--3--319--69084--1_10 10.1007\/978--3--319--69084--1_10 Edward Talmage and Jennifer L.Welch. 2017. Relaxed Data Types as Consistency Conditions. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium, SSS 2017, Boston, MA, USA, November 5--8, 2017, Proceedings (Lecture Notes in Computer Science, Vol. 10616), Paul G. Spirakis and Philippas Tsigas (Eds.). Springer, 142--156. https:\/\/doi.org\/10.1007\/978--3--319--69084--1_10"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688547"}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Philadelphia PA USA","acronym":"SPAA '22"},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538578","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538578","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:08Z","timestamp":1750191128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":39,"alternative-id":["10.1145\/3490148.3538578","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538578","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}