Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2011 | OriginalPaper | Chapter

2. Models of Computation and Languages

Authors : Ivan Radojevic, Zoran Salcic

Published in: Embedded Systems Design Based on Formal Models of Computation

Publisher: Springer Netherlands

Log in

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

search-config
loading …

Abstract

This chapter looks at several important models of computation and languages for embedded systems design. We do not attempt to draw sharp distinctions between models and languages. Thus, the topics in this section are not divided strictly to either models of computation or languages. A model of computation is commonly used for defining the semantics of a language. However, when a model of computation is expressed with a simple syntax, it can also be called a language. For example, synchronous dataflow (SDF) is usually thought of as a model of computation. But as soon as it is expressed with a simple graphical syntax consisting of a network of blocks connected with arrows, it is not incorrect to call it a language.

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 Introduction
next chapter Specification in DFCharts
Literature
6.
E.A. Lee, S. Neuendorffer, Concurrent models of computation for embedded software. IEE Proc. Comput. Digit. Technol. 152(2), 239–250 (2005)CrossRef
7.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation (Addison-Wesley Publishing Company, Reading, 1979)MATH
9.
C.G. Cassandras, Introduction to Discrete Event Systems (Kluwer, Dordrecht/Boston, 1999)MATH
10.
E.A. Lee, T.M. Parks, Dataflow process networks. Proc. IEEE 83, 773–801 (1995)CrossRef
11.
A. Benveniste, G. Berry, The synchronous approach to reactive and real-time systems. Proc. IEEE 79(9), 1270–1282 (1991)CrossRef
12.
T. Murata, Petri nets: properties, analysis, and applications. Proc. IEEE 77(4), 541–580 (1989)CrossRef
13.
14.
R. Milner, Communication and Concurrency (Prentice-Hall, Englewood Cliffs, 1989)MATH
15.
G. Berry, G. Gonthier, The Esterel synchronous programming language: design, semantics, implementation. Sci. Comput. Program. 19(2), 87–152 (1992)MATHCrossRef
16.
N. Halbwachs, P. Caspi, P. Raymond, D. Pilaud, The synchronous data flow programming language LUSTRE. Proc. IEEE 79(9), 1305–1320 (1991)CrossRef
17.
P. Le Guernic, T. Gautier, M. Le Borgne, C. Le Maire, Programming real-time applications with SIGNAL. Proc. IEEE 79(9), 1321–1336 (1991)CrossRef
20.
J. Eker et al., Taming heterogeneity – the ptolemy approach. Proc. IEEE 91(1), 127–144 (2003)CrossRef
22.
23.
E.A. Lee, D.G. Messerschmitt, Synchronous data flow. Proc. IEEE 75(9), 1235–1245 (1987)CrossRef
24.
F. Maraninchi, Y. Remond, Argos: an automaton-based synchronous language. Comput. Lang. 27(1–3), 61–92 (2001)MATHCrossRef
26.
G. Bilsen, M. Engels, R. Lauwereins, J.A. Peperstraete, Cyclo-static dataflow. IEEE Trans. Signal Process. 44(2), 397–408 (1996)CrossRef
27.
G. Kahn, The semantics of a simple language for parallel programming, in Proceedings of IFIP Congress 1974, Stockholm, Aug 1974, pp. 471–475
29.
B.A. Davey, H.A. Priestley, Introduction to Lattices and Order (Cambridge University Press, Cambridge, 1990)MATH
30.
T.M. Parks, Bounded scheduling of process networks. Ph.D. dissertation, Technical Report UCB/ERL 95/105, Department of EECS, University of California, Berkeley, 1995
31.
G. Kahn, D.B. MacQueen, Coroutines and networks of parallel processes, in Proceedings of the IFIP Congress 1977, North-Holland, Aug 1977, pp. 993–998
32.
E.A. Lee, D.G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans. Comput. 36(1), 24–35 (1987)MATHCrossRef
33.
E.A. Lee, Consistency in dataflow graphs. IEEE Trans. Parallel Distrib. Syst. 2(2), 223–235 (1991)CrossRef
34.
J.T. Buck, Scheduling dynamic dataflow graphs with bounded memory using the token flow model. Ph.D. dissertation, Technical Report UCB/ERL 93/69, Department of EECS, University of California, Berkeley 1993
35.
B. Bhattacharya, S. Bhattacharyya, Parameterized dataflow modeling for DSP systems. IEEE Trans. Signal Process. 49(10), 2408–2421 (2001)MathSciNetCrossRef
36.
P.K. Murthy, E.A. Lee, Multidimensional synchronous dataflow. IEEE Trans. Signal Process. 50(8), 3306–3309 (2002)CrossRef
37.
C. Park, J.W. Chung, S. Ha, Extended synchronous dataflow for efficient DSP system prototyping, in Proceedings on Workshop in Rapid System Prototyping, Clearwater, June 1999
38.
H. Oh, N. Dutt, S. Ha, Memory optimal single appearance schedule with dynamic loop count for synchronous dataflow graphs, in Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC’06), Yokohama City, Jan 2006
39.
S. Stuijk, M. Geilen, T. Basten, Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs, in Proceedings of Design Automation Conference (DAC ’06), San Francisco, July 2006
40.
S. Stuijk, M. Geilen, T. Basten, Minimising buffer requirements of synchronous dataflow graphs with model checking, in Proceedings of Design Automation Conference (DAC’05), New York, June 2005
41.
D. Bjorklund, Efficient code synthesis from synchronous dataflow graphs, in Proceedings of Formal Methods and Models for Co-Design (MEMOCODE’04), June 2004
42.
P.K. Murthy, S.S. Bhattacharyya, Shared buffer implementations of signal processing systems using lifetime analysis techniques. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 20(2), 3306–3309 (2001)CrossRef
43.
M. Ade, R. Lauwereins, J.A. Peperstraete, Data memory minimisation for synchronous data flow graphs emulated on DSP-FPGA targets, in Proceedings of Design Automation Conference (DAC’97), Anaheim, June 1997
44.
R. Govindarajan, G.R. Gao, P. Desai, Minimizing buffer requirements under rate-optimal schedule in regular dataflow networks, J. VLSI Sig. Proc. 31(3), 207–229 (2002)MATHCrossRef
45.
J. S. Kin, J.L Pino, Multithreaded synchronous data flow simulation, in Proceedings of Design, Automation and Test in Europe Conference (DATE’03), Mar 2003
46.
C. Hsu, S. Ramasubbu, M. Ko, J.L. Pino, S.S. Bhattacharyya, Efficient simulation of critical synchronous dataflow graphs, in Proceedings of Design Automation Conference (DAC ’06), July 2006
47.
E. Zitzler, J. Teich, S.S. Bhattclcharyya, Evolutionary algorithms for the synthesis of embedded software. IEEE Trans. Very Large Scale Integr. Syst. 8(4) (2000)
48.
W. Sung, S. Ha, Memory efficient software synthesis with mixed coding style from dataflow graphs. IEEE Trans. Very Large Scale Integr. Syst. 8(5), 522–526 (2000)CrossRef
49.
M. Sen, S.S. Bhattacharyya, Systematic exploitation of data parallelism in hardware synthesis of DSP applications, in Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP ’04), May 2004
50.
H. Jung, K. Lee, S. Ha, Efficient hardware controller synthesis for synchronous dataflow graph in system level design. IEEE Trans. Very Large Scale Integr. Syst. 10(2), 672–679 (2002)
51.
M.C. Williamson, E.A. Lee, Synthesis of parallel hardware implementations from synchronous dataflow graph specifications, in Proceedings of Conference on Signals, Systems and Computers, Nov 1996
52.
A. Kalavade, P.A. Subrahmanyam, Hardware/software partitioning for multifunction systems. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 17(9), 819–837 (1998)CrossRef
53.
A. Kalavade, E.A. Lee, A hardware-software codesign methodology for DSP applications. IEEE Des. Test Comput. 10(3), 16–28 (1993)CrossRef
54.
T. Wiangtong, P. Cheung, L. Luk, Hardware/software codesign: a systematic approach targeting data-intensive applications. IEEE Signal Process Mag. 22(3), 14–22 (2005)CrossRef
55.
N. Halbwachs, Synchronous Programming of Reactive Systems (Kluwer, Dordrecht/Boston, 1993)MATH
56.
R. Budde, G.M. Pinna, A. Poigne, Coordination of synchronous programs, in Proceedings of International Conference on Coordination Languages and Models, LNCS 1594, Apr 1999
57.
J. Colaco, B. Pagano, M. Pouzet, Specification and semantics: a conservative extension of synchronous data-flow with state machines, in Proceedings of the 5th ACM International Conference on Embedded Software (EMSOFT ’05), Sept 2005
58.
59.
G. Berry, Esterel on hardware. Philos. Trans. R. Soc. Lond. A 339, 87–104 (1992)CrossRef
60.
S. Edwards, An Esterel compiler for large control-dominated systems. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 21(2), 169–183 (2002)CrossRef
61.
E. Closse, M. Poize, J. Pulou, P. Vernier, D. Weil, SAXO-RT: interpreting Esterel semantic on a sequential execution structure, in Proceedings of International Workshop on Synchronous Languages, Applications, and Programming (SLAP’02), Electronic notes in theoretical computer science 65, Apr 2002
62.
D. Potop-Butucaru, R. de Simone, Optimizations for faster execution of Esterel programs, in Proceedings of Formal Methods and Models for Co-Design (MEMOCODE’03), June 2003
63.
C. Passerone, C. Sansoe, L. Lavagno, P.C. McGeer, J. Martin, R. Passerone, A.L. Sangiovanni-Vincentelli, Modeling reactive systems in Java. ACM Trans. Des. Autom. Electron. Syst. 3(4), 515–523 (1998)CrossRef
64.
L. Lavagno, E. Sentovich, ECL: a specification environment for system-level design, in Proceedings of Design Automation Conference (DAC ’99), June 1999
65.
M. Antonotti, A. Ferrari, A. Flesca, A.L. Sangiovanni-Vincentelli, JESTER: an esterel-based reactive java extension for reactive embedded system development, in Proceedings of Forum on Specification and Design Languages (FDL’00), Sept 2000
66.
F. Boussinot, R. de Simone, The SL synchronous language. IEEE Trans. Softw. Eng. 22(4), 256–266 (1996)CrossRef
67.
J.S. Young, J. MacDonald, M. Shilman, A. Tabbara, P. Hilfinger, A.R. Newton, Design and specification of embedded systems in Java using successive, formal refinement, in Proceedings of Design Automation Conference (DAC ’98), June1998
68.
M. von der Beeck, A comparison of statecharts variants, in Proceedings of Formal Techniques in Real Time and Fault Tolerant Systems, LNCS 863, Sept 1994
69.
F. Maraninchi, Operational and compositional semantics of synchronous automaton compositions, in Proceedings of International Conference on Concurrency Theory (CONCUR'92), LNCS 630, Aug 1992
70.
71.
T. Grotker, S. Liao, G. Martin, S. Swan, System Design with SystemC (Kluwer, Boston/Dordrecht, 2002)
72.
J. Bhasker, A SystemC Primer (Star Galaxy Publishing, Allentown, 2002)
73.
J.G. Lee, C.M. Kyung, PrePack: predictive packetizing scheme for reducing channel traffic in transaction-level hardware/software co-emulation. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(10), 1935–1949 (2006)CrossRef
74.
W. Klingauf, R. Gunzel, O. Bringmann, P. Parfuntseu, M. Burton, GreenBus – a generic interconnect fabric for transaction level modelling, in Proceedings of Design Automation Conference (DAC ’06), July 2006
75.
E. Viaud, F. Pecheux, A. Greiner, An efficient TLM/T modeling and simulation environment based on conservative parallel discrete event principles, in Proceedings of Design, Automation and Test in Europe Conference (DATE’06), Mar2006
76.
T. Wild, A. Herkersdorf, R. Ohlendorf, Performance evaluation for system-on-chip architectures using trace-based transaction level simulation, in Proceedings of Design, Automation and Test in Europe Conference (DATE’06), Mar 2006
77.
A. Habibi, S. Tahar, A. Samarah, D. Li, O. Mohamed, Efficient assertion based verification using TLM, in Proceedings of Design, Automation and Test in Europe Conference (DATE’06), Mar 2006
78.
G. Beltrame, D. Sciuto, C. Silvano, D. Lyonnard, C. Pilkington, Exploiting TLM and object introspection for system-level simulation, in Proceedings of Design, Automation and Test in Europe Conference (DATE’06), Mar 2006
79.
D. Gajski, J. Zhu, R. Domer, A. Gerstlauer, S. Zhao, SpecC: Specification Language and Methodology (Kluwer, Dordrecht/Boston, 2000)CrossRef
80.
D. Ku, G. De Micheli, HardwareC – a language for hardware design (version 2.0) CSL Technical Report CSL-TR-90-419, Stanford University, Stanford, Apr 1990
81.
82.
D. Harel, H. Lachover, A. Naamad, A. Pnueli, M. Politi, R. Sherman, A. Shtull-Trauring, M. Trakhtenbrot, Statemate: a working environment for the development of complex reactive systems. IEEE Trans. Softw. Eng. 16, 403–414 (1990)CrossRef
83.
J. Buck, S. Ha, E.A. Lee, D. Messerschmitt, Ptolemy: a framework for simulating and prototyping heterogeneous systems. Int. J. Comput. Simul. 4(2), 155–182 (1994)
84.
C. Hylands, E.A. Lee, J. Liu, X. Liu, S. Neuendorffer, Y. Xiong, H. Zheng, Heterogeneous concurrent modeling and design in Java, Technical Memorandum UCB/ERL M02/23, University of California, Berkeley, 2002
85.
A. Girault, B. Lee, E.A. Lee, Hierarchical finite state machines with multiple concurrency models. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 18(6), 742–760 (1999)CrossRef
Metadata
Title
Models of Computation and Languages
Authors
Ivan Radojevic
Zoran Salcic
Copyright Year
2011
Publisher
Springer Netherlands
Book
Embedded Systems Design Based on Formal Models of Computation

Print ISBN: 978-94-007-1593-6

Electronic ISBN: 978-94-007-1594-3

Copyright Year: 2011

DOI
https://doi.org/10.1007/978-94-007-1594-3_2

Premium Partners

    Image Credits