{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:02Z","timestamp":1750221242209,"version":"3.41.0"},"reference-count":50,"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"}],"funder":[{"name":"MIT Akamai Fellowship"},{"name":"NSF Graduate Research Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1314547"],"award-info":[{"award-number":["1314547"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"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>A multithreaded Cilk program that is ostensibly deterministic may nevertheless behave nondeterministically due to programming errors in the code. For a Cilk program that uses reducers\u2014a general reduction mechanism supported in various Cilk dialects\u2014such programming errors are especially challenging to debug, because the errors can expose the nondeterminism in how the Cilk runtime system manages reducers.<\/jats:p>\n          <jats:p>We identify two unique types of races that arise from incorrect use of reducers in a Cilk program, and we present two algorithms to catch these races. The first algorithm, called the Peer-Set algorithm, detects view-read races, which occur when the program attempts to retrieve a value out of a reducer when the read may result in a nondeterministic value, such as before all previously spawned subcomputations that might update the reducer have necessarily returned. The second algorithm, called the SP+ algorithm, detects determinacy races\u2014instances where a write to a memory location occurs logically in parallel with another access to that location\u2014even when the raced-on memory locations relate to reducers. Both algorithms are provably correct, asymptotically efficient, and can be implemented efficiently in practice. We have implemented both algorithms in our prototype race detector, Rader. When running Peer-Set, Rader incurs a geometric-mean multiplicative overhead of 2.56 over running the benchmark without instrumentation. When running SP+, Rader incurs a geometric-mean multiplicative overhead of 16.94.<\/jats:p>","DOI":"10.1145\/3205914","type":"journal-article","created":{"date-parts":[[2018,8,13]],"date-time":"2018-08-13T12:29:41Z","timestamp":1534163381000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Race Detection for Reducer Hyperobjects"],"prefix":"10.1145","volume":"4","author":[{"given":"I-Ting Angelina","family":"Lee","sequence":"first","affiliation":[{"name":"Washington University in St. Louis, MO"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao B.","family":"Schardl","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119479.1119480"},{"volume-title":"Stoller","year":"2004","author":"Agrawal Rahul","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007933"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454128"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504287"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093157.2093165"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277696"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512560"},{"edition":"3","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2337159.2337182"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755601"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/99163.99165"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945468"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924943.1924954"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000120"},{"volume-title":"Provably Good Race Detection That Runs in Parallel. Master\u2019s Thesis","author":"Fineman Jeremy T.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584017"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_2_1_21_1","unstructured":"GCC 4.8. 2014. GCC 4.8 Release Series Changes New Features and Fixes. Retrieved from https:\/\/gcc.gnu.org\/gcc-4.8\/changes.html.  GCC 4.8. 2014. GCC 4.8 Release Series Changes New Features and Fixes. Retrieved from https:\/\/gcc.gnu.org\/gcc-4.8\/changes.html."},{"key":"e_1_2_1_22_1","unstructured":"Intel Corporation. 2011. Intrinsics for Low Overhead Tool Annotations. Retrieved from https:\/\/www.cilkplus.org\/open_specification\/intrinsics-low-overhead-tool-annotations-v10.  Intel Corporation. 2011. Intrinsics for Low Overhead Tool Annotations. Retrieved from https:\/\/www.cilkplus.org\/open_specification\/intrinsics-low-overhead-tool-annotations-v10."},{"volume-title":"Version 1.1. Document 324396-002US","author":"Intel Corporation","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","unstructured":"Intel Corporation. 2013. An Introduction to the Cilk Screen Race Detector. Retrieved from https:\/\/software.intel.com\/en-us\/articles\/an-introduction-to-the-cilk-screen-race-detector.  Intel Corporation. 2013. An Introduction to the Cilk Screen Race Detector. Retrieved from https:\/\/software.intel.com\/en-us\/articles\/an-introduction-to-the-cilk-screen-race-detector."},{"key":"e_1_2_1_25_1","unstructured":"ISO\/IEC. 2017. ISO\/IEC 14882:2017(E)\u2014Programming Language C++. Retrieved from https:\/\/isocpp.org\/std\/the-standard.  ISO\/IEC. 2017. ISO\/IEC 14882:2017(E)\u2014Programming Language C++. Retrieved from https:\/\/isocpp.org\/std\/the-standard."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854324"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312056"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-010-0405-3"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810534"},{"key":"e_1_2_1_30_1","unstructured":"Don McCrady. 2008. Avoiding contention using combinable objects. Microsoft Developer Network Blog Post. Re-trieved from. http:\/\/blogs.msdn.com\/nativeconcurrency\/archive\/2008\/09\/25\/avoiding-contention-using-combinable-objects.aspx.  Don McCrady. 2008. Avoiding contention using combinable objects. Microsoft Developer Network Blog Post. Re-trieved from. http:\/\/blogs.msdn.com\/nativeconcurrency\/archive\/2008\/09\/25\/avoiding-contention-using-combinable-objects.aspx."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125861"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/130616.130623"},{"volume-title":"Proceedings of the 1st Israeli Conference on Computer Systems Engineering.","year":"1986","author":"Nudler Itzhak","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/781498.781528"},{"key":"e_1_2_1_36_1","unstructured":"OpenMP Architecture Review Board. 2013. OpenMP Application Program Interface Version 4.0. Retrieved from http:\/\/www.openmp.org\/mp-documents\/OpenMP4.0.0.pdf.  OpenMP Architecture Review Board. 2013. OpenMP Application Program Interface Version 4.0. Retrieved from http:\/\/www.openmp.org\/mp-documents\/OpenMP4.0.0.pdf."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1228965.1228969"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1889997.1890000"},{"volume-title":"Runtime Verification","series-title":"Lecture Notes in Computer Science","author":"Raman Raghavan","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254127"},{"volume-title":"Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism","author":"Reinders James","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/268998.266641"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1791194.1791203"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161071"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935801"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504288"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287624.1287654"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.10"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095832"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3205914","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3205914","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3205914","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:32Z","timestamp":1750212452000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3205914"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,31]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3205914"],"URL":"https:\/\/doi.org\/10.1145\/3205914","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-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}