Top

Published in:

2020 | OriginalPaper | Chapter

8. Scenarios in Dataflow Modeling and Analysis

Authors : Marc C. W. Geilen, Mladen Skelin, J. Reinier van Kampenhout, Hadi Alizadeh Ara, Twan Basten, Sander Stuijk, Kees G. W. Goossens

Published in: System-Scenario-based Design Principles and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Dataflow models can be used to model and program concurrent systems and applications. Static timed dataflow models commonly abstract the temporal behavior of systems in terms of their worst-case behaviors. This may lead to models that are very pessimistic. The scenario methodology can be applied to the dataflow modeling approach to group similar dynamic behaviors into static dataflow behaviors that abstract the system scenarios in a tight fashion. Constraints on the possible scenario transitions in the system can be modeled, among other options, by a finite state automaton. This approach leads to a model called scenario-aware dataflow (SADF) that is presented in this chapter. We introduce the model and its semantics and discuss its fundamental analysis techniques. We discuss a parameterized extension and its analysis. We discuss a dataflow programming model and its implementation challenges. We give an overview of refined analysis techniques and run-time exploitation possibilities of SADF.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

previous chapter System Scenario Application to Dependable System Design

next chapter Scenarios in the Design of Flexible Manufacturing Systems

H.A. Ara, A. Behrouzian, M. Hendriks, M. Geilen, D. Goswami, T. Basten, Scalable analysis of multi-scale dataflow models. ACM Trans. Embed. Comput. Syst. 16(4), 80:1–80:26 (2018)

F. Baccelli, G. Cohen, G., G. Olsder, J.P. Quadrat, Synchronization and Linearity (Wiley, London, 1992)

S.S. Battacharyya, E.A. Lee, P.K. Murthy, Software Synthesis from Dataflow Graphs (Kluwer Academic Publishers, Norwell, 1996)CrossRef

T. Bijlsma, M. Bekooij, G. Smit, Circular buffers with multiple overlapping windows for cyclic task graphs, in ed. by P. Stenström. Transactions on High-Performance Embedded Architectures and Compilers III. Lecture Notes in Computer Science (Springer, Berlin, 2011). https://doi.org/10.1007/978-3-642-19447-4

J.T. Buck, Scheduling dynamic dataflow graphs with bounded memory using the token flow model. Ph.D. thesis, EECS Department, University of California, Berkeley, 1993

A.P. Chandrakasan, S. Sheng, R.W. Brodersen, Low-power CMOS digital design. IEEE J. Solid State Circuits 27(4), 473–484 (1992). https://doi.org/10.1109/4.126534CrossRef

J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. Gettrick, J.P. Quadrat, Numerical computation of spectral elements in max-plus algebra, in Proceedings of the IFAC Conference on System Structure and Control (Nantes, 1998)

M. Damavandpeyma, S. Stuijk, M. Geilen, T. Basten, H. Corporaal, Parametric throughput analysis of scenario-aware dataflow graphs, in 2012 IEEE 30th International Conference on Computer Design (ICCD), pp. 219–226 (IEEE, Piscataway, 2012). https://doi.org/10.1109/ICCD.2012.6378644

M. Damavandpeyma, S. Stuijk, T. Basten, M. Geilen, H. Corporaal, Throughput-constrained DVFs for scenario-aware dataflow graphs, in, 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS) (IEEE, Piscataway, 2013), pp. 175–184. https://doi.org/10.1109/RTAS.2013.6531090CrossRef

10.

A. Dasdan, R.K. Gupta, Faster maximum and minimum mean cycle algorithms for system-performance analysis. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 17(10), 889–899 (1998). https://doi.org/10.1109/43.728912CrossRef

11.

V. Dhingra, S. Gaubert, How to solve large scale deterministic games with mean payoff by policy iteration, in Proceedings of the 1st International Conference on Performance Evaluation Methodologies and Tools, Valuetools ’06 (ACM, New York, 2006). https://doi.org/10.1145/1190095.1190110

12.

S. Gaubert, Performance evaluation of (max, + ) automata. IEEE Trans. Autom. Control 40(12), 2014–2025 (1995)MathSciNetCrossRef

13.

M. Geilen, If we could go back in time…on the use of ‘unnatural’ time and ordering in dataflow models, in ed. by M. Lohstroh, P. Derler, M. Sirjani. Principles of Modeling: Essays Dedicated to Edward A. Lee on the Occasion of His 60th Birthday (Springer International Publishing, Cham, 2018), pp. 267–286. https://doi.org/10.1007/978-3-319-95246-8_16

14.

M. Geilen, T. Basten, Requirements on the execution of Kahn process networks, in ed. by P. Degano. Proceedings of the 12th European Symposium on Programming, ESOP 2003. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003, Warsaw, Poland, April 7–11, 2003. Lecture Notes in Computer Science, vol. 2618 (Springer, Berlin, 2003)

