What is an Embedded System (ES)?

Embedded basically reflects the facts that they are an integral part of
the system.

“ It is a computer system that is built to control one or a few dedicated

functions, and is not designed to be programmed by the end user in
the same way that a desktop computer is”

It Contains processing cores that are either Micro-controllers or DSPs.

“An embedded system is some combination of computer hardware

and software, either fixed in capability or programmable, that is
specifically designed for a particular function.”
Unit-2 EMBEDDED SYSTEMS 1
What is an Embedded System (ES)? Contd…

“Computing systems performing specific tasks

within a framework of real-world constraints”

“An Embedded System is a microprocessor based

system that is embedded as a subsystem, in a
larger system (which may or may not be a
computer system).”

“An ES is designed to run on its own without

human intervention, and may be required to
respond to events in real time”

Unit-2 EMBEDDED SYSTEMS 2

 Application of ES
Automotive: ECS, ABS; Aircraft
Network Appliances: Routers, Modems
Cell Phones, PDA, Mouse, E-Star Power
Printers, Hand Mixers, Toasters!

Unit-2 EMBEDDED SYSTEMS 3

 What is a real time system?
• A real-time system is one that must process
information and produce a response within a
specified time, else risk severe consequences,
including failure.

Unit-2 EMBEDDED SYSTEMS 4

 Modern Embedded Systems

DSP Application Analog

Code Specific Gates I/O

Processor
Memory
Cores

• Embedded systems employ a combination of

– application-specific h/w (boards, ASICs, FPGAs etc.)
• performance, low power
– s/w on prog. processors: DSPs, μcontrollers etc.
• flexibility, complexity
– mechanical transducers and actuators
Unit-2 EMBEDDED SYSTEMS 5
THE EMBEDDED SYSTEM DESIGN PROCESS

Unit-2 EMBEDDED SYSTEMS 6

 THE EMBEDDED SYSTEM DESIGN PROCESS
Embedded system design process aimed at two objectives:

1. It will give us an introduction to the various steps in embedded

system design before we delve into them in more detail.
2. It will allow us to consider the design methodology itself.

A design methodology is important for three reasons. ,

First, it allows us to keep a Scorecard on a design to ensure that we have done
everything we need to do, such as optimizing performance or performing
functional tests.
Second, it allows us to develop computer-aided design(CAD) tools. Developing
a single program that takes in a concept for an embedded system and emits a
completed design would be a daunting task, but by first breaking the process into
manageable steps, we can work on automating (or at least semi automating) the
steps one at a time.
Third, a design methodology makes it much easier for members of a design
team to communicate. Unit-2 EMBEDDED SYSTEMS 7
THE EMBEDDED SYSTEM DESIGN PROCESS Contd..

Unit-2 EMBEDDED SYSTEMS 8

 THE EMBEDDED SYSTEM DESIGN PROCESS Contd..

The major goals of the design:

■ manufacturing cost
■ performance (both overall speed and deadlines); and
■ power consumption.

We must also consider the tasks we need to perform at every step in

the design process. At each step in the design, we add detail:

■ We must analyze the design at each step to determine how we

can meet the specifications.
■ We must then refine the design to add detail.
■ And we must verify the design to ensure that it still meets all
system goals, such as cost, speed, and so on.

Unit-2 EMBEDDED SYSTEMS 9

 THE EMBEDDED SYSTEM DESIGN PROCESS Contd..

1. Requirements

-Creating the architecture and components.

-First, we gather an informal description from the customers known
as requirements, and we refine the requirements into a specification
that contains enough information to begin designing the system
architecture.

Requirements may be functional or nonfunctional

Typical nonfunctional requirements include:
■ Performance
■ Cost (manufacturing cost ; Nonrecurring engineering(NRE) costs)
■ Physical size and weight
■ Power consumption
Unit-2 EMBEDDED SYSTEMS 10
THE EMBEDDED SYSTEM DESIGN PROCESS Contd..

Sample requirements form.

Unit-2 EMBEDDED SYSTEMS 11

THE EMBEDDED SYSTEM DESIGN PROCESS Contd..

EX:
GPS Moving Map

What requirements might we have

for our GPS moving map?
Unit-2 EMBEDDED SYSTEMS 12
 THE EMBEDDED SYSTEM DESIGN PROCESS Contd..

Here is an initial list:

■ Functionality: This system is designed for highway driving and similar uses, not
nautical or aviation uses that require more specialized databases and functions.
The system should show major roads and other landmarks available in standard
topographic databases.
■ User interface: The screen should have at least 1080*2400 pixel resolution. The
device should be controlled by no more than three buttons. A menu system
should pop up on the screen when buttons are pressed to allow the user to make
selections to control the system.
■ Performance: The map should scroll smoothly. Upon power-up, a display should
take no more than one second to appear, and the system should be able to verify
its position and display the current map within 15 s.
■ Cost: The selling cost (street price) of the unit should be no more than $100.
■ Physical size and weight: The device should fit comfortably in the palm of the
hand.
■ Power consumption: The device should run for at least eight hours on four AA
batteries.
Unit-2 EMBEDDED SYSTEMS 13
THE EMBEDDED SYSTEM DESIGN PROCESS Contd..

Finally the Requirement form,

Unit-2 EMBEDDED SYSTEMS 14

THE EMBEDDED SYSTEM DESIGN PROCESS Contd..
2.Specification

Specification serves as the contract between the customer

and the architects.

Specification is probably the least familiar phase of this

methodology, but it is essential to creating working systems with a
minimum of designer effort.

The specification should be understandable enough so that

someone can verify that it meets system requirements and overall
expectations of the customer.

Unit-2 EMBEDDED SYSTEMS 15

 THE EMBEDDED SYSTEM DESIGN PROCESS Contd..

A specification of the GPS system would include several components:

■ Data received from the GPS satellite constellation.

■ Map data.
■ User interface.
■ Operations that must be performed to satisfy customer requests.
■ Background actions required to keep the system running, such as
operating the GPS receiver.

