Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 286 2009-10-2
286 Model-Based Design for Embedded Systems
waiting for (blocking) other processes. A process may atomically pro-
pose multiple events—this represents nondeterminism in the system.
After all processes in the base model are blocked, the design shifts to
the second phase. The execution of processes between blocking points
is beyond the control of the framework.
2. Quantity annotation. In the second phase, each of the proposed events
is annotated with various quantities of interest. For instance, a proposed
event may be annotated with local and global time tags. New events
may not be proposed during this phase of execution. In this way, events
and the methods they correspond to can be associated with cost.
3. Constraint solving. In this phase, a subset of the proposed events is
enabled and permitted to execute, while the remaining events remain
suspended. Events are enabled according to schedulers and constraint
solvers. These enabled events then become inactive again while simul-
taneously allowing their associated processes to resume to the running
state. At most one event per process is permitted to execute. Once again,
new events may not be proposed during this stage. Constraint solv-
ing may be based on the resolution of declarative constraints or on the
imperative code.
A collection of three completed phases is referred to as a round. After the
constraint solving phase, the states of some processes are switched to run-
ning while some others might still be suspended. The execution will then
shift to the first phase and start a new round. Those processes that are in
the running state will resume their executions. The iterations of these three
phases will end when all processes finish their executions. Figure 10.8 illus-
trates the process states, event states, and the three phases in the execution
semantics. Self loops on the inactive and annotated states illustrate that mul-
tiple rounds may pass without an update to a particular event’s state.
Table 10.1 illustrates the relationships between events and phases. In the

first phase (base), events can be proposed and their values can be read or
written. In the second phase (annotation), tags can be read and written and
values can be read. In the final phase (constraint solving), events can be dis-
abled and their tags and values can be read. The semantics have been care-
fully designed so that the event manipulation adheres to our separation of
TABLE 10.1
Phase–Event Relationships
Events Tags Values
Phase Propose Disable Read Write Read Write
Base (1) Yes Yes Yes
Annotation (2) Yes Yes Yes
Constraint solving (3) Yes Yes Yes
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 287 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 287
TABLE 10.2
METRO II Elements and Their Characteristics
Type Threads Events Tags Values Hierarchy
Component 0+ Generate R/W R/W Yes
Adaptor 0+ Generate R/W R Yes
Annotator 0 Propagate R/W R No
Scheduler 0 Disable R R Yes
concerns methodology. This is very helpful not only in debugging simula-
tion but also in making sure that the framework functions efficiently.
Table 10.2 indicates the M
ETRO II elements and their characteristics. This
details the presence of threads as well as the ability to manipulate events,
tags, and values. It also indicates if there is hierarchy. Components and adap-
tors may have zero or more threads, while annotators and schedulers do not
have any threads.
Events, and by extension, services, may be annotated by quantities of

interest. Quantities capture the cost of carrying out particular operations and
are implemented using quantity managers. Annotators are special compo-
nents that provide annotation services. Schedulers are similar to quantity
managers, but instead of a quantity they provide scheduling and arbitration
of shared resources. Adaptors modify tags and provide interfacing between
different MoCs. Depending on the MoC used and the needs of the design,
different annotators and schedulers can be used.
10.4.3.2 Semantics of Required/Provided Ports
The execution semantics of the required and provided ports are as follows.
For required ports, a component proposes a begin event and associates
values with the proposed event that represent the arguments of the method
that is requested. When the proposed event is enabled and executed, the con-
trol transfers to the component at the other end of the connection, which
owns the corresponding provided port. The component waits for the end
event to be executed and obtains the return values from the method.
For provided ports, no separate process exists in the component to carry
out the provided method. Instead, the component inherits the process from
the caller component and executes the events in the provided method using
that process. After the method has been executed, the component proposes
the end event.
10.4.3.3 Semantics of Mapping
A key feature of M
ETRO II is the ability to separately specify the functional and
architectural models. The two are then mapped together to produce a system
model with performance metrics. Mapping is realized by adding constraints
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 288 2009-10-2
288 Model-Based Design for Embedded Systems
between events from the functional model and events from the architectural
model.
We will present three options for the execution semantics of mapping

