{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:05Z","timestamp":1750220885188,"version":"3.41.0"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1150036, CCF-1218017, XPS-1439062, CCF-1150013, CCF-1439126, CCF-1527692, CCF-1733873"],"award-info":[{"award-number":["CCF-1150036, CCF-1218017, XPS-1439062, CCF-1150013, CCF-1439126, CCF-1527692, CCF-1733873"]}],"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":[[2019,12,31]]},"abstract":"<jats:p>\n            Record-and-replay systems are useful tools for debugging non-deterministic parallel programs by first\n            <jats:italic>recording<\/jats:italic>\n            an execution and then\n            <jats:italic>replaying<\/jats:italic>\n            that execution to produce the same access pattern. Existing record-and-replay systems generally target thread-based execution models, and record the behaviors and interleavings of individual threads. Dynamic multithreaded languages and libraries, such as the Cilk family, OpenMP, TBB, and the like, do not have a notion of threads. Instead, these languages provide a\n            <jats:italic>processor-oblivious<\/jats:italic>\n            model of programming, where programs expose task parallelism using high-level constructs such as spawn\/sync without regard to the number of threads\/cores available to run the program. Thread-based record-and-replay would violate the processor-oblivious nature of these programs, as they incorporate the number of threads into the recorded information, constraining the replayed execution to the same number of threads.\n          <\/jats:p>\n          <jats:p>\n            In this article, we present a processor-oblivious\n            <jats:italic>record-and-replay<\/jats:italic>\n            scheme for dynamic multithreaded languages where record and replay can use different number of processors and both are scheduled using work stealing. We provide theoretical guarantees for our record and replay scheme\u2014namely that record is optimal for programs with one lock and replay is near-optimal for all cases. In addition, we implemented this scheme in the Cilk Plus runtime system and our evaluation indicates that processor-obliviousness does not cause substantial overheads.\n          <\/jats:p>","DOI":"10.1145\/3365659","type":"journal-article","created":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T13:32:58Z","timestamp":1576589578000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Processor-Oblivious Record and Replay"],"prefix":"10.1145","volume":"6","author":[{"given":"Robert","family":"Utterback","sequence":"first","affiliation":[{"name":"Monmouth College, Monmouth, IL USA"}]},{"given":"Kunal","family":"Agrawal","sequence":"additional","affiliation":[{"name":"Washington University in St. Louis, MO, USA"}]},{"given":"I-Ting Angelina","family":"Lee","sequence":"additional","affiliation":[{"name":"Washington University in St. Louis, MO, USA"}]},{"given":"Milind","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.11"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612688"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629594"},{"volume-title":"Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA\u201998)","author":"Arora Nimar S.","key":"e_1_2_1_4_1"},{"volume-title":"Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201910)","year":"2010","author":"Aviram Amittai","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.105"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639950.1639989"},{"volume-title":"Proceedings of the 16th Annual ACM Symposium on Parallel Algorithms and Architectures. 133--144","author":"Bender Michael A.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1736020.1736029"},{"volume-title":"Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201910)","author":"Bergan Tom","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640096"},{"volume-title":"Proceedings of the 10th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools (PASTE\u201911)","author":"Andrew","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454128"},{"volume-title":"Proceedings of the 3rd Workshop on Emerging Applications and Many-core Architecture. Springer Berlin, 161--171","year":"2010","author":"Bienia Christian","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145840"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/889664"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"volume-title":"Proceedings of the 1st USENIX Conference on Hot Topics in Parallelism (HotPar\u201909)","year":"2009","author":"Bocchino Robert L.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807426.2807434"},{"volume-title":"O\u2019Hallaron","year":"2015","author":"Bryant Randal E.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869459.1869515"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093157.2093165"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094852"},{"volume-title":"Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA\u201998)","author":"Cheng Guang-Ien","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508255"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950376"},{"volume-title":"Proceedings of the 4th ACM SIGPLAN\/SIGOPS International Conference on Virtual Execution Environments (VEE\u201908)","author":"Dunlap George W.","key":"e_1_2_1_30_1"},{"volume-title":"Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA\u201997)","author":"Feng Mingdong","key":"e_1_2_1_31_1"},{"volume-title":"Leiserson","year":"2011","author":"Fineman Jeremy T.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584017"},{"volume-title":"ACM SIGPLAN Conference on Programming Language Design and Implementation. 212--223","author":"Frigo Matteo","key":"e_1_2_1_34_1"},{"volume-title":"JaRec: A portable record\/replay environment for multi-threaded java applications. Software Practice 8 Experience 34, 6 (May","year":"2004","author":"Georges A.","key":"e_1_2_1_35_1"},{"volume-title":"Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201910)","author":"He Yuxiong","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516046.1516068"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462167"},{"volume-title":"Information Technology\u2014Portable Operating System Interface (POSIX)\u2014Part 1: System Application Program Interface (API) [C Language]","year":"1996","author":"Institute of Electrical and Electronic Engineers. 1997.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","unstructured":"Intel Corporation. 2009. Intel(R) Threading Building Blocks. Intel Corporation. Available from http:\/\/www.threadingbuildingblocks.org\/documentation.php.  Intel Corporation. 2009. Intel(R) Threading Building Blocks. Intel Corporation. Available from http:\/\/www.threadingbuildingblocks.org\/documentation.php."},{"volume-title":"Intel Cilk Plus Language Specification","author":"Intel Corporation","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811057"},{"key":"e_1_2_1_43_1","first-page":"4","article-title":"Debugging parallel programs with instant replay","volume":"36","author":"LeBlanc T. J.","year":"1987","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254119"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1736020.1736031"},{"volume-title":"Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA\u201915)","author":"Lee Ting Angelina","key":"e_1_2_1_46_1"},{"volume-title":"Optimize managed code for multi-core machines. MSDN Magazine","year":"2007","author":"Leijen Daan","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145841"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738001"},{"volume-title":"Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles (SOSP\u201911)","author":"Liu Tongping","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065034"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037751"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125861"},{"volume-title":"Handbook of Randomized Computing","author":"Mitzenmacher Michael","key":"e_1_2_1_54_1"},{"volume-title":"Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201916)","author":"Stefan","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168886"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541964"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508256"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629593"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772958"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1669112.1669183"},{"volume-title":"Randomization and Approximation Techniques in Computer Science, Michael Luby, Jos\u00e9 D","author":"Raab Martin","key":"e_1_2_1_62_1"},{"volume-title":"Efficient data race detection for async-finish parallelism","series-title":"Lecture Notes in Computer Science","author":"Raman Raghavan","key":"e_1_2_1_63_1"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254127"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/291889.291893"},{"volume-title":"Cilk Plus Solver for a Chess Puzzle or: How I Learned to Love Fast Rejection. https:\/\/software.intel.com\/en-us\/articles\/cilk-plus-solver-for-a-chess-puzzle-or-how-i-learned-to-love-rejection. (Feb","year":"2013","author":"Robison Arch D.","key":"e_1_2_1_66_1"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/312203.312214"},{"volume-title":"Proc. ACM Meas. Anal. Comput. Syst. 1, 2, Article 43 (Dec.","year":"2017","author":"Schardl Tao B.","key":"e_1_2_1_68_1"},{"volume-title":"Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA\u201915)","author":"Schardl Tao B.","key":"e_1_2_1_69_1"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295735"},{"volume-title":"Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP\u201909)","author":"Nathan","key":"e_1_2_1_72_1"},{"volume-title":"WBIA Workshop at ASPLOS","year":"2006","author":"Uh Gang-Ryung","key":"e_1_2_1_73_1"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935801"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950370"},{"volume-title":"Proceedings of the ACM\/IEEE International Symposium on Computer Architecture. ACM, 122--135","author":"Xu Min","key":"e_1_2_1_76_1"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178515"},{"volume-title":"Proceedings of the 2011 USENIX Conference on USENIX Annual Technical Conference (USENIXATC\u201911)","year":"2011","author":"Yang Zhemin","key":"e_1_2_1_78_1"},{"volume-title":"Newton","year":"2016","author":"Zakian Christopher S.","key":"e_1_2_1_79_1"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365659","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365659","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365659","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:21Z","timestamp":1750203861000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365659"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,17]]},"references-count":77,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3365659"],"URL":"https:\/\/doi.org\/10.1145\/3365659","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2019,12,17]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}