Unit-2 EMBEDDED SYSTEMS 16

 THE EMBEDDED SYSTEM DESIGN PROCESS Contd..
3. Architecture Design
The specification does not say how the system does things, only
what the system does. Describing how the system implements those
functions is the purpose of the architecture.

The architecture is a plan for the overall structure of the system

that
will be used later to design the components that make up the
architecture.

The creation of the architecture is the first phase of what many

designers think of as design.

Unit-2 EMBEDDED SYSTEMS 17

 THE EMBEDDED SYSTEM DESIGN PROCESS Contd..
3. Architecture Design

Figure below shows a sample system architecture in the form of a block

diagram that shows major operations and data flows among them.

Architectural descriptions must be designed to satisfy both functional and

nonfunctional requirements. Not only must all the required functions be
present, but we must meet cost, speed, power,and other nonfunctional
constraints.
Starting out with a system architecture and refining that to hardware and
software architectures,
Unit-2 EMBEDDED SYSTEMS 18
THE EMBEDDED SYSTEM DESIGN PROCESS Contd..
3. Architecture Design

Hardware

Software

Unit-2 EMBEDDED SYSTEMS 19

THE EMBEDDED SYSTEM DESIGN PROCESS Contd..
4. Designing Hardware and Software Components

The components will in general include both hardware—FPGAs,

boards, and so on and software modules.

Some of the components will be ready-made.

•In the moving map, GPS receiver is a predesigned standard
hardware component.
•Topographic software is a standard software module which uses
standard routines to access the database.
•Printed circuit board are the components which needs to be
designed.
You will have to design some components yourself.

Unit-2 EMBEDDED SYSTEMS 20

 THE EMBEDDED SYSTEM DESIGN PROCESS Contd..
5. System Integration
Bugs are typically found during system integration, and good planning can help us find
the bugs quickly.

By building up the system in phases and running properly chosen tests, we can often find
bugs more easily.

If we debug only a few modules at a time, we are more likely to uncover the simple bugs
and able to easily recognize them.
System integration is difficult because it usually uncovers problems.
It is often hard to observe the system in sufficient detail to determine exactly what is
wrong— the debugging facilities for embedded systems are usually much more limited
than what you would find on desktop systems.
As a result, determining why things do not set work correctly and how they can be fixed
is a challenge in itself.

Careful attention to inserting appropriate debugging facilities during design can help
ease system integration problems, but the nature of embedded computing means that
this phase will always be a challenge.
Unit-2 EMBEDDED SYSTEMS 21
 FORMALISMS FOR SYSTEM DESIGN
(STRUCTURAL DESCRIPTION & BEHAVIORAL DESCRIPTION)

It is often helpful to conceptualize these tasks( Top-Down Design

process) in diagrams.
Luckily, there is a visual language that can be used to capture all
these design tasks: the Unified Modeling Language(UML)

UML is an object-oriented modeling language

UML was designed to be useful at many levels of abstraction in
the design process.
UML is useful because it encourages design by successive
refinement and progressively adding detail to the design, rather
than rethinking the design at each new level of abstraction.

Unit-2 EMBEDDED SYSTEMS 22

 FORMALISMS FOR SYSTEM DESIGN contd..
(STRUCTURAL DESCRIPTION & BEHAVIORAL DESCRIPTION)

Object-Oriented design emphasizes two concepts

of importance:
■ It encourages the design to be described as a number of
interacting objects, rather than a few large monolithic blocks of
code.
▪At least some of those objects will correspond to real pieces of
software or hardware in the system.
▪We can also use UML to model the outside world that interacts
with our system, in which case the objects may correspond to
people or other machines.
▪It is sometimes important to implement a high level as a single
object using several distinct pieces of code or to otherwise break up
the object correspondence in the implementation.
Unit-2 EMBEDDED SYSTEMS 23
The principal component of an object-oriented design is, naturally enough, the object.
An object includes a set of attributes that define its internal state.
When implemented in a programming language, these attributes usually become variables
or constants held in a data structure.

An object describing a display (such as a CRT screen) is shown in UML notation in Figure

The text in the folded-corner page icon

is a note; it does not correspond to an
object in the system and only serves as a
comment.

The name is underlined to show that

this is a description of an object and not
of a class.

A class is a form of type definition—all objects derived from the same class have the
same characteristics, although their attributes may have different values.
A class defines the attributes that an object may have.
It also defines the operations that determine how the object interacts with the rest of the
world. Unit-2 EMBEDDED SYSTEMS 24
There are several types of relationships that can exist between objects and classes:

■ Association occurs between objects that communicate with each other but have no
ownership relationship between them.

■ Aggregation describes a complex object made of smaller objects.

■ Composition is a type of aggregation in which the owner does not allow access to the
component objects.

■ Generalization allows us to define one class in terms of another.

Unit-2 EMBEDDED SYSTEMS 25

 so far what we have seen is STRUCTURAL DESCRIPTION of UML

Next is BEHAVIORAL DESCRIPTION

To specify the behavior of an operation is by state machine.
These state machines will not rely on the operation of a clock, as in hardware; rather,
changes from one state to another are triggered by the occurrence of events.

3 types of Events defined by UML:

1.A signal is an asynchronous occurrence.

It is defined in UML by an object that is
labeled as a <<signal>>.
2. A call event follows the model of a
procedure call in a programming
language.

3. A time-out event causes the machine

to leave a state after a certain amount
of time. The label tm(time-value) on the
edge gives the amount of time after
which the transition occurs.
Unit-2 EMBEDDED SYSTEMS 26
 Design example: Model train controller

Learning of UML through Model Train Controller

Unit-2 EMBEDDED SYSTEMS 27

 Model train setup

rcvr motor

power
supply

console

ECC command address header

Unit-2 EMBEDDED SYSTEMS 28

Unit-2 EMBEDDED SYSTEMS

