{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T14:03:38Z","timestamp":1751033018072,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,31]],"date-time":"2017-12-31T00:00:00Z","timestamp":1514678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>Dynamic race detection is a program analysis technique for detecting errors caused by undesired interleavings of concurrent tasks. A primary challenge when designing efficient race detection algorithms is to achieve manageable space requirements.<\/jats:p>\n          <jats:p>\n            State-of-the-art algorithms for unstructured parallelism require \u0398 (\n            <jats:italic>n<\/jats:italic>\n            ) space per monitored memory location, where\n            <jats:italic>n<\/jats:italic>\n            is the total number of tasks. This is a serious drawback when analyzing programs with many tasks. In contrast, algorithms for programs with a series-parallel (SP) structure require only \u0398 (1) space. Unfortunately, it is currently not well understood if there are classes of parallelism beyond SP that can also benefit from and be analyzed with \u0398 (1) space complexity.\n          <\/jats:p>\n          <jats:p>In this work, we show that structures richer than SP graphs, namely, that of two-dimensional (2D) lattices, can also be analyzed in \u0398 (1) space. Toward that (a) we extend Tarjan\u2019s algorithm for finding lowest common ancestors to handle 2D lattices; (b) from that extension we derive a serial algorithm for race detection that can analyze arbitrary task graphs with a 2D lattice structure; (c) we present a restriction to fork-join that admits precisely the 2D lattices as task graphs (e.g., it can express pipeline parallelism).<\/jats:p>\n          <jats:p>Our work generalizes prior work on structured race detection and aims to provide a deeper understanding of the interplay between structured parallelism and program analysis efficiency.<\/jats:p>","DOI":"10.1145\/3264618","type":"journal-article","created":{"date-parts":[[2018,9,7]],"date-time":"2018-09-07T12:51:06Z","timestamp":1536324666000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Race Detection in Two Dimensions"],"prefix":"10.1145","volume":"4","author":[{"given":"Dimitar","family":"Dimitrov","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Vechev","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vivek","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,9,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Robert Utterback, and Changming Xu.","author":"Agrawal Kunal","year":"2018","unstructured":"Kunal Agrawal , Joseph Devietti , Jeremy T. Fineman , I-Ting Angelina Lee , Robert Utterback, and Changming Xu. 2018 . Race detection and reachability in nearly series-parallel DAGs. In SODA\u201918. Society for Industrial and Applied Mathematics , 16. Kunal Agrawal, Joseph Devietti, Jeremy T. Fineman, I-Ting Angelina Lee, Robert Utterback, and Changming Xu. 2018. Race detection and reachability in nearly series-parallel DAGs. In SODA\u201918. Society for Industrial and Applied Mathematics, 16."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007933"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209958"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Vincent Cav\u00e9 Jisheng Zhao Jun Shirako and Vivek Sarkar. 2011. Habanero- java: The new adventures of old X10. In PPPJ.  Vincent Cav\u00e9 Jisheng Zhao Jun Shirako and Vivek Sarkar. 2011. Habanero- java: The new adventures of old X10. In PPPJ.","DOI":"10.1145\/2093157.2093165"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094852"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755601"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371374"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-014-1430-4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258493"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486174"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755599"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125861"},{"volume-title":"The 1990 International Conference on Parallel Processing. 93--97","author":"Robert H.","key":"e_1_2_1_15_1","unstructured":"Robert H. B. Netzer and Barton P. Miller. 1990. On the complexity of event ordering for shared-memory parallel program executions . In The 1990 International Conference on Parallel Processing. 93--97 . Robert H. B. Netzer and Barton P. Miller. 1990. On the complexity of event ordering for shared-memory parallel program executions. In The 1990 International Conference on Parallel Processing. 93--97."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/130616.130623"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254127"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Raghavan Raman Jisheng Zhao Vivek Sarkar Martin T. Vechev and Eran Yahav. 2010. Efficient data race detection for async-finish parallelism. In RV.   Raghavan Raman Jisheng Zhao Vivek Sarkar Martin T. Vechev and Eran Yahav. 2010. Efficient data race detection for async-finish parallelism. In RV.","DOI":"10.1007\/978-3-642-16612-9_28"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935801"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178515"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3264618","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3264618","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:10:54Z","timestamp":1750212654000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3264618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,31]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3264618"],"URL":"https:\/\/doi.org\/10.1145\/3264618","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2017,12,31]]},"assertion":[{"value":"2016-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}