Top

Published in:

2013 | OriginalPaper | Chapter

Integrated Modeling Using Finite State Machines and Dataflow Graphs

Authors : Joachim Falk, Christian Haubelt, Christian Zebelein, Jürgen Teich

Published in: Handbook of Signal Processing Systems

Publisher: Springer New York

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

search-config

AI-assisted search

Off

Abstract

In this chapter, different application modeling approaches based on the integration of finite state machines with dataflow models are reviewed. Restricted Models of Computation (MoC) may be exploited in design methodologies to generate optimized hardware/software implementations from a given application model. A particular focus is put on the analyzability of these models with respect to schedulability and the generation of efficient schedule implementations. In this purpose, clustering methods for model refinement and schedule optimization are of particular interest.

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

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter DSP Instruction Set Simulation

next chapter C Compilers and Code Optimization for DSPs

We use 2^M to denote the power set of the set of modes M.

The CAL language even allows to specify schedule FSMs by a regular expression.

We use \(\mathbb{S}\) to denote the finite sequence of input tokens from the universal set of values V.

We use the “. ”-operator, e.g., a. I, for member access of tuples whose members have been explicitly named in their definition, e.g., member I of actor a ∈ A from Definition 4. Moreover, this member access operator has a trivial extension to sets of tuples, e.g., \(A.I =\bigcup _{a\in A}a.I\), which is also used throughout this document. We use V ^∗ to denote the set of all possible finite sequences of tokens v ∈ V, i.e., \({V }^{{\ast}} =\bigcup _{n\in \{0,1,\ldots \}}{V }^{n}\).

We use G _γ to denote the set of all possible clusters.

We use the “. ”-operator, e.g., g _γ. A, for member access of tuples whose members have been explicitly named in their definition, e.g., member A of cluster g _γ from Definition 7. We use A ^∗ to denote the set of all possible finite sequences of actors/clusters a ∈ A, i.e., \({A}^{{\ast}} =\bigcup _{n\in \{0,1,\ldots \}}{A}^{n}\). An element of this set can be interpreted as a static schedule of actors/clusters which can be fired one after the other.

We use the “. ”-operator, e.g., ρ. cons, for member access of tuples whose members have been explicitly named in their definition, e.g., member cons of CSDF phase ρ from Definition 10.

The CAL simulator component of the OpenDF environment can be downloaded from sourceforge [23].

Note that we use p(n) to denote that at least n tokens/free space must be available on the channel connected to the actor port p.

In general, the longer the static scheduling sequence which can be executed by checking a single prerequisite, the less schedule overhead is imposed by this schedule.

A more formal definition of this condition can be found in [14].

Baird, M. (ed.): IEEE Standard 1666-2005 SystemC Language Reference Manual. IEEE Standards Association, New Jersey, USA (2005)

Balarin, F., Giusto, P., Jurecska, A., Passerone, C., Sentovich, E., Tabbara, B., Chiodo, M., Hsieh, H., Lavagno, L., Sangiovanni-Vincentelli, A., Suzuki, K.: Hardware-Software Co-Design of Embedded Systems: The POLIS Approach. Kluwer Academic Publishers (1997)MATH

Bhattacharya, B., Bhattacharyya, S.: Parameterized dataflow modeling for DSP systems. Signal Processing, IEEE Transactions on 49(10), 2408–2421 (2001)MathSciNetCrossRef

Bhattacharyya, S., Brebner, G., Eker, J., Mattavelli, M., Raulet, M.: OpenDF – A dataflow toolset for reconfigurable hardware and multicore systems (2008). First Swedish Workshop on Multi-Core Computing, MCC, Ronneby, Sweden, November 27–28, 2008

Bhattacharyya, S.S., Buck, J.T., Ha, S., Lee, E.A.: Generating compact code from dataflow specifications of multirate signal processing algorithms. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 42(3), 138–150 (1995)MATHCrossRef

Bhattacharyya, S.S., Deprettere, E.F., Theelen, B.: Dynamic dataflow graphs. In: S.S. Bhattacharyya, E.F. Deprettere, R. Leupers, J. Takala (eds.) Handbook of Signal Processing Systems, second edn. Springer (2013)

Bilsen, G., Engels, M., Lauwereins, R., Peperstraete, J.: Cyclo-static dataflow. IEEE Transaction on Signal Processing 44(2), 397–408 (1996)CrossRef

Buck, J., Ha, S., Lee, E.A., Messerschmitt, D.G.: Ptolemy: A framework for simulating and prototyping heterogenous systems. International Journal in Computer Simulation 4(2), 155–182 (1994)

Buck, J.T.: Scheduling dynamic dataflow graphs with bounded memory using the token flow model. Ph.D. thesis, Dept. of EECS, UC Berkeley, Berkeley, CA 94720, U.S.A. (1993)

10.

Dennis, J.B.: First version of a data flow procedure language. In: Programming Symposium, Proceedings Colloque sur la Programmation, pp. 362–376. Springer-Verlag, London, UK (1974)

11.

Eker, J., Janneck, J.W.: CAL language report – language version 1.0. Tech. rep., University of California at Berkeley (2003)

12.

Eker, J., Janneck, J.W., Lee, E.A., Liu, J., Liu, X., Ludvig, J., Neuendorffer, S., Sachs, S., Xiong, Y.: Taming heterogeneity - the Ptolemy approach. Proceedings of the IEEE 91(1), 127–144 (2003)CrossRef

13.

Falk, J., Haubelt, C., Teich, J.: Efficient representation and simulation of model-based designs in SystemC. In: Proc. FDL’06, Forum on Design Languages 2006, pp. 129–134. Darmstadt, Germany (2006)

14.