in M
ETRO II. The “call graph” of the mapping options is shown in Figure
10.9. Option 1 is the first call graph shown, option 2 follows, and option 3 is
the last. For options 1 and 2 the structural view (upper right of the figure)
is a connection between required ports in the functional model and pro-
vided ports in the architectural model. For option 3, the mapping structure
is different and is between provided ports in function and provided ports in
architecture.
The first option is a sequential option in which the functional model
begins execution before the architectural model. Some of the highlights of
this option are captured in Table 10.3.
Figure 10.9 shows both a structural and a call-graph view of mapping in
the first option. The ports in these and future diagrams are specified with the
first letter of the component they belong to. Also, ports are designated as “R”
or “P” if they are required or provided. “b” and “e” designate the begin and
end events, respectively. These designations can be combined. For example,
“FP.e” would indicate the end event of component F’s provided port.
Figure 10.9 shows the mapping structure of a system using this option.
The functional model contains a method call to G from P. The mapping
of this method call occurs by assigning events proposed by FR to events
proposed by AP. This is considered a required port to the provided port-
mapping structure.
Figure 10.9 also shows the call graph of the system. Boxes with single
line borders are events. Boxes that have two line borders are code blocks that
may or may not contain events. The arrows indicate program flow (from left
to right). If an arrow is dashed it means that two events connected to it are
treated as a single event by the framework. The functional component F calls
a method from the component G. This is mapped to the architectural com-
ponent A, which further uses the architectural component B when providing
the service.

The execution in this option occurs as follows: component F contains a
process. This process is responsible for proposing the event “FR.b.” “FR.b”
corresponds to “GP.b” (in G). Once these events are enabled, the “G body”
(the code body of the function call to G) can now execute. Upon comple-
tion, “FP.e” (in G) will be proposed. This event corresponds to “AP.b” in the
architecture. The architecture body, “A body,” can now execute and culmi-
nate with the proposal of “AP.e.” As shown, “AP.e” corresponds to “FR.e,”
which completes the execution.
As shown, the mapping of methods is carried out by invoking the
mapped architectural service in the process of the caller after the correspond-
ing functional method has completed the execution.
In option 2, the execution semantics of mapping involve executing
mapped architectural services before their functional counterparts. When a
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 289 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 289
FR.b
FR.e
GP.b
G.body
GP.e
AP.b
A.body
AP.e
FR.b
FR.e
AP.b
A.body
AP.e
GP.b
G.body

GP.e
FR.b
FR.e
AP.b
A.body
AP.e
GP.b
G.body
GP.e
class m2_rendez_constraint : public m2_constraint
{
protected:
m2_event *_m1, *_m2;
public:
m2_rendez_constraint(m2_event* m1, m2_event* m2)
: m2_constraint(M2_RENDEZ_CONSTRAINT)
{
_m1 = m1;
_m2 = m2;
}
bool isSatisfied()
{
return (((_m1–>get_status() == (char)M2_EVENT_PROPOSED)
|| (_m1–>get_status() == (char)M2_EVENT_WAITING))
&& ((_m2–>get_status() == (char)M2_EVENT_PROPOSED)
|| (_m2–>get_status() == (char)M2_EVENT_WAITING)));
}
void solveConstraint()
{
if (isSatisfied()){

_m1–>set_status((char)M2_EVENT_PROPOSED);
_m2–>set_status((char)M2_EVENT_PROPOSED);
}
else {
if (_m1–>get_status() == (char)M2_EVENT_PROPOSED) {
_m1–>set_status((char)M2_EVENT_WAITING);
}
if (_m2–>get_status() == (char)M2_EVENT_PROPOSED) {
_m2–>set_status((char)M2_EVENT_WAITING);
}
}
}
};
F G
A
B
Function
Architecture
RP
P
R
Option #1
Option #2
Option #3
FIGURE 10.9
M
ETRO II mapping semantics options.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 290 2009-10-2
290 Model-Based Design for Embedded Systems
TABLE 10.3

Mapping Options Overview
Execution
Order in Mapping Structure Event Requires
Option Simulation (Func ↔ Arch) Port Correspondence Blocking
1 Functionality Required ↔Provided FR.b, GP.b Yes
then GP.e, AP.b
Architecture AP.e, FR.e
2 Architecture Required ↔Provided FR.b, AP.b Yes
before AP.e, GP.b
Functionality GP.e, FR.e
3 Concurrent Provided ↔Provided FR.b, AP.b, FP.b No
Functionality FR.e, AP.e, FP.e
and Architecture
mapped method is invoked by a functional process, the begin event of that
method is initially proposed, and a phase change is permitted to occur. If this
event is enabled, then the architectural service executes first, immediately
followed by the invoked functional method. After this, the end event of that
method is proposed, with a subsequent phase change. Both the functional
method and the architectural service are executed by the functional process;
there are no special mapping processes. Additionally, both the functional
method and the architectural service may block internally while waiting for
other processes.
The functional method is parameterized with arguments and has a return
type. The architectural service is also parameterized, but the return value is
not used. The correspondence between the architectural service parameters
and the functional service parameters is specified at compile time.
This proposal is in some regards the opposite of the first proposal. It is
summarized in Table 10.3.
Figure 10.9 for the previous option shows the call graph for execution
between the functional and architectural models. Basically, the functional

