Scenario-Aware Data Flow


Scenario-Aware Dataflow [1] is a flavor of Dynamic Dataflow that arises from the application of Scenario-Based Design to capture dynamic variation in Timed Dataflow Models.

Weakly consistent SADF [2]

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. 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] M. Geilen, J. Falk, C. Haubelt, T. Basten, B. Theelen, and S. Stuijk, “Performance analysis of weakly-consistent scenario-aware dataflow graphs,” Journal of signal processing systems, vol. 87, iss. 1, p. 157–175, 2017.
    [Bibtex]
    @Article{GFHea16,
    author = {Geilen, Marc and Falk, Joachim and Haubelt, Christian and Basten, Twan and Theelen, Bart and Stuijk, Sander},
    title = {Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow Graphs},
    journal = {Journal of Signal Processing Systems},
    year = {2017},
    volume = {87},
    number = {1},
    pages = {157--175},
    issn = {1939-8115},
    abstract = {The timed dataflow model of computation is a useful performance analysis tool for electronic system level design automation and embedded software synthesis. Its determinism gives it strong analyzability properties. Its monotonic temporal behavior provides hard real-time guarantees on throughput and latency. It is expressive enough to cover a large class of applications and platforms. The trend however, in both embedded applications and their platforms is to become more dynamic, reaching the limits of what the model can express and analyze with tight performance guarantees. Scenario-aware dataflow (SADF) allows more dynamism to be expressed, introducing a controlled amount of non-determinism into the model to represent different scenarios of behavior. We investigate so-called weakly consistent graphs in which the scenario changes are not tightly coupled with periods of repetitive behavior of the static dataflow behavior in scenarios as in previous methods. We define the semantics of such graphs in terms of ( max , + ) {\$}({\backslash}max , +){\$} -algebra and we introduce a method to analyze throughput using a generalization of ( max , + ) {\$}({\backslash}max , +){\$} -automata. We show that weakly-consistent SADF generalizes many of the existing analyzable dynamic dataflow models, such as CSDF, PDF and CFDF and we present an algorithm to convert CSDF graphs to SADF.},
    doi = {10.1007/s11265-016-1193-7},
    url = {http://dx.doi.org/10.1007/s11265-016-1193-7},
    }

  • H. Alizadeh Ara, A. Behrouzian, M. Hendriks, M. Geilen, D. Goswami, and T. Basten, “Scalable analysis of multi-scale dataflow models,” Acm trans. embedded computing systems, vol. 16, iss. 4, p. 80:1–80:26, 2018.
    [Bibtex]
    @Article{ABHea18,
    author = {Alizadeh Ara, Hadi and Behrouzian, Amir and Hendriks, Martijn and Geilen, Marc and Goswami, Dip and Basten, Twan},
    title = {scalable analysis of multi-scale dataflow models},
    journal = {ACM Trans. Embedded Computing Systems},
    year = {2018},
    volume = {16},
    number = {4},
    pages = {80:1--80:26},
    }

  • [DOI] M. C. W. Geilen, M. Skelin, R. J. van Kampenhout, H. A. Ara, T. Basten, S. Stuijk, and K. G. W. Goossens, “Scenarios in dataflow modeling and analysis,” in System-scenario-based design principles and applications, Cham: Springer international publishing, 2020, p. 145–180.
    [Bibtex]
    @InBook{GSKea20,
    author = {Geilen, Marc C. W. and Skelin, Mladen and van Kampenhout, J. Reinier and Ara, Hadi Alizadeh and Basten, Twan and Stuijk, Sander and Goossens, Kees G. W.},
    pages = {145--180},
    publisher = {Springer International Publishing},
    title = {Scenarios in Dataflow Modeling and Analysis},
    year = {2020},
    address = {Cham},
    isbn = {978-3-030-20343-6},
    booktitle = {System-Scenario-based Design Principles and Applications},
    doi = {10.1007/978-3-030-20343-6_8},
    url = {https://doi.org/10.1007/978-3-030-20343-6_8},
    }

Tools

SDF3 implements many of the published analysis methods for SADF.

References

[1] [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},
}
[2] [doi] M. Geilen, J. Falk, C. Haubelt, T. Basten, B. Theelen, and S. Stuijk, “Performance analysis of weakly-consistent scenario-aware dataflow graphs,” Journal of signal processing systems, vol. 87, iss. 1, p. 157–175, 2017.
[Bibtex]
@Article{GFHea16,
author = {Geilen, Marc and Falk, Joachim and Haubelt, Christian and Basten, Twan and Theelen, Bart and Stuijk, Sander},
title = {Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow Graphs},
journal = {Journal of Signal Processing Systems},
year = {2017},
volume = {87},
number = {1},
pages = {157--175},
issn = {1939-8115},
abstract = {The timed dataflow model of computation is a useful performance analysis tool for electronic system level design automation and embedded software synthesis. Its determinism gives it strong analyzability properties. Its monotonic temporal behavior provides hard real-time guarantees on throughput and latency. It is expressive enough to cover a large class of applications and platforms. The trend however, in both embedded applications and their platforms is to become more dynamic, reaching the limits of what the model can express and analyze with tight performance guarantees. Scenario-aware dataflow (SADF) allows more dynamism to be expressed, introducing a controlled amount of non-determinism into the model to represent different scenarios of behavior. We investigate so-called weakly consistent graphs in which the scenario changes are not tightly coupled with periods of repetitive behavior of the static dataflow behavior in scenarios as in previous methods. We define the semantics of such graphs in terms of ( max , + ) {\$}({\backslash}max , +){\$} -algebra and we introduce a method to analyze throughput using a generalization of ( max , + ) {\$}({\backslash}max , +){\$} -automata. We show that weakly-consistent SADF generalizes many of the existing analyzable dynamic dataflow models, such as CSDF, PDF and CFDF and we present an algorithm to convert CSDF graphs to SADF.},
doi = {10.1007/s11265-016-1193-7},
url = {http://dx.doi.org/10.1007/s11265-016-1193-7},
}