Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 266 2009-10-2
266 Model-Based Design for Embedded Systems
of decisions taken at a higher level of abstraction. Critical decisions instead
involve the abstraction levels and semantics with which the functionality and
the architecture are defined.
10.2.2.3 Design Parameters for PBD
In the PBD refinement-based design process, platforms should be defined
to eliminate large loop iterations for affordable designs. They should restrict
the design space via new forms of regularity and structure that surrender
some design potential for a lower cost and first-pass success. The library of
functional and communication components is the design space that we are
allowed to explore at the appropriate level of abstraction. Establishing the
number, location, and components of intermediate platforms is an essential
part of the PBD.
Designs with different requirements and specifications may use differ-
ent intermediate platforms, hence different layers of regularity and design-
space constraints. The trade-offs involved in the selection of the number
and characteristics of platforms relate to the size of the design space to
be explored and the accuracy of the estimation of the characteristics of
the solution adopted. Naturally, the larger the step across platforms, the
more difficult it is to predict the performance and provide tight bounds on
the performance. In fact, the design space for this approach may actually be
smaller than the one obtained with smaller steps because it becomes more
difficult to explore meaningful design alternatives and these restrictions
on search impede design-space exploration. Ultimately, predictions/abstrac-
tions may be so inaccurate that design optimizations are misguided and the
bounds are incorrect, leading to multiple design iterations.
The identification of precisely defined layers where the mapping pro-
cesses take place is an important design decision and should be agreed upon
at the top design-management level. Each layer supports a design stage
where the performance indexes that characterize the architectural compo-

nents provide an opaque abstraction of lower layers that allows accurate
performance estimations used to guide the mapping process. This approach
results in better reuse, because it decouples independent aspects, e.g., a given
functional specification to low-level implementation details, or to a specific
communication paradigm, or to a scheduling algorithm. It is very important
to define only as many aspects as needed at every level of abstraction, in the
interest of flexibility and rapid design-space exploration.
Success stories of the applications of these principles abound. For exam-
ple, in the semiconductor arena there are many examples of platforms
and of the PBD approaches. The NXP, ST, TI, and Renesas documented
this approach in public presentations and publications [20,23,29,65]. Among
system companies, Magneti-Marelli, BMW, GM, Pirelli, United Technolo-
gies Corporation, and Telecom Italia have demonstrated applications and
research interest in the PBD.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 267 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 267
10.3 METROPOLIS Design Environment
The METROPOLIS design environment was developed to embody the princi-
ples of the PBD. M
ETROPOLIS has its own specification language that is used
to capture functionality, architecture, and mapping, as well as a variety of
design activities.
10.3.1 Overview
The METROPOLIS specification language, the METROPOLIS meta-model (MMM),
is based on formal semantics and remains general enough to support exist-
ing MoCs [37] and accommodate new ones. The MMM also includes a logic
language to capture nonfunctional and declarative constraints. This meta-
model can support not only the functionality capture and analysis, but also
the architecture description and the mapping of functionality to architectural
elements. Because the MMM has a precise semantics, in addition to a simula-

tion M
ETROPOLIS is able to perform synthesis, and formal analysis for complex
electronic-system design.
The M
ETROPOLIS design environment supports three design activities:
specification, analysis, and synthesis.
• Specification serves to communicate the design intent and expected
results. It focuses on the interactions among people working at differ-
ent abstraction levels and among people working concurrently at the
same abstraction level. The MMM includes constraints that represent,
in an abstract form, requirements not yet implemented or assumed to
be satisfied by the rest of the system and its environment.
• Analysis determines how well an implementation satisfies the require-
ments through simulation and formal verification. A proper use of
abstraction can dramatically accelerate verification. An overuse of
detailed representations, on the other hand, can introduce exces-
sive dependencies between developers, reduce understandability, and
diminish the efficiency of analysis mechanisms.
• Synthesis is supportedacross the abstraction levels used in a design. The
typical problems we address include setting the parameters of architec-
tural elements such as cache sizes, or designing scheduling algorithms
and interface blocks. We also deal with synthesis of the final implemen-
tations in hardware and software. In M
ETROPOLIS, a specification may
mix declarative and executable constructs of the MMM, which are then
automatically translated into the semantically equivalent mathematical
models to which the synthesis algorithms are applied.
M
ETROPOLIS offers syntactic and semantic mechanisms to compactly store
and communicate all relevant design information. Designers can plug in