29
 Model train controller -

The user sends messages to the train with a control box attached to the tracks.

The control box may have familiar controls such as a throttle, emergency stop button, and so
on.

Since the train receives its electrical power from the two rails of the track, the control box
can send signals to the train over the tracks by modulating the power supply voltage.

The control panel sends packets over the tracks to the receiver on the train.

The train includes analog electronics to sense the bits being transmitted and a control system
to set the train motor’s speed and direction based on those commands.

Each packet includes an address so that the console can control several trains on the same
track; the packet also includes an error correction code (ECC) to guard against transmission
errors.

This is a one-way communication system—the model train cannot send commands back to the
user.
For design, we start with requirement first

Unit-2 EMBEDDED SYSTEMS 30

1.Requirements
Here is a basic set of requirements for the system:
■ The console shall be able to control up to eight trains on a single track.
■ The speed of each train shall be controllable by a throttle to at least 63 different
levels in each direction (forward and reverse).
■There shall be an inertia control that shall allow the user to adjust the responsiveness
of the train to commanded changes in speed.
■ There shall be an emergency stop button.
■ An error detection scheme will be used to transmit messages.

We can put the requirements into our chart format:

Unit-2 EMBEDDED SYSTEMS 31

 2. Specifications
The Digital Command Control (DCC) standard
was created by the National Model Railroad Association to support interoperable
digitally-controlled model trains.

The DCC standard is given in two documents:

■ Standard S-9.1, the DCC Electrical Standard, defines how bits are encoded on
the rails for transmission.
■ Standard S-9.2, the DCC Communication Standard, defines the packets that
carry information.

DCC Communication Standard

The basic Packet format PSA(sD)+E

P is the Preamble-atleast a sequence of atleast 10 -1 bits
S is the packet start bit. It is a 0 bit
A is an address data byte-8 bits long
s is the data start bit. It is a 0 bit
D is the data byte contain instruction data or Error correction information
E is the packet end bit.
Unit-2 EMBEDDED SYSTEMS 32
Basic system commands

Unit-2 EMBEDDED SYSTEMS 33

Typical control sequence

:console :train_rcvr
set-inertia
set-speed

set-speed

estop

set-speed

Unit-2 EMBEDDED SYSTEMS 34

 Conceptual Specification
Digital Command Control specifies some important aspects of the system,
particularly those that allow equipment to interoperate. But DCC deliberately does
not specify everything about a model train control system

There are clearly two major subsystems:

The command unit and the train-board
component as shown in Fig1.

Fig1: Class diagram for the train controller messages.

Fig2: UML collaboration diagram for major subsystems of the train controller
system
Unit-2 EMBEDDED SYSTEMS 35
Let’s break down the command unit and receiver into their
major components.

The console needs to perform three functions:

•Read the state of the front panel on the command unit

•Format messages
•Transmit messages

The train receiver must also perform three major functions:

•Receive the message

•Interpret the message (taking into account the current speed,
inertia setting, etc.)
•Control the motor.

Unit-2 EMBEDDED SYSTEMS 36

Fig: A UML class diagram for the train controller showing the composition of the subsystems

Unit-2 EMBEDDED SYSTEMS 37

The Console class describes the command unit’s front panel,
which contains the analog knobs and hardware to interface to
the digital parts of the system.

■ The Formatter class includes behaviors that know how to read

the panel knobs and creates a bit stream for the required
message.

■ The Transmitter class interfaces to analog electronics to send

the message along the track.

■ Knobs* describes the actual analog knobs, buttons, and levers

on the control panel.
■ Sender* describes the analog electronics that send bits along
the track.

Unit-2 EMBEDDED SYSTEMS 38

Likewise, the Train makes use of three other classes that define
its components:

■ The Receiver class knows how to turn the analog signals on the
track into digital form.

■ The Controller class includes behaviours that interpret the

commands and figures out how to control the motor.

■ The Motor interface class defines how to generate the analog

signals required to control the motor.

■ Detector* detects analog signals on the track and converts

them into digital form.
■ Pulser* turns digital commands into the analog signals
required to control the motor speed.
Unit-2 EMBEDDED SYSTEMS 39
Detailed Specification

knobs* pulser*

train-knob: integer pulse-width: unsigned-

speed-knob: integer integer
inertia-knob: unsigned- direction: boolean
integer
emergency-stop: boolean

sender* detector*

send-bit() read-bit() : integer

Unit-2 EMBEDDED SYSTEMS 40

Panel and motor interface classes

panel motor-interface

speed: integer
train-number() : integer
speed() : integer
inertia() : integer
estop() : boolean
new-settings()

Unit-2 EMBEDDED SYSTEMS 41

Transmitter and receiver classes

transmitter receiver

current: command
new: boolean
send-speed(adrs: integer,
speed: integer)
send-inertia(adrs: integer, read-cmd()
val: integer)
new-cmd() : boolean
set-estop(adrs: integer)
rcv-type(msg-type:
command)
rcv-speed(val: integer)
rcv-inertia(val:integer)

Unit-2 EMBEDDED SYSTEMS 42

Formatter class
Formatter class holds state for
each train, setting for current
formatter train.
The operate() operation
performs the basic formatting
current-train: integer task.
current-speed[ntrains]: integer
current-inertia[ntrains]:
unsigned-integer
current-estop[ntrains]: boolean

send-command()
panel-active() : boolean
operate()

Unit-2 EMBEDDED SYSTEMS 43

 Control input sequence diagram
:knobs :panel :formatter :transmitter
change in read panel
control panel-active
change in speed/

settings
inertia/estop

panel settings send-command

read panel
send-speed,
send-inertia.
panel settings
send-estop
read panel
change in
train number

train panel settings

change in

number
new-settings

set-knobs

Unit-2 EMBEDDED SYSTEMS 44

Formatter operate behavior

update-panel()

panel-active() new train number

idle

send-command()
other

Unit-2 EMBEDDED SYSTEMS 45

 Panel-active behavior

