Tải bản đầy đủ (.pdf) (10 trang)

Model-Based Design for Embedded Systems- P50 doc

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (492.43 KB, 10 trang )

Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 466 2009-10-2
466 Model-Based Design for Embedded Systems
semantic anchoring is defined by model transformation rules expressed in
the UMT (Unified Model Transformation) language of the GReAT tool suite
[26]. In UMT, model transformations are expressed as graph transformations
that can be executed (in interpreted and/or compiled form) by the GReAT
tool. In summary, semantic anchoring specifies DSML behavioral semantics
by the operational semantics of selected semantic units (defined in ASML)
and by the transformation rules (defined in UMT). The integrated tool suite
enables the simulation of domain models defined in a DSML according to
their “reference semantics” by automatically translating them into ASML
data models using the transformation rules.
In the rest of this section, we show the process of semantic anchoring
using a simple example. Readers can refer for detailed discussion about the
use of the semantic anchoring tool suite in specifying a TASU in [9], and for
specifying semantics for a complex DSML by composing several semantic
units in [11].
14.4.2 Semantic Anchoring Example: Timed Automata
Timed Automata [2,3] model the behavior of real-time systems over the pro-
gression of time. This formalism extends the definition of state-based transi-
tion systems to include a finite set of real-valued clocks that synchronously
progress time. The enabling of transitions is further restricted using con-
straints over the clock valuations, and transitions can specify a set of clocks
to reset to zero upon firing.
Timed automata have previously been defined within the semantic
anchoring framework [9]; however, the semantic unit included many fea-
tures to provide semantic equivalences to other versions of timed automata
modeling languages (e.g., UPPAAL [4] and IF [37]). The proposed TASU
specified here is intended to be simple while capturing all the basic facili-
ties of the original timed automata model. In the AsmL semantic definition,
the structures mimic the abstract constructs of the behavioral formalism. The


first two sections provide the Abstract Data Model (ADM) and operational
semantics that govern a single automaton. The ADM describes the data struc-
tures of the semantic unit, and the operational semantics provide a model
interpretation over an instance of the ADM, the data model. The succeed-
ing sections will explain how automata are composed to form more com-
plex systems and then define the modeling language of the semantic unit, L
s
,
required for semantic anchoring.
14.4.2.1 Timed Automata Overview
Structurally, a timed automaton is a mathematical 5-tuple < L, l
0
, C,E, Pr
e
>
with an event alphabet Σ:
1. L is a finite set of locations.
2. l
0
is an initial location, l
0
∈ L.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 467 2009-10-2
Semantics of Domain-Specific Modeling Languages 467
3. C is a finite set of clock variables.
4. E ⊆ L × Σ × 2
C
× L is a set of edges. An edge < l, α, φ, λ, ω, l

> is a

transition from l to l

on a set of input events α ⊂ Σ and the satisfaction
of the guard φ(v) over the valuation function v of the clocks c ∈ C, v :
c → N. Upon the firing of a transition, the clocks λ ⊆ C are reset to 0,
and the set of output events ω ∈ Σ are generated.
5. Pr
e
: E×N
n
→ N is a map that assigns to each edge a nonnegative integer
priority with respect to a given clock evaluation v,sothatPr
e
(e, v) is the
priority of edge e at clock valuation v.
Transitions are assigned a priority to model the dynamics of many com-
mon real-time systems. This mechanism allows for dynamic priority assign-
ment throughout the execution of a model. Following the model of [9], the
progression of time is modeled as a transition; therefore, it too must be
assigned a priority, the lowest priority in the specification. This supports the
notion of urgent transitions; however, unlike [9], this semantic unit does not
provide mechanisms for blocking time or most urgent transitions (i.e., the
time transition is always enabled).
The semantics for a timed automaton fitting the structure above defines
the state of a timed automaton as a pair of (l, v) where l is a location in L and v
is a valuation of the clocks C. The possible state changes are enabled over the
union of location-switching transitions and the progression of time defined
respectively as
(l, v)
α

−→ (l

, v[λ := 0]) ⇔∃e =< l, α,φ, λ,ω, l

>∈ E
such that
φ(v) = true and
∀e

=< l, α, φ

, λ

, ω

, l