algorithms and tools for all possible design activities that operate on the
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 268 2009-10-2
268 Model-Based Design for Embedded Systems
design information. The capability of introducing external algorithms and
tools is important, because these needs vary significantly for different appli-
cation domains. To support this capability, M
ETROPOLIS provides a parser that
reads the MMM designs and a standard API that lets developers browse,
analyze, modify, and augment additional information within these designs.
For each tool integrated into M
ETROPOLIS, a back-end uses the API to generate
the required input by the tool from the relevant portion of the design.
10.3.2 METROPOLIS Meta-Model
The MMM is a language that specifies networks of concurrent objects, each
taking sequential actions. The behavior of a network is formally defined by
the execution semantics of the language [7,59]. A set of networks can be used
to represent all the aspects for designs, i.e., function, architecture, mapping,
refinement, abstraction, and platforms.
10.3.2.1 Function Modeling
The function of a system is described as a set of objects that concurrently take
actions while communicating with each other. Each such object is termed a
process in the MMM, and associated with a sequential program called a thread.
A process communicates through ports where a port is specified with an inter-
face, declaring a set of methods that can be used by the process through
the port. In general, one may have a set of implementations of the same
interface, and we refer to objects that implement port interfaces as media.
Any medium can be connected to a port if it implements the interface of
the port. This mechanism allows the MMM to separate computation by pro-
cesses from communication among them. This separation is essential to facil-
itate the description of the objects to be reused for other designs. Figure 10.2

shows a network of two producer processes and one consumer process that
communicate through a medium.
ltl G( beg(P0, M.write) −> !beg(P1, M.write) U end(P0, M.write) &&
beg(P1, M.write) −> !beg(P0, M.write) U end(P1, M.write)); }
process X {
port Read R;
port Write W;
void thread(){
while(true){
x = R.read();
z = foo(x);
W.write(z);
}
}
}
process X
name C
process X
name P1
process X
name P0
medium S
name M
medium S implements Read, Write {
int n, space;
int[] storage;
int read(){ }; int nItems(){ };
int write(){ }; int nSpace(){ };
}
interface Read extends Port {

update int read();
eval int nItems();
}
interface Write extends Port {
update int write(int data);
eval int nSpace();
}
constraint {
FIGURE 10.2
Functional model of two producers and one consumer. (From Balarin, F.
et al., IEEE Comput., 36, 45, April 2003. With permission.)
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 269 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 269
Once a network of processes is given, the behavior of the network is pre-
cisely defined by the MMM semantics as a set of executions. First, we define
an execution of a process as a sequence of events. Events are entries to or exits
from a piece of code by a program. For example, for process X in Figure 10.2,
the beginning of the call to R.read() is an event, as is its termination. The
execution of a network is then defined as a sequence of vectors of events,
where each vector has at the most one event for each process to define the
set of events that happen altogether. The MMM can model nondeterministic
behavior, which is useful to abstract a part of the design, and thus there may
be more than one possible executions of the network in general.
Constraints, written in logic formulas, further restrict the set of execu-
tions defining the set of legal executions [7,64]. For example, the constraint in
Figure 10.2 specifies the mutual exclusion of the two producers when one
calls the medium’s write method. Constraints describe the coordination of
processes or relate the behavior of networks through mapping or refinement.
10.3.2.2 Architecture Modeling
Architectures are distinguished by two aspects: the functionality they can

implement and that implementation’s efficiency. In the meta-model, the for-
mer is modeled as a set of services offered by an architecture to the functional
model. Services are just methods, bundled into interfaces [56].
To represent the efficiency of an implementation, we need to model the
cost of each service. This is done first by decomposing each service into a
sequence of events, and then annotating each event with a value representing
the cost of the event.
To decompose services into sequences of events, we use networks of
media and processes, just as in the functional model. These networks often
correspond to physical structures of implementation platforms.
For example, Figure 10.3 shows an architecture consisting of n pro-
cesses, T1, , Tn, and three media, CPU, BUS,andMEM. The architecture in
Figure 10.3 also contains so-called quantity managers, represented by
diamond-shaped symbols. The processes model software tasks executing on
a CPU, while the media model the CPU, bus, and memory. The services
offered by this architecture are the execute, read,andwrite methods imple-
mented in the Task processes. The thread function of a Task process repeatedly
and nondeterministically executes one of the three methods. In this way, we
model the fact that the Tasks are capable of executing these methods in any
order. The actual order will become fixed only after the system functional-
ity is mapped to this architecture, when each Task implements a particular
process of the functional model.
While a Task process offers its methods to the functional part of the sys-
tem, the process itself uses services offered by the CPU medium, which, in
turn, uses services of the BUS medium. In this way, the top-level services
offered by the Tasks are decomposed into sequences of events throughout
the architecture.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 270 2009-10-2
270 Model-Based Design for Embedded Systems
$}

cpu.execute(n);
}
void read() {

cpu.read();
}
void write() { }
void thread() { }
}
medium MEM implements SlaveService {
void read {
{$
// make request to Time
// for a memory read delay
$}
}
void write { }
}
medium
CPU
medium
BUS
medium
MEM
q–manager
BusArb
q–manager
Energy
q–manager
CpuArb

