Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 126 2009-10-13
126 Model-Based Design for Embedded Systems
Application
Mapping
Execution platform
Network
m
1
f
1
f
2
r
1
r
2
os
1
pe
1
os
2
pe
2
m
2
τ
1
τ
2
τ

3
τ
4
FIGURE 5.5
System-level model of an embedded system.
these layers for a very simple example of an embedded system, which will
be used to explain the aspects of the model throughout the chapter.
• The application is described by a collectionofcommunicating sequential
tasks. Each task is characterized by four timing properties, described
later. The dependencies between tasks are captured by an acyclic
directed graph (called a “task graph”), which might not be fully con-
nected.
• The execution platform consists of several processing elements of possi-
bly different types and clock frequencies. Each processing element will
run its own real-time operating system, scheduling tasks in a priority-
driven manner (static or dynamic), according to their priorities, depen-
dencies, and resource usage. When a task needs to communicate with
a task on another processing element, it uses a network. The setup of
the network between processing elements must also be specified, and
is part of the platform.
• The “mapping” between the application and the execution platform
(shown as dashed arrows in the figure) is done by placing each task on
a specific processing element. In our model, this mapping is static, and
tasks cannot migrate during run-time.
The top level of the embedded system consists of an application mapped
onto an execution platform. This mapping is depicted in Figure 5.5 with
dashed arrows. The timing characteristics in Table 5.2 originate from [SL96],
while the memory and power figures (in Table 5.4) are created for the pur-
pose of demonstrating parameters of an embedded system. We will elaborate
on the various parameters in the following.

Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 127 2009-10-13
Modeling and Analysis Framework for Embedded Systems 127
TABLE 5.2
Characterization of Tasks
Task ωδπ
τ
1
044
τ
2
066
τ
3
066
τ
4
466
5.3.1 Application Model
The task graph for the application can be thought of as an abstraction of
a set of independent sequential programs that are executed on the execu-
tion platform. Each program is modeled as a directed acyclic graph of tasks
where edges indicate causal dependencies. Dependencies are shown with
solid arrows in Figure 5.5. A task is a piece of a sequential code and is con-
sidered to be an atomic unit for scheduling. A task τ
j
is periodic and is char-
acterized by a “period” π
j
, a “deadline” δ
j

, an initial “offset” ω
j
, and a fixed
priority fp
j
(used when an operating system uses fixed priority scheduling).
The properties of periodic tasks (except the fixed priority) can be seen in
Table 5.2 and are all given in some time unit.
5.3.2 Execution Platform Model
The execution platform is a heterogeneous system, in which a number of
processing elements, pe
1
, , pe
n
, are connected through a network.
5.3.2.1 Processing-Element Model
A processing element pe
i
is characterized by a “clock frequency” f
i
, a “local
memory” m
i
with a bounded size, and a “real-time operating system” os
i
.
The operating system handles synchronization of tasks according to their
dependencies using direct synchronization [SL96].
The access to a shared resource r
m

(such as a shared memory or a bus)
is handled using a resource allocation protocol, which in the current ver-
sion consists of one of the following protocols: preemptive critical section,
nonpreemptive critical section, or priority inheritance. The tasks are in the
current version scheduled using either rate monotonic, deadline monotonic,
fixed priority, or earliest deadline first scheduling [Liu00]. The properties of
a processing element can be seen in Table 5.3. Allocation and scheduling are
designed in M
OVES for easy extensions, that is, new algorithms can easily be
added to the current pool.
The interaction between the operating system and the application model
is shown in Figure 5.6. The operating system model consists of a controller,
a synchronizer,anallocator,andascheduler. The controller receives ready or
Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 128 2009-10-13
128 Model-Based Design for Embedded Systems
TABLE 5.3
Characterization of Processors
pe
1
pe
2
f
1
11
Scheduling RM RM
allocation PRI_INH PRI_INH
Application
Controller
Synchronizer
Allocator

Scheduler
Processing element
ready!
finish!
run!
preempt!
3
2
1

