Academic Commons

Articles

Compositional Dataflow Circuits

Edwards, Stephen A.; Townsend, Richard Morse; Barker, Martha Massee; Kim, Martha Allen

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. 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.

Files

  • thumnail for edwards2019compositional.pdf edwards2019compositional.pdf application/pdf 1.1 MB Download File

Also Published In

Title
ACM Transactions on Embedded Computing System
DOI
https://doi.org/10.1145/3274280

More About This Work

Academic Units
Computer Science
Published Here
April 2, 2019
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.