T
current-train = train-knob
panel*:read-train() update-screen
changed = true
F

T
panel*:read-speed() current-speed = throttle
changed = true

... ...

Unit-2 EMBEDDED SYSTEMS 46

 ARM Architecture Version
About Advanced RISC Machine
• Instructions are same size : 32 bit
• Instructions are executed in 1 clock cycle
• Load/Store access memory

• Advantage:
– Number of transistors are less compared to similar CISC
architecture.
– Less hardware results in less die size
– Low power consumption

Unit-2 EMBEDDED SYSTEMS 47

Unit-2 EMBEDDED SYSTEMS 48
Unit-2 EMBEDDED SYSTEMS 49
Unit-2 EMBEDDED SYSTEMS 50
Unit-2 EMBEDDED SYSTEMS 51
Unit-2 EMBEDDED SYSTEMS 52
Unit-2 EMBEDDED SYSTEMS 53
Unit-2 EMBEDDED SYSTEMS 54
Unit-2 EMBEDDED SYSTEMS 55
Unit-2 EMBEDDED SYSTEMS 56
Unit-2 EMBEDDED SYSTEMS 57
Unit-2 EMBEDDED SYSTEMS 58
Unit-2 EMBEDDED SYSTEMS 59
Unit-2 EMBEDDED SYSTEMS 60
Unit-2 EMBEDDED SYSTEMS 61
Unit-2 EMBEDDED SYSTEMS 62
Unit-2 EMBEDDED SYSTEMS 63
Unit-2 EMBEDDED SYSTEMS 64
Unit-2 EMBEDDED SYSTEMS 65
Unit-2 EMBEDDED SYSTEMS 66
Unit-2 EMBEDDED SYSTEMS 67
Unit-2 EMBEDDED SYSTEMS 68
Unit-2 EMBEDDED SYSTEMS 69
Unit-2 EMBEDDED SYSTEMS 70
Unit-2 EMBEDDED SYSTEMS 71
 Features of ARM Instruction set
• ARM –RISC Processor which every instruction
has a maximum size of 32 bits.
• Instruction are executed in one cycle.
• Load store architecture-All the computations
are register based. Before computation all
operations are register based.
• ALU has a barrel shifter.(performing shift and
Rotate)
• Conditions can be append to the instructions.

Unit-2 EMBEDDED SYSTEMS 72

 Little Endian and Big Endian Format
• A 32 bit data needs 4 bytes of space required
defined by 4 consecutive address.
• When the lowest byte of 32 bit word stored in
lowest of these address it is called little endian
format.
• Otherwise Big endian Format.
bit 31 bit 0 bit 0 bit 31

byte 3 byte 2 byte 1 byte 0 byte 0 byte 1 byte 2 byte 3

little-endian big-endian

Unit-2 EMBEDDED SYSTEMS 73

Unit-2 EMBEDDED SYSTEMS 74
Unit-2 EMBEDDED SYSTEMS 75
Unit-2 EMBEDDED SYSTEMS 76
Unit-2 EMBEDDED SYSTEMS 77
Unit-2 EMBEDDED SYSTEMS 78
Unit-2 EMBEDDED SYSTEMS 79
Unit-2 EMBEDDED SYSTEMS 80
Unit-2 EMBEDDED SYSTEMS 81
Unit-2 EMBEDDED SYSTEMS 82
Unit-2 EMBEDDED SYSTEMS 83
Unit-2 EMBEDDED SYSTEMS 84
Unit-2 EMBEDDED SYSTEMS 85
Unit-2 EMBEDDED SYSTEMS 86
Unit-2 EMBEDDED SYSTEMS 87
Unit-2 EMBEDDED SYSTEMS 88
Unit-2 EMBEDDED SYSTEMS 89
Unit-2 EMBEDDED SYSTEMS 90
Unit-2 EMBEDDED SYSTEMS 91
Unit-2 EMBEDDED SYSTEMS 92
Unit-2 EMBEDDED SYSTEMS 93
 • Example-1

B NEW ;transfers control

unconditionally to location
NEW
STOP B STOP ;Continually
branches to its own label STOP

• Example-2
BNE LOOP ; Branch to LOOP if
Zero flag is set
MOV r5,#0
LOOP ADD r2,r3,r4
Unit-2 EMBEDDED SYSTEMS 94
Unit-2 EMBEDDED SYSTEMS 95
Stacks and Subroutines/Procedures

Unit-2 EMBEDDED SYSTEMS 96

Stacks and Subroutines/Procedures

Unit-2 EMBEDDED SYSTEMS 97

Unit-2 EMBEDDED SYSTEMS 98
Unit-2 EMBEDDED SYSTEMS 99
Unit-2 EMBEDDED SYSTEMS 100
Unit-2 EMBEDDED SYSTEMS 101
 CPUs
• Input and output.
• Supervisor mode, exceptions, traps.
• Co-processors.

Unit-2 EMBEDDED SYSTEMS 102

 I/O devices

• Usually includes some non-digital

component.
• Typical digital interface to CPU:
statu

mechanism
s
CPU reg
data
reg

Unit-2 EMBEDDED SYSTEMS 103

 Application: 8251 UART
• Universal asynchronous receiver transmitter
(UART) : provides serial communication.
• 8251 functions are integrated into standard
PC interface chip.
• Allows many communication parameters to
be programmed.

Unit-2 EMBEDDED SYSTEMS 104

 Serial communication

• Characters are transmitted separately:

no
char
bit bit ... bit stop
start
0 1 n-1
time

Unit-2 EMBEDDED SYSTEMS 105

Serial communication parameters
• Baud (bit) rate.
• Number of bits per character.
• Parity/no parity.
• Even/odd parity.
• Length of stop bit (1, 1.5, 2 bits).

Unit-2 EMBEDDED SYSTEMS 106

 8251 CPU interface

statu
s
(8
CPU xmit/
bit) 8251
data rcv
serial
(8
port
bit)