τ
1
τ
2
τ
k
FIGURE 5.6
Interaction of the k tasks, τ
1
to τ
k
, with the single processing element to which
they are mapped.
finish signals from those tasks of the application that are mapped to the
processing element (see 1 in Figure 5.6); activates synchronization, alloca-
tion, and scheduling to find the task with the highest priority (see 2 in Fig-
ure 5.6); and finally sends run or preempt signals back to the tasks (see 3 in
Figure 5.6).
5.3.2.2 Network Model
Inter-processor communication takes place when two tasks with a depen-

dency are mapped to different processing elements. In this case, the data to
be transferred is modeled as a message task τ
m
. Message tasks have to be
transferred across the network between the processing elements. A network
is modeled in the same way as a processing element. So far, only busses have
been implemented in our model; however, it is shown in [MMV04] how
more complicated intercommunication structures, such as meshes or torus
Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 129 2009-10-13
Modeling and Analysis Framework for Embedded Systems 129
networks, can be modeled. As a bus transfer is nonpreemptable, message
tasks are modeled as run-to-completion. This is achieved by having all mes-
sage tasks running on the bus, that is, the processing elements emulating the
bus, using the same resource r
m
, thereby preventing the preemption of any
message task. Intraprocessor communication is assumed to be included in
the execution time of the two communicating tasks, and is therefore mod-
eled without the use of message tasks.
5.3.3 Task Mapping
A mapping is a static allocation of tasks to processing elements of the
execution platform. This is depicted by the dashed arrows in Figure 5.5.
Suppose that the task τ
j
is mapped onto the processing element pe
i
. The “exe-
cution time,” e
ij
measured in cycles, memory footprint (“static memory,” sm

ij
and “dynamic memory,” dm
ij
), and “power consumption,” pw
ij
of a task τ
j
,
depend on the characteristics of the processing element pe
i
executing the task,
and can be seen in Table 5.4. In particular, when selecting the operation fre-
quency f
i
of the processing element pe
i
, the execution time in seconds, 
ij
,of
task τ
j
can be calculated as 
ij
= e
ij
·
1
f
i
.

5.3.4 Memory and Power Model
In order to be able to verify that memory and power consumption stay within
given bounds, the model keeps track of the memory usage and power costs
in each cycle. Additional cost parameters can easily be added to the model as
long as the cost can be expressed in terms of the cost of being in a certain state.
The memory model includes both static memory allocation (sm), because
of program memory, and dynamic memory allocation (dm), because of data
memory of the task. The example in Figure 5.7 illustrates the memory model
for a set of tasks executing on a single processor. It shows the scheduling
and resulting memory profiles (split into static and dynamic memories). The
dynamic part is split into private data memory (pdm) needed while execut-
ing the task, and communication data memory (cdm) needed to store data
exchanged between tasks. The memory needed for data exchange between
TABLE 5.4
Characterization of Tasks on Processors
Task esmdmpw
τ
1
21 3 2
τ
2
11 7 3
τ
3
21 9 3
τ
4
31 6 4
τ
m

1
Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 130 2009-10-13
130 Model-Based Design for Embedded Systems
pe
1
(a)
τ
2
τ
1
τ
3
τ
3
τ
4
(b)
pdm(τ
1
)
pdm(τ
2
)
cdm(τ
2
, τ
3
)
pdm(τ
3

)
sm(τ
4
)
sm(τ
3
)
sm(τ
2
)
sm(τ
1
)
pdm(τ
3
) pdm(τ
3
)
pdm(τ
4
)
Memory usage
(c)
τ
2
τ
1
τ
3
τ

3
τ
4
Power usage
(d)
τ
4
τ
2
τ
1
τ
3
FIGURE 5.7
Memory and power profiles for pe
1
when all four tasks in Figure 5.5 are
mapped onto pe
1
. (a) Schedule where τ
3
is preempted by τ
4
. (b) Memory
usage on pe
1
: static memory (sm), private data memory (pdm), and com-
munication data memory (cdm). (c) Power usage. (d) Task graph from
Figure 5.5.
τ