Falk, J., Keinert, J., Haubelt, C., Teich, J., Bhattacharyya, S.: A generalized static data flow clustering algorithm for MPSoC scheduling of multimedia applications. In: EMSOFT’08: Proceedings of the 8th ACM international conference on Embedded software (2008)

15.

Falk, J., Zebelein, C., Haubelt, C., Teich, J.: A rule-based static dataflow clustering algorithm for efficient embedded software synthesis. In: Proceedings of Design, Automation and Test in Europe (DATE’11) (2011)

16.

http://www.forteds.com (2011)

17.

Geilen, M., Basten, T.: Kahn process networks and a reactive extension. In: S.S. Bhattacharyya, E.F. Deprettere, R. Leupers, J. Takala (eds.) Handbook of Signal Processing Systems, second edn. Springer (2013)

18.

Girault, A., Lee, B., Lee, E.: Hierarchical finite state machines with multiple concurrency models. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 18(6), 742–760 (1999)CrossRef

19.

Grötker, T., Liao, S., Martin, G., Swan, S.: System Design with SystemC. Kluwer Academic Publishers (2002)

20.

Gu, R., Janneck, J.W., Raulet, M., Bhattacharyya, S.S.: Exploiting statically schedulable regions in dataflow programs. J. Signal Processing Systems 63(1), 129–142 (2011)CrossRef

21.

Ha, S., Oh, H.: Decidable dataflow models for signal processing: Synchronous dataflow and its extensions. In: S.S. Bhattacharyya, E.F. Deprettere, R. Leupers, J. Takala (eds.) Handbook of Signal Processing Systems, second edn. Springer (2013)

22.

Hsu, C., Bhattacharyya, S.S.: Cycle-breaking techniques for scheduling synchronous dataflow graphs. Tech. Rep. UMIACS-TR-2007-12, Institute for Advanced Computer Studies, University of Maryland at College Park (2007). URL http://hdl.handle.net/1903/4328

23.

Janneck, J.W.: The open dataflow project. http://opendf.sourceforge.net (2009)

24.

Janneck, J.W., Miller, I.D., Parlour, D.B., Roquier, G., Wipliez, M., Raulet, M.: Automatic software synthesis of dataflow program: An MPEG-4 simple profile decoder case study. In: Proc. of the IEEE Workshop on Signal Processing Systems (SiPS’08), pp. 281–286 (2008)

25.

Janneck, J.W., Miller, I.D., Parlour, D.B., Roquier, G., Wipliez, M., Raulet, M.: Synthesizing hardware from dataflow programs: An MPEG-4 simple profile decoder case study. In: Proc. of the IEEE Workshop on Signal Processing Systems (SiPS’08), pp. 287–292 (2008)

26.

Kahn, G.: The semantics of simple language for parallel programming. In: IFIP Congress, pp. 471–475 (1974)

27.

Keinert, J., Streubühr, M., Schlichter, T., Falk, J., Gladigau, J., Haubelt, C., Teich, J., Meredith, M.: SYSTEMCODESIGNER - An automatic ESL synthesis approach by design space exploration and behavioral synthesis for streaming applications. Transactions on Design Automation of Electronic Systems 14(1), 1–23 (2009)CrossRef

28.

Lee, E.A.: Overview of the Ptolemy project. Tech. Rep. UCB/ERL M03/25, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA, 94720, USA (2004)

29.

Lee, E.A., Messerschmitt, D.G.: Synchronous data flow. Proceedings of the IEEE 75(9), 1235–1245 (1987)CrossRef

30.

Lukasiewycz, M., Glaß, M., Haubelt, C., Teich, J., Regler, R., Lang, B.: Concurrent topology and routing optimization in automotive network integration. In: Proceedings of the 2008 ACM/EDAC/IEEE Design Automation Conference (DAC’08), pp. 626–629. Anaheim, USA (2008)

31.

Necula, G.C., McPeak, S., Rahul, S.P., Weimer, W.: CIL: Intermediate language and tools for analysis and transformation of C programs. In: R.N. Horspool (ed.) Compiler Construction, Lecture Notes in Computer Science, vol. 2304, pp. 209–265. Springer (2002)

32.

Pino, J., Bhattacharyya, S., Lee, E.: A hierarchical multiprocessor scheduling system for DSP applications. In: Signals, Systems and Computers, 1995. 1995 Conference Record of the Twenty-Ninth Asilomar Conference on, vol. 1, pp. 122–126 (1995)

33.

Plishker, W., Sane, N., Bhattacharyya, S.: A generalized scheduling approach for dynamic dataflow applications. In: Design, Automation Test in Europe Conference Exhibition, 2009. DATE ’09., pp. 111–116 (2009)

34.

Plishker, W., Sane, N., Kiemb, M., Bhattacharyya, S.S.: Heterogeneous design in functional DIF. In: Proceedings of the 8th international workshop on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS ’08, pp. 157–166. Springer-Verlag, Berlin, Heidelberg (2008)

35.

Sangiovanni-Vincentelli, A.L., Sgroi, M., Lavagno, L.: Formal models for communication-based design. In: Proceedings of the 11th International Conference on Concurrency Theory, CONCUR ’00, pp. 29–47. Springer-Verlag, London, UK (2000)

36.

XILINX: Embedded SystemTools Reference Manual - Embedded Development Kit EDK 8.1ia (2005)

Title: Integrated Modeling Using Finite State Machines and Dataflow Graphs
Authors: Joachim Falk
Christian Haubelt
Christian Zebelein
Jürgen Teich
Publisher: Springer New York
Book: Handbook of Signal Processing Systems
Print ISBN: 978-1-4614-6858-5

Electronic ISBN: 978-1-4614-6859-2

Copyright Year: 2013
DOI: https://doi.org/10.1007/978-1-4614-6859-2_30

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"