{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T17:45:26Z","timestamp":1789235126446,"version":"build-2803163510"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2403144"],"award-info":[{"award-number":["CCF-2403144"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,10,8]]},"abstract":"<jats:p>Coarse-grained reconfigurable arrays (CGRAs) have gained attention in recent years due to their promising power efficiency compared to traditional von Neumann architectures. To program these architectures using ordinary languages such as C, a dataflow compiler must transform the original sequential, imperative program into an equivalent dataflow graph, composed of dataflow operators running in parallel. This transformation is challenging since the asynchronous nature of dataflow graphs allows out-of-order execution of operators, leading to behaviors not present in the original imperative programs.<\/jats:p>\n                  <jats:p>Weaddress this challenge by developing a translation validation technique for dataflow compilers to ensure that the dataflow program has the same behavior as the original imperative program on all possible inputs and schedules of execution. We apply this method to a state-of-the-art dataflow compiler targeting the RipTide CGRAarchitecture. Our tool uncovers 8 compiler bugs where the compiler outputs incorrect dataflow graphs, including a data race that is otherwise hard to discover via testing. After repairing these bugs, our tool verifies the correct compilation of all programs in the RipTide benchmark suite.<\/jats:p>","DOI":"10.1145\/3689729","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T03:23:04Z","timestamp":1728357784000},"page":"499-526","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["FlowCert: Translation Validation for Asynchronous Dataflow via Dynamic Fractional Permissions"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5475-5765","authenticated-orcid":false,"given":"Zhengyao","family":"Lin","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2257-7073","authenticated-orcid":false,"given":"Joshua","family":"Gancher","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9113-1684","authenticated-orcid":false,"given":"Bryan","family":"Parno","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1982.1653938"},{"key":"e_1_3_1_3_1","first-page":"225","volume-title":"Dataflow Architectures.","year":"1986","unstructured":"Arvind and David E. Culler. 1986. Dataflow Architectures. Annual Reviews Inc., USA, 225\u2013253."},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172752"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133934"},{"issue":"3","key":"e_1_3_1_6_1","first-page":"39","article-title":"A Survey of Symbolic Execution Techniques","volume":"51","author":"Baldoni Roberto","year":"2018","unstructured":"Roberto Baldoni, Emilio Coppa, Daniele Cono D'elia, Camil Demetrescu, and Irene Finocchi. 2018. A Survey of Symbolic Execution Techniques. ACM Comput. Surv. 51, 3, Article 50 (may 2018), 39 pages. https:\/\/doi.org\/10.1145\/3182657 10.1145\/3182657","journal-title":"ACM Comput. Surv."},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028770"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062358"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36946-9_10"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.04.008"},{"key":"e_1_3_1_11_1","first-page":"510","volume-title":"Computer Aided Verification","author":"Champion Adrien","year":"2016","unstructured":"Adrien Champion, Alain Mebsout, Christoph Sticksel, and Cesare Tinelli. 2016. The Kind 2 Model Checker. In Computer Aided Verification, Swarat Chaudhuri and Azadeh Farzan (Eds.). Springer International Publishing, Cham, 510\u2013517. https:\/\/doi.org\/10.1007\/978-3-319-41540-6_29 10.1007\/978-3-319-41540-6_29"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00359-0"},{"key":"e_1_3_1_13_1","unstructured":"Brad Conte. 2024. Basic implementations of standard cryptography algorithms. https:\/\/github.com\/B-Con\/crypto-algorithms."},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134029"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/641675.642111"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2019.100513"},{"key":"e_1_3_1_18_1","first-page":"15","article-title":"The semantics of a simple language for parallel programming","volume":"74","author":"Gilles Kahn","year":"1974","unstructured":"Kahn Gilles. 1974. The semantics of a simple language for parallel programming. Information processing 74, 471-475 (1974), 15\u201328.","journal-title":"Information processing"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00084"},{"key":"e_1_3_1_20_1","first-page":"546","volume-title":"Proceedings of the 55th Annual IEEE\/ACM International Symposium on Microarchitecture (Chicago, Illinois, USA) (MICRO \u201822)","author":"Gobieski Graham","year":"2023","unstructured":"Graham Gobieski, Souradip Ghosh, Marijn Heule, Todd Mowry, Tony Nowatzki, Nathan Beckmann, and Brandon Lucia. 2023. RipTide: A Programmable, Energy-Minimal Dataflow Compiler and Architecture. In Proceedings of the 55th Annual IEEE\/ACM International Symposium on Microarchitecture (Chicago, Illinois, USA) (MICRO \u201822). IEEE Press, New York, NY, USA, 546\u2013564. https:\/\/doi.org\/10.1109\/MICRO56248.2022.00046 10.1109\/MICRO56248.2022.00046"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.839324"},{"key":"e_1_3_1_22_1","unstructured":"Paul Govereau. 2012. Denotational Translation Validation. Ph. D. Dissertation. Harvard University USA. Advisor(s) Morrisett John G. AAI3495610."},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1517424.1517439"},{"key":"e_1_3_1_24_1","doi-asserted-by":"crossref","unstructured":"Kohei Honda. 1993. Types for dyadic interaction. In CONCUR'93 Eike Best (Ed.). Springer Berlin Heidelberg Berlin Heidelberg 509\u2013523. https:\/\/doi.org\/10.1007\/3-540-57208-2_35 10.1007\/3-540-57208-2_35","DOI":"10.1007\/3-540-57208-2_35"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013208.1013209"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775051.2676980"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114108"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446751"},{"key":"e_1_3_1_29_1","first-page":"263","volume-title":"Computational Problems in Abstract Algebra","author":"Knuth Donald E","year":"1970","unstructured":"Donald E. Knuth and Peter B. Bendix. 1970. Simple Word Problems in Universal Algebras. In Computational Problems in Abstract Algebra. Pergamon, Oxford, UK, 263\u2013297. https:\/\/doi.org\/10.1016\/B978-0-08-012975-4.50028-X 10.1016\/B978-0-08-012975-4.50028-X"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385980"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542513"},{"key":"e_1_3_1_32_1","doi-asserted-by":"crossref","unstructured":"Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 4 32 (December 2001) 51\u201358. https:\/\/www.microsoft.com\/en-us\/research\/publication\/paxos-made-simple\/","DOI":"10.1145\/568425.568433"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_3_1_34_1","first-page":"30","article-title":"Verus: Verifying Rust Programs using Linear Ghost Types","author":"Lattuada Andrea","year":"2023","unstructured":"Andrea Lattuada, Travis Hance, Chanhee Cho, Matthias Brun, Isitha Subasinghe, Yi Zhou, Jon Howell, Bryan Parno, and Chris Hawblitzel. 2023. Verus: Verifying Rust Programs using Linear Ghost Types. Proc. ACM Program. Lang. 7, OOPSLA1, Article 85 (apr 2023), 30 pages. https:\/\/doi.org\/10.1145\/3586037 10.1145\/3586037","journal-title":"Proc. ACM Program. Lang."},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538814"},{"key":"e_1_3_1_37_1","unstructured":"Zhengyao Lin Joshua Gancher and Bryan Parno. 2024a. FlowCert GitHub Repository. https:\/\/github.com\/secure-foundations\/riptide-verification\/tree\/oopsla2024-ae."},{"key":"e_1_3_1_38_1","unstructured":"Zhengyao Lin Joshua Gancher and Bryan Parno. 2024b. Translation Validation for Asynchronous Dataflow via Dynamic Fractional Permissions. Carnegie Mellon University. https:\/\/doi.org\/10.5281\/zenodo.12552491 10.5281\/zenodo.12552491"},{"issue":"6","key":"e_1_3_1_39_1","first-page":"39","article-title":"A Survey of Coarse-Grained Reconfigurable Architecture and Design: Taxonomy, Challenges, and Applications","volume":"52","author":"Liu Leibo","year":"2019","unstructured":"Leibo Liu, Jianfeng Zhu, Zhaoshi Li, Yanan Lu, Yangdong Deng, Jie Han, Shouyi Yin, and Shaojun Wei. 2019. A Survey of Coarse-Grained Reconfigurable Architecture and Design: Taxonomy, Challenges, and Applications. ACM Comput. Surv. 52, 6, Article 118 (Oct 2019), 39 pages. https:\/\/doi.org\/10.1145\/3357375 10.1145\/3357375","journal-title":"ACM Comput. Surv."},{"key":"e_1_3_1_40_1","unstructured":"LLVM. 2024a. Clang: a C language family frontend for LLVM. https:\/\/clang.llvm.org."},{"key":"e_1_3_1_41_1","unstructured":"LLVM. 2024b. LLVM Language Reference Manual. https:\/\/llvm.org\/docs\/LangRef.html."},{"key":"e_1_3_1_42_1","doi-asserted-by":"crossref","unstructured":"Nuno P. Lopes Juneyoung Lee Chung-Kil Hur Zhengyang Liu and John Regehr. 2021. Alive2: Bounded Translation Validation for LLVM. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (Virtual Canada) (PLDI 2021). https:\/\/doi.org\/10.1145\/3453483.3454030 10.1145\/3453483.3454030","DOI":"10.1145\/3453483.3454030"},{"key":"e_1_3_1_43_1","article-title":"Provably Correct Peephole Optimizations with Alive","author":"Lopes Nuno P","year":"2015","unstructured":"Nuno P. Lopes, David Menendez, Santosh Nagarakatte, and John Regehr. 2015. Provably Correct Peephole Optimizations with Alive. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (Portland, OR, USA) (PLDI \u201815). https:\/\/doi.org\/10.1145\/2737924.2737965 10.1145\/2737924.2737965","journal-title":"Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (Portland, OR, USA) (PLDI \u201815)"},{"key":"e_1_3_1_44_1","volume-title":"Communicating and Mobile Systems: The n-calculus.","author":"Milner Robin","year":"1999","unstructured":"Robin Milner. 1999. Communicating and Mobile Systems: The n-calculus. Cambridge University Press, United States."},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49122-5_2"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349314"},{"key":"e_1_3_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054170"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/550448"},{"key":"e_1_3_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/559050"},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614283"},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509509"},{"key":"e_1_3_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/956417.956546"},{"key":"e_1_3_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480915"},{"key":"e_1_3_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993533"},{"key":"e_1_3_1_55_1","first-page":"30","article-title":"Pretend synchrony: synchronous verification of asynchronous distributed programs","author":"Gleissenthall Klaus v","year":"2019","unstructured":"Klaus v. Gleissenthall, Rami G\u00f6khan Kici, Alexander Bakst, Deian Stefan, and Ranjit Jhala. 2019. Pretend synchrony: synchronous verification of asynchronous distributed programs. Proc. ACM Program. Lang. 3, POPL, Article 59 (jan 2019), 30 pages. https:\/\/doi.org\/10.1145\/3290372 10.1145\/3290372","journal-title":"Proc. ACM Program. Lang."},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.125"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689729","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689729","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T09:04:21Z","timestamp":1770195861000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":55,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2024,10,8]]}},"alternative-id":["10.1145\/3689729"],"URL":"https:\/\/doi.org\/10.1145\/3689729","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"2024-04-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}