2
and τ
3
must be allocated until it has been read by τ
3
at the start of τ
3
’s
execution. When τ
3
becomes preempted, the private data memory of the task
remains allocated till the task finishes.
Currently, a simple approach for the modeling of power has been taken.
When a task is running, it uses power pw. The power usage of a task is zero
at all other times. The possible different power usages of tasks can be seen
as the heights of the execution boxes in Figure 5.7c. This approach can easily
be extended to account for different power contributions depending on the
state of the task.
5.4 Model of Computation
In the following, we will give a rather informal presentation of the model
of computation. For a formal and more comprehensive description, please
refer to [BHM08]. To model the computations of a system, the notion of
Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 131 2009-10-13
Modeling and Analysis Framework for Embedded Systems 131
a “state”, which is a snapshot of the state of affairs of the individual pro-
cessing elements, is introduced. For the sake of argument, we will con-
sider a system consisting of a single processing element pe
i
and a set
of tasks τ

j
∈ T
pe
i
assigned to pe
i
. Furthermore, we shall assume that
each τ
j
is characterized by “best-case” and “worst-case” execution times,
bcet
j
∈ N and wcet
j
∈ N, respectively. At the start of each new period,
there is a nondeterministic choice concerning which execution time e
ij
∈
{bcet
τ
j
, bcet
τ
j
+1, , wcet
τ
j
−1, wcet
τ
j

} is needed by τ
j
to finish its job on pe
i
of that period.
For the processing element pe
i
, the state component must record which
task τ
j
(if any) is currently executing, and for every task τ
j
∈ T
pe
i
record the
execution time e
ij
that is needed by τ
j
to finish its job in its current period.
We denote the state σ, where τ
j
is running and where there is a total of n
tasks assigned to pe
i
,asσ = (τ
j
, (e
i1

, , e
in
)). Here, we consider execution
time only; other resource aspects, such as memory or power consumption
are disregarded.
A trace is a finite sequence of states, σ
1
σ
2
···σ
k
, where k ≥ 0 is the length
of the trace. A trace with length k describes a system behavior in the interval
[0, k]. For every new period of a task, the task execution time for that period
can be any of the possible execution times in the natural number interval
[bcet, wcet]. If bcet = wcet for all tasks, there is only one trace of length k,for
any k.Ifbcet = wcet, we may explore all possible extensions of the current
trace by creating a new branch for every possible execution time, every time
a new period is started for a task. A “computation tree” is an infinite, finitely
branching tree, where every finite path starting from the root is a trace, and
where the branching of a given node in the tree corresponds to all possible
extensions of the trace ending in that node. This is further explained in the
following example.
Example 5.2 Let us consider a simple example consisting of three independent tasks
assigned to a single processor. The characteristics of each task are shown in Table 5.5.
The computation tree for the first 8 time units is shown in Figure 5.8. Here, we will
give a short description of how this initial part of the tree is created.
Time t = 0: Only task τ
1
is ready, as τ

2
and τ
3
both have an offset of 2. Hence, τ
1
starts executing, and as bcet = wcet = 2, there is only one possible execution
time for τ
1
. The state then becomes σ
1
= (τ
1
, (2, 0, 0)).
TABLE 5.5
Characterization of Tasks
Task Priority ω bcet wcet π
τ
1
10223
τ
2
22124
τ
3
32126
Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 132 2009-10-13
132 Model-Based Design for Embedded Systems
8
7
6

5
4
3
2
1
0
(τ
1
,(2,1,2))
(τ
1
,(2,1,2))
(τ
1
,(2,1,2))
(τ
1
,(2,0,0))
(τ
1
,(2,0,0))
(τ
1
,(2,1,2))
(τ
2
,(2,1,2))
(τ
3
,(2,1,2))

τ
1
π
1
π
1
π
1
π
2
π
3
π
2
τ
2
τ
3
Offset
Offset
(τ
2
,(2,2,2))(τ
2
,(2,1,1)) (τ
2
,(2,2,1))
(τ
1
,(2,2,2))

