Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 276 2009-10-2
276 Model-Based Design for Embedded Systems
terms of the resulting language. We have tested this simulation approach in
SystemC 2.0 [49], Java [3], and C++ with a thread library. In addition, we
have devised a service-based formalism [62] that can effectively integrate
models specified at different abstraction levels, in different specification lan-
guages, and with different MoCs. We also enhanced our simulation tool
to support the co-simulation of these heterogeneous models. Further, this
service-based formalism became the foundation of the second generation of
the M
ETROPOLIS environment, covered in Section 10.4.
10.3.3.2 Formal Property Verification
Both academia and industry have long studied formal property verification,
but the state-explosion problem restricts its usefulness to protocols and other
high abstraction levels. At the implementation level or other low abstraction
levels, hardware and software engineers have used simulation monitors as
basic tools to check simulation traces while debugging designs.
Verification languages, such as Promela, which are used by the Spin
model checker [28], allow only simple concurrency modeling and are not
amenable to the system design specification, which requires complex syn-
chronization and architecture constraints. In contrast, M
ETROPOLIS,withits
formal semantics, automatically generates verification models for all the lev-
els of the design [15].
Our translator automatically constructs the Spin verification model from
the MMM specification, taking care of all system-level constructs. For exam-
ple, it can automatically generate a verification model for the example in
Figure 10.2 and verify the medium’s nonoverwriting properties. Further, as
the translator refines the design through structural transformation and archi-
tectural mapping, it can prove more properties, including throughput and
latency. This kind of property verification typically requires several minutes

of computation on a 1.8 GHz Xeon machine with 1 Gbyte of memory. When
the state space complexity becomes too high, M
ETROPOLIS uses an approxi-
mate verification and provides the user with a confidence factor on the pass-
ing result.
10.3.3.3 Simulation Monitor
Simulation monitors offer an attractive alternative to formal property verifi-
cation. In M
ETROPOLIS, designers can use logic of constraints (LOC) formulas
[7] to specify quantitative properties. The system can automatically translate
the specification to simulation monitors in C++ [16], thus relieving design-
ers from the tedious and error-prone task of writing monitors in the simula-
tor’s language. The monitors analyze the traces and report any LOC formula
violations. Like any other simulation-based approach, this one can only dis-
prove an LOC formula if it finds a violation—it can never prove conclusively
the formula’s correctness because that would require exhaustively analyzing
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 277 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 277
traces. The automatic trace analyzer can be used in concert with model check-
ers. It can perform property verification on a single trace even when other
approaches would fail because of their excessive memory and space require-
ments.
In our experience with applying the automatic LOC-monitor technique
to large designs with complex traces, we have found that in most cases the
analysis completes in minutes and consumes only hundreds of bytes of data
memory to store the LOC formulas. The analysis time tends to grow linearly
with the trace size, while the memory requirement remains constant regard-
less of the trace size.
10.3.3.4 Quasi-Static Scheduling
We have developed an automatic synthesis technique called quasi-static

scheduling (QSS) [19] to schedule a concurrent specification on computa-
tional resources that provide limited concurrency. The QSS considers a sys-
tem to be specified as a set of concurrent processes communicating through
the FIFO queues, and generates a set of tasks that are fully and statically
scheduled, except for data-dependent controls that can be resolved only
at runtime. A task usually results from merging parts of several processes
together and shows less concurrency than the initial specification. Moreover,
the QSS allows interprocess optimizations that are difficult to achieve if pro-
cesses remain separated, such as replacing interprocess communication with
assignments.
This technique proved particularly effective and allowed us generate a
production-quality code with improved performance. Applying the QSS to
a significant portion of an MPEG-2 decoder resulted in a 45% increase in the
overall performance.
The assumptions that the QSS requires for the input specification form
a subset of what the MMM can represent. Therefore, when integrating the
QSS into the M
ETROPOLIS framework, we addressed two main problems: how
to verify if a design satisfies the required set of rules and how to convey all
relevant design information to the QSS tool.
We addressed the first problem by providing a library of interfaces and
communication media that implement a FIFO communication model. Those
parts of the design optimized with the QSS need to use these communication
primitives.
To convey relevant design information to the QSS, we use a back-end tool
that translates a design to be scheduled with the QSS into a Petri net speci-
fication, which is QSS’s underlying model. The QSS then uses the Petri net
to produce a new set of processes. These new processes show no interpro-
cess communication because the QSS removes it. The processes communicate
with the environment using the same primitives implemented in the library.

