Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Signal Processing for Stereoscopic and Multi-View 3D Displays Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Integrated Modeling Using Finite State Machines and Dataflow Graphs

verfasst von : Joachim Falk, Christian Haubelt, Christian Zebelein, Jürgen Teich

Erschienen in: Handbook of Signal Processing Systems

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel DSP Instruction Set Simulation
Nächstes Kapitel C Compilers and Code Optimization for DSPs
Fußnoten
1
We use 2 M to denote the power set of the set of modes M.
 
2
The CAL language even allows to specify schedule FSMs by a regular expression.
 
3
We use \(\mathbb{S}\) to denote the finite sequence of input tokens from the universal set of values V.
 
4
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}\).
 
5
We use G γ to denote the set of all possible clusters.
 
6
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.
 
7
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.
 
8
The CAL simulator component of the OpenDF environment can be downloaded from sourceforge [23].
 
9
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.
 
10
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.
 
11
A more formal definition of this condition can be found in [14].
 
Literatur
1.
Baird, M. (ed.): IEEE Standard 1666-2005 SystemC Language Reference Manual. IEEE Standards Association, New Jersey, USA (2005)
2.
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
3.
Bhattacharya, B., Bhattacharyya, S.: Parameterized dataflow modeling for DSP systems. Signal Processing, IEEE Transactions on 49(10), 2408–2421 (2001)MathSciNetCrossRef
4.
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
5.
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
6.
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)
7.
Bilsen, G., Engels, M., Lauwereins, R., Peperstraete, J.: Cyclo-static dataflow. IEEE Transaction on Signal Processing 44(2), 397–408 (1996)CrossRef
8.
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)
9.
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.
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.
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)
Metadaten
Titel
Integrated Modeling Using Finite State Machines and Dataflow Graphs
verfasst von
Joachim Falk
Christian Haubelt
Christian Zebelein
Jürgen Teich
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Handbook of Signal Processing Systems

Print ISBN: 978-1-4614-6858-5

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

Copyright-Jahr: 2013

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

Neuer Inhalt

    Bildnachweise