Scenario-Aware Data Flow

Scenario-Aware Dataflow (SADF) [1, 2, 3, 4] is a flavor of Dynamic Dataflow that arises from the application of Scenario-Based Design to capture dynamic variation in Timed Dataflow Models. While in traditional timed dataflow models, the same behavior is permanently repeated, SADF allows for (periodic and non-periodic) variations, for example in execution times of actors, but also in firing rates and graph topology [3]. An SADF graph distinguishes a finite set of such scenarios of behavior and defines in what orders they may occur in one or more (possibly inter-dependent) finite state automata. These automata are expressed as non-deterministic state machines, regular expressions or probabilistic/stochastic state machines (Markov chains), which determines the supported analysis capabilities [1].

Like regular timed dataflow graphs, SADF graphs need to be consistent, i.e., any produced token should eventually also be consumed. If individual scenarios are consistent, they can be freely combined to create consistent behavior. Such a graph is called strongly consistent. Weakly consistent SADF graphs follow a weaker constraint in which individual scenarios may be inconsistent, but the possible sequences of scenarios are such that the overall behaviors are always consistent [5].

Where max-plus-linear systems capture the timing and performance of timed dataflow graphs, SADF graphs with a single (non-deterministic) automaton (aka FSM-SADF) can be captured with switching max-plus-linear systems, where each scenario corresponds to a linear mode of operation. Analysis of for example throughput is in this case based on max-plus automata [6, 7].

In case probabilistic information on the occurrence of scenarios (and/or execution times for any specific scenario) is provided, an SADF graph with a single or multiple (possibly inter-dependent) automata is amenable to both worst/best-case and average-case analysis by interpreting it as a Timed Probabilistic System [8]. Evaluation of throughput, latency and buffer occupancy properties are in this case based on efficiently transforming the Timed Probabilistic System into a discrete Markov chain [8, 9].

Tools

SDF3 implements many of the published analysis methods for FSM-SADF and SADF.

Selected Related Publications

  • [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.",
title="Scenarios in Dataflow Modeling and Analysis",
bookTitle="System-Scenario-based Design Principles and Applications",
year="2020",
publisher="Springer International Publishing",
address="Cham",
pages="145--180",
isbn="978-3-030-20343-6",
doi="10.1007/978-3-030-20343-6_8",
url="https://doi.org/10.1007/978-3-030-20343-6_8"
}
  • [DOI] B. D. Theelen, E. F. Deprettere, and S. S. Bhattacharyya, “Dynamic dataflow graphs,” in Handbook of signal processing systems, S. S. Bhattacharyya, E. F. Deprettere, R. Leupers, and J. Takala, Eds., Cham: Springer international publishing, 2019, p. 1173–1210.
    [Bibtex] 
    @Inbook{HSPS17,
author="Theelen, Bart D.
and Deprettere, Ed F.
and Bhattacharyya, Shuvra S.",
editor="Bhattacharyya, Shuvra S.
and Deprettere, Ed F.
and Leupers, Rainer
and Takala, Jarmo",
title="Dynamic Dataflow Graphs",
bookTitle="Handbook of Signal Processing Systems",
year="2019",
publisher="Springer International Publishing",
address="Cham",
pages="1173--1210",
abstract="Much of the work to date on dataflow models for signal processing system design has focused on decidable dataflow models. This chapter reviews more general dataflow modeling techniques targeted to applications that include dynamic dataflow behavior. The complexity in such applications demands for increased degrees of agility and flexibility in dataflow models. With the application of dataflow techniques addressing these challenges, interest in classes of more general dataflow models has risen correspondingly. We first provide a motivation for dynamic dataflow models of computation, and review a number of specific methods that have emerged in this class of models. The dynamic dataflow models covered in this chapter are Boolean Dataflow, CAL, Parameterized Dataflow, Enable-Invoke Dataflow, Scenario-Aware Dataflow, and Dynamic Polyhedral Process Networks.",
isbn="978-3-319-91734-4",
doi="10.1007/978-3-319-91734-4_32",
url="https://doi.org/10.1007/978-3-319-91734-4_32"
}
  • 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},
}
  • R. van Kampenhout, S. Stuijk, and K. Goossens, “Programming and analysing scenario-aware dataflow on a multi-processor platform,” in Proc. design, automation and test in europe conference and exhibition (date), 2017.
    [Bibtex] 
    @InProceedings{Kampenhout2017,
Title = {Programming and analysing scenario-aware dataflow on a multi-processor platform},
Author = {Reinier van Kampenhout and Sander Stuijk and Kees Goossens},
Booktitle = {Proc. Design, Automation and Test in Europe Conference and Exhibition (DATE)},
Year = {2017},
Month = {March},
Owner = {rvkampenhout},
Timestamp = {2017.03.20}
}
  • [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},