The new code can thus be directly plugged into the MMM specification as a
refinement of the network selected for scheduling.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 278 2009-10-2
278 Model-Based Design for Embedded Systems
10.4 METRO II Design Environment
METRO II [21] is the successor to METROPOLIS [8]. METRO II was developed at
the University of California, Berkeley, starting in 2006. The following sec-
tions introduce the reader to the goals of M
ETRO II, the components of the
framework, and the mapping and execution semantics used.
10.4.1 Overview
The second-generation METRO II framework is based on considerations
derived from the limitations of M
ETROPOLIS we experienced in a set of designs
that were carried out in collaboration with our industrial partners. These con-
siderations are as follows.
1. Heterogeneous IP import. IP providers create models using domain-
specific languages and tools. Requiring a singular form of design entry
in a system-level environment requires complex translation of the orig-
inal specification into the new language while making sure that seman-
tics is preserved. If different designs or different components within the
same design can have different semantics, the heterogeneity has to be
supported by the new environment. There are two main challenges that
have to be addressed: wrapping and interconnecting the IP.
First, IPs can be described in different languages and can have dif-
ferent semantics that can be tightly related to a particular simulator.
Importing the IP entails providing a way of exposing the IP interface.
The user must have the necessary aids to define wrappers that medi-
ate between the IP and the framework such that the behavior can be
exposed in an unambiguous way.

Secondly, wrapped components have to be interconnected. Even if
the interfaces are exposed in a unified way, interconnecting them is
not usually a straightforward process. The data and the flow of control
between IP blocks must be exposed in such a way that the framework
has sufficient visibility.
2. Behavior-performance orthogonalization. For design frameworks that sup-
port multiple abstraction levels, different implementations of the same
basic functionality may have the same behavioral representations but
different costs. For instance, different processors will be abstracted into
the same programmable components. What distinguishes them is the
performance vs. cost trade-off. Moreover, not all metrics are considered
or optimized simultaneously. It should be possible to introduce perfor-
mance metrics during the design process, as the design proceeds from
specification to implementation.
The specification of what a component does should be independent
of how long it takes or how much power it consumes to carry out a
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 279 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 279
task. This is the reason why we introduce dedicated components, called
annotators, to annotate quantities to events.
A distinction has to be made between quantities used just to track the
value of a specific metric of interest and quantities whose value is used
for synchronization. For instance, time is used to synchronize actions
and it is not merely a number that is computed based on the state evo-
lution of the system. For quantities that influence the evolution of the
system, special components, called schedulers, are provided to arbitrate
shared resources.
The separation of schedulers from annotators allows for a sim-
pler specification and provides a cleaner separation between behavior
and performance. As a result, instead of a two-phase execution as in

M
ETROPOLIS, the execution semantics become three phase.
3. Mapping specification. Mapping relates the functional and architectural
models to realize the system model. The specification of this mapping
must be carried out such that there is minimal modification to the func-
tional and architectural models themselves.
Following the PBD approach, we want to keep the functionality and
the architecture separate. The implementation of the functionality on
the architecture is achieved in the mapping step. In order to explore
several different implementations with minimal effort, the design envi-
ronment needs to provide a fast and an efficient way of mapping with-
out modifying either the functional or the architectural model much. In
M
ETROPOLIS, this is achieved by event-level synchronization constraints,
as shown in [22]. While providing a powerful way to link the models,
this approach breaks the encapsulation of the models by allowing con-
straints between arbitrary pairs of events and allowing access to any
local variables in the scope of the events. Also, since there are no spe-
cial declarative constructs for mapping, this process of finding events
and setting up constraints is not easy for designers to manipulate and
debug.
In M
ETRO II, we restrict the mapping to be at the service level, i.e., the
only accessible events for synchronization constraints are the begin/end
events of interface methods in function and architecture models. Also,
the only accessible values are parameters and return values of the inter-
face methods. This coarser granularity and a more restrictive map-
ping approach maintain the IP encapsulation and make mapping more
robust for designers.
10.4.2 METRO II Design Elements

