Model-Based Design for Embedded Systems- P20

Chia sẻ: Cong Thanh | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

60
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Model-Based Design for Embedded Systems- P20:The unparalleled flexibility of computation has been a key driver and feature bonanza in the development of a wide range of products across a broad and diverse spectrum of applications such as in the automotive aerospace, health care, consumer electronics, etc.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Model-Based Design for Embedded Systems- P20

546 Model-Based Design for Embedded Systems implicitly the synchronization. This property verifies that after a cycle exe- cuted by each model, both are at the same time stamp (and by consequence are synchronized) Definition: Invariantly both processes in the Start location (initial state) imply the time in the continuous domain tc is equal with the time in the discrete domain td . P4 Causality principle (liveness property) The causality can be defined as a cause and effect relationship. The causal- ity of two events describes to what extent one event is caused by the other. The causality is already verified by P3 for scheduled events. However, when a state event is generated by the continuous domain, the discrete domain has to detect this event at the same precise time (the cause precedes or equals the effect time) and not some other possible event existing at a different time in the continuous domain. Definition: Invariantly both processes in the StEvDetect location (detection of state event) imply the time in the continuous tc is equal with the time in the discrete td . 16.6.6 Deﬁnition of the Internal Architecture of the Simulation Interfaces The overall continuous/discrete simulation interface is formally defined using the DEVS formalism. As shown in Figure 16.4, the interface is described as a set of coupled models: the continuous domain interface (CDI), the discrete domain interface (DDI), and the co-simulation bus. Figure 16.12 shows the atomic modules composing the interface used in our implementation. The specific functionalities of the interfaces were presented in Sec- tion 16.4.2. In terms of internal architecture, the blocks assuring these fea- tures are For the Continuous Model Simulation Interface • The State Event Indication and Time Sending block (SETS) • The Signal Conversion and Data Exchange block (SCDE) • The Event Detection block (DED) • The Context Switch block (CS) For the Discrete Model Simulation Interface • The End of Discrete Simulation Cycle Detection and Time Sending block (DDTS) • The Data Exchange block (DE) • The Event Detection block (DEC) • The Context Switch block (CS) These atomic modules are forming the co-simulation library and the co- simulation tools enable their parameterization and their assembly in order to generate a new co-simulation instance.
Generic Methodology for the Design 547 Continuous/discrete global simulation model Continuous Continuous/discrete Discrete model simulation interface model Continuous domain Discrete model simulation simulation interface-CDI interface-DDI Context Event Data switch Context exchange detection DED switch CS CS Co-simulation DE bus Signal State event Event End of discrete simulation conversion and indication and time detection DEC cycle detection and data exchange sending SETS time sending SCDE DDTS Elements from the co-simulation library FIGURE 16.12 The hierarchical representation of the generic architecture of the co- simulation model with the elements of the co-simulation library defined. (From Gheorghe, L. et al., Formal definition of simulation interfaces in a continuous/discrete co-simulation tool, Proceedings of the 17th IEEE Inter- national Workshop on RSP, Chania, Crete, Greece, pp. 186–192, 2006. With permission.) Data to/from the discrete Data to/from the continuous simulator DS simulator DS End of discrete Signal State event simulation cycle Event Context Data conversion Context Event indication detection and detection switch exchange and data switch detection and time time sending DEC CS DE exchange CS DED DDTS SCDE sending SETS Discrete domain interface DDI Continuous domain interface CDI Discrete/continuous data exchange Flag from the discrete to the continuous model Flag from the continuous to the discrete model Time of state event tse Time of the next scheduled event in the discrete simulator td FIGURE 16.13 Internal architecture of the continuous/discrete simulation interface. (From Gheorghe, L. et al., Formal definition of simulation interfaces in a continuous/discrete co-simulation tool, Proceedings of the 17th IEEE Inter- national Workshop on RSP, Chania, Crete, Greece, pp. 186–192, 2006. With permission.) Figure 16.13 presents the atomic modules interconnection in each domain specific simulation interface as well as the signals and interactions between the interfaces.
548 Model-Based Design for Embedded Systems The internal architecture is defined as a set of coupled modules that respect the coupled modules DEVS formalism as presented in Section 16.6.1: -Ninterface = (X,Y, D, {Md |d ∈ D}, EIC,EOC,IC ) -X = {(pd , vd )|pd ∈ InPorts, vd ∈ X pd } -Y = {( pd , vd )|pd ∈ OutPorts, vd ∈ Y pd } -X pd, Y pd = values for input ports, respectively output ports -InPorts = Pin,c ∪ Pin,d ∪ Pin,td ∪ Pin,tse ∪ Pin,flag where Pin,c – set of ports receiving data from the continuous model; Pin,d – set of ports receiving data from the discrete model (via the co-simulation bus); Ptd – port receiving the timestamp of the next discrete event Pin,flag – port receiving the command for the context switch - OutPorts = Pout,c ∪ Pout,d ∪ Pout,td ∪ Pout,tse ∪ Pout,flag Pout,flag, Pout,c , Pout,d are defined similarly to Pin,flag,, Pin,c and Pin,d - D = {“Continuous Domain Interface” (with associated model NinterfaceCDI ), “Discrete Domain Interface” (with associated model NinterfaceDDI ), “co-simulation bus” (with associated model Mcosim )} −Md = (NinterfaceCDI , MinterfaceDDI , Mcosim ) −EIC = {((Ninterface , “inc,1 ), (NinterfaceCDI , “inc,1 )); ...; ((Ninterface , “inc,n ), (NinterfaceCDI , “inc,n )); ((Ninterface , “ind,0 ), (NinterfaceDDI , “ind,0 )); ...; ((Ninterface , “ind,m ), (NinterfaceDDI , “ind,m ))} −EOC = {((NinterfaceCDI , “outc,1 ), (Ninterface , “outc,1 )); ...; ((NinterfaceCDI , “outc,p ), (Ninterface , “outc,p )); ((NinterfaceDDI , “outd,1 ), (Ninterface , “outd,1 )); ...; ((NinterfaceDDI , “outd,q ), (Ninterface , “outd,q ))} −IC = {((NinterfaceCDI , opCDI ), (Mcosim , ipcosim ))|NinterfaceCDI , − Mcosim ∈ D, opCDI ∈ OutPortsCDI, ipcosim ∈ InPortscosim }∪ {((NinterfaceDDI , opDDI ), (Mcosim , ipcosim ))|NinterfaceDDI , Mcosim ∈ D, opDDI ∈ OutPortsDDI, ipcosim ∈ InPortscosim }∪ {((Mcosim , opcosim ), (NinterfaceCDI , ipCDI ))|NinterfaceCDI , Mcosim ∈ D, opcosim ∈ OutPortscosim, ipCDI ∈ InPortsCDI, }∪ {((Mcosim , opcosim ), (NinterfaceDDI , ipDDI ))|NinterfaceDDI , − Mcosim ∈ D, opcosim ∈ OutPortscosim, ipDDI ∈ InPortsDDI, }[12] We show here the atomic module co-simulation bus that can be formally defined as follows: - X. = {(pd , vd ) |pd ∈ InPorts, vd ∈ Xpd } - Y = {(pd , vd ) |pd ∈ OutPorts, vd ∈ Ypd }
Generic Methodology for the Design 549 - InPorts = Pin,c ∪ Pin,d ∪ Pin,td ∪ rmPin,tse ∪ Pin,flag - OutPorts = Pout,c ∪ Pout,d ∪ Pout,td ∪ Pout,tse ∪ Pout,flag where Pin,c , Pin,d Pin,td , Pin,tse , Pin,flag Pout,c , Pout,d , Pout,td , Pout,tse, Pout,flag as well as Xpd , Ypd were previously defined. States triplet S: (phase * σ * job) where: phase: (“passive,” “active”) σ : + advance time 0 job: (“store,” “respond”) S = {“passive,” “active”} * + * {“store”, “respond”} 0 δext ((“passive” * σ * job), e, x))= (“passive,” σ –e, x), if x = 0 (“active”, σ –e, job), if x! = 0 δint (s) = (“active”, σ, job) λ (“active,” σ, job) = {“store”, “respond” } ta (phase, σ, job) = σ The architecture of the discrete domain interface and the continuous domain interface are also formally defined as a set of coupled modules. For- mal descriptions for DDI and CDI respect the coupled module DEVS formal- ism. Each element of the structure follows the concepts presented in Section 16.6.1 and that were applied for the overall continuous/discrete simulation interface. 16.6.7 Analysis of the Simulation Tools for the Integration in the Co-Simulation Framework The previous steps that describe the gradual formal definition of the simu- lation interfaces and the required library elements are independent of the different simulation tools and specification languages used generally for the specification/execution of the continuous and discrete subsystems. After the analysis of the existing tools we found that Simulink is an illustra- tive example of a continuous simulator enabling the control functionalities that were presented in Section 16.4.5. These functionalities can be added in generic library blocks and a given Simulink model may be prepared for the co-simulation by parameterization and addition of these blocks. Several discrete simulators present the characteristics detailed in Section 16.4.5. SystemC is an illustrative example. Since it is an open source, SystemC enables the addition of the presented functionalities in an efficient way—the scheduler can be modified and adapted for co-simulation. In this way, the co- simulation overhead may be minimized. However, the addition of simula- tion interfaces is more difficult than in Simulink because the specifications in SystemC are textual and a code generator is required to facilitate the addition of simulation interfaces. The automatic generation of the co-simulation inter- faces is very suitable, since their design is time consuming and an important source of errors. The strategy currently used is based on the configuration of the components and their assembly. These components are selected from a co-simulation library.
550 Model-Based Design for Embedded Systems 16.6.8 Implementation of the Library Elements Speciﬁc to Different Simulation Tools The implementation for the validation of continuous/discrete systems was realized using SystemC for the discrete simulation models and Simulink for the continuous simulation models. For Simulink, the interfaces are functional blocks programmed in C++ using S-Functions [24]. These blocks are manipulated like all other compo- nents of the Simulink library. They contain input/output ports compatible with all model ports that can be connected directly using Simulink signals. The user starts by dragging the interfaces from the interface components library into the model’s window, then parameterizes them, and finally con- nects them to the inputs and the outputs of his model. For SystemC, in order to increase the simulation performance, part of the synchronization functionality has been implemented at the scheduler’s level, which is a part of the state event management and the end of the dis- crete cycle detection (detects that there are no more delta cycles at the cur- rent time). For the generation of the co-simulation interfaces for SystemC, the implementation of a code generator was necessary. This script has as input user-defined parameters such as sampling periods, number and type of ports, and synchronization ports. 16.7 Formalization and Verification of the Interfaces One of the key issues for the automatic generation of co-simulation inter- faces is the rigorous definition of the behavior and architecture of simula- tion interfaces and this can be achieved by their formalization and formal verification in terms of behavior. Formal definitions can be used to develop easy-to-verify designs [16]. On this mathematical foundation one can define the criteria that allows for the automatic selection of the components from the co-simulation library and the automatic generation of the co-simulation interfaces. This section presents the formalization and the verification of the co-simulation interfaces. 16.7.1 Discrete Simulator Interface This section presents the operational semantics of the discrete simulation interfaces (DSI). The semantics were defined with respect to the synchroniza- tion model presented in Section 16.6.1, using the DEVS formalism. Table 16.2 presents a set of rules that show the transitions between states. For all the rules, the semantics of the global variable flag is related to the context switch between the continuous and discrete simulators. When the flag is set to “1,” the discrete simulator is executed. When it is “0,” the con- tinuous simulator is executed. The global variable synch is used to impose
Generic Methodology for the Design 551 TABLE 16.2 Operational Semantics for the DSI Nr. Rule synch = 1 ∧ flag = 1 ∧ (xdk , tdk ) = δext ((xdk , tdk ), 0, x) 1. ?DataFromDisc !(data,tdk+1 ((xdk ,tdk )));flag:=0 ((xdk ,tdk ), ∞) − − − − ((xdk , tdk ), 0) − − − − − − − − → ((xdk , tdk ), tdk+1 ) −−−→ −−−−−−−− synch = 0 ∧ flag = 1 ∧ ¬stateevent ∧ (xdk , tdk ) = δext ((xdk , tdk ), 0, x) 2. ?Event ?data;synch:=1 !DataToDisc ((xdk , tdk ), edk ) − → ((xdk , tdk ), 0) − − − − ((xdk , tdk ), 0) − − − → ((xdk+1 , tdk+1 ), edk+1 ) − − − −→ −−− synch = 0 ∧ flag = 1 ∧ stateevent ∧ (xdk , tdk ) = δext ((xdk , tdk ), 0, x) 3. ?Event ?(data,tse );synch:=1 !(DataToDisc,tse ) ((xdk , tdk ), edk ) − → ((xdk , tdk ), 0) − − − − − → ((xdk , tdk ), 0) − − − − → ((xse , tse ), ese ) − −−−−− −−−− the order of the different operations expressed by the rules. The first rule covers arrow 1 in Figure 16.5a and b. The second and third rules correspond to arrows 3 (on the receiving part) and 4 in Figure 16.5a and b. In order to clarify, we present here the first rule in detail. The premises of this rule are: the synch variable has value “1,” the flag variable has value “1,” and we have an external transition function (δext ) for the DSI. This rule expresses the following actions of the discrete simulator inter- face (DSI): • Receiving data from the discrete model. This is an external transition (δext ) expressed by ?(DataFromDisc). • Sending data to the continuous simulator interface (CSI) (!DataToCSI). The data sent to the CSI is the output function λ(xdk ,tdk ) and it is possible, in accordance with DEVS formalism, only as a consequence of an internal transition (δint ). In our case, the output is represented by !(data,tdk+1 (xdk ,tdk )). This transition corresponds to arrow 1 in Fig- ure 16.5a and b. • Switching the simulation context from the discrete to the continuous domain (action expressed by flag: = 0). All the other rules presented in this table follow the same format [13]. TABLE 16.3 Operational Semantics for the CSI Nr. Rule synch = 1 ∧ flag = 1 ∧ qk = δext ((xck , tck ), 0, x) 1. ?(data,tdk+1 );synch:=0 !(DataToCont,ta (xdk ,tdk )) (xck , ∞) − − − − − − − (xck , tck ) − − − − − − − → (xck , tck ) − − − − − −→ −−−−−−− synch = 0 ∧ flag = 0 ∧ ¬stateevent ∧ qk+1 = δint ((xck , tck )) 2. ?(DataFromCont) !(data);flag:=1 (xck , tck ) − − − − − → (xck , tck ) − − − − → (q, td, k+1 ) −−−−− −−−− synch = 0 ∧ flag = 0 ∧ stateevent ∧ qk+1 = δint (qk ) 3. ?(DataFromCont) !(data,tse );flag:=1 (xck , tck ) − − − − − → (xck , tck ) − − − − − → (se, tse ) −−−−− −−−−−
552 Model-Based Design for Embedded Systems 16.7.2 Continuous Simulator Interface The operational semantics for the CSI is given by the set of rules presented in Table 16.3. In these rules, the Data notation refers to the data exchanged between the DSI and the discrete simulator. All the rules presented in Table 16.3 can be explained analogously to the one already illustrated in Section 16.7.1. 16.8 Implementation Stage: CODIS a C/D Co-Simulation Framework In Section 16.4, we proposed a generic methodology, in two stages, for the efficient design of C/D co-simulation tools. These stages are: a generic stage and an implementation stage. The generic stage, divided in four steps, was presented in detail and applied in Sections 16.4.1 through 16.4.4 and Sections 16.6.3 through 16.6.6. This section presents, CODIS [5], a tool for the generation of simula- tion models in more detail. This tool can automatically produce the global simulation model instances for C/D systems simulation using SystemC and Simulink simulators. This is done by generating and providing the interfaces that implement the simulation model layers and building the co-simulation bus. In the development of this framework, the generic steps of the method- ology that we presented in detail in this chapter are “hidden” in different stages of the simulation flow. The “definition of the library elements and the internal architecture of the co-simulation interfaces” step represents the foundation for the generation of the co-simulation library and implicitly for the generation of the co-simulation interfaces. The internal architecture of the interfaces respects the definition of the operational semantics, the distri- bution of the synchronization functionality, as well as the synchronization model. Figure 16.14 gives an overview of the flow of the instance generation in the case of CODIS. The inputs in the flow are the continuous model in Simulink and the discrete model in SystemC which are schematic and textual models, respectively. The output of the flow is the global simulation model (co-simulation model) instance. For Simulink, the interfaces can be parameterized starting with their dia- log box. The user starts by dragging the interfaces from the interface compo- nents library into the model’s window, then parameterizes them, and finally connects them to the inputs and the outputs of the model. Before the sim- ulation, the functionalities of these blocks are loaded by Simulink from the .dll libraries. The parameters of the interfaces are the number of input and output ports, their type, and the number of state events.
Generic Methodology for the Design 553 User parameters SystemC model Simulink model Interface components Generation Automatic interface Parametrized script generation interfaces Modified SystemC .lib Simulation library Link .dll Simulation library .lib SystemC model Simulink model Simulation Simulation interface interface Co-simulation bus FIGURE 16.14 Automatic generation of global simulation model instances. (From Gheorghe, L. et al., Formal definition of simulation interfaces in a continuous/discrete co-simulation tool, Proceedings of the 17th IEEE Inter- national Workshop on RSP, Chania, Crete, Greece, pp. 186–192, 2006. With permission.) For SystemC, the interface parameters are: the names, the number and the data type of the discrete model inputs ports and the sampling periods. The interfaces are automatically generated by a script generator that has as input the user-defined parameters. The tool also generates the function sc_main (or modifies the existing sc_main) that connects the interfaces to the user model. The model is compiled and the link editor calls the library from SystemC and a static library (the simulation library in Figure 16.14). 16.9 Conclusion This chapter presented a generic methodology for the design of efficient continuous/discrete co-simulation tools. The methodology can be divided
554 Model-Based Design for Embedded Systems into two main stages: (1) a generic stage, defining simulation interface functionality in a conceptual framework when formal methods for the specification and validation are used, and (2) a stage that provides the imple- mentation for the rigorously defined functionality. Given the importance of the co-simulation interfaces, the methodology concentrates on the co- simulation interfaces, their behavior, as well as the synchronization they assure in the global validation of a C/D heterogeneous system. We also present here a formal representation of the functionality of each interface independent of the other. We illustrate the methodology with CODIS, a tool for C/D systems co- simulation. In the development of CODIS, all the steps of the methodology we proposed in this paper are “hidden” in different stages of the simula- tion flow. The “definition of the library elements and the internal architec- ture of the co-simulation interfaces” step represents the foundation for the generation of the co-simulation library and implicitly for the co-simulation interfaces generation. The definition of the operational semantics and the dis- tribution of the synchronization functionality as well as their behavior play an important role at the output flow with the behavior of the co-simulation interfaces and the synchronization model. The “analysis of the simulation tools for the integration in the co-simulation framework” helped choosing the tools that were used for the modeling of the continuous and the discrete simulators while the “implementation of the library elements specific to dif- ferent simulation tools” constitutes the final implementation of the libraries. References 1. R. Alur and D. Dill, Automata for modeling real-time systems, in Proceed- ings of the Seventeenth International Colloquium on Automata, Languages and Programming, Warwick University, England, 1990, Vol. 443, pp. 322–335. 2. G. Behrmann, A. David, and K. Larsen, A tutorial on UPPAAL, Real-Time Systems Symposium, Miami, FL, 2005. 3. J. Bengtsson and W. Yi, Timed automata: Semantics, algorithms and tools, Uppsala University, Uppsala, Denmark, 1996. 4. J.-S. Bolduc and H. Vangheluwe, The modelling and simulation pack- age PythonDEVS for classical hierarchical DEVS. MSDL technical report MSDL-TR-2001-01, McGill University, Montreal, Quebec, Canada, June 2001. 5. F. Bouchhima, G. Nicolescu, M. Aboulhamid, and M. Abid, Generic discrete–continuous simulation model for accurate validation in hetero- geneous systems design, Microelectronics Journal, 38, 2007, 805–815.
Generic Methodology for the Design 555 6. C. G. Cassandras, Discrete Event Systems: Modeling and Performance Anal- ysis, Richard Irwin, New York, 1993. 7. F. E. Cellier, Combined continuous/discrete system simulation languages—usefulness, experiences and future development, Methodol- ogy in Systems Modelling and Simulation. North-Holland, Amsterdam, the Netherlands, 1979, pp. 201–220. 8. M. D’Abreu and G. Wainer, M/CD++: Modeling continuous systems using Modelica and DEVS, in Proceedings of the IEEE International Sym- posium of MASCOTS’05, Atlanta, GA, 2005, pp. 229–238. 9. S. Edwards, L. Lavagno, E. Lee, and A. L. Sangiovanni-Vincentelli, Design of embedded systems: Formal models, validation, and synthesis, Proceedings of the IEEE, 85, 1997, 366–390. 10. P. Frey and D. O’Riordan, Verilog-AMS: Mixed-signal simulation and cross domain connect modules, in Proceedings BMAS International Work- shop, Orlando, FL, 2000, pp. 103–108. 11. H. R. Ghasemi and Z. Navabi, An effective VHDL-AMS simulation algo- rithm with event, in International Conference on VLSI Design, Kolkata, India, 2005, pp. 762–767. 12. L. Gheorghe, F. Bouchhima, G. Nicolescu, and H. Boucheneb, For- mal definition of simulation interfaces in a continuous/discrete co- simulation tool, in Proceedings of the 17th IEEE International Workshop on RSP, Chania, Crete, Greece, 2006, pp. 186–192. 13. L. Gheorghe, F. Bouchhima, G. Nicolescu, and H. Boucheneb, Semantics for model-based validation of continuous/discrete systems, in Proceed- ings of the DATE, Munich, Germany, 2008, pp. 498–503. 14. N. Giambiasi, J.-L. Paillet, and F. Chane, From timed automata to DEVS, in Proceedings of the 2003 Winter Simulation Conference, New Orleans, LA, 2003. 15. IEEE Standard VHDL Analog and Mixed-Signal Extensions (1999), IEEE Std 1076.1-1999 16. International Technology Roadmap for Semiconductor Design. [Online]. Available at: http://public.itrs.net/ 17. A. Jantsch and I. Sander, Models of computation and languages for embedded system design, IEE Proceedings Computers and Digital Tech- niques, 152, 2005,114–129.
556 Model-Based Design for Embedded Systems 18. A. Jantsch, Modeling Embedded Systems and SoCs—Concurrency and Time in Models of Computation. Systems on Silicon. Morgan Kaufmann Publishers, San Francisco, CA, June 2003. 19. T. G. Kim, DEVSim++ User’s Manual, SMSLab, Dept. of EECS, KAIST, Taejon, Korea, 1994, http://smslab.kaist.ac.kr 20. Y. J. Kim, J. H. Kim, and T. G. Kim, Heterogeneous simulation framework using DEVS-BUS, in Simulation, the Society for Modeling and Simulation International, 79, 2003, 3–18. 21. E. A. Lee and H. Zheng, Operational semantics of hybrid systems, in Hybrid Systems: Computation and Control: 8th International Workshop, HSCC, Zurich, Switzerland, 2005, pp. 25–53. 22. E. A. Lee and A. L. Sangiovanni-Vincentelli, Comparing models of com- putation, in IEEE Proceedings of the International Conference on Computer- Aided Design (ICCAD), San Jose, CA, 1996, pp. 234–241. 23. S. Levitan, J. Martinez, T. Kurzveg, P. Marchand, and D. Chiarulli, Multi technology system-level simulation, Analog Integrated Circuits and Signal Processing, 29, 2001, 127–149. 24. MATLAB-Simulink [Online]. Available at: www.mathworks.com 25. J.-F. Monin, Understanding Formal Methods, Springer, Berlin, 2003. 26. G. Nicolescu et al., Validation in a component-based design flow for mul- ticore SoCs, in Proceedings of ISSS, Kyoto, Japan, 2002, pp. 162–167. 27. D. H. Patel and S. K. Shukla, SystemC Kernel—Extensions for Heterogeneous System Modeling, Kluwer Academic Publishers, Dordrecht, the Nether- lands, 2004. 28. Ptolemy project [Online]. Available at: http://ptolemy.eecs.berkeley. edu/ 29. S. Romitti, C. Santoni, and P. François, A design methodology and a pro- totyping tool dedicated to adaptive interface generation, in Proceedings of the 3rd ERCIM Workshop on “User Interfaces for All”, Obernai, France, 1997. 30. SystemC LRM [Online]. Available at: www.systemc.org 31. SystemVerilog [Online]. Available at: www.systemverilog.org 32. A. Vachoux, C. Grimm, and K. Einwich, Analog and mixed signal model- ing with SystemC-AMS, in Proceedings International on Symposium Circuits System, Bangkok, Thailand, 2003, pp. 914–917.
Generic Methodology for the Design 557 33. VHDL [Online]. Available at: www.vhdl.org 34. B. P. Zeigler, H. Praehofer, and T. G. Kim, Modeling and Simulation— Integrating Discrete Event and Continuous Complex Dynamic Systems, Aca- demic Press, San Diego, CA, 2000. 35. G. Wainer, Modeling and simulation of complex systems with cell-DEVS, in Winter Simulation Conference, Washington, DC, 2004, pp. 49–60. 36. F. Wang, Formal verification of times systems: A survey and perspective, Proceedings of the IEEE, 92, 2004, 1283–1305.
17 Modeling and Simulation of Mixed Continuous and Discrete Systems Edward A. Lee and Haiyang Zheng CONTENTS 17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559 17.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560 17.3 Actor-Oriented Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561 17.4 Actor Abstract Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563 17.5 Synchronous/Reactive Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566 17.6 Discrete-Event Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568 17.7 Continuous-Time Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573 17.8 Software Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 17.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579 17.1 Introduction An embedded system mixes digital controllers realized in hardware and soft- ware with the continuous dynamics of physical systems [30]. Such systems are semantically heterogeneous, combining continuous dynamics, periodic timed actions, and asynchronous event reactions. Modeling and design of such heterogeneous systems is challenging. A number of researchers have defined concurrent models of computation (MoCs) that support modeling, specification, and design of such systems [11,22,26,28,34]. A variety of approaches have been tried for dealing with the intrin- sic heterogeneity of embedded systems. This chapter describes a particu- larly useful combination of semantics, providing a disciplined and rigorous mixture of synchronous/reactive (SR) systems [4], discrete-event (DE) sys- tems [13,19,29,49], and continuous-time (CT) dynamics [20,35,42,46]. Our approach embraces heterogeneity, in that subsystems can be modeled using any of the three semantics, and these subsystem models can be combined hierarchically to form a whole system. We leverage the idea of an actor abstract semantics [33] to provide a coherent and rigorous meaning for 559
560 Model-Based Design for Embedded Systems the heterogeneous system. Our approach also provides improvements to conventional DE and CT semantics by leveraging the principles of SR lan- guages. These improvements facilitate the heterogeneous combination of the three distinct modeling styles. 17.2 Related Work A number of authors advocate heterogeneous combinations of semantics. Ptolemy Classic [11] introduced the concept, showing useful combinations of asynchronous models based on variants of dataflow and timed DE mod- els. The concept was picked up for hardware design in SystemC (version 2.0 and higher) [45], on which some researchers have specifically built heterogeneous design frameworks [26]. Metropolis [22] introduced com- munication refinement as a mechanism for specializing a general MoC in domain-specific ways, and also introduced quantity managers that provide a unified approach to resource management in heterogeneous systems. Our approach in this chapter is closest in spirit to SML-Sys [41], which builds on Standard ML to provide for mixtures of MoCs. SML-Sys combines asynchronous models (dataflow models) with synchronous models (which the authors call “timed”). Our approach, in contrast, combines only timed models, including both DE and CT dynamics. A particular form of heterogeneous systems, hybrid systems provide for joint modeling of continuous and discrete dynamics. A few software tools have been built to provide simulation of hybrid systems, including Charon [2], Hysdel [47], HyVisual [10], ModelicaTM [46], Scicos [16], Shift [15], and Simulink R /StateflowTM (from The MathWorks). An excellent analysis and comparison of these tools is given by Carloni et al. [12]. We have previ- ously extensively studied the semantics of hybrid systems as heterogenous combinations of finite state machines (FSM) and continuous dynamics [35]. Our approach in this chapter extends this to include SR and DE models. We focus here on the interactions between SR, DE, and CT, because the interactions betweenFSMandSR,DE,andCThavealreadybeenextensivelystudied[21,35]. Several authors advocate unified MoCs as a binding agent for hetero- geneous models [3,9,23]. Heterogeneous designs are expressed in terms of a common semantics. Some software systems, such as Simulink from The MathWorks, take the approach of supporting a general MoC (CT systems in the case of Simulink) within which more specialized behaviors (like peri- odic discrete-time) can be simulated. The specialized behaviors amount to a design style or design pattern within a single unified semantics. Con- formance to design styles within this unified semantics can result in mod- els from which effective embedded software can be synthesized, using, for example, Real-Time WorkshopTM or TargetLinkTM from dSpace.
Mixed Continuous and Discrete Systems 561 Our approach in this chapter is different in that the binding agent is an abstract semantics. By itself, it is not sufficiently complete to specify system designs. Its role is exclusively as a binding agent between diverse concrete MoCs, each of which is expressive enough to define system behavior (each in a different way). We are heavily inspired here by the fixed-point semantics of synchronous languages [4], particularly Lustre [25], Esterel [8], and Signal [24]. SCADE [7] (Safety Critical Application Development Environment), a commercial prod- uct of Esterel Technologies, builds on the synchronous language, Lustre [25], providing a graphical programming framework with Lustre semantics. All the synchronous languages have strong formal properties that yield quite effectively to formal verification techniques. Our approach, however, is to use the principles of synchronous languages in the style of a coordination language rather than a programming language. This coordination language approach has been realized in Ptolemy [17] and ForSyDe [44]. It allows for “primitives” in a model to be complex components rather than built-in lan- guage primitives. This approach will allow for heterogeneous combinations of MoCs, since the complex components may themselves be given as compo- sitions of further subcomponents under some other MoCs. A number of researchers have combined synchronous languages with asynchronous interactions using a principle called globally asynchronous, locally synchronous or GALS (see for example [5]). In our case, all the MoCs we consider are timed, so there is a measure of synchrony through- out. Instead, we focus on combinations of heterogeneous timing properties, including abstracted discrete sequences (SR), time-stamped events (DE), and continuous-time dynamics (CT). 17.3 Actor-Oriented Models Our approach here closely follows the principles of actor-oriented design [33], a component methodology where components called actors execute and communicate with other actors in a model, as illustrated in Figure 17.1. Fig- ure 17.1 shows an actor with a single output port that produces a sequence of data values that constitute a sine wave. Internally, the actor is realized as a network of actors. It has three parameters, frequency, phase, and samplingFre- quency, with default values shown. Actors have a well-defined component interface. This interface abstracts the internal state and behavior of an actor, and restricts how an actor interacts with its environment. The interface includes ports that represent points of communication for an actor, and parameters that are used to con- figure the operation of an actor. Often, parameter values are part of the a priori configuration of an actor and do not change when a model is
562 Model-Based Design for Embedded Systems SR director Frequency : 440 Phase : 0.0 Sampling frequency : 8000 Ramp External port AddSubtract TrigFunction + Output Const. Sin – Phase Port Actor Composite actor Sine wave Hierarchical abstraction FIGURE 17.1 Illustration of a composite actor (above) and its hierarchical abstraction (below). executed. The configuration of a model also contains explicit communica- tion channels that pass data from one port to another. The use of channels to mediate communication implies that actors interact only with the channels that they are connected to and not directly with other actors. Like actors, which have a well-defined external interface, a composition of actors may also define an external interface, which we call its hierarchi- cal abstraction. This interface consists of external ports and external parameters, which are distinct from the ports and parameters of the individual actors in the composite. The external ports of a composite can be connected (on the inside) by channels to other external ports of the composite or to the ports of actors within the composite. External parameters of a composite can be used to determine the values of the parameters of actors inside the compos- ite. Actors that are not composite actors are called atomic actors. We assume that the behavior of atomic actors is given in a host language (in Ptolemy II, Java, or C). Taken together, the concepts of actors, ports, parameters, and channels describe the abstract syntax of actor-oriented design. This syntax can be rep- resented concretely in several ways, such as graphically, as in Figure 17.1, in XML [32], or in a program designed to a specific API (as in SystemC). Ptolemy II [18] offers all three alternatives. In some systems, such as SML- Sys, the syntax of the host language specifies the interconnection of actors. It is important to realize that the syntactic structure of an actor-oriented design says little about the semantics. The semantics is largely orthogonal to the syntax, and is determined by an MoC. The model of computation might give operational rules for executing a model. These rules determine when actors perform internal computation, update their internal state, and perform
Mixed Continuous and Discrete Systems 563 external communication. The model of computation also defines the nature of communication between components (buffered, rendezvous, etc.). Our notion of actor-oriented modeling is related to the term actor as introduced in the 1970s by Carl Hewitt of MIT to describe the concept of autonomous reasoning agents [27]. The term evolved through the work of Agha and others to describe a formalized model of concurrency [1]. Agha’s actors each have an independent thread of control and communi- cate via asynchronous message passing. We are further developing the term to embrace a larger family of models of concurrency that are often more con- strained than general message passing. Our actors are still conceptually con- current, but unlike Agha’s actors, they need not have their own thread of control. Moreover, although communication is still through some form of message passing, it need not be strictly asynchronous. In this chapter, we will consider three MoCs, namely, SR, DE, and CT. We carefully define the semantics of DE and CT so that the three MoCs are related in an interesting way. Specifically, SR is a special case of DE, and DE is a special case of CT. This does not mean that we should automatically use the most general MoC, CT, because execution efficiency, modeling convenience, and synthesizability all may be compromised. In fact, there are good reasons to use all three MoCs. Most interestingly, we will show that these three MoCs can be combined hierarchically in arbitrary order. That is, in a hierarchical model like that in Figure 17.1, the higher level of the hierarchy and the lower level need not use the same MoC. In fact, all combinations of SR, DE, and CT are supported by our framework. We describe a prototype of this framework constructed in Ptolemy II. 17.4 Actor Abstract Semantics In order to preserve the specialization of MoC while also building general models overall, we concentrate on the hierarchical composition of heteroge- nous MoC. The composition of arbitrary MoC is made tractable by an abstract semantics, which abstracts how communication and flow of control work. The abstract semantics is (loosely speaking) not the union of interesting seman- tics, but rather the intersection. It is abstract in the sense that it represents the common features of MoC as opposed to their collection of features. A familiar example of an abstract semantics is represented by the Simulink S-function interface. Although not formally described as such, it in fact functions as such. In fact, simulink works with stateflow to accomplish a limited form of hierarchical heterogeneity through this S-function interface. We will describe an abstract semantics that is similar to that of Simulink, but
564 Model-Based Design for Embedded Systems simpler. It is the one realized in the Ptolemy II framework for actor-oriented design. In Ptolemy II models, a director realizes the model of computation. A director is placed in a model by the model builder to indicate the model of computation for the model. For example, an SR director is shown visually as the uppermost icon in Figure 17.1. The director manages the execution of the model, defining the flow of control, and also defines the communication semantics. When a director is placed in a composite actor, as in Figure 17.1, the com- posite actor becomes an opaque composite actor. To the outside environ- ment, it appears to be an atomic actor. But inside, it is a composite, executing under the semantics defined by the local director. Obviously, there has to be some coordination between the execution on the outside and the execution on the inside. That coordination is defined by the abstract semantics. The flow of control and communication semantics are abstracted in Ptolemy II by the executable and receiver interfaces, respectively. These inter- faces define a suite of methods, the semantics of which are the actor abstract semantics of Ptolemy II. A receiver is supplied for each channel in a model by the director; this ensures that the communication semantics and flow of control work in concert to implement the model of computation. In the Ptolemy II abstract semantics, actors execute in three phases, setup, a sequence of iterations, and wrapup. An iteration is a sequence of operations that read input data, produce output data, and update the state, but in a particular, structured way. The operations of an iteration consist of one or more invocations of the following pseudocode: if (prefire()) { fire(); } If fire is invoked at least once in the iteration, then the iteration concludes with exactly one invocation of postfire. These operations and their significance constitute the executable inter- face and are summarized in Figure 17.2. The first part of an itera- tion is the invocation of prefire, which tests preconditions for firing. The actor thus determines whether its conditions for firing are satisfied. If it setup Initialize the actor. preﬁre Test preconditions for ﬁring. ﬁre Read inputs and produce outputs. postﬁre Update the state. wrapup End execution of the actor. FIGURE 17.2 The key flow of control operations in the Ptolemy II abstract semantics. These are methods of the executable interface.
Mixed Continuous and Discrete Systems 565 indicates that they are (by a return value of true), then the iteration proceeds by invoking fire. This may be repeated an arbitrary number of times. The con- tract with the actor is that prefire and fire do not change the state of the actor. Hence, multiple invocations with the same input values in a given iteration will produce the same results. This contract is essential to guarantee conver- gence to a fixed point. If prefire indicates that preconditions are satisfied, then most actors guar- antee that invocations of fire and postfire will complete in a finite amount of time. Such actors are said to realize a precise reaction [37]. A director that tests these preconditions prior to invoking the actor, and fires the actor only if the preconditions are satisfied, is said to realize a responsible framework [37]. Responsible frameworks coupled with precise reactions are key to hierarchi- cal heterogeneity. The abstract semantics also provides the set of primitive communication operations as shown in Figure 17.3. These operations allow an actor to query the state of communication channels, and subsequently retrieve information from the channels or send information to the channels. These operations are invoked in prefire and fire. Actors are also permitted to read inputs in postfire, but they are not permitted to produce outputs (by invoking put). Violations of this contract can lead to nondeterminism. These operations are abstract, in the sense that the mechanics of the com- munication channel is not defined. It is determined by the model of compu- tation. A domain-polymorphic actor is not concerned with how these oper- ations are implemented. The actor is designed assuming only the abstract semantics, not the specific realization. A hierarchically heterogeneous model is supported by this abstract seman- tics as follows. Figure 17.1 shows an opaque composite actor. It is opaque because it contains a director. That director gives the composite a behavior like that of an atomic actor viewed from the outside. A director implements the executable interface, and thus provides the operations of Figure 17.2. Suppose that in Figure 17.1 the hierarchical abstraction of the sine wave component is used in a model of computation different from SR. Then from the outside, this model will appear to be a domain-polymorphic actor. When its prefire method is invoked, for example, the inside director must deter- mine whether the preconditions are satisfied for the model to execute (in the SR case, they always are), and return true or false accordingly. When fire is get Retrieve a data token via the port. put Produce a data token via the port. hasToken(k) Test whether get will succeed k times. hasRoom(k) Test whether put will succeed k times. FIGURE 17.3 Communication operations in Ptolemy II. These are methods of the receiver interface.