Unit-2 EMBEDDED SYSTEMS 107

 Programming I/O
• Two types of instructions can support I/O:
– special-purpose I/O instructions;
– memory-mapped load/store instructions.
• Intel x86 provides in, out instructions. Most
other CPUs use memory-mapped I/O.
• I/O instructions do not preclude
memory-mapped I/O.

Unit-2 EMBEDDED SYSTEMS 108

 ARM memory-mapped I/O
• Define location for device:
DEV1 EQU 0x1000
• Read/write code:
LDR r1,#DEV1 ; set up device adrs
LDR r0,[r1] ; read DEV1
LDR r0,#8 ; set up value to write
STR r0,[r1] ; write value to device

Unit-2 EMBEDDED SYSTEMS 109

 Interrupt I/O
• Busy/wait is very inefficient.
– CPU can’t do other work while testing device.
– Hard to do simultaneous I/O.
• Interrupts allow a device to change the flow of
control in the CPU.
– Causes subroutine call to handle device.

Unit-2 EMBEDDED SYSTEMS 110

 Interrupt interface

intr request statu

mechanism
s
intr ack
PC

reg
IR

CPU
data/address data
reg

Unit-2 EMBEDDED SYSTEMS 111

 Interrupt behavior
• Based on subroutine call mechanism.
• Interrupt forces next instruction to be a
subroutine call to a predetermined location.
– Return address is saved to resume executing
foreground program.

Unit-2 EMBEDDED SYSTEMS 112

 Interrupt physical interface
• CPU and device are connected by CPU bus.
• CPU and device handshake:
– device asserts interrupt request;
– CPU asserts interrupt acknowledge when it can
handle the interrupt.

Unit-2 EMBEDDED SYSTEMS 113

 Priorities and vectors
• Two mechanisms allow us to make interrupts
more specific:
– Priorities determine what interrupt gets CPU first.
– Vectors determine what code is called for each
type of interrupt.
• Mechanisms are orthogonal: most CPUs
provide both.

Unit-2 EMBEDDED SYSTEMS 114

 Prioritized interrupts

device 1 device 2 device n

interrupt
acknowledge

L1 L2 .. Ln
CPU

Unit-2 EMBEDDED SYSTEMS 115

 Interrupt prioritization
• Masking: interrupt with priority lower than
current priority is not recognized until pending
interrupt is complete.
• Non-maskable interrupt (NMI):
highest-priority, never masked.
– Often used for power-down.

Unit-2 EMBEDDED SYSTEMS 116

 Example: Prioritized I/O
:foregrou
:interrupts :A :B :C
nd

A,
B

Unit-2 EMBEDDED SYSTEMS 117

 Interrupt vectors

• Allow different devices to be handled by

different code.
• Interrupt vector table:
Interrupt handler 0
vector
handler 1
table head
handler 2
handler 3

Unit-2 EMBEDDED SYSTEMS 118

Interrupt vector acquisition

:CPU :device

receive
request
receive
ack
receive
vector

Unit-2 EMBEDDED SYSTEMS 119

 Generic interrupt mechanism
continue intr?
Assume priority selection is
N
execution Y handled before this
point.
N intr priority >
ignore current
priority?
Y

ack
Y
Y N
bus error timeout? vector?
Y

call table[vector]

Unit-2 EMBEDDED SYSTEMS 120

 Interrupt sequence
• CPU acknowledges request.
• Device sends vector.
• CPU calls handler.
• Software processes request.
• CPU restores state to foreground program.

Unit-2 EMBEDDED SYSTEMS 121

 Sources of interrupt overhead
• Handler execution time.
• Interrupt mechanism overhead.
• Register save/restore.
• Pipeline-related penalties.
• Cache-related penalties.

Unit-2 EMBEDDED SYSTEMS 122

 ARM interrupts
• ARM7 supports two types of interrupts:
– Fast interrupt requests (FIQs).
– Interrupt requests (IRQs).
• Interrupt table starts at location 0.

Unit-2 EMBEDDED SYSTEMS 123

 ARM interrupt procedure
• CPU actions:
– Save PC. Copy CPSR to SPSR.
– Force bits in CPSR to record interrupt.
– Force PC to vector.
• Handler responsibilities:
– Restore proper PC.
– Restore CPSR from SPSR.
– Clear interrupt disable flags.

Unit-2 EMBEDDED SYSTEMS 124

 ARM interrupt latency
• Worst-case latency to respond to interrupt is
27 cycles:
– Two cycles to synchronize external request.
– Up to 20 cycles to complete current instruction.
– Three cycles for data abort.
– Two cycles to enter interrupt handling state.

Unit-2 EMBEDDED SYSTEMS 125

 Supervisor mode
• May want to provide protective barriers
between programs.
– Avoid memory corruption.
• Need supervisor mode to manage the various
programs.

Unit-2 EMBEDDED SYSTEMS 126

 ARM supervisor mode
• Use SWI instruction to enter supervisor mode,
similar to subroutine:
SWI CODE_1
• Sets PC to 0x08.
• Argument to SWI is passed to supervisor
mode code.
• Saves CPSR in SPSR.

Unit-2 EMBEDDED SYSTEMS 127

 Exception
• Exception: internally detected error.
• Exceptions are synchronous with instructions
but unpredictable.
• Build exception mechanism on top of
interrupt mechanism.
• Exceptions are usually prioritized and
vectorized.

Unit-2 EMBEDDED SYSTEMS 128

 Trap
• Trap (software interrupt): an exception
generated by an instruction.
– Call supervisor mode.
• ARM uses SWI instruction for traps.

Unit-2 EMBEDDED SYSTEMS 129

 Models of programs
In this section , we develop models for programs that are more
general than source code like ALP, C …and so on...

• Source code is not a good representation for

programs:
– clumsy;
– leaves much information implicit.
• Compilers derive intermediate representations
to manipulate and optimize the program.