15.

M. Geilen, 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 (ACM, New York, 2010), pp. 125–134

16.

M. Geilen, S. Tripakis, M. Wiggers, The earlier the better: A theory of timed actor interfaces, in Proceedings of the 14th International Conference on Hybrid Systems: Computation and Control, HSCC ’11 (ACM, New York, 2011), pp. 23–32MATH

17.

M. Geilen, J. Falk, C. Haubelt, T. Basten, B. Theelen, S. Stuijk, Performance analysis of weakly-consistent scenario-aware dataflow graphs. J. Signal Process. Syst. 87(1), 157–175 (2017). https://doi.org/10.1007/s11265-016-1193-7CrossRef

18.

A.H. Ghamarian, M.C.W. Geilen, T. Basten, S. Stuijk, Parametric throughput analysis of synchronous data flow graphs, in 2008 Design, Automation and Test in Europe (IEEE, Piscataway, 2008), pp. 116–121. https://doi.org/10.1109/DATE.2008.4484672CrossRef

19.

K. Goossens, A. Azevedo, K. Chandrasekar, M.D. Gomony, S. Goossens, M. Koedam, Y. Li, D. Mirzoyan, A. Molnos, A.B. Nejad, A. Nelson, S. Sinha, Virtual execution platforms for mixed-time-criticality systems: the CompSOC architecture and design flow. SIGBED Rev. 10(3), 23–34 (2013). https://doi.org/10.1145/2544350.2544353CrossRef

20.

R. Gu, J.W. Janneck, M. Raulet, S.S. Bhattacharyya, Exploiting statically schedulable regions in dataflow programs. J. Signal Process. Syst. 63(1), 129–142 (2011). https://doi.org/10.1007/s11265-009-0445-1CrossRef

21.

B. Heidergott, G.J. Olsder, J. van der Woude, Max Plus at Work (Princeton University Press, Princeton, 2006)

22.

C.A.R. Hoare, Communicating sequential processes. Commun. ACM 21(8), 666–677 (1978) https://doi.org/10.1145/359576.359585CrossRef

23.

A. Jantsch, Modeling Embedded Systems and SoC’s: Concurrency and Time in Models of Computation (Morgan Kaufmann Publishers, San Francisco, 2003)

24.

G. Kahn, The semantics of a simple language for parallel programming, in ed. by J. Rosenfeld. Information Processing 74: Proceedings of the IFIP Congress, vol. 74, Stockholm, Sweden, August 1974 (North-Holland, Amsterdam, 1974), pp. 471–475

25.

E. Lee, D. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans. Comput. C-36(1), 24–35 (1987). https://doi.org/10.1109/TC.1987.5009446CrossRef

26.

T. Lundqvist, P. Stenström, Timing anomalies in dynamically scheduled microprocessors, in Proceedings of the 20th IEEE Real-Time Systems Symposium, RTSS ’99 (IEEE Computer Society, Washington, 1999), pp. 12. http://dl.acm.org/citation.cfm?id=827271.829103

27.

A. Moonen, M. Bekooij, R. van den Berg, J.L. van Meerbergen, Practical and accurate throughput analysis with the cyclo static dataflow model, in 15th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS 2007) (IEEE, Piscataway, 2007), pp. 238–245. http://dx.doi.org/10.1109/MASCOTS.2007.52

28.

O. Moreira, Temporal analysis and scheduling of hard real-time radios running on a multi-processor. Ph.D. thesis, Eindhoven University of Technology, 2012

29.

O. Moreira, H. Corporaal, Scheduling Real-Time Streaming Applications onto an Embedded Multiprocessor (Springer, Berlin, 2014)CrossRef

30.

O. Moreira, T. Basten, M. Geilen, S. Stuijk, Buffer sizing for rate-optimal single-rate data-flow scheduling revisited. IEEE Trans. Comput. 59(2), 188–201 (2010). https://doi.org/10.1109/TC.2009.155. Cited By 24MathSciNetCrossRef

31.

S. Neuendorffer, E. Lee, Hierarchical reconfiguration of dataflow models, in Proceedings. Second ACM and IEEE International Conference on Formal Methods and Models for Co-Design, 2004. MEMOCODE ’04 (IEEE, Piscataway, 2004), pp. 179–188. https://doi.org/10.1109/MEMCOD.2004.1459852

32.

T. Parks, Bounded Scheduling of Process Networks. Ph.D. thesis, University of California, EECS Dept., Berkeley, CA, 1995

33.

F. Siyoum, M. Geilen, J. Eker, C. von Platen, H. Corporaal, Automated extraction of scenario sequences from disciplined dataflow networks, in 2013 Eleventh IEEE/ACM International Conference on Formal Methods and Models for Codesign (MEMOCODE) (IEEE, Piscataway, 2013), pp. 47–56