methods need to be completed before the corresponding architecture ser-
vices start. However, in some cases, this approach may not be able to reflect
all the situations in the mapped system.
For instance, let us consider a shared FIFO example. Option #1 cannot
assure that the architectural ordering decision impacts the functional execu-
tion, since the function methods will finish before the architecture is invoked.
Therefore, the shared FIFO example may not work as expected with option
# 1 if one wants to use the state of the architectural FIFO to block functional
processes (i.e., it is full). Essentially, functional nondeterminism cannot be
resolved by the architecture. Such operations may be desirable when the
architecture is better able to perform given the opportunity to make deci-
sions based on its state (free resources, for example). This also removes some
scheduling burden from other areas of the system.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 291 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 291
The second option remedies this problem by completing architecture ser-
vices before the corresponding function method starts. The new call graph
is shown in Figure 10.9. This proposal shares the same mapping structure as
option # 1.
The third option is summarized in Table 10.3. There is a consensus that
the M
ETRO II environment is rooted in the PBD methodology [54], where the
functional model and the architectural model meet in the middle with a set
of well-defined services as the binding contract. To the architectural model,
the middle point represents what services it can provide to implement cer-
tain functionalities, or to estimate the implementation cost. To the functional
model, the middle point describes its need of services to achieve its entire
function. If we look at the design scenarios, the services that are exposed at
the middle point include execute, read_fifo,andwrite_fifo. Therefore, the archi-
tecture model has to provide at least those services. As the three proposals

exhibit, there are multiple possibilities in terms of the ports to be mapped. In
fact, the syntactic difference does not really matter.
What matters is the role of the mapped architectural component and its
relationship to the components on the functional side. Imagine on the func-
tional side, the source component calls write_fifo that is provided by FIFO1.
No matter which part in the connection (the required port, the provided
port, or the connection) is mapped to the architecture, we expect the archi-
tectural service at some point to perform write_fifo. In that sense, the archi-
tectural counterpart corresponds to FIFO1, where both the functional and
architectural parts react to the write_fifo request and do the job. If we can
agree on this correspondence, then any mapping syntax will work. That is,
on the functional side, the required port, the provided port, and the connec-
tion, each represents a pair of events; on the architectural side, the service
is also represented by a pair of events. Then mapping establishes another
pair of correspondences between the two pairs of events. However, from the
methodology point of view, where we emphasize the meeting point between
functional and architectural models, mapping connections or provided ports
from the functional side seem to be better choices.
When running the functional and the architectural models together,
∗
we would like the mapped services on both sides to finish simultaneously,
because this will provide the most information about how an architectural
model implements a functional model. However, there are concerns about
the fact that suspension of processes on either side would prevent the entire
mapped system from progressing. This is primarily caused by the semantics
mismatch of the services from both sides. By carefully designing the consis-
tent services, we should be able to make the mapped system work even with
blocking behaviors on either or both sides.
∗
Note that we can also run the functional model first, recording the service demands, and

then drive the execution of the architectural model. But this eliminates the behavior where the
feedback from the architectural model would affect the execution of the functional model.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 292 2009-10-2
292 Model-Based Design for Embedded Systems
The mapping structure and the call graph for the third proposal are
shown in Figure 10.9. Notice that in option # 3, the provided ports in the func-
tional model are mapped to the provided ports in the architectural model as
well. This is different from the previous two options. Also in the call graph,
it is shown that the correspondence points must be created in the form of
protocols in order to create a more granular operation at the event level in
each model. An example of such a protocol will be shown in more detail in
the hand traces for proposal # 3.
F and G are two components in the functional model, where F is mak-
ing a method call on its required port Req to G’s provided port Prov.Inthis
example, the architecture is represented by components A and B,andthe
provided port of G has the same interface as the provided port of A.Inthis
case, we can say that component G has been mapped into component A. For
simplicity, assume that the interface of ports F.Req, G.Prov,andA.Prov con-
tains only one method. The mapping between G and A is realized by plac-
ing rendezvous constraints on the begin and end events associated with this
method, as shown at the bottom of Figure 10.9. Starting at the bottom left of
the figure, one sees the initial event proposal of F.Req.b. Moving to the right,
the other events are proposed in turn. Left–right arrows indicate causality
while vertical arrows indicate the presence of a constraint.
Within the framework, these rendezvous constraints are handled in the
same way as any other event constraints during Phase 3 of the execution
semantics. Mapping uses the same infrastructure as the rest of the system,
and, therefore, the simulation is not burdened with another set of semantics
for mapping.
10.5 Related Work