>∈ E ∧ φ(v) = true
⇒ Pr
e
(e, v)  Pr
e
(e

, v)
(14.46)
(l, v)
t
−→ (l


, v +ε) ⇒ Pr
e
(e, v +ε) = 0 (14.47)
In the following, we will use AsmL syntax in the specifications. The
advantage of this approach is that these specifications are directly executable
using the freely available AsmL tools [18] that can be used with the latest
Microsoft Visual Studio distributions.
14.4.2.2 Semantic Unit Abstract Data Model
In ASML, Events and Clocks (shown in Figure 14.12) are enumerated stores
for the defined events (∈ Σ) and clock variables (C) of the automaton. The
TimedAutomaton class captures the mathematical model described above for
the semantic unit. The id field, present in all following class definitions, pro-
vides a naming construct to identify objects, but it has no semantic implica-
tions. The initial field holds the initial location of the automaton, and it must
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 468 2009-10-2
468 Model-Based Design for Embedded Systems
1. enum Clocks
2. enum Events
3. class TimedAutomaton
4. const id as String
5. const locations as Set of Location
6. const initial as Location
7. const transitions as Set of Transition
8. const local_clocks as Set of Clockss
9. var v as Set of Clocks of Clocks to Integer ={−>}
10. var cur as (Location, Set of Events) = ( null, {})
FIGURE 14.12
Structures: Clocks, events, and timed automata.
be a predefined location of the system, member of the field locations,oran
error will occur. The transitions field holds the set of all defined transitions

between the locations of this automaton. The variable v is the valuation of
the clock variables in local_clocks. The valuation is a partial function specified
as a mapping from the clock domain, C, to the domain of natural numbers,
N. Natural numbers were chosen for discrete time steps for clarity. Domain
models from a DSML that uses variable discrete time steps can be scaled
as required, complicating the operational code. The variable field cur is a
2-tuple indicating the location and set of active events in the current execut-
ing step of the simulation.
Location and Transition are defined as first-class types (Figure 14.13). Loca-
tions contain only the unique identifier, id. Transition defines a move from a
location src to a location dst, given the appropriate input events, trigger, and
the satisfaction of the time guard condition, φ(v). The variable time_guard
is a partial function that maps clock valuations to a Boolean. The time guard
must be defined as a variable since the valuation of the clocks v(C) is variable
over the progression of time. Upon taking a transition, the event set outputs is
added to the set of currently active events. The resets field holds the clocks to
1. class Location
2. const id as String
4. class Transition
5. const id as String
6. const src as Location
7. const dst as Location
8. const trigger as Set of Events
9. const output as Set of Events
10. const resets as Set of Clocks
11. var time_guard as Map of (Map of Clocks to Integer) to Boolean
13. const time = new Transition(“time”, null, null, {}, {time_ev},
{}, {->})
FIGURE 14.13
Structures: Locations, transitions, and time.

Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 469 2009-10-2
Semantics of Domain-Specific Modeling Languages 469
be reset to zero upon taking the transition. According to the original model,
the progression of time is enabled in every state of a timed automaton; there-
fore, the time transition is defined as a constant. If the time transition is taken,
all clocks in the timed automaton will be incremented by some value  ∈ N
that must be defined for the model. Note that the time transition has an out-
put event, time_ev. This event must be included in the data model definition.
14.4.2.3 Operational Semantics
As is the case for all MIC semantic units, the operational semantics of the
timed automaton semantic unit are specified as a set of ASML rules that exe-
cute over models instantiated using the ADM data structures.
A global function InputEvents provides an interface to continue the execu-
tion of a model within the AsmL tools, that is, it provides a means to drive the
simulation. This method receives an input parameter set of TimedAutoma-
ton objects, and should return a set of Events to serve as input to the current
simulation step. It must be provided by the consumer of the semantic unit
(i.e., the simulation environment).
The InitializeTA method (shown in Figure 14.16) first initializes the cur
variable to the initial location and an empty active event set, and then sets
the valuation of all local clock variables to zero. The set of currently enabled
transitions returned by the EnabledTransitionsTA method is the time transition
added to the set of transitions that meet the enabling conditions: the source
location of the transition is the current location, the triggering events of the
transition are a subset or equal to the set of currently active input events,
et.trigger <= cur.Second,andtime_guard(v) evaluates to true.
The EvolveTA method (Figure 14.14) fires the transition passed to it, tr,
by updating the current configuration to be the destination location of the
transition and the generated output events of the transition and resets all
clocks specified in the resets field of tr to zero. The partial update to the map-