FIGURE 5.8
Possible execution traces. A  indicates a subtree, the details of which are
not further processed in this example.
Time t = 2: τ
1
has finished its execution of 2 time units, but a new period for
τ
1
has not yet started as π
1
= 3.Bothτ
2
and τ
3
are now ready. Since
τ
2
has the highest priority (i.e., the lowest number), it gets to execute. As
the execution time interval for both τ
2
and τ
3
is [1, 2], there are two dif-
ferent execution times for each, and hence, four different possible states,
(τ
2
, (2, 1, 1)), (τ
2
, (2, 1, 2)), (τ
2

, (2, 2, 1)), and (τ
2
, (2, 2, 2)), which give rise to
four branches. In Figure 5.8, we will only continue the elaboration from state
(τ
2
, (2, 1, 2)).
Time t = 3: τ
2
finishes its execution. τ
3
is still ready and the first period of τ
1
has
completed initiating its second iteration, hence, τ
1
is also ready. As τ
1
has the
highest priority, it gets to execute. The state becomes (τ
1
, (2, 1, 2)).
Time t = 5: τ
1
finishes its execution. τ
3
is the only task ready, as the first period
for τ
2
has not yet finished. The state becomes (τ

3
, (2, 1, 2)).
Time t = 6:Bothτ
1
and τ
2
become ready as a new period starts for each of them.
Again, τ
1
has the highest priority and gets executed, preempting τ
3
,which
then still needs one time unit of execution to complete its job for the current
period. Since the execution time of τ
2
can be 1 or 2, and that of τ
1
only 1, we
just have two branches, that is, the possible new states are (τ
1
, (2, 1, 2)) and
(τ
1
, (2, 2, 2)).
Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 133 2009-10-13
Modeling and Analysis Framework for Embedded Systems 133
Time t = 8: τ
1
has completed its execution allowing τ
2

to take over. However, at
this point, the second period of τ
3
starts, while τ
3
has not yet completed its job
for the first period. Hence, τ
3
will not meet its deadline and this example is not
schedulable.
This model of computation can easily be extended to a system with mul-
tiple processors. The system state then becomes the union of the states for
each processor.
A run of a system is an infinite sequence of states. We call a system
“schedulable” if for every run, each task finishes its job in all its periods.
In [BHM08], we have shown that the schedulability problem is decidable
and an upper bound on the depth of the part of the computation tree, which
is sufficient to consider when checking for schedulability, is established. An
upper bound for that depth is given by
Ω
M
+Π
H
·(1 +Σ
τ∈T
wcet
τ
)
where T is the set of all tasks, Ω
M

is the maximal offset, Π
H
is the hyper-
period of the system (i.e., the least common multiple of all periods of tasks in
the system), and Σ
τ∈T
wcet
τ
an upper bound of the number of hyper-periods
after which any traces of the system will reach a previous state.
The reason why it is necessary to “look deeper” than just one hyper-
period can be explained as follows: Prior to the time point Ω
M
, some tasks
may already have started, while others are still waiting for the first period
to start. At the time O
M
, the currently executing tasks (on various process-
ing elements) may therefore have been granted more execution time in their
current periods, than would be the case in periods occurring later than Ω
M
—
you may say that they have “saved up” some execution time and this saving
is bounded by the sum of the worst-case execution times in the system. In
[BHM08], we have provided an example where the saving is reduced by one
in each hyper-period following Ω
M
until a missed deadline is detected. The
upper bound above can be tightened:
Ω

M
+Π
H
·(1 +Σ
τ∈T
X
wcet
τ
)
where T
X
is the set of all tasks that do not have a period starting at Ω
M
.
Example 5.3 Let us illustrate the challenge of analyzing multiprocessor systems by
a small example illustrated in Table 5.6.
We have Ω
M
= 27, Π
H
= LCM{11, 8,251}=22088, and Σ
τ∈T
X
wcet
τ
=
3+4 = 7. The upper bound on the depth of the tree is Ω
M
+Π
H

·(1+Σ
τ∈T
X
wcet
τ
) =
176731. The number of nodes (states) in the computation tree occurring at a depth
≤ 176731 can be calculated to approximately 3.9 ·10
13
. For details concerning such
calculations we refer to [BHM08].
Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 134 2009-10-13
134 Model-Based Design for Embedded Systems
TABLE 5.6
Small Example with a Huge State Space
Execution Time Period Offset
Task (bcet
τ
,wcet
τ
) π
τ
ω
τ
τ
1
(1, 3) 11 0
τ
2
(1, 4) 8 10

