Introduction to
Embedded Systems
Edward A. Lee and Prabal Dutta
UC Berkeley
EECS 149/249A
Fall 2017
Model Based Design
Modeling, Design, Analysis:
An Iterative Process
Modeling is the process of
gaining a deeper understanding
of a system through imitation.
Models specify what a system does.
Design is the structured creation of
artifacts. It specifies how a system does
what it does. This includes optimization.
Analysis is the process of gaining a deeper
understanding of a system through dissection.
It specifies why a system does what it does
(or fails to do what a model says it should do).
EECS 149/249A, UC Berkeley: 2
Focus on Models
Lee, Berkeley EECS 149/249A, UC Berkeley: 3
Models vs. Reality
The model In this example, the
modeling
framework is
calculus and
Newton’s laws.
The target
(the thing Fidelity is how well
being the model and its
modeled). target match
Lee, Berkeley EECS 149/249A, UC Berkeley: 4
Engineers often confuse the
model with its target
You will never strike oil by
drilling through the map!
But this does not in any way
diminish the value of a map!
Solomon Wolf Golomb
Lee, Berkeley 5
EECS 149/249A, UC Berkeley: 5
Determinacy
Some of the most valuable models
are deterministic.
A model is deterministic if, given the initial state and the
inputs, the model defines exactly one behavior.
Deterministic models have proven extremely valuable in
the past.
Lee, Berkeley EECS 149/249A, UC Berkeley: 6
Schematic of a simple embedded system
Lee, Berkeley EECS 149/249A, UC Berkeley: 7
Do deterministic models make sense for
embedded systems?
Unknowable delays
Packet losses
Uncontrollable scheduling
Unknowable
execution times
Physical noise
Parts failures Imperfect actuation
Lee, Berkeley EECS 149/249A, UC Berkeley: 8
A Model Need not be True to be Useful
“Essentially, all models are wrong, but
some are useful.”
Box, G. E. P. and N. R. Draper, 1987: Empirical Model-Building and
Response Surfaces. Wiley Series in Probability and Statistics, Wiley.
Let’s look at the most successful kinds of models
from the cyber and the physical worlds.
Lee, Berkeley EECS 149/249A, UC Berkeley: 9
Software is a Model
Physical System Model
Single-threaded imperative programs
are deterministic models
Lee, Berkeley EECS 149/249A, UC Berkeley: 10
Consider single-threaded
imperative programs
This program defines exactly one
behavior, given the input x.
Note that the modeling framework
(the C language, in this case)
defines “behavior” and “input.”
The target of the model is
nondeterministic (electrons
sloshing around in silicon).
Lee, Berkeley EECS 149/249A, UC Berkeley: 11
Software relies on another deterministic
model that abstracts the hardware
Physical System Model
Waterman, et al., The RISC-V Instruction Set Manual,
Image: Wikimedia Commons UCB/EECS-2011-62, 2011
Instruction Set Architectures (ISAs)
are deterministic models
Lee, Berkeley EECS 149/249A, UC Berkeley: 12
… which relies on yet another
deterministic model
Physical System Model
Synchronous digital logic
is a deterministic model
Lee, Berkeley EECS 149/249A, UC Berkeley: 13
Deterministic Models for the
Physical Side of Cyber Physical Systems
Physical System Model
Signal Signal
Image: Wikimedia Commons
Differential Equations
are deterministic models
Lee, Berkeley EECS 149/249A, UC Berkeley: 14
A Major Problem for CPS: Combinations of
Deterministic Models are Nondeterministic
Signal Signal
Lee, Berkeley Image: Wikimedia Commons EECS 149/249A, UC Berkeley: 15
A Story
In “fly by wire” aircraft,
computers control the
plane, mediating pilot
commands.
EECS 149/249A, UC Berkeley: 16
Abstraction Layers
The purpose of an
abstraction is to hide
details of the
implementation below
and provide a platform
for design from above.
EECS 149/249A, UC Berkeley: 17
Abstraction Layers
Every abstraction
layer has failed for
the aircraft designer.
The design is the
implementation.
EECS 149/249A, UC Berkeley: 18
Abstraction Layers
How about raising
the level of
abstraction to solve
these problems?
EECS 149/249A, UC Berkeley: 19
Higher abstractions rely on an
increasingly problematic fiction: WCET
WCET: worst case execution time
Ferdinand et al. [2001] determine the WCET of astonishingly
simple avionics code from Airbus running on a Motorola
ColdFire 5307, a pipelined CPU with a unified code and data
cache. Despite the software consisting of a fixed set of non-
interacting tasks containing only simple control structures, their
solution required detailed modeling of the seven-stage pipeline
and its precise interaction with the cache, generating a large
integer linear programming problem. (NP-complete problem)
Fundamentally, the ISA of the processor has failed to provide
an adequate abstraction. And the problem has gotten worse
since 2001!
EECS 149/249A, UC Berkeley: 20
Timing is not Part of
Software and Network Semantics
Correct execution of a program in all widely used
programming languages, and correct delivery of a network
message in all general-purpose networks has nothing to do
with how long it takes to do anything.
Programmers have to step outside the
programming abstractions to specify
timing behavior.
Embedded software designers
have no map!
Lee, Berkeley EECS 149/249A, UC Berkeley: 21
Determinism? Really?
CPS applications operate in an intrinsically
nondeterministic world.
Does it really make sense to insist on deterministic
models?
Lee, Berkeley EECS 149/249A, UC Berkeley: 22
The Value of Models
In science, the value of a model lies in how well its
behavior matches that of the physical system.
In engineering, the value of the physical system lies
in how well its behavior matches that of the model.
In engineering, model fidelity is a two-way street!
For a model to be useful, it is necessary
(but not sufficient) to be able to
construct a faithful physical realization.
Lee, Berkeley EECS 149/249A, UC Berkeley: 23
A Model
Lee, Berkeley EECS 149/249A, UC Berkeley: 24
A Physical Realization
Lee, Berkeley EECS 149/249A, UC Berkeley: 25
Model Fidelity
To a scientist, the model is flawed.
To an engineer, the realization is flawed.
I’m an engineer…
Lee, Berkeley EECS 149/249A, UC Berkeley: 26
For CPS, we need to
Change the Question
The question is not whether deterministic models can
describe the behavior of cyber-physical systems (with
high fidelity).
The question is whether we can build cyber-physical
systems whose behavior matches that of a deterministic
model (with high probability).
Lee, Berkeley EECS 149/249A, UC Berkeley: 27
Determinism?
What about Resilience? Adaptability?
Deterministic models do not eliminate the need for
robust, fault-tolerant designs.
In fact, they enable such designs, because they make it
much clearer what it means to have a fault!
Lee, Berkeley EECS 149/249A, UC Berkeley: 28
We have to fix the
models!
But how?
Lee, Berkeley EECS 149/249A, UC Berkeley: 29