{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:22:11Z","timestamp":1751660531451,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2107289"],"award-info":[{"award-number":["CCF-2107289"]}],"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":[[2022,1,16]]},"abstract":"<jats:p>Many algorithms for analyzing parallel programs, for example to detect deadlocks or data races or to calculate the execution cost, are based on a model variously known as a cost graph, computation graph or dependency graph, which captures the parallel structure of threads in a program. In modern parallel programs, computation graphs are highly dynamic and depend greatly on the program inputs and execution details. As such, most analyses that use these graphs are either dynamic analyses or are specialized static analyses that gather a subset of dependency information for a specific purpose.<\/jats:p>\n          <jats:p>This paper introduces graph types, which compactly represent all of the graphs that could arise from program execution. Graph types are inferred from a parallel program using a graph type system and inference algorithm, which we present drawing on ideas from Hindley-Milner type inference, affine logic and region type systems. We have implemented the inference algorithm over a subset of OCaml, extended with parallelism primitives, and we demonstrate how graph types can be used to accelerate the development of new graph-based static analyses by presenting proof-of-concept analyses for deadlock detection and cost analysis.<\/jats:p>","DOI":"10.1145\/3498708","type":"journal-article","created":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T17:03:12Z","timestamp":1642006992000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Static prediction of parallel computation graphs"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3210-9727","authenticated-orcid":false,"given":"Stefan K.","family":"Muller","sequence":"first","affiliation":[{"name":"Illinois Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Arvind and K. P. Gostelow. 1978. The Id Report: An Asychronous Language and Computing Machine. Department of Information and Computer Science University of California Irvine.  Arvind and K. P. Gostelow. 1978. The Id Report: An Asychronous Language and Computing Machine. Department of Information and Computer Science University of California Irvine."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01088832"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147403.1147416"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54108-7_15"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/224164.224210"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/232627.232650"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/582419.582440"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48046-3_17"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CMPSAC.1993.404187"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3229060"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3143359"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945468"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.WCET.2007.1194"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_2_2_15_1","volume-title":"North","author":"Gansner Emden R.","year":"2000","unstructured":"Emden R. Gansner and Stephen C . North . 2000 . An Open Graph Visualization System and Its Applications to Software Engineering. Softw. Pract. Exper ., 30, 11 (2000), Sept., 1203?1233. issn:0038-0644 https:\/\/doi.org\/10.1002\/1097-024X(200009)30:11&lt;1203::AID-SPE338&gt;3.0.CO;2-N Emden R. Gansner and Stephen C. North. 2000. An Open Graph Visualization System and Its Applications to Software Engineering. Softw. Pract. Exper., 30, 11 (2000), Sept., 1203?1233. issn:0038-0644 https:\/\/doi.org\/10.1002\/1097-024X(200009)30:11&lt;1203::AID-SPE338&gt;3.0.CO;2-N"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/319838.319848"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"volume-title":"Advanced Topics in Types and Programming Languages, Benjamin C","author":"Henglein Fritz","key":"e_1_2_2_18_1","unstructured":"Fritz Henglein , Henning Makholm , and Henning Niss . 2005. Effect Types and Region-Based Memory Management . In Advanced Topics in Types and Programming Languages, Benjamin C . Pierce (Ed.). MIT Press , Cambridge, Massachusetts . 87\u2013135. Fritz Henglein, Henning Makholm, and Henning Niss. 2005. Effect Types and Region-Based Memory Management. In Advanced Topics in Types and Programming Languages, Benjamin C. Pierce (Ed.). MIT Press, Cambridge, Massachusetts. 87\u2013135."},{"key":"e_1_2_2_19_1","first-page":"29","article-title":"The Principal Type-Scheme of an Object in Combinatory","volume":"146","author":"Hindley J. Roger","year":"1969","unstructured":"J. Roger Hindley . 1969 . The Principal Type-Scheme of an Object in Combinatory Logic. Trans. Amer. Math. Soc. , 146 (1969), 29 \u2013 60 . issn:00029947 http:\/\/www.jstor.org\/stable\/1995158 J. Roger Hindley. 1969. The Principal Type-Scheme of an Object in Combinatory Logic. Trans. Amer. Math. Soc., 146 (1969), 29\u201360. issn:00029947 http:\/\/www.jstor.org\/stable\/1995158","journal-title":"Logic. Trans. Amer. Math. Soc."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46669-8_6"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604148"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-18317-5_14"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/73141.74837"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114108"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/APSEC.1995.496974"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90102-5"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.664229"},{"volume-title":"Types and Effects toward the Integration of Functional and Imperative Programming","author":"Lucassen John M.","key":"e_1_2_2_29_1","unstructured":"John M. Lucassen . 1987. Types and Effects toward the Integration of Functional and Imperative Programming . Massachusetts Institute of Technology . Cambridge, Massachusetts. Available as Technical Report MIT-LCS-TR-408. John M. Lucassen. 1987. Types and Effects toward the Integration of Functional and Imperative Programming. Massachusetts Institute of Technology. Cambridge, Massachusetts. Available as Technical Report MIT-LCS-TR-408."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90014-4"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236790"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386013"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12925-1_41"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450136.2450138"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345212"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Mads Rosendahl. 1989. Automatic complexity analysis. In FPCA \u201989: Functional Programming Languages and Computer Architecture. ACM 144\u2013156.  Mads Rosendahl. 1989. Automatic complexity analysis. In FPCA \u201989: Functional Programming Languages and Computer Architecture. ACM 144\u2013156.","DOI":"10.1145\/99370.99381"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52592-0_74"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/291891.291894"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2613"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295732"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935801"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295724"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1984.5010248"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374536"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498708","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498708","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498708","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:28Z","timestamp":1750188628000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498708"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":44,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2022,1,16]]}},"alternative-id":["10.1145\/3498708"],"URL":"https:\/\/doi.org\/10.1145\/3498708","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"assertion":[{"value":"2022-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}