The literature on system-level design and design-space exploration is vast.
In the previous work, we presented a broad survey of numerous tools and
methodologies in the context of platform-based design [25], both from indus-
try and academia, and categorized them along different axes, such as the abil-
ity of supporting functional, architectural, and mapping descriptions, and
the depth of the levels of abstraction that are covered. In this section, we
focus on the approaches that are directly related to the topics presented.
10.5.1 Origin of METRO II: From Polis to METROPOLIS
The roots of the METROPOLIS framework can be traced back to the Polis
project [5]. The main idea behind Polis is to raise the level of abstraction
at which designers work and reason about the system in terms of models
that can be then implemented as either hardware or software components.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 293 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 293
System optimization is therefore carried out using a hardware/software
codesign methodology. The success of the Polis framework was largely due
to its well-defined MoC, co-design finite state machines (CFSMs). In CFSMs,
each component is described synchronously, using a specification stylebased
on the language Esterel [10] that is well suited for the definition of reactive
systems. Using Esterel, the behavior of the system can be described as an
instantaneous reaction to the external events, thus abstracting away time
and facilitating verification. The synchronous hypothesis is not, however,
satisfied by real implementations, especially when the system is deployed
on a mixed hardware/software architecture, where delays may be depen-
dent upon the current state of the application and on the particular schedul-
ing policy used by the processors. To explicitly account for this, Polis intro-
duces a globally asynchronous interaction model for the interconnection of
the locally synchronous components. Asynchronicity is guaranteed by the
presence of buffers that hold the data until the recipient is ready to react.
This scheme also facilitates the development of several different ways for the

hardware and the software components to interact, through direct commu-
nication or shared memory areas.
M
ETROPOLIS was born as an extension of Polis to deal with systems built
out of different MoCs, instead of only CFSMs. One of the central ideas
of the new framework is to separate between the computation (the pro-
cess) and the communication (the media). Different media implementations
would be used to simulate different interaction semantics. For this reason,
the M
ETROPOLIS MoC was named the MMM. Along with the hardware/
software codesign technique, M
ETROPOLIS was also intended to implement a
full refinement-based design flow. To support this, another innovation in
M
ETROPOLIS was introduced, the ability to define the model of the platform or
of the architecture in the same formalism used to define the functionality of
the system. This made it possible to keep the function and the architecture
separate on one side, and to synchronize their execution using a dedicated
language of constraints (LoC) on the other. This device was central in the
way of mapping development in M
ETROPOLIS. In particular, communication
media could be refined to explore different ways of carrying out the com-
munication. In addition, a third element called quantity manager was intro-
duced to account for the evaluation of performance metrics under arbitrary
algebras (defined in the methods of the manager) during the very simulation
of the system. This technique was also useful to regulate access to shared
resources, which introduce an indirect interaction between otherwise unre-
lated functional blocks.
M
ETRO II builds on the METROPOLIS experience, but focuses less on the

