{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:29Z","timestamp":1750220549134,"version":"3.41.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T00:00:00Z","timestamp":1629331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR00112020013, HR001120C0191"],"award-info":[{"award-number":["HR00112020013, HR001120C0191"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1763514"],"award-info":[{"award-number":["CCF 1763514"]}],"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":[[2021,8,22]]},"abstract":"<jats:p>We present a dataflow model for modelling parallel Unix shell pipelines. To accurately capture the semantics of complex Unix pipelines, the dataflow model is order-aware, i.e., the order in which a node in the dataflow graph consumes inputs from different edges plays a central role in the semantics of the computation and therefore in the resulting parallelization. We use this model to capture the semantics of transformations that exploit data parallelism available in Unix shell computations and prove their correctness. We additionally formalize the translations from the Unix shell to the dataflow model and from the dataflow model back to a parallel shell script. We implement our model and transformations as the compiler and optimization passes of a system parallelizing shell pipelines, and use it to evaluate the speedup achieved on 47 pipelines.<\/jats:p>","DOI":"10.1145\/3473570","type":"journal-article","created":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T10:44:29Z","timestamp":1629369869000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["An order-aware dataflow model for parallel Unix pipelines"],"prefix":"10.1145","volume":"5","author":[{"given":"Shivam","family":"Handa","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Kallas","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikos","family":"Vasilakis","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin C.","family":"Rinard","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,19]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528412"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_2_2_3_1","unstructured":"K. Arvind E. David Culler Robert Iannucci Vinod Kathail Keshav Pingali and Robert Thomas. 1984. The tagged token dataflow architecture. Technical report MIT Laboratory for Computer Science.  K. Arvind E. David Culler Robert Iannucci Vinod Kathail Keshav Pingali and Robert Thomas. 1984. The tagged token dataflow architecture. Technical report MIT Laboratory for Computer Science."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.48862"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-739X(97)00037-X"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3532.315102"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/5948.315654"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(92)90005-V"},{"key":"e_1_2_2_9_1","unstructured":"Pawan Bhandari. 2020. Solutions to unixgame.io. https:\/\/git.io\/Jf2dn Accessed: 2020-04-14.  Pawan Bhandari. 2020. Solutions to unixgame.io. https:\/\/git.io\/Jf2dn Accessed: 2020-04-14."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461328.2461348"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-06859-7_145"},{"key":"e_1_2_2_13_1","unstructured":"Tom Duff. 1990. Rc\u2014a Shell for Plan 9 and UNIX. 283\u2013296. isbn:0030475295  Tom Duff. 1990. Rc\u2014a Shell for Plan 9 and UNIX. 283\u2013296. isbn:0030475295"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034675.2034690"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062355"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314612"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168918.1168877"},{"key":"e_1_2_2_18_1","unstructured":"Michael Greenberg. 2018. The POSIX shell is an interactive DSL for concurrency.  Michael Greenberg. 2018. The POSIX shell is an interactive DSL for concurrency."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371111"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458336.3465296"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458336.3465294"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.4776838"},{"key":"e_1_2_2_23_1","unstructured":"Michael Hart. 1971. Project Gutenberg. https:\/\/www.gutenberg.org\/  Michael Hart. 1971. Project Gutenberg. https:\/\/www.gutenberg.org\/"},{"key":"e_1_2_2_24_1","unstructured":"Dan Jurafsky. 2017. Unix for Poets. https:\/\/web.stanford.edu\/class\/cs124\/lec\/124-2018-UnixForPoets.pdf  Dan Jurafsky. 2017. Unix for Poets. https:\/\/web.stanford.edu\/class\/cs124\/lec\/124-2018-UnixForPoets.pdf"},{"key":"e_1_2_2_25_1","first-page":"471","article-title":"The Semantics of a Simple Language for Parallel Programming","volume":"74","author":"Kahn Gilles","year":"1974","unstructured":"Gilles Kahn . 1974 . The Semantics of a Simple Language for Parallel Programming . Information Processing , 74 (1974), 471 \u2013 475 . Gilles Kahn. 1974. The Semantics of a Simple Language for Parallel Programming. Information Processing, 74 (1974), 471\u2013475.","journal-title":"Information Processing"},{"key":"e_1_2_2_26_1","first-page":"993","article-title":"Coroutines and Networks of Parallel Processes","volume":"77","author":"Kahn Gilles","year":"1977","unstructured":"Gilles Kahn and David B. MacQueen . 1977 . Coroutines and Networks of Parallel Processes . Information Processing , 77 (1977), 993 \u2013 998 . Gilles Kahn and David B. MacQueen. 1977. Coroutines and Networks of Parallel Processes. Information Processing, 77 (1977), 993\u2013998.","journal-title":"Information Processing"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428221"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114108"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250755"},{"key":"e_1_2_2_30_1","unstructured":"Nokia Bell Labs. 2019. The Unix Game\u2014Solve puzzles using Unix pipes. https:\/\/unixgame.io\/unix50 Accessed: 2020-03-05.  Nokia Bell Labs. 2019. The Unix Game\u2014Solve puzzles using Unix pipes. https:\/\/unixgame.io\/unix50 Accessed: 2020-03-05."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1986.1164809"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009446"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066193"},{"key":"e_1_2_2_35_1","volume-title":"Semantic Foundations for Deterministic Dataflow and Stream Processing. In European Symposium on Programming. 394\u2013427","author":"Mamouras Konstantinos","year":"2020","unstructured":"Konstantinos Mamouras . 2020 . Semantic Foundations for Deterministic Dataflow and Stream Processing. In European Symposium on Programming. 394\u2013427 . Konstantinos Mamouras. 2020. Semantic Foundations for Deterministic Dataflow and Stream Processing. In European Symposium on Programming. 394\u2013427."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062369"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314580"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-0551(01)00016-9"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380181007"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1978.tb02135.x"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.53354"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.16"},{"key":"e_1_2_2_44_1","volume-title":"Proceedings of the summer 1990 UKUUG Conference. 1\u20139. http:\/\/css.csail.mit.edu\/6.824\/2014\/papers\/plan9.pdf","author":"Pike Rob","year":"1990","unstructured":"Rob Pike , Dave Presotto , Ken Thompson , and Howard Trickey . 1990 . Plan 9 from Bell Labs . In Proceedings of the summer 1990 UKUUG Conference. 1\u20139. http:\/\/css.csail.mit.edu\/6.824\/2014\/papers\/plan9.pdf Rob Pike, Dave Presotto, Ken Thompson, and Howard Trickey. 1990. Plan 9 from Bell Labs. In Proceedings of the summer 1990 UKUUG Conference. 1\u20139. http:\/\/css.csail.mit.edu\/6.824\/2014\/papers\/plan9.pdf"},{"key":"e_1_2_2_45_1","volume-title":"POSH: A Data-Aware Shell. In 2020 USENIX Annual Technical Conference (USENIX ATC 20)","author":"Raghavan Deepti","year":"2020","unstructured":"Deepti Raghavan , Sadjad Fouladi , Philip Levis , and Matei Zaharia . 2020 . POSH: A Data-Aware Shell. In 2020 USENIX Annual Technical Conference (USENIX ATC 20) . USENIX Association, 617\u2013631. isbn:978-1-939133-14-4 https:\/\/www.usenix.org\/conference\/atc20\/presentation\/raghavan Deepti Raghavan, Sadjad Fouladi, Philip Levis, and Matei Zaharia. 2020. POSH: A Data-Aware Shell. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). USENIX Association, 617\u2013631. isbn:978-1-939133-14-4 https:\/\/www.usenix.org\/conference\/atc20\/presentation\/raghavan"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/125083.123062"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/301104.301111"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2013.221"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086365.1086370"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908102"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2017.2695447"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.16303"},{"key":"e_1_2_2_53_1","unstructured":"Ole Tange. 2020. Differences Between GNU parallel and Alternatives. https:\/\/www.gnu.org\/software\/parallel\/parallel_alternatives.html  Ole Tange. 2020. Differences Between GNU parallel and Alternatives. https:\/\/www.gnu.org\/software\/parallel\/parallel_alternatives.html"},{"key":"e_1_2_2_54_1","volume-title":"OS X, and UNIX Systems","author":"Taylor Dave","unstructured":"Dave Taylor and Brandon Perry . 2016. Wicked Cool Shell Scripts: 101 Scripts for Linux , OS X, and UNIX Systems ( 2 nd ed.). No Starch Press, USA. isbn:1593276028 Dave Taylor and Brandon Perry. 2016. Wicked Cool Shell Scripts: 101 Scripts for Linux, OS X, and UNIX Systems (2nd ed.). No Starch Press, USA. isbn:1593276028","edition":"2"},{"volume-title":"Proceedings of the 11th International Conference on Compiler Construction (CC \u201902)","author":"Thies William","key":"e_1_2_2_55_1","unstructured":"William Thies , Michal Karczmarek , and Saman P. Amarasinghe . 2002. StreamIt: A Language for Streaming Applications . In Proceedings of the 11th International Conference on Compiler Construction (CC \u201902) . Springer-Verlag, Berlin, Heidelberg. 179\u2013196. isbn:3540433694 William Thies, Michal Karczmarek, and Saman P. Amarasinghe. 2002. StreamIt: A Language for Streaming Applications. In Proceedings of the 11th International Conference on Compiler Construction (CC \u201902). Springer-Verlag, Berlin, Heidelberg. 179\u2013196. isbn:3540433694"},{"key":"e_1_2_2_56_1","unstructured":"Eleftheria Tsaliki and Diomidis Spinellis. 2021. The real statistics of buses in Athens. https:\/\/insidestory.gr\/article\/noymera-leoforeia-athinas?token=0MFVISB8N6 Published by the Inside Story news organization.  Eleftheria Tsaliki and Diomidis Spinellis. 2021. The real statistics of buses in Athens. https:\/\/insidestory.gr\/article\/noymera-leoforeia-athinas?token=0MFVISB8N6 Published by the Inside Story news organization."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456228"},{"volume-title":"Proceedings of the 15th USENIX Conference on Hot Topics in Operating Systems (HOTOS\u201915)","author":"Vasilakis Nikos","key":"e_1_2_2_58_1","unstructured":"Nikos Vasilakis , Ben Karel , and Jonathan M. Smith . 2015. From Lone Dwarfs to Giant Superclusters: Rethinking Operating System Abstractions for the Cloud . In Proceedings of the 15th USENIX Conference on Hot Topics in Operating Systems (HOTOS\u201915) . USENIX Association, Berkeley, CA, USA. 15\u201315. http:\/\/dl.acm.org\/citation.cfm?id=2831090.2831105 Nikos Vasilakis, Ben Karel, and Jonathan M. Smith. 2015. From Lone Dwarfs to Giant Superclusters: Rethinking Operating System Abstractions for the Cloud. In Proceedings of the 15th USENIX Conference on Hot Topics in Operating Systems (HOTOS\u201915). USENIX Association, Berkeley, CA, USA. 15\u201315. http:\/\/dl.acm.org\/citation.cfm?id=2831090.2831105"},{"key":"e_1_2_2_59_1","volume-title":"Concurrent Programming in ERLANG","author":"Virding Robert","unstructured":"Robert Virding , Claes Wikstr\u00f6m , Mike Williams , and Joe Armstrong . 1996. Concurrent Programming in ERLANG ( 2 nd Ed.). Prentice Hall International (UK) Ltd ., GBR. isbn:013508301X Robert Virding, Claes Wikstr\u00f6m, Mike Williams, and Joe Armstrong. 1996. Concurrent Programming in ERLANG (2nd Ed.). Prentice Hall International (UK) Ltd., GBR. isbn:013508301X","edition":"2"},{"key":"e_1_2_2_60_1","volume-title":"Proceedings of the 1st International Symposium on Cluster Computing and the Grid (CCGRID \u201901)","author":"Sun W. Gentzsch","year":"2001","unstructured":"W. Gentzsch ( Sun Microsystems). 2001 . Sun Grid Engine: Towards Creating a Compute Power Grid . In Proceedings of the 1st International Symposium on Cluster Computing and the Grid (CCGRID \u201901) . IEEE Computer Society, USA. 35. isbn:0769510108 W. Gentzsch (Sun Microsystems). 2001. Sun Grid Engine: Towards Creating a Compute Power Grid. In Proceedings of the 1st International Symposium on Cluster Computing and the Grid (CCGRID \u201901). IEEE Computer Society, USA. 35. isbn:0769510108"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645164.1645175"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/MARK.1979.8817164"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/10968987_3"},{"key":"e_1_2_2_64_1","volume-title":"Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201912)","author":"Zaharia Matei","year":"2012","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Tathagata Das , Ankur Dave , Justin Ma , Murphy McCauley , Michael J. Franklin , Scott Shenker , and Ion Stoica . 2012 . Resilient Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing . In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201912) . USENIX Association, Berkeley, CA, USA. 2\u20132. http:\/\/dl.acm.org\/citation.cfm?id=2228298.2228301 Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing. In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201912). USENIX Association, Berkeley, CA, USA. 2\u20132. http:\/\/dl.acm.org\/citation.cfm?id=2228298.2228301"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503222"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473570","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473570","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473570","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:15Z","timestamp":1750195695000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473570"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,19]]},"references-count":65,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2021,8,22]]}},"alternative-id":["10.1145\/3473570"],"URL":"https:\/\/doi.org\/10.1145\/3473570","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2021,8,19]]},"assertion":[{"value":"2021-08-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}