Our fundamental model for programs is the

control/data flow graph (CDFG).
Unit-2 EMBEDDED SYSTEMS 130
 Data flow graph
• DFG: data flow graph.
• Does not represent control.
• Models basic block: code with one entry and
exit.
• Describes the minimal ordering requirements
on operations.

Unit-2 EMBEDDED SYSTEMS 131

 Single assignment form
w = a + b; w = a + b;
x = a – c; x 1 = a – c;
y = x + d; y = x1 + d;
x = a + c; x2 = a + c;
z = y + e; z = y + e;
original basic block single assignment form

Unit-2 EMBEDDED SYSTEMS 132

• There are two assignments to the variable x—it appears twice on
the left side of an assignment.

• We need to rewrite the code in single-assignment form, in which

a variable appears only once on the left side.

• Since our specification is C code, we assume that the statements

are executed sequentially, so that any use of a variable refers to
its latest assigned value.

• In this case, x is not reused in this block (presumably it is used

elsewhere), so we just have to eliminate the multiple assignment
to x.

• The result is shown, where we have used the names x1 and x2 to

distinguish the separate uses of x.

Unit-2 EMBEDDED SYSTEMS 133

 Data flow graph

w = a + b;
x 1 = a – c;
y = x1 + d;
x2 = a + c;
z = y + e;
single assignment
form

Unit-2 EMBEDDED SYSTEMS 134

 SDFGs
• Here the variables are not
a b c d e explicitly represented by
nodes.
+ + - • Instead the edges are
labeled with the variables
x w
x they represent.
2 1
+ • As a result a variable can be
represented by more than
y one edge.
+ • The edges are directed and
all the edges for the variable
z must come from single
source.
• We use this form for its
simplicity and compactness.
Unit-2 EMBEDDED SYSTEMS 135
 Control-data flow graph
• CDFG: represents control and data.
• Uses data flow graphs as components.
• Two types of nodes:
– decision;
– data flow.

Unit-2 EMBEDDED SYSTEMS 136

Encapsulates a data flow graph:
Data flow node
Write operations in basic block form for simplicity.

x = a + b;
y=c+d

T v1 v4
cond value

F v2 v3

Equivalent forms

Unit-2 EMBEDDED SYSTEMS 137

 CDFG example
if (cond1) bb1(); T
cond bb1()
else bb2(); 1
F
bb3();
switch (test1) { bb2()

case c1: bb4(); break;

case c2: bb5(); break; bb3()
case c3: bb6(); break;
} c1 test1
c3

c2
bb4() bb5() bb6()

Unit-2 EMBEDDED SYSTEMS 138

 for loop
for (i=0; i<N; i++)
loop_body(); i=0

for loop
F
i<N
i=0;
T
while (i<N) {
loop_body(); i++; }
loop_body()
equivalent

Unit-2 EMBEDDED SYSTEMS 139

 Assembly , linking, loading
• Assembly and linking are the last steps in the compilation process.
• they turn a list of instructions into an image of the program’s bits in
memory.
• Loading actually puts the program in memory so that it can be
executed.

HLL assembl
assembl
HLL
HLL compiler assembl
yy assembler
y

Object
Object
Code
Code

Executab
loader le linker
Binary

Unit-2 EMBEDDED SYSTEMS 140

 Assembly , linking, loading
• As the figure shows, most compilers do not directly generate
machine code, but instead create the instruction-level
program in the form of human-readable assembly language.
• The assembler’s job is to translate symbolic assembly
language statements into bit-level representations of
instructions known as object code.
• A linker allows a program to be stitched together out of
several smaller pieces. The linker operates on the object files
created by the assembler and modifies the assembled code to
make the necessary links between files.
• The linker, which produces an executable binary file.
• That file may not necessarily be located in the CPU’s memory,
however, unless the linker happens to create the executable
directly in RAM.
• The program that brings the program into memory for
execution is called a loader.
Unit-2 EMBEDDED SYSTEMS 141
 Assemblers
• Major tasks: When translating assembly code
into object code
--generate binary for symbolic instructions;
--translate labels into addresses;
--Labels make the assembly process more
complex, but they are the most important
abstraction provided by the assembler.
– handle pseudo-ops (data, etc.).
• Generally one-to-one translation.

Unit-2 EMBEDDED SYSTEMS 142

 Assemblers Contd…
• Label processing requires making two passes
through the assembly source code
as follows:
1. The first pass scans the code to determine
the address of each label.
2. The second pass assembles the instructions
using the label values computed in the first
pass.

Unit-2 EMBEDDED SYSTEMS 143

• The name of each symbol and its address is stored in a symbol table that is
built during the first pass.
• During scanning, the current location in memory is kept in a program
location counter (PLC). The PLC is not used to execute the program, only to
assign memory locations to labels(Like Program Counter).
• If the instruction begins with a label, a new entry is made in the symbol
table, which includes the label name and its value.
• The value of the label is equal to the current value of the PLC.
• At the end of the first pass, the assembler rewinds to the beginning of the
assembly language file to make the second pass.
• During the second pass, when a label name is found, the label is looked up
in the symbol table and its value substituted into the appropriate place in
the instruction.

Unit-2 EMBEDDED SYSTEMS 144

 Generating a symbol table
• ORG 100
label1 ADR r4,c
LDR r0,[r4]
label2 ADR r4,d
LDR r1,[r4]
label3 SUB r0,r0,r1

Unit-2 EMBEDDED SYSTEMS 145

 Pseudo-operations
• Pseudo-ops do not generate instructions:
– ORG sets program location.
– EQU generates symbol table entry without
advancing PLC.
– Data statements define data blocks.

Unit-2 EMBEDDED SYSTEMS 146

 Linking
• Many assembly language programs are written as
several smaller pieces rather than as a single large
file.
• A linker allows a program to be stitched together out
of several smaller pieces.
• The linker operates on the object files created by the
assembler and modifies the assembled code to make
the necessary links between files.
• Combines several object modules into a single
executable module.

