{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:07:38Z","timestamp":1781258858446,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T00:00:00Z","timestamp":1548374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>We present a technique for implementing dataflow networks as compositional hardware circuits. We first define an abstract dataflow model with unbounded buffers that supports data-dependent blocks (mux, demux, and nondeterministic merge); we then show how to faithfully implement such networks with bounded buffers and handshaking.<\/jats:p>\n          <jats:p>Handshaking admits compositionality: our circuits can be connected with or without buffers, and combinational cycles arise only from a completely unbuffered cycle. While bounding buffer sizes can cause the system to deadlock prematurely, the system is guaranteed to produce the same, correct, data before then. Thus, unless the system deadlocks, inserting or removing buffers only affects its performance. We demonstrate how this enables design space to be explored.<\/jats:p>","DOI":"10.1145\/3274280","type":"journal-article","created":{"date-parts":[[2019,1,28]],"date-time":"2019-01-28T14:01:39Z","timestamp":1548684099000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Compositional Dataflow Circuits"],"prefix":"10.1145","volume":"18","author":[{"given":"Stephen A.","family":"Edwards","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7149-1172","authenticated-orcid":false,"given":"Richard","family":"Townsend","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martha","family":"Barker","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martha A.","family":"Kim","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,25]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"ARM. 2010. AMBA 4 AXI4-Stream Protocol Specification Version 1.0.  ARM. 2010. AMBA 4 AXI4-Stream Protocol Specification Version 1.0."},{"key":"e_1_2_1_2_1","volume-title":"Communicating Process Architectures (CPA)","author":"Basten Twan","unstructured":"Twan Basten and Jan Hoogerbrugge . 2001. Efficient execution of process networks . In Communicating Process Architectures (CPA) , Alan Chalmers, Majid Mirmehdi, and Henk Muller (Eds.). IOS Press , Bristol, UK , 1--14. Twan Basten and Jan Hoogerbrugge. 2001. Efficient execution of process networks. In Communicating Process Architectures (CPA), Alan Chalmers, Majid Mirmehdi, and Henk Muller (Eds.). IOS Press, Bristol, UK, 1--14."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Symposium on Image and Signal Processing and Analysis (ISPA\u201913)","author":"Bezati Endri","unstructured":"Endri Bezati , Marco Mattavelli , and J\u00f6rn W. Janneck . 2013. High-level synthesis of dataflow programs for signal processing systems . In Proceedings of the International Symposium on Image and Signal Processing and Analysis (ISPA\u201913) . IEEE, 750--755. Endri Bezati, Marco Mattavelli, and J\u00f6rn W. Janneck. 2013. High-level synthesis of dataflow programs for signal processing systems. In Proceedings of the International Symposium on Image and Signal Processing and Analysis (ISPA\u201913). IEEE, 750--755."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(88)90016-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2015.7340485"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.05.036"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.945302"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2030436"},{"key":"e_1_2_1_10_1","volume-title":"Leiserson","author":"Cormen Thomas H.","year":"2001","unstructured":"Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , and Charles E . Leiserson . 2001 . Introduction to Algorithms (McGraw-Hill , New York, NY). Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. 2001. Introduction to Algorithms (McGraw-Hill, New York, NY)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2010.5558639"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the ACM International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems. ACM","author":"Cortadella Jordi","year":"2006","unstructured":"Jordi Cortadella , Mike Kishinevsky , and Bill Grundmann . 2006 . SELF: Specification and design of synchronous elastic circuits . In Proceedings of the ACM International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems. ACM , New York, NY, 6. Jordi Cortadella, Mike Kishinevsky, and Bill Grundmann. 2006. SELF: Specification and design of synchronous elastic circuits. In Proceedings of the ACM International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems. ACM, New York, NY, 6."},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"Programming Symposium","author":"Dennis Jack B.","unstructured":"Jack B. Dennis . 1974. First version of a data flow procedure language . In Programming Symposium , Lecture Notes in Computer Science , Vol. 19 . Springer , Berlin , 362--376. Jack B. Dennis. 1974. First version of a data flow procedure language. In Programming Symposium, Lecture Notes in Computer Science, Vol. 19. Springer, Berlin, 362--376."},{"key":"e_1_2_1_14_1","volume-title":"Microarchitecture of Network-on-Chip Routers: A Designer\u2019s Perspective","author":"Dimitrakopoulos Giorgos","unstructured":"Giorgos Dimitrakopoulos , Anastasios Psarras , and Ioannis Seitanidis . 2015. Microarchitecture of Network-on-Chip Routers: A Designer\u2019s Perspective . Springer , Berlin . Giorgos Dimitrakopoulos, Anastasios Psarras, and Ioannis Seitanidis. 2015. Microarchitecture of Network-on-Chip Routers: A Designer\u2019s Perspective. Springer, Berlin."},{"key":"e_1_2_1_15_1","volume-title":"Janneck","author":"Eker Johan","year":"2003","unstructured":"Johan Eker and J\u00f6rn W . Janneck . 2003 . CAL Language Report: Specification of the CAL Actor Language. Technical Report UCB\/ERL M03\/48. EECS Department, University of California , Berkeley. Johan Eker and J\u00f6rn W. Janneck. 2003. CAL Language Report: Specification of the CAL Actor Language. Technical Report UCB\/ERL M03\/48. EECS Department, University of California, Berkeley."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Forum on Specification and Design Languages (FDL\u201906)","volume":"6","author":"Falk Joachim","year":"2006","unstructured":"Joachim Falk , Christian Haubelt , and J\u00fcrgen Teich . 2006 . Efficient representation and simulation of model-based designs in SystemC . In Proceedings of the Forum on Specification and Design Languages (FDL\u201906) , Vol. 6 . ECSI, Darmstadt, 129--134. Joachim Falk, Christian Haubelt, and J\u00fcrgen Teich. 2006. Efficient representation and simulation of model-based designs in SystemC. In Proceedings of the Forum on Specification and Design Languages (FDL\u201906), Vol. 6. ECSI, Darmstadt, 129--134."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1992.226558"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765712.1765736"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065796"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1878961.1878985"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference on Formal Methods in Computer-Aided Design (FMCAD\u201908)","author":"Hartel Pieter H.","unstructured":"Pieter H. Hartel , Theo C. Ruys , and Marc C. W. Geilen . 2008. Scheduling optimisations for SPIN to minimise buffer requirements in synchronous data flow . In Proceedings of the Conference on Formal Methods in Computer-Aided Design (FMCAD\u201908) . IEEE, Los Alamitos, CA, 161--170. Pieter H. Hartel, Theo C. Ruys, and Marc C. W. Geilen. 2008. Scheduling optimisations for SPIN to minimise buffer requirements in synchronous data flow. In Proceedings of the Conference on Formal Methods in Computer-Aided Design (FMCAD\u201908). IEEE, Los Alamitos, CA, 161--170."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1155\/2007\/47580"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/373243.360209"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"e_1_2_1_25_1","volume-title":"8008 8-Bit Parallel Central Processor Unit Users Manual","author":"Intel Corporation","unstructured":"Intel Corporation . 1972. 8008 8-Bit Parallel Central Processor Unit Users Manual . Intel Corporation , Santa Clara, CA . Intel Corporation. 1972. 8008 8-Bit Parallel Central Processor Unit Users Manual. Intel Corporation, Santa Clara, CA."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-009-0397-5"},{"key":"e_1_2_1_27_1","volume-title":"Information Processing 74: Proceedings of IFIP Congress 74","author":"Kahn Gilles","year":"1974","unstructured":"Gilles Kahn . 1974 . The semantics of a simple language for parallel programming . In Information Processing 74: Proceedings of IFIP Congress 74 . North-Holland, Stockholm, Sweden, 471--475. Gilles Kahn. 1974. The semantics of a simple language for parallel programming. In Information Processing 74: Proceedings of IFIP Congress 74. North-Holland, Stockholm, Sweden, 471--475."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455229.1455230"},{"key":"e_1_2_1_29_1","volume-title":"Lee and Eleftherios Matsikoudis","author":"Edward","year":"2008","unstructured":"Edward A. Lee and Eleftherios Matsikoudis . 2008 . The semantics of dataflow with firing. In From Semantics to Computer Science : Essays in Memory of Gilles Kahn. Cambridge University Press , Cambridge, UK, Chapter 4, 71--94. Edward A. Lee and Eleftherios Matsikoudis. 2008. The semantics of dataflow with firing. In From Semantics to Computer Science: Essays in Memory of Gilles Kahn. Cambridge University Press, Cambridge, UK, Chapter 4, 71--94."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.381846"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2007.371256"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/581199.581219"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.155"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318.3480"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2016.7753285"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/554220.838073"},{"key":"e_1_2_1_39_1","volume-title":"Introduction to VLSI Systems","author":"Seitz Charles L.","unstructured":"Charles L. Seitz . 1980. System timing . In Introduction to VLSI Systems , Carver Mead and Lynn Conway (Eds.). Addison-Wesley , Reading, MA , Chapter 7, 218--262. Charles L. Seitz. 1980. System timing. In Introduction to VLSI Systems, Carver Mead and Lynn Conway (Eds.). Addison-Wesley, Reading, MA, Chapter 7, 218--262."},{"key":"e_1_2_1_40_1","volume-title":"Sharp and Alan Mycroft","author":"Richard","year":"2000","unstructured":"Richard W. Sharp and Alan Mycroft . 2000 . The FLaSH Compiler: Efficient Circuits from Functional Specifications. Technical Report tr.2000.3. AT8T Laboratories Cambridge . Richard W. Sharp and Alan Mycroft. 2000. The FLaSH Compiler: Efficient Circuits from Functional Specifications. Technical Report tr.2000.3. AT8T Laboratories Cambridge."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.58"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of Design and Architectures for Signal and Image Processing (DASIP\u201909)","author":"Thavot Richard","year":"2009","unstructured":"Richard Thavot , Romuald Mosqueron , Julien Dubois , and Marco Mattavelli . 2009 . Hardware synthesis of complex standard interfaces using CAL dataflow descriptions . In Proceedings of Design and Architectures for Signal and Image Processing (DASIP\u201909) . ECSI, Sophia Antipolis, France, 127--134. Richard Thavot, Romuald Mosqueron, Julien Dubois, and Marco Mattavelli. 2009. Hardware synthesis of complex standard interfaces using CAL dataflow descriptions. In Proceedings of Design and Architectures for Signal and Image Processing (DASIP\u201909). ECSI, Sophia Antipolis, France, 127--134."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033019.3033027"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2014.6893194"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2638550"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of Design, Automation, and Test in Europe (DATE). IEEE, 216--219","author":"Zebelein Christian","year":"2014","unstructured":"Christian Zebelein , Christian Haubelt , Joachim Falk , Tobias Schwarzer , and J\u00fcrgen Teich . 2014 . Model-based actor multiplexing with application to complex communication protocols . In Proceedings of Design, Automation, and Test in Europe (DATE). IEEE, 216--219 . Christian Zebelein, Christian Haubelt, Joachim Falk, Tobias Schwarzer, and J\u00fcrgen Teich. 2014. Model-based actor multiplexing with application to complex communication protocols. In Proceedings of Design, Automation, and Test in Europe (DATE). IEEE, 216--219."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274280","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:06Z","timestamp":1750207446000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,25]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3274280"],"URL":"https:\/\/doi.org\/10.1145\/3274280","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,25]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}