Data Flow models [1] are a mathematical abstraction of networks of software or of hardware tasks that repetitively and concurrently compute outputs in the form of data tokens as a function of consumed input tokens.
Those tasks are often called actors. Actors are related by channels. A channel carries data tokens produced by one actor to an input of another actor. This creates dependencies between the executions (called firings) of these actors.
Timed Data Flow Models
Timed Data Flow is a branch of data flow analysis that emphasizes the timing, performance, dependencies and concurrency in data flow graphs, rather than the functional computations performed by the actors. It provides techniques to compute, among other things, throughput, latency, and minimal buffer sizes.
Tools
Many analysis algorithms for Timed Data Flow graphs are implemented in SDF3 [2]. The Computation Modeling Workbench supports modeling and analysis of Timed Data Flow models. The analysis implemented in the work bench uses the cmlib open source library for analysis of different computational models. More details about timed data flow models can be found in the Lecture notes on Dataflow modeling and Max-Plus algebra used in the course Computational Modeling (5XIE0).
And here are some related exam problems.
Selected Related Publications
-
![[DOI]](https://computationalmodeling.info/wp/wp-content/plugins/papercite/img/external.png)
S. Stuijk, M. Geilen, and T. Basten, “Throughput-buffering trade-off exploration for cyclo-static and synchronous dataflow graphs,” Ieee trans. comput., vol. 57, iss. 10, p. 1331–1345, 2008.
[Bibtex]@Article{SGB08, author = {Sander Stuijk and Marc Geilen and Twan Basten}, title = {Throughput-Buffering Trade-Off Exploration for Cyclo-Static and Synchronous Dataflow Graphs}, journal = {IEEE Trans. Comput.}, year = {2008}, volume = {57}, number = {10}, pages = {1331--1345}, issn = {0018-9340}, address = {Washington, DC, USA}, doi = {http://dx.doi.org/10.1109/TC.2008.58}, owner = {mgeilen}, publisher = {IEEE Computer Society}, timestamp = {2008.12.19}, } - M. Geilen and S. Stuijk, “Worst-case performance analysis of synchronous dataflow scenarios,” in Proceedings of the eighth ieee/acm/ifip international conference on hardware/software codesign and system synthesis, New York, NY, USA, 2010, p. 125–134.
[Bibtex]@InProceedings{GS10, author = {Geilen, Marc and Stuijk, Sander}, title = {Worst-Case Performance Analysis of Synchronous Dataflow Scenarios}, year = {2010}, isbn = {9781605589053}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/1878961.1878985}, doi = {10.1145/1878961.1878985}, booktitle = {Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis}, pages = {125–134}, numpages = {10}, location = {Scottsdale, Arizona, USA}, series = {CODES/ISSS '10} } - M. Geilen, “If we could go back in time… on the use of `unnatural’ time and ordering in dataflow models,” in Principles of modeling: essays dedicated to edward a. lee on the occasion of his 60th birthday, M. Lohstroh, P. Derler, and M. Sirjani, Eds., Cham: Springer international publishing, 2018, p. 267–286.
[Bibtex]@InCollection{Gei18, author = {Geilen, Marc}, title = {If We Could Go Back in Time... On the Use of `Unnatural' Time and Ordering in Dataflow Models}, booktitle = {Principles of Modeling: Essays Dedicated to Edward A. Lee on the Occasion of His 60th Birthday}, publisher = {Springer International Publishing}, year = {2018}, editor = {Lohstroh, Marten and Derler, Patricia and Sirjani, Marjan}, pages = {267--286}, address = {Cham}, isbn = {978-3-319-95246-8}, doi = {10.1007/978-3-319-95246-8\_16}, url = {https://doi.org/10.1007/978-3-319-95246-8\_16}, }
References
[1] E. Lee and D. G. Messerschmitt, “Static scheduling of synchronous data flow programs for digital signal processing,” Computers, ieee transactions on, vol. C-36, iss. 1, pp. 24-35, 1987.
[Bibtex]
E. Lee and D. G. Messerschmitt, “Static scheduling of synchronous data flow programs for digital signal processing,” Computers, ieee transactions on, vol. C-36, iss. 1, pp. 24-35, 1987. [Bibtex]
@Article{Lee1987,
Title = {Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing},
Author = {Lee, E. and Messerschmitt, D.G.},
Journal = {Computers, IEEE Transactions on},
Year = {1987},
Month = {Jan},
Number = {1},
Pages = {24-35},
Volume = {C-36},
Abstract = {Large grain data flow (LGDF) programming is natural and convenient for describing digital signal processing (DSP) systems, but its runtime overhead is costly in real time or cost-sensitive applications. In some situations, designers are not willing to squander computing resources for the sake of programmer convenience. This is particularly true when the target machine is a programmable DSP chip. However, the runtime overhead inherent in most LGDF implementations is not required for most signal processing systems because such systems are mostly synchronous (in the DSP sense). Synchronous data flow (SDF) differs from traditional data flow in that the amount of data produced and consumed by a data flow node is specified a priori for each input and output. This is equivalent to specifying the relative sample rates in signal processing system. This means that the scheduling of SDF nodes need not be done at runtime, but can be done at compile time (statically), so the runtime overhead evaporates. The sample rates can all be different, which is not true of most current data-driven digital signal processing programming methodologies. Synchronous data flow is closely related to computation graphs, a special case of Petri nets. This self-contained paper develops the theory necessary to statically schedule SDF programs on single or multiple processors. A class of static (compile time) scheduling algorithms is proven valid, and specific algorithms are given for scheduling SDF systems onto single or multiple processors.},
Doi = {10.1109/TC.1987.5009446},
ISSN = {0018-9340},
Keywords = {Data flow computing;Digital signal processing;Digital signal processing chips;Flow graphs;Processor scheduling;Programming profession;Real time systems;Runtime;Scheduling algorithm;Signal processing;Block diagram;Petri nets;computation graphs;data flow digital signal processing;hard real-time systems;multiprocessing;static scheduling;synchronous data flow},
Owner = {reinier},
Timestamp = {2014.10.23}
}[2] S. Stuijk, M. C. W. Geilen, and T. Basten, “SDF$^3$: SDF For Free,” in Application of concurrency to system design, 6th international conference, acsd 2006, proceedings, 2006, p. 276–278.
[Bibtex]
S. Stuijk, M. C. W. Geilen, and T. Basten, “SDF$^3$: SDF For Free,” in Application of concurrency to system design, 6th international conference, acsd 2006, proceedings, 2006, p. 276–278. [Bibtex]
@InProceedings{SGB06,
Title = {{SDF}$^3$: {SDF For Free}},
Author = {S. Stuijk and M.C.W. Geilen and T. Basten},
Booktitle = {Application of Concurrency to System Design, 6th International Conference, ACSD 2006, Proceedings},
Year = {2006},
Month = {June},
Pages = {276--278},
Publisher = {IEEE Computer Society Press, Los Alamitos, CA, USA},
Doi = {10.1109/ACSD.2006.23},
Location = {Turku, Finland},
Owner = {reinier},
Timestamp = {2014.10.23},
Url = {http://www.es.ele.tue.nl/sdf3}
}