Unit-2 EMBEDDED SYSTEMS 147

 • Some labels will be both
defined and used in the
same file. Other labels will
be defined in a single file
but used elsewhere.
• The place in the file where a
label is defined is
known as an entry point.
• The place in the file where
the label is used is called an
external reference.

Unit-2 EMBEDDED SYSTEMS 148

The linker proceeds in two phases.
• First, it determines the address of the start of each object file.
• The order in which object files are to be loaded is given by the user,
either by specifying parameters when the loader is run or by
creating a load map file that gives the order in which files are to be
placed in memory.
• Given the order in which files are to be placed in memory and the
length of each object file, it is easy to compute the starting address
of each file.
• At the start of the second phase, the loader merges all symbol
tables from the object files into a single, large table.
• It then edits the object files to change relative addresses into
addresses.
• This is typically performed by having the assembler write extra bits
into the object file to identify the instructions and fields that refer
to labels.
• If a label cannot be found in the merged symbol table, it is
undefined and an error message is sent to the user.

Unit-2 EMBEDDED SYSTEMS 149

 Loading
• The main job of the loader is to resolve external
references based on available entry points.
• As a result of the need to know how definitions and
references connect, the assembler passes to the
linker not only the object file but also the symbol
table.
• Even if the entire symbol table is not kept for later
debugging purposes, it must at least pass the entry
points.
• External references are identified in the object code
by their relative symbol identifiers.

Unit-2 EMBEDDED SYSTEMS 150

 COMPILATION TECHNIQUES
It is useful to understand how a high-level language program is
translated into instructions.

Understanding how the compiler works can help you know when
you cannot rely on the compiler.

Next, because many applications are also performance sensitive,

understanding how code is generated can help you meet your
performance goals, either by writing high-level code that gets
compiled into the instructions you want or by recognizing when you
must write your own assembly code.

Compilation combines translation and optimization.

Unit-2 EMBEDDED SYSTEMS 151

 Compilation
• Compiler determines quality of code:
– use of CPU resources;
– memory access scheduling;
– code size.

Unit-2 EMBEDDED SYSTEMS 152

Basic compilation phases
•The high-level language
program is parsed to
HLL break it into statements
and expressions.
•In addition, a symbol table
parsing, symbol table is generated, which
includes all the named
objects in the program.
machine-independent
optimizations •Simplifying arithmetic
expressions is one
example of a
machine-dependent
Optimizations machine-independent
optimization.
•Instruction –level
assembly optimization and code
Unit-2 EMBEDDED SYSTEMS generation 153
 Statement translation and
optimization
• Source code is translated into intermediate
form such as CDFG.
• CDFG is transformed/optimized.
• CDFG is translated into instructions with
optimization decisions.
• Instructions are further optimized.

Unit-2 EMBEDDED SYSTEMS 154

 Compiling an Arithmetic expressions
DFG
expression

a*b + 5*(c-d)
a b c d
W,X,Y,Z are temp variables

* -
5
X
W *

Unit-2 EMBEDDED SYSTEMS 155

Compilation of Arithmetic expressions,
cont’d.
a b c d ADR r4,a
MOV r1,[r4]
1 + 2 - ADR r4,b
MOV r2,[r4]
5 ADD r3,r1,r2

ADR r4,c
3 * MOV r1,[r4]
ADR r4,d
MOV r5,[r4]
SUB r6,r4,r5
4 +
MUL r7,r6,#5
ADD r8,r7,r3

DFG code

Unit-2 EMBEDDED SYSTEMS 156

Similarly for Control Structure code generation

if (a+b > 0)
x = 5;
T
else a+b>0 x=5
x = 7;

x=7

Unit-2 EMBEDDED SYSTEMS 157

 Control code generation, cont’d.

ADR r5,a
LDR r1,[r5]
ADR r5,b
1 a+b>0 x=5 2 LDR r2,b
ADD r3,r1,r2
BLE label3
LDR r3,#5
3 x=7 ADR r5,x
STR r3,[r5]
B stmtent

LDR r3,#7
ADR r5,x
STR r3,[r5]
stmtent ...
Unit-2 EMBEDDED SYSTEMS 158
 Procedure linkage
Another major code generation problem is the creation of
procedures
• Need code to:
– call and return;
– pass parameters and results.
• Parameters and returns are passed on stack.
– Procedures with few parameters may use
registers.

Unit-2 EMBEDDED SYSTEMS 159

 Procedure stacks

growth
proc1(int a) {
proc1 proc2(5);
}
FP
frame pointer
(defines the end of the Last frame)
proc2
5 accessed relative to SP
SP
stack pointer
(defines the end of the current frame)

When a new procedure is called, the sp and fp are modified to push

Unit-2 EMBEDDED SYSTEMS 160
another frame onto the stack.
 Data structures
The compiler must also translate references to data structures into
references to raw memories. In general, this requires address
computations.
• Different types of data structures use different
data layouts.
• Some offsets into data structure can be
computed at compile time, others must be
computed at run time.
• An array element must in general be
computed at run time, since the array index
may change.
• Let us first consider one-dimensional arrays:
Unit-2 EMBEDDED SYSTEMS 161
 One-dimensional arrays

• C array name points to 0th element:

a a[0]
= *(a + 1)
a[1]

a[2]

Unit-2 EMBEDDED SYSTEMS 162

 Two-dimensional arrays

• Column-major layout:
a[0,0]
M
a[0,1]
...
N

... a[1,0]
= a[i*M+j]
a[1,1]

Unit-2 EMBEDDED SYSTEMS 163

 Program-level performance analysis
•Embedded systems must perform functions in
real time, we often need to know how fast a
program runs.
•The techniques we use to analyze program
execution time are also helpful in analyzing
properties such as power consumption.
•we study how to analyze programs to estimate
their run times.

Unit-2 EMBEDDED SYSTEMS 164

 Program-level performance analysis