34.

M. Skelin, Worst-case performance analysis of scenario-aware real-time streaming applications. Ph.D. thesis, Norwegian University of Science and Technology (NTNU), 2016

35.

M. Skelin, M. Geilen, Compositionality in scenario-aware dataflow: a rendezvous perspective, in Proceedings of the 19th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems (Association for Computing Machinery, New York, 2018), pp. 55–64

36.

M. Skelin, M. Geilen, F. Catthoor, S. Hendseth, Parameterized dataflow scenarios. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 36(4), 669–682 (2017). https://doi.org/10.1109/TCAD.2016.2597223CrossRef

37.

M. Skelin, M. Geilen, F. Catthoor, S. Hendseth, Worst-case performance analysis of sdf-based parameterized dataflow. Microprocess. Microsyst. 52, 439–460 (2017). https://doi.org/10.1016/j.micpro.2016.12.004CrossRef

38.

S. Sriram, S.S. Bhattacharyya, Embedded Multiprocessors: Scheduling and Synchronization, 2nd edn. (CRC Press, Boca Raton, 2009)

39.

S. Stuijk, M. Geilen, T. Basten, SDF³: SDF for free, in Proceedings of the 6th International Conference on Application of Concurrency to System Design, ACSD 2006 (IEEE Computer Society Press, Los Alamitos, 2006), pp. 276–278. http://www.es.ele.tue.nl/sdf3

40.

S. Stuijk, M. Geilen, T. Basten, Throughput-buffering trade-off exploration for cyclo-static and synchronous dataflow graphs. IEEE Trans. Comput. 57(10), 1331–1345 (2008). http://dx.doi.org/10.1109/TC.2008.58MathSciNetCrossRef

41.

S. Stuijk, M. Geilen, 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 (IEEE, Piscataway, 2010), pp. 548–555. https://doi.org/10.1109/DSD.2010.31

42.

S. Stuijk, M. Geilen, B. Theelen, T. Basten, Scenario-aware dataflow: modeling, analysis and implementation of dynamic applications, in 2011 International Conference on Embedded Computer Systems (SAMOS) (IEEE, Piscataway, 2011), pp. 404–411. https://doi.org/10.1109/SAMOS.2011.6045491

43.

B. Theelen, M. Geilen, T. Basten, J. Voeten, S. Gheorghita, S. Stuijk, A scenario-aware data flow model for combined long-run average and worst-case performance analysis, In: Proceedings of the Fourth ACM and IEEE International Conference on Formal Methods and Models for Co-Design, 2006. MEMOCODE ’06 (IEEE, Piscataway, 2006), pp. 185–194. https://doi.org/10.1109/MEMCOD.2006.1695924

44.

T. van den Boom, B. De Schutter, Modelling and control of discrete event systems using switching max-plus-linear systems. Control. Eng. Pract. 14(10), 1199–1211 (2006). https://doi.org/10.1016/j.conengprac.2006.02.006CrossRef

45.

B. van der Sanden, Performance analysis and optimization of supervisory controllers. Ph.D. thesis, Eindhoven University of Technology, 2018

46.

B. van der Sanden, J. Bastos, J. Voeten, M. Geilen, M.A. Reniers, T. Basten, J. Jacobs, R.R.H. Schiffelers, Compositional specification of functionality and timing of manufacturing systems, in 2016 Forum on Specification and Design Languages, FDL 2016, (IEEE, Piscataway, 2016), pp. 1–8. https://doi.org/10.1109/FDL.2016.7880372

47.

R. van Kampenhout, S. Stuijk, K. Goossens, A scenario-aware dataflow programming model, in 2015 Euromicro Conference on Digital System Design (DSD) (IEEE, Piscataway, 2015), pp. 25–32. https://doi.org/10.1109/DSD.2015.28CrossRef

48.

R. van Kampenhout, S. Stuijk, K. Goossens, Programming and analysing scenario-aware dataflow on a multi-processor platform, in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE) (IEEE, Piscataway, 2017)

49.

Y. Yang, M. Geilen, T. Basten, S. Stuijk, 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. https://doi.org/10.1109/DATE.2012.6176462

Title: Scenarios in Dataflow Modeling and Analysis
Authors: Marc C. W. Geilen
Mladen Skelin
J. Reinier van Kampenhout
Hadi Alizadeh Ara
Twan Basten
Sander Stuijk
Kees G. W. Goossens
Publisher: Springer International Publishing
Book: System-Scenario-based Design Principles and Applications
Print ISBN: 978-3-030-20342-9

Electronic ISBN: 978-3-030-20343-6

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-20343-6_8