q–manager
Time
medium CPU implements CpuService {
prt BusService bus;
void execute(int n) {
{$
// make request to Time
// for a delay of n clock cycles
$}
}
void read() { bus.read(); }
void write() { bus.write(); }
}
medium BUS implements BusService {
port SlaveService mem;
void read() {
{$
// make request to BusArb
// to become bus master
$}
mem.read();
}
void write() { mem.write(); }
}
process Task
name T 1
process Task
name Tn
process Task {
port CpuService cpu;

void execute(int n) {
{$
// make request to CpuArb
// to become CPU owner
FIGURE 10.3
An architectural model. (From Balarin, F. et al., IEEE Comput., 36, 45, April 2003. With permission.)
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 271 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 271
The MMM includes the notion of quantity used to annotate individual
events with values measuring cost. For example, in Figure 10.3 there is a
quantity named energy used to annotate each event with the energy required
to process it. To specify that a given event takes a given amount of energy, we
associate with that event a request for that amount. These requests are made
to the object called quantity manager, which collects all requests and fulfills
them, if possible.
Quantities can also be used to model shared resources. For example, in
Figure 10.3, the quantity CpuArb labels every event with the task identifier
of the current CPU owner. Assuming that a process can progress only if it
is the current CPU owner, the CpuArb manager effectively models the CPU
scheduling algorithm.
The MMM has no built-in notion of time, but it can be modeled as yet
another quantity that puts an annotation, in this case a time stamp, on each
event. Managers for common quantities such as time are provided with
M
ETROPOLIS as standard libraries, and are understood directly by some tools
(e.g., time-driven simulators) for the sake of efficiency. However, quantity
managers can also be written by design flow developers, in order to support
quantities that are relevant for a specific application domain. When multi-
ple quantity managers coexist in the same architectural model, they often
need to interact with each other. For example, if the CpuArb manager decides

not to schedule a particular event, other quantity managers, such as Time
and Energy, do not need to annotate the same event. Therefore, the quantity
annotation process is iterative, and reaches a fixpoint at the end, where all
quantity managers agree on the annotations for all events.
10.3.2.3 Mapping
Evaluating a particular implementation’s performance requires mapping a
functional model to an architectural model. The MMM can do this without
modifying the functional and architectural networks. It does so by defining a
new network to encapsulate the functional and architectural networks, and
relates the two by synchronizing events between them. This new network,
called a mapping network, can be considered as a top layer that specifies the
mapping between the function and the architecture.
The synchronization mechanism roughly corresponds to an intersection
of the sets of executions of the functional and architectural models. Func-
tional model executions specify a sequence of events for each process, but
usually allow arbitrary interleaving of event sequences of the concurrent pro-
cesses, as their relative speed is undetermined. On the other hand, architec-
tural model executions typically specify each service as a timed sequence of
events, but exhibit nondeterminism with respect to the order in which ser-
vices are performed, and on what data. Mapping eliminates from the two sets
all executions except those in which the events that should be synchronized
always appear simultaneously. Thus, the remaining executions represent
timed sequences of events of the concurrent processes.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 272 2009-10-2
272 Model-Based Design for Embedded Systems
constraint { ltl G( beg(P0,P0.foo) <−>beg(T1,CPU.execute(50)) &&
end(P0,P0.foo) <−>end(T1,CPU.execute(50)) &&
beg(P0,M.write) <−>beg(T1,CPU.write) &&

end(P1,P1.foo) <−>end(T2,CPU.execute(50)) &&

end(C,C.foo) <−>end(T3,CPU.execute(50)) &&
)}

process Task
name T1
process Task
name T2
q−manager
BusArb
q−manager
Energy
q−manager
CpuArb
q−manager
Time
process X
name P1
process X
name C
process Task
name T3
process X
name P0
medium S
name M
constraint{ ltl G( beg(P0, M.write) −> !beg(P1, M.write) U end(P0, M.write) &&
beg(P1, M.write) −> !beg(P0, M.write) U end(P1, M.write)); }
medium
CPU
medium

BUS
medium
MEM
FIGURE 10.4
Mapping of function to architecture. (From Balarin, F. et al., IEEE Comput., 36, 45, April 2003. With permission.)
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 273 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 273
For example, Figure 10.4 shows a mapping network that combines the
functional network from Figure 10.2 with the architectural network from
Figure 10.3. The mapping network’s constraint clauses synchronize the
events of the two networks. For example, executions of foo, read,andwrite
by P0 have been synchronized with executions of execute, read,andwrite by
T1. Since P0 executes its actions in a fixed order while T1 chooses its actions
nondeterministically, the effect of synchronization is that T1isforcedtofol-
low the decisions of P0, while P0 “inherits” the quantity annotations of T1. In
other words, by mapping P0toT1 we make T1 become a performance model
of P0. Similarly, T2andT3 are made to be performance models of P1andC,
respectively.
10.3.2.4 Recursive Paradigm of Platforms
Suppose that a mapping network such as in Figure 10.4 has been obtained as
described above. One can consider such a network itself as an implementa-
tion of a certain service. The algorithm for implementing the service is given
by its functional network while its performance is defined by the architec-
ture counterpart. In Figure 10.5, the interface on the top defines methods
specifying a service, and the medium in the middle implements the inter-
face at the desired abstraction level. Underneath the medium is a mapping
network, providing a more detailed description of the implementation of the
service. The MMM can relate the medium and each network by using the
construct refine and constraints. For example, the constraints may say that
the begin event of mpegDecode of the medium is synchronized with the

begin event of vldGet of the VLD process in the network, and the end of
mpegDecode is synchronized with the end of yuvPut of the OUTPUT pro-
cess, while the value of the variable YUV at the event agrees with the output
value of mpegDecode.
In general, many mapping networks may exist for the same service with
different algorithms or architectures. Such a set of networks, together with
constraints on event relations for a given interface implementation, consti-
tutes a platform. The elements of the platform provide the same service with
different costs, and one is favored over another for given design require-
ments. This concept of platforms appears recursively in the design process.
In general, an implementation of what one designer conceives as the entire
system is a refinement of a more abstract model of a service, which is in turn
employed as a single component of the larger system. For example, a partic-
ular implementation of an MPEG decoder is given by a mapping network,
but its service may be modeled by a single medium, where the events gener-
ated in the medium are annotated with performance quantities to character-
ize the decoder. Such a medium may be used as a part of the architecture by
a company that designs set-top appliances. This medium serves as a model
used by the appliance company to evaluate the set-top box design, while the
same is used as design requirements by the provider of the MPEG decoder.
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 274 2009-10-2
274 Model-Based Design for Embedded Systems
constraint { ltl G( ); }
VideoData mpegDecode(ElemStream es){
// body of abstracted mpegDecode
}
interface MpegDecode extends Port{
update VideoData mpegDecode(ElemStream)
}
refine(AbsMpeg, MC1);

constraint{ }
constraint { ltl G( ); }
constraint { ltl G( ); }
medium AbsMpeg implements MpegDecode
FIGURE 10.5
Multiple mapping netlists refining the same service to form a platform. (From Balarin, F. et al., IEEE Comput., 36, 45, April
2003. With permission.)
Nicolescu/Model-Based Design for Embedded Systems 67842_C010 Finals Page 275 2009-10-2
Platform-Based Design and Frameworks: METROPOLIS and METRO II 275
Similarly, the MPEG decoder may use in its architecture a model of a bus
represented as a medium provided by another company or group. For the
latter, the bus design itself is the entire system, which is given by another
mapping network that refines the medium. This mapping network may be
only one of the candidates in the platform of the communication service, and
the designer of the MPEG decoder may explore various options based on his
design criteria.
This recursive paradigm of the PBD is described in a uniform way in the
MMM. The key is the formal semantics to precisely define the behavior of
networks, and the mechanism of relating events of different networks with
respect to quantities annotated with the events.
10.3.3 METROPOLIS Tools
The METROPOLIS environment includes tools to perform a variety of tasks,
some common, such as simulation and formal verification, and some more
specialized, such as property verification and synthesis. These tasks are
described in this section.
10.3.3.1 Simulation
Nondeterminism, inherent in the MMM, poses unique verification problems.
Traditionally, systems are verified by simulating their response to a given
set of stimuli. However, with nondeterminism, there may be many valid
responses, and it is impossible to know which one will be exhibited by the

final implementation. In [6], we have proposed a generic MMM simulation
algorithm that allows exhibiting one of the acceptable behaviors for a given
input stimulus. Which behavior is selected is to some extent under the user’s
control. The choice may be driven by different objectives at various design
stages. In the beginning, one may want any legal behavior to check for trivial
mistakes. At a later stage of the design, one may want to simulate as many
legal behaviors as possible in order to evaluate the design more thoroughly.
Another challenge comes from the orthogonalization of concerns prin-
ciple embodied in the MMM, which requires special treatment to gain effi-
cient simulation. In contrast, the simulation of traditional specifications with
monolithic modeling styles can be made efficient with much less effort.
In [63], by exploring the intrinsic characteristics of orthogonal concerns, we
came up with a series of optimization techniques that boost the simulation
performance by two orders of magnitude.
In M
ETROPOLIS, instead of generating the machine code directly from meta-
model descriptions, we translate the meta-model to an executable language,
which is combined with the simulation algorithm also implemented in the
same language. This feature is important to co-simulate designs captured
in the meta-model together with existing designs that have been already
specified in other languages. The actual simulation is then carried out in