ping v also maintains the current valuations of all other clocks not in resets,
local_clocks -(local_clocks intersect resets). Even though the time transition is
always returned as an enabled transition, its effect it not yielded by pass-
ing it to the EvolveTA method. Instead, the TimeProgressTA method must be
invoked to increment all local clock valuations by the defined integer value 
1. class TimedAutomaton
2. EvolveTA(tr as Transition)
3. require tr in transitions
4. cur := (tr.dst, tr.output)
5. v := {clki − > 0 | clki in (tr.resets intersect local_clocks) }
6. union {clki − > v(clki) |
7. in local_clocks -(tr.resets intersect local_clocks) }
FIGURE 14.14
Execution: Stepping a timed automaton.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 470 2009-10-2
470 Model-Based Design for Embedded Systems
and must set the time_ev event as the only active event for the given automa-
ton. The UpdateEvents and GetEvents methods are self-explanatory. The Prior-
ityTA and UpdateTimeGaurdTA methods are not predefined functions as they
are model dependent. Each must be specified when simulating an instance
model of a DSML.
The PriorityTA method returns a nonnegative integer value for each tran-
sition in the system with the base priority being 0, that of the time transition.
Returning identical priorities for multiple transitions allows for nondeter-
minism in the data models.
The UpdateTimeGuardTA method reevaluates the guard condition of
every transition given the current valuation of the clocks. The time tran-
sition’s time guard is never included in this method since it is always an
enabled transition.
14.4.2.4 Composition of Timed Automata

The timed automaton semantic unit presented thus far describes the behav-
ioral semantics and data structures of a single automaton. To model larger,
more complex systems and behaviors, the semantic unit needs to be extended
to model concurrently executing automata. Here, we show the synchronous
parallel execution semantics for multiple automata and provide the appro-
priate metamodel for the TASU.
The modeling of concurrent automata was previously approached in
[9]; however, the resulting semantic unit appeared overly complex and
insufficiently expressive. These issues motivated this new specification that
is intended to be simpler and extensible to a wider variety of execution
semantics.
The set of globally scoped clocks, global_clocks, is a set of clocks that
all automata can read and possibly reset. Conversely, the set of clocks in
the TimedAutomaton class, local_clocks, is scoped exclusively to its respective
automaton. The variable g_v is the partial function that maps the global clock
variables to their valuations. Figure 14.15 contains the ASML structures for a
global system definition.
The class Comp_System (Figure 14.15) contains the set of concurrently exe-
cuting TimedAutomaton objects and a variable E. E represents the set of all
1. const global_clocks as Set of Clocks
2. var g_v as Map of Clocks to Integer = {clki − > 0 | clki in
global_clocks}
4. class Comp_System
5. const TA_components as Set of TimedAutomaton
6. var E as Set of Events = {}
FIGURE 14.15
Execution: ASML structures supporting concurrent composition of indepen-
dent timed automata.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 471 2009-10-2
Semantics of Domain-Specific Modeling Languages 471

1. class Comp_System
2. InitializeCS_TA()
3. forall c in TA_components
4. require {t} intersect {tr.resets | tr in c.transitions} = {}
5. require c.local_clocks intersect global_clocks = {}
6. require c.local_clocks intersect {h.local_clocks | hin
TA_components
7. where h <> c} = {}
8. c.InitializeTA()
10. UpdateEventsCS_TA()
11. let e = E union InputEvents(TA_components)
12. E := e
13. forall c in TA_components
14. c.UpdateEvents(e)
16. UpdateTimeGuardCS_TA()
17. forall c in my_sys.TA_components
18. c.UpdateTimeGuardTA()
FIGURE 14.16
Execution: Initialization and update for noninteracting concurrent timed
automata.
active events in the composed system. This composition does not restrict or
scope events that an automaton can see; therefore, events generated from
one automaton will be visible for all other automata in the composed system
as well.
The InitializeCS_TA method invokes the InitializeTA method for each
TimedAutomaton object in the composed system after it checks constraints
that are placed on the clock variables (Figure 14.16). First, in the composed
system, the clock variable t is the system clock and is not allowed to be reset.
The next two constraints ensure that no clock is defined both globally and
locally and that no clock is defined as local to multiple automata. The Upda-