An initial implementation of the METRO II framework has been carried out
in SystemC 2.2. The framework has been tested under Linux, Solaris, and
cygwin.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 280 2009-10-2
280 Model-Based Design for Embedded Systems
sc_eventsc_module
Method
Port
Event
Interface
Mapper Adaptor
Component
Constraint
solver
Annotator
Scheduler
Manager
Implementation platform:
SystemC 2.2
M
ETRO II core
FIGURE 10.6
Implementation of M
ETRO II.
The infrastructure is summarized in Figure 10.6. The sc_event and
sc_module classes from SystemC are leveraged directly to derive the cor-
responding event and component classes in M
ETRO II.
The connection and coordination of components are carried out through
events. The event is a key concept in M

ETRO II. It is formally defined as a tuple
< p, T, V >, where p is a process that generates the event, T is a tag set, and
V is a set of associated values. Tags are used to describe the semantics of the
system and values are used to represent the states of the system.
Methods, interfaces, and ports are built on the concept of event. A method
is characterized by a pair of begin and end events. An interface contains one
or more methods. Ports are associated with interfaces, and only ports with
compatible interfaces can be connected. A component can have zero or more
ports. To handle different aspects of the events, special objects are defined,
including annotators, schedulers, and constraint solvers. Annotators anno-
tate events with quantities, schedulers coordinate the execution sequence of
events, and constraint solvers resolve the declarative constraints on events.
Mappers and adaptors are defined to interconnect components. Mappers
bridge the function methods and architecture services. Adaptors intercon-
nect components with heterogeneous MoCs. Finally, the manager coordi-
nates the execution of all the objects using three-phase execution semantics.
Figure 10.7 illustrates the major M
ETRO II elements. We attempt to use the
iconography here throughout the work. A snippet of the M
ETRO II code for
a reader component, a mapper, a scheduler, and an annotator in a typical
producer–consumer design example is shown in the figure. More details of
these elements are introduced below.
10.4.2.1 Components
A component is an object that encapsulates an imperative code in a
design, either functional or architectural. Components interface with other
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 281 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 281
Wrapper
Component

View port
Required
port
Provided
port
Annotator
Constraint
solver
Scheduler
IP
Event
<proc, tag, value>
M2_INTERFACE(i_func_receiver)
{
public:
M2_TWOARG_PROCEDURE(receive, void *, unsigned long);
};
M2_COMPONENT(Reader)
{
public:
m2_required_port<i_func_receiver> out_port;
sc_process_handle this_thread;
SC_HAS_PROCESS(Reader);
Reader(sc_module_name n) : m2_component(n)
{
SC_THREAD(main);
}
void main()
{
this_thread = sc_get_current_process_handle();

int array[3];
for (int i=0; i<5; i++)
{ out_port->receive(array, 3 * sizeof(int)) }
}
};
c_double_handshake c("rendezvous");
Writer w("Writer");
Reader r("Reader");
M2_CONNECT(r, out_port, c, read_port);
M2_CONNECT(w, out_port, c, write_port);
//mapper definition
class receive_mapper: public m2_mapper<i_func_receiver, i_arch_receiver>
{
public:
receive_mapper(sc_module_name name) :
m2_mapper<i_func_receiver, i_arch_receiver>(name)
{}
void receive(void * data, unsigned long len){
out_port->receive(data, len, 1000);}
};
//instantiation
receive_mapper r_mapper("receive_mapper");
//mapping between ports
M2_MAP(r, out_port, r_mapper, p, read_port);
// setup physical time annotator
std::vector<m2_event *> ptime_event_list;
ptime_event_list.push_back(r.read_event_end);
ptime_event_list.push_back(w.write_event_end);
std::map<const char*, double, ltstr> ptime_table;
ptime_table[r.read_event_end->get_full_name()]=1;