• Need to understand performance in detail:
– Real-time behavior, not just typical.
– On complex platforms.
• Program performance ≠ CPU performance:
– Pipeline, cache are windows into program.
– We must analyze the entire program.

Unit-2 EMBEDDED SYSTEMS 165

 Complexities of analyzing program
performance
• The execution time of a program often varies
with the input data values because those values
select different execution paths in the program.
- For example, loops
• Cache effects.
– The cache’s behavior depends in part on the data
values input to the program.
• Instruction-level performance variations:
– Pipeline interlocks.
– Fetch times.

Unit-2 EMBEDDED SYSTEMS 166

 How to measure program performance
• Simulate execution of the CPU (Simulator).
– Makes CPU state visible.
– Be careful for some microprocessor performance
simulators are not 100% accurate, and simulation of
I/O-intensive code may be difficult.
– Also measures execution time of program
• Measure on real CPU using timer.
– A timer connected to the microprocessor bus can be
used to measure performance of executing sections of
code.
– Requires modifying the program to control the timer.
• Measure on real CPU using logic analyzer.
– By measuring the start and stop times of a code segment
– Requires events visible on the pins.
Unit-2 EMBEDDED SYSTEMS 167
 Program performance metrics
• Average-case execution time.
– Typically used in application programming.
• Worst-case execution time.
– A component in deadline satisfaction.
• Best-case execution time.
– Task-level interactions can cause best-case
program behavior to result in worst-case system
behavior.

Unit-2 EMBEDDED SYSTEMS 168

 Elements of program performance
• The key to evaluating execution time is breaking the
performance problem into parts.

• Basic program execution time formula:

execution time = program path + instruction timing

– The path is the sequence of instructions executed by the

program (or its equivalent in the high-level language
representation of the program).

– The instruction timing is determined based on the

sequence of instructions traced by the program path,
which takes into account data dependencies, pipeline
behaviour, and caching.
Unit-2 EMBEDDED SYSTEMS 169
Data-dependent paths in an if statement
Here is a pair of nested if statements a b c path

0 0 0 T1=F, T3=F: no assignments

if (a || b) { /* T1 */
if ( c ) /* T2 */ 0 0 1 T1=F, T3=T: A4

x = r*s+t; /* A1 */ 0 1 0 T1=T, T2=F: A2, A3

else y=r+s; /* A2 */
0 1 1 T1=T, T2=T: A1, A3
z = r+s+u; /* A3 */
} 1 0 0 T1=T, T2=F: A2, A3
else {
1 0 1 T1=T, T2=T: A1, A3
if ( c ) /* T3 */
y = r-t; /* A4 */ 1 1 0 T1=T, T2=F: A2, A3
}
1 1 1 T1=T, T2=T: A1, A3

Unit-2 EMBEDDED SYSTEMS 170

 Paths in a loop

for (i=0, f=0; i<N; i++)

i=0
f = f + c[i] * x[i]; f=0

• The CDFG makes it clear

Loop N
that the loop initiation block exit i<N
is executed once, the test is
Y
executed N +1 times, and
the body and loop variable f = f + c[i] * x[i]
update are each executed N
times. i=i+1

Unit-2 EMBEDDED SYSTEMS 171

 Instruction timing
Once we know the execution path of the program, we have to measure the execution time of
the instructions executed along that path.

However , even ignoring cache effects, this technique is simplistic for the reasons summarized
below.
• Not all instructions take the same amount of time.
– Multi-cycle instructions (RISC, Fixed length instruction)
– Fetches.
• Execution times of instructions are not independent.
(many CPUs use register bypassing to speed up instruction sequences when
the result of one instruction is used in the next instruction.)
– Pipeline interlocks.
– Cache effects.
• Execution times may vary with operand value.
– This is clearly true of floating-point instructions in which a different
number of iterations may be required to calculate the result
– Some multi-cycle integer Unit-2
operations.
EMBEDDED SYSTEMS 172
 Measurement-driven performance
analysis
• Not so easy as it sounds:
– Must actually have access to the CPU.
– Must know data inputs that give worst/best case
performance.
– Must make state visible.
• Still an important method for performance
analysis.

Unit-2 EMBEDDED SYSTEMS 173

 Measurement-driven performance
analysis
•Most methods of measuring program performance
combine the determination of the execution path and
the timing of that path : as the program executes, it
chooses a path and we observe the execution time
along that path.
•We refer to the record of the execution path of a
program as a program trace (or more succinctly, a
trace).
•Traces can be valuable for other purposes, such as
analyzing the cache behaviour of the program .

Unit-2 EMBEDDED SYSTEMS 174

 Measurement Issues-Feeding the
program
• Need to know the desired input values.
• May need to write software scaffolding to
generate the input values.
• Software scaffolding may also need to
examine outputs to generate feedback-driven
inputs.

Unit-2 EMBEDDED SYSTEMS 175

 Profiling
• Profiling is a method for analyzing software
performance.
• A profiler doesn’t measure execution
time-instead it counts the number of times
that procedure executed.
• Modifying executable program by adding
instructions that increment the location every
time the program passes that point.

Unit-2 EMBEDDED SYSTEMS 176

 Physical Measurement
• To Watch the program counter value, Start the timer
when PC reached the start point and stop the timer
when it reaches end.
• In-circuit emulator allows tracing.
– Affects execution timing.
• Logic analyzer can measure behavior at pins.
– Address bus can be analyzed to look for events.
– Code can be modified to make events visible.
• Particularly important for real-world input streams.

Unit-2 EMBEDDED SYSTEMS 177

 Hardware Traces
• Some processors generate trace information
by means of special bus cycle, a trace message
that shows source and destination address of
a branch.

CPU simulation
• Some simulators are less accurate.
• Cycle-accurate simulator provides accurate
clock-cycle timing.
– Simulator models CPU internals.
– Simulator writer must know how CPU works.
Unit-2 EMBEDDED SYSTEMS 178