teEventsCS_TA method must correctly update the global set of active events
for all TimedAutomaton objects in the system. Remember, all of the automata
see the same set of active events (i.e., there is no scoping of local events ver-
sus global events). Still, this could be extended to allow event scoping in
the semantics of other variations of a composed system. The UpdateTime-
GuardCS_TA method simply calls the UpdateTimeGuardTA method for each
TimedAutomaton.
The TimeProgressCS_TA and EvolveCS_TA methods (shown in Figure
14.17) are responsible for changing the state of the system for every execu-
tion step. Along with calling the TimeProgressTA method for each automa-
ton, TimeProgressCS_TA must increment all global clock valuations by the
defined constant . This method is only called if all automata in the sys-
tem have elected to take the time transition in this step. The EvolveCS_TA
method takes as input each timed automaton in the system with its respec-
tive highest priority currently enabled transition. ev and nev are initialized to
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 472 2009-10-2
472 Model-Based Design for Embedded Systems
1. class Comp_System
2. TimeProgressCS_TA()
3. g_v := {clki -> g_v (clki) + epsilon | clki in global_clocks}
4. forall c in TA_components
5. c.TimeProgressTA()
7. EvolveCS_TA(cT as Set of (TimedAutomaton, Transition))
8. let ev = {k | k in cT where k.Second <> time}
9. let nev = {l | l in cT where l.Second = time}
10. let gr = BigUnion({ h.Second.resets | h in ev})
12. g_v := {clki -> 0 | clki in ( gr intersect global_clocks) }
13. union { clki -> g_v (clki) | clki in global_clocks
14. - ( gr intersect global_clocks)}
16. forall m in ev

17. m.First.EvolveTA(m.Second)
18. forall n in nev
19. n.FirstUpdateEvents({})
FIGURE 14.17
Execution: Progress for global time and individual automata.
the automata that will take a non-time transition in this step and those that
will not, respectively. The automata in nev indicate that their highest prior-
ity transition is the time transition; however, all other automata (specified
in ev) do not agree so the time transition will not be taken. If a transition is
not taken by an automaton, the set of active output events for that automa-
ton are cleared. Given the automata that will be taking a non-time transition,
the method must also reset global clocks specified in the resets field of the
enabled transitions. The EvolveTA method of each automaton will reset the
local clocks. Accordingly, the EvolveTA method is called for each automaton
in the set ev.
The RunCS_TA method provides a single execution loop for the com-
posed system (Figure 14.18). First, each automaton of the composed sys-
tem must be initialized. Notice that the variable count restricts the number
of execution steps of the loop and has no semantic meaning for the system.
During each iteration of the execution loop, the active event set is updated
(UpdateEventsCS_TA method) to include the events generated from the last
set of transitions, initially held in E, joined to the events returned from the
InputEvents method. Also, all time guards must be reevaluated given the
resulting system state from the last execution step.
Following these updates, the set of enabled transitions for all automata
can be determined. First, the set of all enabled transitions for each automa-
ton are stored in eT in the anonymous 2-tuple of type <TimedAutomaton,
Set of Transitions> . Next, the set of enabled transitions for each automaton
is reduced to a single transition that has the highest priority of all enabled
transitions. This reduction is nondeterministic if multiple enabled transi-

tions have the highest priority value. Time will progress only if all automata
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 473 2009-10-2
Semantics of Domain-Specific Modeling Languages 473
1. class Comp_System
2. RunCS_TA()
3. Var_ count = 1
4. step my_sys.InitializeCS_TA()
5. step while count < 35
6. step
7. UpdateEventsCS_TA()
8. UpdateTimeGuardCS_TA()
9. step
10. let eT = {(ta, ta.EnabledTransitionsTA()) | ta in
TA_components}
11. let eT2 = {(b.First, (any h | l in b.Second where
12. b.First PriorityTA(h) = (max b.First.PriorityTA(tp)
13. | tp in b.Second))) | bineT}
14. if {b2.Second | b2 in eT2} = {time} then
15. TimeProgressCS_TA()
16. else
17. EvolveCS_TA(eT2)
18. step
19. E := BigUnion({ c.GetEvents()| c in TA_Components})
20. count := count + 1
21.
FIGURE 14.18
Execution: Global coordination code.
indicate that the time transition should be taken; otherwise, eT2 is passed to
EvolveCS_TA. Following either action (time progress or taking other transi-
tions) all generated events from each automaton in the composed system are

