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.
References
- (1987): Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing. In: Computers, IEEE Transactions on, vol. C-36, no. 1, pp. 24-35, 1987, ISSN: 0018-9340.
- (2006): SDF$^3$: SDF For Free. In: Application of Concurrency to System Design, 6th International Conference, ACSD 2006, Proceedings, pp. 276โ278, IEEE Computer Society Press, Los Alamitos, CA, USA, Turku, Finland, 2006.
Selected Related Publications
2020
Scenarios in Dataflow Modeling and Analysis Book Chapter
In: System-Scenario-based Design Principles and Applications, pp. 145โ180, Springer International Publishing, Cham, 2020, ISBN: 978-3-030-20343-6.
2019
Monotonic optimization of dataflow buffer sizes Journal Article
In: Journal of signal processing systems, vol. 91, pp. 21โ32, 2019.
2018
If We Could Go Back in Time... On the Use of `Unnatural' Time and Ordering in Dataflow Models Book Section
In: Lohstroh, Marten; Derler, Patricia; Sirjani, Marjan (Ed.): Principles of Modeling: Essays Dedicated to Edward A. Lee on the Occasion of His 60th Birthday, pp. 267โ286, Springer International Publishing, Cham, 2018, ISBN: 978-3-319-95246-8.
Compositionality in Scenario-aware Dataflow: A Rendezvous Perspective Proceedings Article
In: Proc. of LCTES'18, 2018.
2017
Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow Graphs Journal Article
In: Journal of Signal Processing Systems, vol. 87, no. 1, pp. 157โ175, 2017, ISSN: 1939-8115.
2014
Performance analysis of weakly-consistent scenario-aware dataflow graphs Proceedings Article
In: 2014 48th Asilomar Conference on Signals, Systems and Computers, pp. 393-397, 2014.
2012
Modeling static-order schedules in synchronous dataflow graphs Proceedings Article
In: Design, Automation Test in Europe Conference Exhibition (DATE), 2012, pp. 775-780, 2012, ISSN: 1530-1591.
Playing games with scenario- and resource-aware SDF graphs through policy iteration Proceedings Article
In: 2012 Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 194-199, 2012.
2011
Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications Proceedings Article
In: 2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation, pp. 404-411, 2011.
Analyzing synchronous dataflow scenarios for dynamic software-defined radio applications Proceedings Article
In: 2011 International Symposium on System on Chip (SoC), pp. 14-21, 2011.
2010
Worst-Case Performance Analysis of Synchronous Dataflow Scenarios Proceedings Article
In: Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, pp. 125โ134, Association for Computing Machinery, Scottsdale, Arizona, USA, 2010, ISBN: 9781605589053.
2008
Parametric Throughput Analysis of Synchronous Data Flow Graphs Proceedings Article
In: 2008 Design, Automation and Test in Europe, pp. 116-121, 2008, ISSN: 1530-1591.
Throughput-Buffering Trade-Off Exploration for Cyclo-Static and Synchronous Dataflow Graphs Journal Article
In: IEEE Trans. Comput., vol. 57, no. 10, pp. 1331โ1345, 2008, ISSN: 0018-9340.
2007
Predictable mapping of streaming applications on multiprocessors PhD Thesis
Electrical Engineering, 2007, ISBN: 978-90-386-1624-7, (Proefschrift.).
Multiprocessor Resource Allocation for Throughput-constrained Synchronous Dataflow Graphs Proceedings Article
In: Proceedings of the 44th Annual Design Automation Conference, pp. 777โ782, ACM, San Diego, California, 2007, ISBN: 978-1-59593-627-1.
2006
SDF$^3$: SDF For Free Proceedings Article
In: Application of Concurrency to System Design, 6th International Conference, ACSD 2006, Proceedings, pp. 276โ278, IEEE Computer Society Press, Los Alamitos, CA, USA, Turku, Finland, 2006.
Throughput Analysis of Synchronous Data Flow Graphs Proceedings Article
In: Sixth International Conference on Application of Concurrency to System Design (ACSD'06), pp. 25-36, 2006.
Exploring Trade-Offs in Buffer Requirements and Throughput Constraints for Synchronous Dataflow Graphs Proceedings Article
In: Proceedings of the 43rd Annual Design Automation Conference, pp. 899โ904, Association for Computing Machinery, San Francisco, CA, USA, 2006, ISBN: 1595933816.
2005
Minimising Buffer Requirements of Synchronous Dataflow Graphs with Model Checking Proceedings Article
In: Proceedings of the 42nd Annual Design Automation Conference, pp. 819โ824, Association for Computing Machinery, Anaheim, California, USA, 2005, ISBN: 1595930582.