model itself, and more on the integration of different existing models. This is
achieved with a more lightweight, wrapper-style environment built on top of
SystemC. It also greatly simplifies the annotation and scheduling aspects of
event management by separating each activity into its own phase. Mapping
is also made easier by abstracting the constraints at the service level.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 294 2009-10-2
294 Model-Based Design for Embedded Systems
10.5.2 Industrial Approaches
A host of industrial tools have their roots in the model driven architec-
ture (MDA) developed by the OMG [43], which can be cast in the gen-
eral framework of the PBD. The MDA is an approach to using models in
software development. At its basis is the separation between the specifica-
tion of the operations of a system from the details of the way the system
uses the capabilities of a platform. The goal is to achieve portability, inter-
operability, and reusability of models. In this approach, the development
starts with a computation-independent model (CIM) representing the sys-
tem in the context of the environment in which it will operate, by detailing
its requirements with no regard to functionality. This model is later refined
into a platform-independent model (PIM), used to specify the functionality
of the system without committing to any particular platform. At the same
time, platform models are developed as sets of subsystems and technologies
that provide a coherent set of functionality through interfaces and specified
use patterns. A PIM is transformed into a platform-specific model (PSM) via
a mapping that consists of model transformations, i.e., rules or algorithms
that take objects in the PIM model language and generate (one or more)
objects in the PSM model language. Each mapping is therefore specific to
a particular platform. While the basic principles underlying our methodol-
ogy are similar to the MDA, our objectives are different and geared toward
a wider architecture-service exploration. We, therefore, use a mapping that
is more generic, and is intended to provide performance metrics rather than

generating a detailed implementation. Our notion of mapping makes it eas-
ier to adapt to different platforms, which in turn results in a more efficient
evaluation of design alternatives.
In addition to the tools inspired by the MDA, industrial approaches can
also be classified according to their ability of capturing functionality, describ-
ing architecture services, or aiding in the assignment of functionality to ser-
vices. Four approaches related to our work that follow this classification are
presented here.
An industrial tool for creating platform descriptions with mapping capa-
bilities (two of the three Y-chart branches) is the VaST Systems Technology’s
Comet/Meteor [60]. Comet focuses on creating high performance processor
and architecture models at the system level. This tool uses virtual processors,
buses, and peripheral devices to create candidate architectures, called virtual
system prototypes (VSP), for design-space exploration. The VSP models are
provided by VaST in the form of libraries or can be entered by the user in
C/C++/SystemC.
Meteor is an embedded software development environment for the
VSPs created by Comet. It interacts with VSPs for cycle-accurate simula-
tion and parameter-driven configuration. This process follows much more
closely a typical design process for a microprocessor including an optimiz-
ing code development, than our approach. A code is developed for a specific
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 295 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 295
VSP environment as opposed to capturing the pure functionality of an
application.
An industrial tool with functional, platform, and mapping capabilities (all
three branches of the Y chart) is the MLDesign’s MLDesigner [45]. This tool
supports discrete event, dynamic dataflow, synchronous dataflow, Boolean
dataflow, continuous time, and FSM MoCs. It is intended for a top-down
design flow starting from the initial specification to the final implementation.

The MLDesigner includes an integrated development environment (IDE) to
integrate all aspects in one package. The two major ways in which this work
differs from ours are in its inherent top-down nature and in the fact that it
supports a finite set (albeit large) of MoCs.
The Mirabilis Design’s Visual Sim [44] product family supports the same
MoCs natively as MLDesigner and also covers all three branches of the
Y chart. The design process in Visual Sim begins by constructing a model of
the system using a parameterizable library providedbyMirabilis. This model
can be augmented with C, C++, Java, SystemC, Verilog, or VHDL blocks.
The library blocks operate semantically using a wide variety of MoCs. The
design is then partitioned into software, middleware, and hardware. Finally,
the design is optimized by running simulations and adjusting parameters
of the library elements. The underlying simulation kernel is the Ptolemy. This
tool focuses very much on design-space exploration via the manipulation of
the library block parameters. Unlike our approach, it begins with a mono-
lithic design and refines it into its HW and SW components via a manual ad
hoc refinement process.
The closest approach to our work is the Cofluent’s Systems Studio [17]
that provides the transaction-level SystemC models to perform design-
space exploration using the Y-chart modeling methodology. The functional
description is a set of communicating processes executing concurrently. The
platform model is a set of communicating processes and shared memories
linked by shared communication nodes. The platform model has perfor-
mance attributes associated with it as well. This approach is very similar
to M
ETROPOLIS but does not support as wide a variety of MoCs or as rich a
constraint-verification infrastructure.
10.5.3 Academic Approaches
An approach similar to the MDA is model-integrated computing [32] (MIC).
It is based on the use of models for design and representation, and on the use

of generators to synthesize and integrate the system. In the MIC, the vehicles
for facilitating the design process are the models described in an appropri-
ate modeling language. Unlike the MDA, which uses the UML, the MIC is
based on the observation that a single modeling language is not suitable for
all embedded systems. Instead, domain-specific modeling languages must
be tailored to the needs of each particular domain. Thus, different modeling
languages are used to express the functionality, the architecture, and their