DEMES SimulMag2011 v4
DEMES SimulMag2011 v4
DEMES SimulMag2011 v4
1 2
Gabriel Wainer SMSCS Rodrigo Castro MSCS
1 2
Department of Systems and Computer Engineering Computer Science Department
VSim Centre. Carleton University. Ottawa, ON. Universidad de Buenos Aires and CIFASIS-
K1S 5B6. Canada. CONICET (Rosario, Santa Fe). Argentina.
http://www.sce.carleton.ca/faculty/wainer
In the last thirty years, the Software Engi- deals with these issues by using a model-based.
neering community has spent a tremendous ef- The approach combines the advantages of M&S
fort in creating formal methods and tools for de- with the rigor of a formal methodology based on
veloping embedded systems, in particular, those DEVS (Discrete Event systems Specification)
with real-time constraints. Despite these efforts, formalism [1]; it supports rapid prototyping and
most existing methods are still hard to scale up, encourages reuse. DEVS is a well-defined for-
and they require expensive testing efforts with malism that is expressive, operates at a high lev-
no guarantees for bug-free products. Instead, el of specification, and it can be used to
systems engineers have often relied on modeling represent both computing systems and the physi-
and simulation (M&S) techniques to improve the cal systems they control. DEVS models have a
development task and obtain higher quality rich structural representation of components, and
products. M&S-based testing is widely used for formal means for explicitly specifying their tim-
the early stages of a project; however, when the ing, which is central for real-time systems.
development tasks switch towards the target en- DEMES enables the incremental construc-
vironment, early models are often abandoned. In tion of such embedded applications using a dis-
order to deal with these issues, we introduce crete-event architecture for both simulation and
DEMES (Discrete-Event Modeling of Embed- the target product architecture. The use of DEVS
ded Systems) an M&S-based development me- for DEMES offers the following advantages:
thodology based on discrete-event systems spe- - Reliability: logical and timing correctness rely
cifications. DEMES combines the advantages of on DEVS system theoretical roots and sound
a practical approach with the rigor of a formal mathematical theory.
method, in which one consistently use models - Model reuse: DEVS has well-defined concepts
throughout the development cycle. for coupling of components and hierarchical,
modular model composition.
Introduction to DEMES
- Hybrid modeling and knowledge reuse: it
Formal methods for embedded systems de- has been proven that DEVS is the most general
velopment use mathematical notations to define discrete event formalism (i.e., every other me-
the system’s requirements, allowing proving sys- thod can be expressed as DEVS), and many
tem properties (liveness, timeliness, etc.). These techniques used for embedded systems have
techniques have had success, but they are still been mapped into DEVS (e.g., Verilog, VHDL,
difficult to apply and do not scale up well. In- Timed Automata, State Charts, etc.). Hence, we
stead, construction of system models and their can use different methods while keeping inde-
analysis through simulation (M&S) reduces cost pendence at the level of the executive, using the
and risk, allowing exploring changes and testing most adequate technique on each part of system
of dynamic conditions in a risk-free environ- architecture and reusing existing expertise.
ment. This is a useful approach, moreover con- - Process flexibility: these hybrid modeling ca-
sidering that testing under actual operating con- pabilities are transparent for the executive,
ditions may be impractical and in some cases which is defined by an abstract mechanism that
impossible. Despite the net gains, most project is independent from the model itself. Existing
managers are reluctant to use M&S because they DEVS tools have showed their ability to execute
require extra initial resources for models that such variety of models with high performance.
will not be part of the final application. DEMES
- Testing: defining experimental frames (i.e., the ronment after thorough testing in the simulated
set of conditions under which the system is ob- platform, allowing reusing of models throughout
served or experimented with) can be automated. the process. The approach does not impose any
DEMES uses M&S for the initial stages, order in the deployment in the actual hardware
and replaces models incrementally with hard- platform, providing flexibility to the overall
ware surrogates without modifying the original process. Figure 1 shows the architecture of the
models. The transition can be done in incremen- process used in DEMES.
tal steps, incorporating models in the target envi-
Initially (1), we define a specification mod- software and hardware models can be refined,
el of the System of Interest (SoI) using a formal progressively setting checkpoints in real proto-
model (using DEVS or alternative techniques types. The executive allows to execute dynamic
translated to equivalent DEVS models). Once models and to schedule static and dynamic tasks.
the DEVS specification model is complete, At this point, those parts that are still unve-
model-checking can be used for validation of the rified in the formal and simulated environments
model properties (2). The same models are then are tested, increasing the confidence of the engi-
used to run DEVS simulations of the behavior of neer into the implemented system (7). Any mod-
the different submodels under specific loads (3). ifications require going back to the same model
In brief, we first study system properties analyti- specifications (8), which ensure that we can pro-
cally, and complement the proofs using simula- vide a consistent set throughout the develop-
tion, which can also be used for hard- ment. This software lifecycle is cyclic, allowing
ware/software codesign (and for training). refinement following a spiral approach. On each
The same DEVS specification model is cycle of the spiral, we end with a prototype ap-
used to derive test cases (4), which can be also plication consisting of software/hardware com-
used for the simulation studies. Deriving test ponents interacting with simulated components.
cases from both the model (4) and from the si-
Other Model-Based approaches
mulation results (5) allows us to check that the
models conform to the requirements. Once we Different techniques have been proposed to
are satisfied with both analytical and simulated deal with the issues discussed earlier. For in-
results, the models are incrementally moved into stance, BIP [2] defines components as the super-
a target platform. A real-time Executive (6) ex- position of three layers: Behavior (a set of transi-
ecutes the models on the particular hardware (9). tions); Interactions (between transitions) and
If the hardware is not readily available, the soft- Priorities (to choose amongst interactions). BIP
ware components can still be developed incre- preserves properties during model composition
mentally and tested against a model of the hard- and supports analysis and transformations across
ware to verify viability and take early design de- heterogeneous boundaries (untimed/timed, asyn-
cisions. As the design process evolves, both chronous/synchronous, event /data-triggered).
Ptolemy II [3] is a structured and hierar- cur before ta(s), the model activates the output
chical method for modeling heterogeneous sys- function λ (outputs Y) and moves to a new state
tems using specific MoC that covers the flow of determined by the internal transition function
data and control. ECSL (Embedded Control Sys- δint. A DEVS coupled model is:
tems Language) supports the development of CM = < X, Y, D, {Mi}, {Zij}, select >
distributed controllers [4], including a domain- CM represents a set of basic components
specific environment for automotive systems Mi (i∈D) interconnected through their interfaces
(extending the Matlab family with capabilities (X, Y). The translation function Zij converts the
for specification, verification, scheduling, per- outputs of a model into inputs for others, and the
formance analysis, etc.). select function is used for tie-breaking. The clo-
SystemC and Esterel are system-level lan- sure under coupling (i.e., a coupled model has an
guages used to simulate and execute models, atomic equivalent) enables model reuse.
which have widespread industry adoption [5]. In the last few years, DEVS has been used
SystemC represents hardware/software systems for modeling applications with real-time con-
at different abstraction levels, allowing choosing straints. RT-DEVS [7] introduced a DEVS-
the desired level of detail for each component. based framework for the transformation from the
Esterel is used for hardware/software synthesis system design to the implementation of embed-
through a synchronous reaction-based language ded systems. In [8] the authors present a formal
and higher-level statements for concurrency. mapping of DEVS models into timed Communi-
One of the most popular techniques, UML- cating Sequential Process (tCSP) for hard-
RT, provides an object-oriented methodology. A ware/software codesign. DEVS/DOC [9], a co-
comparison between DEVS and UML-RT [6] design methodology, was used to predict archi-
shows that, although available in the UML-RT tectural decisions that could lead to incorrect
Profile, time, scheduling and performance are system behavior, introducing a modeling layer
coded using UML constructions (i.e., not for- on top of fine grained DEVS modeling con-
mally defined). Instead, DEVS provides sound structs. In [10] DEVS was implemented on a
syntax/semantics for structure, behaviour, time TINI Chip using a just-as-needed real time envi-
representation and composition, which lend ronment to run on the chip efficiently. A co-
themselves to well-defined computation. DEVS, development methodology defined in [11] facili-
however, is not intended for software design and tated the repetitive testing of on-going system
development, and "it is key to support the trans- specifications. PowerDEVS, which supports
formation of simulation models to their software continuous and hybrid systems with quantized
model counterparts and their complementary state numerical methods was extended with real-
roles in handling modeling and computational time support.
complexity of embedded systems". DEMES
software development environment focuses on E-CD++: an environment for DEMES
complementing these shortcomings. CD++ [12] provides a mechanism to build
Modeling with DEVS DEVS models (which can be implemented in
C++ or using a built-in language) using DEVS
A real system modeled with DEVS [1] is formal specifications. The ButtonInputModule
described as a hierarchical and modular compo- model shows parts of the transition functions for
site of models that can be behavioral (atomic) or a component of a cruise control system (CCS).
structural (coupled). A DEVS atomic model is:
AM = < X, S, Y, δint, δext, λ, ta > ButtonInputModule::ButtonInputModule ( const
Every state s ∈ S is associated with a life-
string &name ) : Atomic( name ),
in_BUTTON( addInputPort("in_BUTTON") ),
time, defined by the time advance function ta(s). out_ON( addOutputPort("out_ON") ),
When a model receives an input event X, the ex- out_RESUME( addOutputPort("out_RESUME"))
{reactionTime = VTime( 0, 0, 0, 15 );}
ternal transition function δext is triggered. This
function uses the input event, the current state Model &ButtonInputModule::externalFunction (
const ExternalMessage &msg ) {
and the time elapsed since the last event to de- if( msg.port() == in_BUTTON ) {
termine the next model’s state. If no events oc- inType=(int)msg.value();
holdIn( active, reactionTime );}}
Model &ButtonInputModule::outputFunction (
const InternalMessage &msg ) {
switch(inType) {
case ON: //take action {
sendOutput( msg.time(), out_ON, HIGH); }
case OFF: //take action {
sendOutput( msg.time(), out_OFF, HIGH);
...} ... } }
Model &ButtonInputModule::internalFunction (
const InternalMessage & ) {passivate();}