doi = {10.1007/s11265-016-1193-7},
url = {http://dx.doi.org/10.1007/s11265-016-1193-7},
}
  • [DOI] J. Katoen and H. Wu, “Probabilistic model checking for uncertain scenario-aware data flow,” Acm transactions on embedded computing systems, vol. 28, 2016.
    [Bibtex] 
    @article{KW16,
author = {Katoen, Joost-Pieter and Wu, Hao},
year = {2016},
month = {02},
pages = {},
title = {Probabilistic Model Checking for Uncertain Scenario-Aware Data Flow},
volume = {28},
journal = {ACM Transactions on Embedded Computing Systems},
doi = {10.1145/2914788}
}
  • [DOI] A. Hartmanns, H. Hermanns, and M. Bungert, “Flexible support for time and costs in scenario-aware dataflow,” in 2016 international conference on embedded software (emsoft), 2016, pp. 1-10.
    [Bibtex] 
    @INPROCEEDINGS{HHB16,
author={Hartmanns, Arnd and Hermanns, Holger and Bungert, Michael},
booktitle={2016 International Conference on Embedded Software (EMSOFT)},
title={Flexible support for time and costs in scenario-aware dataflow},
year={2016},
volume={},
number={},
pages={1-10},
doi={10.1145/2968478.2968496}}
  • [DOI] F. Grützmacher, B. Beichler, C. Haubelt, and B. Theelen, “Dataflow-based modeling and performance analysis for online gesture recognition,” in 2016 2nd international workshop on modelling, analysis, and control of complex cps (cps data), 2016, pp. 1-8.
    [Bibtex] 
    @INPROCEEDINGS{GBHT16,
author={Grützmacher, Florian and Beichler, Benjamin and Haubelt, Christian and Theelen, Bart},
booktitle={2016 2nd International Workshop on Modelling, Analysis, and Control of Complex CPS (CPS Data)},
title={Dataflow-based modeling and performance analysis for online gesture recognition},
year={2016},
volume={},
number={},
pages={1-8},
doi={10.1109/CPSData.2016.7496423}}
  • [DOI] R. van Kampenhout, S. Stuijk, and K. Goossens, “A scenario-aware dataflow programming model,” in Digital system design (dsd), 2015 euromicro conference on, 2015, pp. 25-32.
    [Bibtex] 
    @InProceedings{Kampenhout2015,
Title = {A Scenario-Aware Dataflow Programming Model},
Author = {R. van Kampenhout and S. Stuijk and K. Goossens},
Booktitle = {Digital System Design (DSD), 2015 Euromicro Conference on},
Year = {2015},
Month = {Aug},
Pages = {25-32},
Doi = {10.1109/DSD.2015.28},
Keywords = {data flow computing;finite state machines;multiprocessing systems;CompSOC platform;FSM-SADF programming model;communication budgets;finite state machines;memory budgets;reduced resource budget;scenario switching;scenario-aware dataflow programming model;Loading;Programming;Schedules;Switches;Throughput;Time division multiplexing;Timing;CompSOC;dataflow;programming model;scenario-aware},
Owner = {reinier},
Timestamp = {2016.04.11}
}
  • [DOI] M. Skelin, E. R. Wognsen, M. C. Olesen, R. R. Hansen, and K. G. Larsen, “Model checking of finite-state machine-based scenario-aware dataflow using timed automata,” in 10th ieee international symposium on industrial embedded systems (sies), 2015, pp. 1-10.
    [Bibtex] 
    @INPROCEEDINGS{SWOHL15,
author={Skelin, Mladen and Wognsen, Erik Ramsgaard and Olesen, Mads Chr. and Hansen, René Rydhof and Larsen, Kim Guldstrand},
booktitle={10th IEEE International Symposium on Industrial Embedded Systems (SIES)},
title={Model checking of finite-state machine-based scenario-aware dataflow using timed automata},
year={2015},
volume={},
number={},
pages={1-10},
doi={10.1109/SIES.2015.7185065}}
  • [DOI] J. Katoen and H. Wu, “Exponentially timed sadf: compositional semantics, reductions, and analysis,” in 2014 international conference on embedded software (emsoft), 2014, pp. 1-10.
    [Bibtex] 
    @INPROCEEDINGS{KW14,
author={Katoen, Joost-Pieter and Wu, Hao},
booktitle={2014 International Conference on Embedded Software (EMSOFT)},
title={Exponentially timed SADF: Compositional semantics, reductions, and analysis},
year={2014},
volume={},
number={},
pages={1-10},
doi={10.1145/2656045.2656058}}
  • [DOI] M. Geilen, J. Falk, C. Haubelt, T. Basten, B. Theelen, and S. Stuijk, “Performance analysis of weakly-consistent scenario-aware dataflow graphs,” in 2014 48th asilomar conference on signals, systems and computers, 2014, pp. 393-397.
    [Bibtex] 
    @INPROCEEDINGS{GFHea14,
author={Geilen, Marc and Falk, Joachim and Haubelt, Christian and Basten, Twan and Theelen, Bart and Stuijk, Sander},
booktitle={2014 48th Asilomar Conference on Signals, Systems and Computers},
title={Performance analysis of weakly-consistent scenario-aware dataflow graphs},
year={2014},
volume={},
number={},
pages={393-397},
doi={10.1109/ACSSC.2014.7094470}}
  • [DOI] M. Damavandpeyma, S. Stuijk, T. Basten, M. Geilen, and H. Corporaal, “Throughput-constrained dvfs for scenario-aware dataflow graphs,” in 2013 ieee 19th real-time and embedded technology and applications symposium (rtas), 2013, pp. 175-184.
    [Bibtex] 
    @INPROCEEDINGS{DSBGC13,
author={M. Damavandpeyma and S. Stuijk and T. Basten and M. Geilen and H. Corporaal},
booktitle={2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS)},
title={Throughput-constrained DVFS for scenario-aware dataflow graphs},
year={2013},
volume={},
number={},
pages={175-184},
keywords={data flow graphs;decoding;energy consumption;mobile radio;quality of service;telecommunication power management;video coding;video streaming;DVFS controller;SADF;dynamic behavior;energy consumption minimization;frame rate;handheld device;mobile device;multiprocessor DVFS point;quality-of-service;scenario-aware dataflow graph;streaming application;throughput-constrained DVFS;timing guarantees;video decoder;video stream;Clocks;Concrete;Energy consumption;Streaming media;Throughput;Timing;Vectors},
doi={10.1109/RTAS.2013.6531090},
ISSN={1080-1812},
month={April},}
  • [DOI] S. S. Bhattacharyya, E. F. Deprettere, and B. D. Theelen, “Dynamic dataflow graphs,” in Handbook of signal processing systems, S. S. Bhattacharyya, E. F. Deprettere, R. Leupers, and J. Takala, Eds., New York, NY: Springer new york, 2013, p. 905–944.
    [Bibtex] 
    @Inbook{HSPS13,
author="Bhattacharyya, Shuvra S.
and Deprettere, Ed F.
and Theelen, Bart D.",
editor="Bhattacharyya, Shuvra S.
and Deprettere, Ed F.
and Leupers, Rainer
and Takala, Jarmo",
title="Dynamic Dataflow Graphs",
bookTitle="Handbook of Signal Processing Systems",
year="2013",
publisher="Springer New York",
address="New York, NY",
pages="905--944",
abstract="Much of the work to date on dataflow models for signal processing system design has focused on decidable dataflow models that are best suited for one-dimensional signal processing. This chapter reviews more general dataflow modeling techniques that are targeted to applications that include multidimensional signal processing and dynamic dataflow behavior. As dataflow techniques are applied to signal processing systems that are more complex, and demand increasing degrees of agility and flexibility, these classes of more general dataflow models are of correspondingly increasing interest. We first provide a motivation for dynamic dataflow models of computation, and review a number of specific methods that have emerged in this class of models. Our coverage of dynamic dataflow models in this chapter includes Boolean dataflow, CAL, parameterized dataflow, enable-invoke dataflow, dynamic polyhedral process networks, scenario aware dataflow, and a stream-based function actor model.",
isbn="978-1-4614-6859-2",
doi="10.1007/978-1-4614-6859-2_28",
url="https://doi.org/10.1007/978-1-4614-6859-2_28"
}
  • [DOI] M. Damavandpeyma, S. Stuijk, M. Geilen, T. Basten, and H. Corporaal, “Parametric throughput analysis of scenario-aware dataflow graphs,” in 2012 ieee 30th international conference on computer design (iccd), 2012, pp. 219-226.
    [Bibtex] 
    @INPROCEEDINGS{DSGBC12,
author={M. Damavandpeyma and S. Stuijk and M. Geilen and T. Basten and H. Corporaal},
booktitle={2012 IEEE 30th International Conference on Computer Design (ICCD)},
title={Parametric throughput analysis of scenario-aware dataflow graphs},
year={2012},
volume={},
number={},
pages={219-226},
keywords={automata theory;data flow graphs;design-space exploration;max-plus automata;parametric throughput analysis;run-time management;scenario-aware dataflow graphs;synchronous dataflow graphs;throughput calculations;video decoder;Algorithm design and analysis;Analytical models;Automata;Concrete;Throughput;Timing;Vectors},
doi={10.1109/ICCD.2012.6378644},
ISSN={1063-6404},
month={Sept},}
  • [DOI] M. Geilen, S. Stuijk, and T. Basten, “Predictable dynamic embedded data processing,” in 2012 international conference on embedded computer systems (samos), 2012, pp. 320-327.
    [Bibtex] 
    @INPROCEEDINGS{GSB12,
author={Geilen, Marc and Stuijk, Sander and Basten, Twan},
booktitle={2012 International Conference on Embedded Computer Systems (SAMOS)},
title={Predictable dynamic embedded data processing},
year={2012},
volume={},
number={},
pages={320-327},
doi={10.1109/SAMOS.2012.6404194}
}
  • [DOI] Y. Yang, M. Geilen, T. Basten, S. Stuijk, and H. Corporaal, “Playing games with scenario- and resource-aware sdf graphs through policy iteration,” in 2012 design, automation & test in europe conference & exhibition (date), 2012, pp. 194-199.
    [Bibtex] 
    @INPROCEEDINGS{YGBSC12,
author={Yang, Yang and Geilen, Marc and Basten, Twan and Stuijk, Sander and Corporaal, Henk},
booktitle={2012 Design, Automation & Test in Europe Conference & Exhibition (DATE)},
title={Playing games with scenario- and resource-aware SDF graphs through policy iteration},
year={2012},
volume={},
number={},
pages={194-199},
doi={10.1109/DATE.2012.6176462}}
  • [DOI] B. Theelen, J. Katoen, and H. Wu, “Model checking of scenario-aware dataflow with cadp,” in 2012 design, automation & test in europe conference & exhibition (date), 2012, pp. 653-658.
    [Bibtex] 
    @INPROCEEDINGS{TKW12,
author={Theelen, Bart and Katoen, Joost-Pieter and Wu, Hao},
booktitle={2012 Design, Automation & Test in Europe Conference & Exhibition (DATE)},
title={Model checking of Scenario-Aware Dataflow with CADP},
year={2012},
volume={},
number={},
pages={653-658},
doi={10.1109/DATE.2012.6176552}}
  • [DOI] B. Theelen, M. Geilen, and J. Voeten, “Performance model checking scenario-aware dataflow,” in Formal modeling and analysis of timed systems, Berlin, Heidelberg, 2011, p. 43–59.
    [Bibtex] 
    @InProceedings{TGV11,
author="Theelen, Bart
and Geilen, Marc
and Voeten, Jeroen",
editor="Fahrenberg, Uli
and Tripakis, Stavros",
title="Performance Model Checking Scenario-Aware Dataflow",
booktitle="Formal Modeling and Analysis of Timed Systems",
year="2011",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="43--59",
abstract="Dataflow formalisms are useful for specifying signal processing and streaming applications. To adequately capture the dynamic aspects of modern applications, the formalism of Scenario-Aware Dataflow (SADF) was recently introduced, which allows analysis of worst/best-case and average-case performance across different modes of operation (scenarios). The semantic model of SADF integrates non-deterministic and discrete probabilistic behaviour with generic discrete time distributions. This combination is different from the semantic models underlying contemporary quantitative model checking approaches, which often assume exponentially distributed or continuous time or they lack support for expressing discrete probabilistic behaviour. This paper discusses a model-checking approach for computing quantitative properties of SADF models such as throughput, time-weighted average buffer occupancy and maximum response time. A compositional state-space reduction technique is introduced as well as an efficient implementation of this method that combines model construction with on-the-fly state-space reductions. Strong reductions are possible because of special semantic properties of SADF, which are common to dataflow models. We illustrate this efficiency with several case studies from the multi-media domain.",
isbn="978-3-642-24310-3",
doi="10.1007/978-3-642-24310-3_5",
url="https://doi.org/10.1007/978-3-642-24310-3_5"
}
  • [DOI] F. Siyoum, M. Geilen, O. Moreira, R. Nas, and H. Corporaal, “Analyzing synchronous dataflow scenarios for dynamic software-defined radio applications,” in 2011 international symposium on system on chip (soc), 2011, pp. 14-21.
    [Bibtex] 
    @INPROCEEDINGS{SGMNC11,
author={Siyoum, Firew and Geilen, Marc and Moreira, Orlando and Nas, Rick and Corporaal, Henk},
booktitle={2011 International Symposium on System on Chip (SoC)},
title={Analyzing synchronous dataflow scenarios for dynamic software-defined radio applications},
year={2011},
volume={},
number={},
pages={14-21},
doi={10.1109/ISSOC.2011.6089222}}
  • [DOI] S. Stuijk, M. Geilen, B. Theelen, and T. Basten, “Scenario-aware dataflow: modeling, analysis and implementation of dynamic applications,” in 2011 international conference on embedded computer systems: architectures, modeling and simulation, 2011, pp. 404-411.
    [Bibtex] 
    @INPROCEEDINGS{SGTB11,
author={Stuijk, Sander and Geilen, Marc and Theelen, Bart and Basten, Twan},
booktitle={2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation},
title={Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications},
year={2011},
volume={},
number={},
pages={404-411},
doi={10.1109/SAMOS.2011.6045491}
}
  • [DOI] S. Stuijk, M. Geilen, and T. Basten, “A predictable multiprocessor design flow for streaming applications with dynamic behaviour,” in 2010 13th euromicro conference on digital system design: architectures, methods and tools, 2010, pp. 548-555.
    [Bibtex] 
    @INPROCEEDINGS{SGB10,
author={S. Stuijk and M. Geilen and T. Basten},
booktitle={2010 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools},
title={A Predictable Multiprocessor Design Flow for Streaming Applications with Dynamic Behaviour},
year={2010},
volume={},
number={},
pages={548-555},
keywords={data flow graphs;embedded systems;multimedia systems;multiprocessing systems;dynamic application behaviour;embedded systems;predictable multiprocessor design flow;synchronous dataflow graphs;time-constrained streaming applications;Bandwidth;Decoding;Schedules;Throughput;Tiles;Timing;Transform coding;dataflow;mapping;multi-processor;throughput},
doi={10.1109/DSD.2010.31},
ISSN={},
month={Sept},}
  • [DOI] 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}
}
  • B. D. Theelen, M. C. W. Geilen, S. Stuijk, S. V. Gheorghita, T. Basten, J. P. M. Voeten, and A. H. Ghamarian, “Scenario-aware dataflow,” Eindhoven University of Technology, ESR-2008-8, 2008.
    [Bibtex] 
    @TechReport{TGSGBVG08,
Title = {Scenario-Aware Dataflow},
Author = {Theelen, B.D. and Geilen, M.C.W. and Stuijk, S. and Gheorghita, S.V. and Basten, T. and Voeten, J.P.M and Ghamarian, A.H.},
Institution = {Eindhoven University of Technology},
Year = {2008},
number = {ESR-2008-8}
}
  • [DOI] B. D. Theelen, “A performance analysis tool for scenario-aware streaming applications,” in Fourth international conference on the quantitative evaluation of systems (qest 2007), 2007, pp. 269-270.
    [Bibtex] 
    @INPROCEEDINGS{The07,
author={Theelen, B.D.},
booktitle={Fourth International Conference on the Quantitative Evaluation of Systems (QEST 2007)},
title={A Performance Analysis Tool for Scenario-Aware Streaming Applications},
year={2007},
volume={},
number={},
pages={269-270},
doi={10.1109/QEST.2007.7}}
  • [DOI] B. D. Theelen, M. C. W. Geilen, T. Basten, J. P. M. Voeten, S. V. Gheorghita, and S. Stuijk, “A scenario-aware data flow model for combined long-run average and worst-case performance analysis,” in Memocode, 2006, pp. 185-194.
    [Bibtex] 
    @InProceedings{TGBea06,
Title = {A scenario-aware data flow model for combined long-run average and worst-case performance analysis},
Author = {Theelen, B.D. and Geilen, M.C.W. and Basten, T. and Voeten, J.P.M. and Gheorghita, S.V. and Stuijk, S.},
Booktitle = {MEMOCODE},
Year = {2006},
Month = {July},
Pages = {185-194},
Abstract = {Data flow models are used for specifying and analysing signal processing and streaming applications. However, traditional data flow models are either not capable of expressing the dynamic aspects of modern streaming applications or they do not support relevant analysis techniques. The dynamism in modern streaming applications often originates from different modes of operation (scenarios) in which data production and consumption rates and/or execution times may differ. This paper introduces a scenario-aware generalisation of the synchronous data flow model, which uses a stochastic approach to model the order in which scenarios occur. The formally defined operational semantics of a scenario-aware data flow model implies a Markov chain, which can be analysed for both long-run average and worst-case performance metrics using existing exhaustive or simulation-based techniques. The potential of using scenario-aware data flow models for performance analysis of modern streaming applications is illustrated with an MPEG-4 decoder example},
Doi = {10.1109/MEMCOD.2006.1695924},
Keywords = {Markov processes;data compression;data flow graphs;video codecs;video coding;video streaming;MPEG-4 decoder;Markov chain;long-run average performance analysis;operational semantics;scenario-aware data flow model;scenario-aware generalisation;simulation-based technique;stochastic approach;streaming application;synchronous data flow model;worst-case performance analysis;Analytical models;Detectors;Embedded system;Kernel;Measurement;Performance analysis;Production;Signal analysis;Signal processing;Stochastic processes},
Owner = {reinier},
Timestamp = {2014.10.23}
}