ptime_table[w.write_event_end->get_full_name()]=2;
m2_physical_time_annotator* ptime=new
m2_physical_time_annotator("pt_annotator",ptime_event_list,&ptime_table);
register_annotator(ptime);
// setup logical time scheduler
m2_logical_time_scheduler* ltime = new
m2_logical_time_scheduler("lt_scheduler");
ltime->add_event(r.read_event_beg);
ltime->add_event(r.read_event_end);
ltime->add_event(w.write_event_beg);
ltime->add_event(w.write_event_end);
register_scheduler(ltime);
Mapper
FIGURE 10.7
Overview of M
ETRO II design elements.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 282 2009-10-2
282 Model-Based Design for Embedded Systems
components via ports. There are two descriptions of component composi-
tion: atomic components and composite components. An atomic component
is a block specified in some language and is viewed by the framework as a
black box with only its interface information exposed. A composite compo-
nent is a group of one or more objects as well as any connections between
them. When an existing IP is being imported, it will be encapsulated by
a wrapper, which translates and exposes the appropriate events and inter-
faces from the IP. The wrapped IP becomes an atomic component in the
framework.
10.4.2.2 Ports
Components can interface with each other via ports. Each port is character-
ized by an interface that contains a set of methods. A method consists of

a sequence of events, with a unique begin/end event pair. Variables in the
scope of the begin event are method arguments. Variables in the scope of the
end event are return values.
By setting constraints between events associated with the ports of dif-
ferent components, the execution of these components can be coordinated.
There are two types of ports: required ports and provided ports. Required
ports are used by components to request methods that are implemented in
other components. Provided ports are used by components to provide meth-
ods to other components. Connections between components are made only
between a required port and a provided port with the same interface. The
execution semantics that coordinate a pair of required and provided ports
will be introduced in Section 10.4.3.
10.4.2.3 Constraint Solvers
Constraints are used to specify the design via declarative means, as opposed
to imperative specification which is contained in components. Constraints
are described in terms of events: their status (enabled or disabled), their tags,
and the values associated with them. The events referenced by constraints
must be exposed by ports.
Constraint solvers are objects that resolve these declaration constraints
during runtime. Depending on the status, tags, and values of the events, con-
straint solvers decide whether to enable or disable events, thereby coordinat-
ing the execution of components.
Designers can derive various constraint solvers from the base class solver
provided by the M
ETRO II infrastructure. The main function to be imple-
mented is the one to resolve the constraints. In M
ETRO II, a synchronization
constraint solver is provided. Two events that are specified in a synchroniza-
tion constraint need to be enabled at the same time—during simulation, they
need to be enabled in the same iteration. Further examples will be given in

Section 10.4.3. Synchronization constraints are used for mapping between
the functionality and the architecture, as is explained later.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 283 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 283
10.4.2.4 Annotators and Schedulers
In M
ETROPOLIS, both the performance annotation and the scheduling of events
were carried out by a type of special component called a quantity man-
ager. As stated before, to have a more clear separation of design concerns,
these two aspects will be handled separately by annotators and schedulers
in M
ETRO II.
Annotators annotate events with quantities by writing tags. Each tag that
represents some quantity (such as power and physical time) is determined
in terms of the parameters supplied to the annotator, the status of the event,
and the values of the event. Parameters are given by the designers based
on the characterization of the architecture platforms. Only static parameters
are permitted for annotators, which may not have their own state. For vari-
ous quantities or quantities in various systems, designs can derive their own
annotators from the annotator base class in M
ETRO II. Currently, a physical
time annotator is provided in the M
ETRO II library.
The instantiation of a physical time annotator is shown in Figure 10.7. The
r.read_event_end and w.write_event_end are events associated with a reader
and writer component, respectively. These two events are added to a list of
events to be considered for annotation. In addition, a table indexed by these
events is created along with the assigned time units required for execution
(1 and 2 units, respectively). This list and the table are then added to the
annotator object itself. If these events are present during the second phase of

execution, their tags will be updated accordingly.
Schedulers coordinate the execution of the components by enabling/dis-
abling the events proposed by the processes of the components. Based on
the local state of the scheduler, the status of the events, as well as their val-
ues and tags, the scheduler determines the scheduling of the events. A base
class scheduler is provided in M
ETRO II for designers to derive various sched-
ulers. A logical time scheduler that schedules the events based on the physi-
cal time tags, and a round-robin scheduler that schedules the access to shared
resources are provided as library schedulers. An example using the logical
time scheduler is shown in the code snippet in Figure 10.7.
10.4.2.5 Mappers
As a framework based on the PBD, M
ETRO II supports mapping through map-
pers, which synchronize the begin and end events of the functional meth-
ods and architectural methods. Designers are only allowed to specify map-
ping at this service level, with access to the parameters and return values of
the methods. When the begin/end events in the functional and architectural
methods are synchronized, the parameters and return values can be trans-
fered between the two models. For instance, a functional method may have
one parameter that the corresponding architectural method is unaware of.
During mapping, the value of this parameter can be passed to the architec-
tural method for its usage. M
ETRO II provides an API to specify mappers at
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 284 2009-10-2
284 Model-Based Design for Embedded Systems
the service level. The implementation of mappers is a synchronization con-
straint solver with value passing of parameters and return values.
An example of a mapper is shown in Figure 10.7. This mapper is called
“receive_mapper” and is used to map the consumer in a producer–consumer

