Dataflow Models


Data Flow models [1] are a mathematical abstraction of networks of software of 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 called actors

Timed Dataflow Models

TBD

Tools

Many analysis algorithms for Timed Dataflow graph are implemented in SDF3 [2].

The Computation Modeling Workbench supports modeling and analysis if Timed Dataflow models.

Selected Related Publications

  • M. C. W. Geilen and S. Stuijk, “Worst-case performance analysis of synchronous dataflow scenarios,” in International conference on hardware-software codesign and system synthesis, codes+isss 10, proc., scottsdale, az, usa, 24-29 october, 2010, 2010, pp. 125-134.
    [Bibtex]
    @InProceedings{GS10,
    author = {M.C.W. Geilen and S. Stuijk},
    title = {Worst-case Performance Analysis of Synchronous Dataflow Scenarios},
    booktitle = {International Conference on Hardware-Software Codesign and System Synthesis, CODES+ISSS 10, Proc., Scottsdale, Az, USA, 24-29 October, 2010},
    year = {2010},
    pages = {125-134},
    owner = {mgeilen},
    timestamp = {2011.04.08},
    }

  • [DOI] 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{Stuijk2006a,
    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}
    }

  • [DOI] S. Stuijk, M. Geilen, B. Theelen, and T. Basten, “Scenario-aware dataflow: modeling, analysis and implementation of dynamic applications,” in Embedded computer systems (samos), 2011 international conference on, 2011, pp. 404-411.
    [Bibtex]
    @InProceedings{Stuijk2011,
    author = {Stuijk, S. and Geilen, M. and Theelen, B. and Basten, T.},
    title = {Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications},
    booktitle = {Embedded Computer Systems (SAMOS), 2011 International Conference on},
    year = {2011},
    pages = {404-411},
    month = {July},
    abstract = {Embedded multimedia and wireless applications require a model-based design approach in order to satisfy stringent quality and cost constraints. The Model-of-Computation (MoC) should appropriately capture system dynamics, support analysis and synthesis, and allow low-overhead model-driven implementations. This combination poses a significant challenge. The Scenario-Aware DataFlow (SADF) MoC has been introduced to address this challenge. This paper surveys SADF, and compares dataflow MoCs in terms of their ability to capture system dynamics, their support for analysis and synthesis, and their implementation efficiency.},
    comment = {Comparison (H)SDF and SADF, overview. (H)SDF is static, bounds on storage &WCET and no runtime overhead but no dynamics, overestimation of requirements. KPN: overhead during runtime, no guarantees SADF: analyzable, efficient, captures dynamics through scenarios. Worst-case throughput analysis: 3 options, one of which constructs complete state space Good (graphic) comparison of DF related MoCs on expressiveness/succinctness, impementation efficiency and analyzability. Con: good explanation but no examples or proofs},
    doi = {10.1109/SAMOS.2011.6045491},
    keywords = {computational complexity;data flow analysis;embedded systems;multimedia systems;radio networks;software engineering;SADF MoC;cost constraints;dynamic application analysis;dynamic application modeling;embedded multimedia;low-overhead model-driven implementation;model of computation;model-based design approach;quality satisfaction;scenario-aware dataflow;system dynamics;wireless application;Computational modeling;Decoding;Markov processes;Throughput;Timing},
    owner = {reinier},
    timestamp = {2014.08.05},
    }

  • [DOI] A. H. Ghamarian, M. C. W. Geilen, T. Basten, and S. Stuijk, “Parametric throughput analysis of synchronous data flow graphs,” in 2008 design, automation and test in europe, 2008, pp. 116-121.
    [Bibtex]
    @INPROCEEDINGS{Ghamarian2008Parametric,
    author={A. H. Ghamarian and M. C. W. Geilen and T. Basten and S. Stuijk},
    booktitle={2008 Design, Automation and Test in Europe},
    title={Parametric Throughput Analysis of Synchronous Data Flow Graphs},
    year={2008},
    volume={},
    number={},
    pages={116-121},
    keywords={data flow graphs;divide and conquer methods;SDFG models;actor execution times;divide and conquer algorithm;parametric throughput analysis;synchronous data flow graphs;Algorithm design and analysis;Data analysis;Digital signal processing;Flow graphs;Performance analysis;Runtime;Space exploration;State-space methods;Throughput;Timing},
    doi={10.1109/DATE.2008.4484672},
    ISSN={1530-1591},
    month={March},}

  • [DOI] 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},
    }

  • [DOI] 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},
    abstract = {Model-based design methods have become common practice for the design, analysis, and synthesis of embedded and cyber-physical systems. Different models of computation are used (for example state-based models, dataflow models, differential equations, hybrid-models). In real-time and cyber-physical systems it is common to incorporate in such models some representation of time, physical, logical or otherwise. We are used to time progressing in forward direction. This assumption is built into the very definition of many of our favorite models of computation. Execution times or delays are usually non-negative. Time stamps usually increase monotonically. Tasks can depend on past activations of other tasks, but not on future activations. Tasks are temporally causal. In this paper we explore the possibilities and the potential benefits of liberating our models from these assumptions, allowing time go backward in our models. We will use the dataflow model of computation for our exploration and show that there are potential benefits to negative execution times, negative delays on channels, and non-monotone events in event traces.},
    doi = {10.1007/978-3-319-95246-8\_16},
    url = {https://doi.org/10.1007/978-3-319-95246-8\_16},
    }

References

[1] [doi] 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] [doi] 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{Stuijk2006a,
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}
}