References

[1] [doi] B. D. Theelen, E. F. Deprettere, and S. S. Bhattacharyya, “Dynamic dataflow graphs,” in Handbook of signal processing systems, S. S. Bhattacharyya, E. F. Deprettere, R. Leupers, and J. Takala, Eds., Cham: Springer international publishing, 2019, p. 1173–1210.
[Bibtex]
@Inbook{HSPS17,
author="Theelen, Bart D.
and Deprettere, Ed F.
and Bhattacharyya, Shuvra S.",
editor="Bhattacharyya, Shuvra S.
and Deprettere, Ed F.
and Leupers, Rainer
and Takala, Jarmo",
title="Dynamic Dataflow Graphs",
bookTitle="Handbook of Signal Processing Systems",
year="2019",
publisher="Springer International Publishing",
address="Cham",
pages="1173--1210",
abstract="Much of the work to date on dataflow models for signal processing system design has focused on decidable dataflow models. This chapter reviews more general dataflow modeling techniques targeted to applications that include dynamic dataflow behavior. The complexity in such applications demands for increased degrees of agility and flexibility in dataflow models. With the application of dataflow techniques addressing these challenges, interest in classes of more general dataflow models has risen correspondingly. We first provide a motivation for dynamic dataflow models of computation, and review a number of specific methods that have emerged in this class of models. The dynamic dataflow models covered in this chapter are Boolean Dataflow, CAL, Parameterized Dataflow, Enable-Invoke Dataflow, Scenario-Aware Dataflow, and Dynamic Polyhedral Process Networks.",
isbn="978-3-319-91734-4",
doi="10.1007/978-3-319-91734-4_32",
url="https://doi.org/10.1007/978-3-319-91734-4_32"
}
[2] [doi] B. D. Theelen, M. C. W. Geilen, T. Basten, J. P. M. Voeten, S. V. Gheorghita, and S. Stuijk, “A scenario-aware data flow model for combined long-run average and worst-case performance analysis,” in Memocode, 2006, pp. 185-194.
[Bibtex]
@InProceedings{TGBea06,
Title = {A scenario-aware data flow model for combined long-run average and worst-case performance analysis},
Author = {Theelen, B.D. and Geilen, M.C.W. and Basten, T. and Voeten, J.P.M. and Gheorghita, S.V. and Stuijk, S.},
Booktitle = {MEMOCODE},
Year = {2006},
Month = {July},
Pages = {185-194},
Abstract = {Data flow models are used for specifying and analysing signal processing and streaming applications. However, traditional data flow models are either not capable of expressing the dynamic aspects of modern streaming applications or they do not support relevant analysis techniques. The dynamism in modern streaming applications often originates from different modes of operation (scenarios) in which data production and consumption rates and/or execution times may differ. This paper introduces a scenario-aware generalisation of the synchronous data flow model, which uses a stochastic approach to model the order in which scenarios occur. The formally defined operational semantics of a scenario-aware data flow model implies a Markov chain, which can be analysed for both long-run average and worst-case performance metrics using existing exhaustive or simulation-based techniques. The potential of using scenario-aware data flow models for performance analysis of modern streaming applications is illustrated with an MPEG-4 decoder example},
Doi = {10.1109/MEMCOD.2006.1695924},
Keywords = {Markov processes;data compression;data flow graphs;video codecs;video coding;video streaming;MPEG-4 decoder;Markov chain;long-run average performance analysis;operational semantics;scenario-aware data flow model;scenario-aware generalisation;simulation-based technique;stochastic approach;streaming application;synchronous data flow model;worst-case performance analysis;Analytical models;Detectors;Embedded system;Kernel;Measurement;Performance analysis;Production;Signal analysis;Signal processing;Stochastic processes},
Owner = {reinier},
Timestamp = {2014.10.23}
}
[3] B. D. Theelen, M. C. W. Geilen, S. Stuijk, S. V. Gheorghita, T. Basten, J. P. M. Voeten, and A. H. Ghamarian, “Scenario-aware dataflow,” Eindhoven University of Technology, ESR-2008-8, 2008.
[Bibtex]
@TechReport{TGSGBVG08,
Title = {Scenario-Aware Dataflow},
Author = {Theelen, B.D. and Geilen, M.C.W. and Stuijk, S. and Gheorghita, S.V. and Basten, T. and Voeten, J.P.M and Ghamarian, A.H.},
Institution = {Eindhoven University of Technology},
Year = {2008},
number = {ESR-2008-8}
}
[4] [doi] S. Stuijk, M. Geilen, B. Theelen, and T. Basten, “Scenario-aware dataflow: modeling, analysis and implementation of dynamic applications,” in 2011 international conference on embedded computer systems: architectures, modeling and simulation, 2011, pp. 404-411.
[Bibtex]
@INPROCEEDINGS{SGTB11,
author={Stuijk, Sander and Geilen, Marc and Theelen, Bart and Basten, Twan},
booktitle={2011 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation},
title={Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications},
year={2011},
volume={},
number={},
pages={404-411},
doi={10.1109/SAMOS.2011.6045491}
}
[5] [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},
doi = {10.1007/s11265-016-1193-7},
url = {http://dx.doi.org/10.1007/s11265-016-1193-7},
}
[6] [doi] 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}
}
[7] [doi] F. Siyoum, M. Geilen, O. Moreira, and H. Corporaal, “Worst-case throughput analysis of real-time dynamic streaming applications,” in Proceedings of the eighth ieee/acm/ifip international conference on hardware/software codesign and system synthesis, New York, NY, USA, 2012, p. 463–472.
[Bibtex]
@InProceedings{SGMC12,
author = {Siyoum, Firew and Geilen, Marc and Moreira, Orlando and Corporaal, Henk},
title = {Worst-case Throughput Analysis of Real-time Dynamic Streaming Applications},
booktitle = {Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis},
year = {2012},
series = {CODES+ISSS '12},
pages = {463--472},
address = {New York, NY, USA},
publisher = {ACM},
acmid = {2380517},
doi = {10.1145/2380445.2380517},
isbn = {978-1-4503-1426-8},
keywords = {max-plus algebra, scenario-aware data flow, self-timed execution, synchronous data flow, worst-case throughput},
location = {Tampere, Finland},
numpages = {10},
owner = {reinier},
timestamp = {2014.07.22},
url = {http://doi.acm.org/10.1145/2380445.2380517},
}
[8] [doi] B. Theelen, M. Geilen, and J. Voeten, “Performance model checking scenario-aware dataflow,” in Formal modeling and analysis of timed systems, Berlin, Heidelberg, 2011, p. 43–59.
[Bibtex]
@InProceedings{TGV11,
author="Theelen, Bart
and Geilen, Marc
and Voeten, Jeroen",
editor="Fahrenberg, Uli
and Tripakis, Stavros",
title="Performance Model Checking Scenario-Aware Dataflow",
booktitle="Formal Modeling and Analysis of Timed Systems",
year="2011",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="43--59",
abstract="Dataflow formalisms are useful for specifying signal processing and streaming applications. To adequately capture the dynamic aspects of modern applications, the formalism of Scenario-Aware Dataflow (SADF) was recently introduced, which allows analysis of worst/best-case and average-case performance across different modes of operation (scenarios). The semantic model of SADF integrates non-deterministic and discrete probabilistic behaviour with generic discrete time distributions. This combination is different from the semantic models underlying contemporary quantitative model checking approaches, which often assume exponentially distributed or continuous time or they lack support for expressing discrete probabilistic behaviour. This paper discusses a model-checking approach for computing quantitative properties of SADF models such as throughput, time-weighted average buffer occupancy and maximum response time. A compositional state-space reduction technique is introduced as well as an efficient implementation of this method that combines model construction with on-the-fly state-space reductions. Strong reductions are possible because of special semantic properties of SADF, which are common to dataflow models. We illustrate this efficiency with several case studies from the multi-media domain.",
isbn="978-3-642-24310-3",
doi="10.1007/978-3-642-24310-3_5",
url="https://doi.org/10.1007/978-3-642-24310-3_5"
}
[9] [doi] B. D. Theelen, “Performance modelling for system-level design,” PhD Thesis, 2004.
[Bibtex]
@phdthesis{The04,
title = "Performance modelling for system-level design",
author = "B.D. Theelen",
note = "Proefschrift.",
year = "2004",
doi = "10.6100/IR581220",
language = "English",
isbn = "90-386-1633-3",
publisher = "Technische Universiteit Eindhoven",
school = "Electrical Engineering",
}