τ
3
(1, 13) 251 27
5.5 MoVES Analysis Framework
One aim of our work is to establish a verification framework, called the
“MoVES analysis framework” (see Figure 5.1), that can be used to provide
guarantees, for example, about the schedulability, of a system-level model
of an embedded system. We have chosen to base this verification framework
on timed automata [AD94] and, in particular, the U
PPAAL [BDL04,LPY97] sys-
tem for modeling, verification, and simulation. In this section, we will briefly
discuss the rationale behind this choice and give a flavor of the framework.
We refer to [BHM08] for more details.
First of all, the timed-automata model for an embedded system must be
constructed so that the transition system of this model is a refinement of
the computation-tree model of Section 5.4, that is, the timed-automata model
must be correct with respect to the model of computation.
Another design criteria is that we want the model to be easily extendible
in the sense that new scheduling, allocation, and synchronization principles
for example, could be added. We therefore structure the timed-automata
model in the same way the ARTS [MVG04,MVM07] model of the multi-
processor platform is structured (cf. Figure 5.6). This, furthermore, has the
advantage that the U
PPAAL model of the system can also be used for sim-
ulation, because an U
PPAAL trace in a direct manner reflects events on the
multiprocesser platform.
The timed-automata model is constructed as a parallel composition of
communicating timed automata for each of the components of the embedded
system. We shall now give a brief overview of the model (details are found in

[BHM08]), where an embedded system is modeled as a parallel composition
of an application and an execution platform:
System = Application  ExecutionPlatform
Application =
τ∈T
TA(τ)
ExecutionPlatform =
N
j=1
TA(pe
j
)
where denotes the parallel composition of timed automata, TA(τ) the timed
automaton for the task τ,andTA(pe) the timed automaton for the processing
Nicolescu/Model-Based Design for Embedded Systems 67842_C005 Finals Page 135 2009-10-13
Modeling and Analysis Framework for Embedded Systems 135
element, pe. Thus, an application consists of a collection of timed automata
for tasks combined in parallel, and an execution platform consists of a paral-
lel composition of timed automata for processing elements.
The timed-automata model of a processing element, say pe
j
, is structured
according to the ARTS model described in Figure 5.6 as a parallel composi-
tion of a controller,asynchronizer,anallocator,andascheduler:
TA(pe
j
) = Controller
j
 Synchronizer
j

 Allocator
j
 Scheduler
j
In the UPPAAL model, these timed automata communicate synchronously
over channels and over global variables. Furthermore, the procedural lan-
guage part of U
PPAAL proved particularly useful for expressing many
algorithms. For example, the implementation of the earliest deadline first
scheduling principle is directly expressed as a procedure using appropriate
data structures.
Despite that the model of computation in Section 5.4 is a discrete model in
nature, the real-time clock of U
PPAAL proved useful for modeling the timing
in the system in a natural manner, and the performance in verification exam-
ples was promising as we shall see in Section 5.6. One could have chosen a
model checker for discrete systems, such as SPIN [Hol03], instead of U
PPAAL .
This would result in a more explicit and less natural modeling of the timing
in the system. Later experiments must show whether the verification would
be more efficient.
The small example in Table 5.6 shows that verification of “real” sys-
tems becomes a major challenge because of the state explosion problem. The
M
OVES analysis framework is therefore parameterized with respect to the
U
PPAAL model of the embedded system in order to be able to experiment
with different approaches and in order to provide an efficient support for
special cases of systems. In the following, we will briefly highlight four of
these different models.

1. One model considers the special case where worst-case and best-case
execution times are equal. Since scheduling decisions are deterministic,
nondeterminism is eliminated, and the computation tree of such a sys-
tem consists of only one infinite run. Note that for such systems it may
still be necessary to analyze a very long initial part of the run before
schedulability can be guaranteed. However, it is possible to analyze
very large systems. For the implementation of this model, we used a
special version of U
PPAAL in which no history is saved.
2. Another model extends the previous one by including the notion of
resource allocation to be used in the analysis of memory footprint and
power consumption.
3. A third model includes nondeterminism of execution times, as
described in the model of computation in Section 5.4. In this timed-
automata model, the execution time for tasks was made discrete in