design example to a processing element, p. During mapping when the
receive method is called by the functional model with two arguments, the
mapper’s out_port will call the architectural model’s receive method that has
three arguments. Also shown in Figure 10.7 are the instantiation of the map-
per along with how the mapper is connected between the functional model
and the architectural model.
10.4.2.6 Adaptors
There are various ways of handling heterogeneous MoCs in a design. One of
the most common approaches is the hierarchical composition as in Ptolemy II
[38]. With the hierarchical composition, each level of the hierarchy is homo-
geneous, i.e., a single MoC exists at each level, while different interaction
mechanisms are allowed to be specified at different levels in the hierarchy
[26]. To allow models in two heterogeneous MoCs to communicate, a third
MoC may need to be found within which the two will be embedded.
In our experience, there is a strong need to interconnect heterogeneous
models directly at the same level. For instance, the user may want to connect
the output of a base-band-processing component (described by a dataflow
model) to the input of an RF component (described by a continuous-time
model). This way of handling complexity does not require changing the
interface of a model in order to behave like another model. This is in line
with one of our main concerns: being able to reuse IPs in different contexts.
The complexity of this approach lies in designing the correct intercon-
nections between different MoCs. To bridge the different semantics of het-
erogeneous components, we use adaptors to modify events as they pass
from one component to another. Denotationally, an adaptor is a relation,
A ⊆ (V × T) × (V

× T

), that maps events from one model to events of

another model.
Adaptors are connected with components through specialized adaptor
channels. In the PBD methodology, adaptors can be regarded as the bridge
between heterogeneous functional components or between heterogeneous
architectural components. The M
ETRO II infrastructure provides the base
classes of adaptors and adaptor channels. M
ETRO II also includes an exam-
ple of adaptors between dataflow and finite-state machine (FSM) semantics.
10.4.3 METRO II Semantics
Like METROPOLIS, the semantics of the METRO II framework will be cen-
tered around the connection and coordination of components. The execu-
tion semantics discussed here are involved in the simulation of a system for
design-space exploration.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 285 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 285
10.4.3.1 Three-Phase Execution
M
ETRO II has three-phase execution semantics. In order to discuss this seman-
tics, two other concepts must be introduced: process states and event states.
In Figure 10.8, the states that an event can have are shown. Events can
be inactive, proposed, and annotated. All events begin as inactive. As the
self loop shows, they can remain inactive indefinitely. When a method call
on a required port generates an event it becomes proposed. It will then be
annotated. If the event is then deemed appropriate to enable (via a variety of
scheduling decisions) it will transition to inactive again.
Each process in
METRO II has two states: running and suspended. Processes
execute concurrently until an event is proposed on a required port of the
component containing the process or until they are blocked on a provided

port. At this point they transition to the suspended state. Once the event
is enabled or the internal blocking is resolved, the processes return to the
running state.
Based on this treatment of events, the design is partitioned into three
phases of execution. In the first phase, processes propose possible events; the
second phase associates tags with the proposed events; and the third phase
allows a subset of the proposed events to execute.
1. Base model execution. The base model consists of concurrently exe-
cuting processes that may suspend only after proposing events or by
3b. Enable some events
Phase 2Phase 1
FC
FC
AC
1. Block processes at interfaces 2. Annotate events
Event enabled by CS
Event disabled
by CS and must
be reannotated
Event disabled by CS
but keeps annotation
Event proposed by processPropose event(s) or block
Enable event or resume process
M
ETRO II process states
Running
Suspended
Start
M
ETRO II event states

Event annotated
ProposedInactive
Annotated
AC
Phase 3
Physical
time
Constraint
solver
3a. Schedule
resolution
Resource
scheduler
Logical
time
FIGURE 10.8
M
ETRO II three-phase execution semantics.