collected and stored in the variable field E.
14.4.2.5 TASU Modeling Language
Within the MIC semantic anchoring framework, model transformations
between metamodels of a given DSML and the TASU specifies the anchoring
of the DSML to the TASU. In order to connect the ASML and the MIC tool
suites, we must represent the TASU ADM as a MIC metamodel (expressed
in MetaGME) and must implement a translator that translates MIC model
instances into ADM model instances. Figure 14.19 shows the metamodel of
the TASU specified in the MetaGME metamodeling language [22] of the MIC
tool GME.
The metamodel in Figure 14.19 captures the Abstract Data Model of the
TASU. Note that the metamodel includes Constant and Variable objects for
defining model-dependent data. The remaining piece of the TASU is a model
translator that generates the ASML of data models from timed automata
models created in the MIC tool suite. Since these time automata models are
instances of the TASU Metamodel as well as the TASU ADM on the ASML
side, the translator is a simple XML parser.
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 474 2009-10-2
474 Model-Based Design for Embedded Systems
Event
<<Atom>>
0
x
0
x
0
x
0
x
0

x
0
x
src 0
x
dst
0
x
0
x
0
x
0
x
Constant
<<Atom>>
Variable
<<Atom>>
Initial
<<Reference>>
Location
<<Atom>>
Type : field
Value : field
Type : field
Value : field
output : field
resets : field
trigger : field
time_guard : field

Priority : field
TimedAutomaton
<<Model>>
Transition
<<Connection>>
System
<<Model>>
Clock
<<Atom>>
FIGURE 14.19
Metamodel for our timed automata abstract data model.
14.4.2.6 Semantic Anchoring Example: The Timing Definition Language
The timing definition language (TDL) [16,36] provides a high-level pro-
gramming abstraction that allows distributed real-time system designers to
describe the temporal behavior of components apart from their functional
code and deployment/configuration concerns. This timing model is based
on logical execution time (LET) introduced by the Giotto modeling lan-
guage [20]. TDL preserves many other artifacts of Giotto, but some syntactic
and semantic differences remain.
This case study will capture the timing behavior of a TDL application
by anchoring a TDL modeling language to the TASU. For simplicity, in this
example, all TDL communication artifacts will be excluded from the map-
ping since they have no effect on the temporal behavior of a TDL application.
In Giotto [20] a system is defined over a set of nonconcurrent modes,
each of which contains periodically executing activities and a communica-
tion topology description. The periodic activities, task invocations under LET
semantics, actuator updates, and mode switches, all conditionally execute a
finite number of times, their frequency, within the mode’s cyclic execution
period. A task’s timed execution cycle is initiated by a release for scheduled
execution and finished by a completion event at time after the release. Actua-

tor updates and mode switches are considered synchronous activities; there-
fore, they take zero logical time to execute.
In TDL [16] the notion of a mode is preserved; however, the model is
extended to include a module, a TDL component. A module encapsulates
Nicolescu/Model-Based Design for Embedded Systems 67842_C014 Finals Page 475 2009-10-2
Semantics of Domain-Specific Modeling Languages 475
what is characterized as a Giotto system, and a TDL system is defined as
a set of modules and communication networks between them. Like Giotto,
the modes within a single module do not execute concurrently; however,
modules of a TDL system execute in parallel.
14.4.2.7 Anchoring the TDL Modeling Language to the TASU
Figure 14.20 shows an abbreviated metamodel for the TDL modeling lan-
guage. The full metamodel contains data handling mechanisms, such as
ports and drivers; however, these omitted artifacts do not affect the tim-
ing behavior of a TDL application. Notice that the ModeSwitch class inherits
from the abstract class Periodics. The attribute frequency that ModeSwitch
now contains will be ignored in the transformation since nonharmonic mode
switches are not allowed in TDL unlike Giotto [20]. The TaskReference class
is used to copy a previously defined Task into a new mode that may define
a different frequency value for the TaskReferemce versus the original Task
object’s frequency.
The model transformation that provides the anchoring across the meta-
models is specified in the UMT language of the MIC tool GReAT [26]. The
transformation is given by a set of rules that define the mapping between the
TDL metamodel and the TASU metamodel. The transformation takes a TDL
System
<<Model>>
Module
<<Model>>
Mode

<<Model>>
Periodics
<<FCO>>
0
x
0
x
0
x
Task
<<Model>>
TaskReference
<<Reference>>
ModeSwitch
<<Reference>>
ModePeriod: field
StartMode: bool
Frequency: field
DriverFunction:field
FIGURE 14.20
TDL MetaGME Metamodel (abbreviated).

×