Embedded AI Control

Chair for Embedded Systems

Prof. Dr. -Ing Roman Obermaisser, Dr. -Ing Daniel Onwuchekwa
&
Dr Hassan Sabo Miya
Centre For Embedded AI and Smart Energy Systems
ATBU
Course Book
• Introduction to Embedded
Systems:
A Cyber-Physical Systems Approach
• E.A. Lee, S.A. Seshia
• Version 2.2
• Second Edition, MIT Press, 2017
• 585 pages
• The new chapter 7 covers sensors
and actuators with an emphasis
on modeling
• Also available to
download:
[Link] 2
What are Embedded Systems?
• Systems designed to perform a specific (dedicated) function.
• Combination of both hardware and software.
• Examples of embedded systems include:
• Automobile: engine controls, brakes, seatbelts, airbag, and audio
systems.
• Household appliances: Microwave, refrigerator, washing machine,
and dishwashers.
• Industrial applications: Process control in chemical plants, used to
command robots on factory floors etc.
• Aviation: Controls in aircraft, brake, landing gears etc.
• Railway: Train traction control, passenger systems, etc.

3
Embedded Systems Challenge
• The key engineering problem of embedded systems:
• coping with limited resources, e.g.
• limited processing power,
• limited energy sources,
• small memories, etc.
• The engineering challenge is to optimize the designs.

•Recently, it is understood that the principal challenges

in embedded systems stem from their interaction
with physical processes, and not only from their
limited resources.

4
Introduction - Applications
• Cyber-physical system (CPS) – integration of
computation, networking and physical processes.
• The behaviour of the resulting system is defined by both cyber
and physical process
• Intersection of physical and cyber.

• Not sufficient separately understand the physical components

and the computational components

5
 Examples and applications

V2V cooperation for Fly-by-wire

Heart Surgery • Lighter
[2] easy traffic flow [4]
[3] • Computer mediates
between pilot’s
command and
actuator

• Other examples include Tele-surgery, drive assist, robotic manufacturing

aid, distributed computer games .
• All safety-critical systems

6
Application - Overview

7
Goals of the course
• Goal of the Course “Embedded Control”
A principled, scientific approach to designing and implementing embedded
control systems

With Focus on:

• How to model and design the joint dynamics of computation, networks, and
physical processes.
• Application fields of embedded control systems
• Models of embedded control systems and working methods to
develop embedded control systems
• State-of-the-art of development tools for real-time simulation and
rapid control prototyping (such as MATLAB/Simulink or SCILAB/XCOS).

8
Design Process

9
Book Map

10
Continuous Dynamics
• Newtonian Mechanics
• Actor Models
• Properties of a
System
• Feedback Control

11
Newtonian Mechanics

12
Newtonian Mechanics
• Changes in position or orientation are governed by the second law of
Newton.

note
∀ 𝑡 > 0,

initial velocity in three directions

∀ 𝑡 > 0,

To Obtain the position

Note The parameters are vectors.

13
Newtonian Mechanics
• Again the torque T is related to the moment of inertia.

Orientation is the integral of rotational

velocity

14
Newtonian Mechanics-Model-order reduction

15
Actor Models
• Continuous-time system can be modelled as a box with input
port and an output port.

𝑥 : ℝ → ℝ y: ℝ → ℝ
Domain -> time, codomain -> value of the signal
S: 𝑋 → 𝑌
• The box above is called an actor : as the input are functions and
the outputs are functions.
• The actor above depends on parameters p, and q and are written
in the box.

16
Properties of a system
• Causal Systems
• Memoryless Systems
• Linearity and Time invariance
• Stability

17
Causal system

18
Memoryless Systems

19
Linearity and Time Invariance

20
Stability

21
Feedback Control
• A feedback system is one in which the output of the system is
fed back to affect the input of the same system.

• The above diagram is a proportional control feedback

loop.
• The control signal is proportional to the error.

22
Summary
• Discussed continuous dynamics – modelled using
differential equations.
• Concept of the actor model was discussed.
• Properties of a system: Causal, linearity, stability ….
• Finally the feedback control system was briefly introduced.

23
Discrete Dynamics
• Discrete Systems
• The Notion of State
• Finite-State machines
• Extended State machines
• Nondeterminism
• Behaviours and Traces
• Summary

24
Discrete
Systems
• A system that operates in a sequence of discrete steps.
• A discrete event occurs at an instant of time rather than over
time.

25
Discrete
Systems
• The dynamics of a discrete system can be described as a sequence
of steps called reactions.
• A reaction observes the values of the inputs at a particular time t,
and calculate the output values for that same time t.

26
The Notion of State

27
Finite-State Machines

28
Finite-State Machines

29
Finite-State Machines - Examples
• Thermostat modelled by an FSM.
• A model with hysteresis to avoid
chattering

30
Finite-State Machines – Update Function

31
Extended State Machines
• Large number of
states

• An extended state machine is used to augment a finite state

machine model with variables that may be read and written as part
of taking a transition between states.

32
Difference between FSM and Extended SM
• There are three differences between the extended state machine
and the basic finite state machine notation.

Finite state Extended state

machine machine
representation representation

33
Extended State Machine- Traffic light
model

34
Determinacy, Receptiveness
and Nondeterminism
• A state machine is said to be deterministic if, for each state, there
is at most one transition enabled by each input value.
• A state machine is said to be receptive if, for each state, there is
at least one transition possible on each input symbol.
• If for any state of a state machine, there are two distinct transitions
with guards that can evaluate to true in the same reaction, then
the state machine is nondeterministic.

35
Behaviour and traces

36
Behaviour and
Traces

37
Summary
• We use finite state machines to model discrete dynamics
• The extended state machine notation are used to
compactly represent large number of states.
• The concepts of determinism have been explained.

38
Hybrid systems
• A hybrid system combines discrete and continuous dynamics.
• Cyber-physical systems integrate physical dynamics (based on
continuous dynamics) and computational systems (based on
discrete dynamics).
• For continuous dynamics we use differential equations and
for discrete dynamics we use state machines.
• What do we use to model continuous dynamics, and what do we
use to model discrete dynamics?

39
Actor Model of a finite state machine
• Actor model enables composition of state machines
• Input ports and output ports: At each reaction the value is
either present/absent or a member of a set of values
• Guards: subsets of possible values on input ports
• Actions: assignment of values to output ports

40
Hybrid systems – Continuous input/output

Example 1

Example 2 Example 3 Example 4

41
Classes of hybrid
systems
• Timed automata
• Higher-order Dynamics
• Supervisory Control

42
Timed Automata

43
Timed Automata Example: Thermostat
• Example: A timed automaton modeling a thermostat with a single
temperature threshold, 20, and minimum times Tc and Th in each
mode
• we use the notation “:=” to emphasize that this is an assignment, not a
predicate

44
Timed Automata Example: Thermostat

45
Higher-Order Dynamics
• More complex of refinements than in timed
automata
• Example: Spring-mass system with collisions
• Two sticky round masses are attached to springs.
• Springs are compressed or extended and then released
• After a collision, they stick together and oscillate together
• Stickiness decays and masses pull apart again

46
Physics of Sticky Masses

47
Physics of Sticky Masses

48
Hybrid system model of the sticky mass

49
Physics of Sticky Masses

50
Physics of Sticky Masses

51
Supervisory Control
Plant

Environment

Control
Sensors
System
Supervisory Control
Controller
Low-level Control

52
Supervisory Control Example

53
Supervisory Control Example - Plant

54
Supervisory Control Example
• The vehicle always moves at its maximum speed of 10 mph.
• If AGV strays to far right, the controller steers it towards the left.
• If the AGV strays to far left, the controller steers it to the right.
• If the AGV stays close to the track the controller maintains a
straight line.

• 4 modes: left, right , straight, and stop.

55
Supervisory Control – low level controller

56
Supervisory Control

57
Supervisory Control - Environment

58
Supervisory Control
• In summary
• The plant :

59
Composition of State Machines
• System behaviour modelled conveniently using state
machines.

• Disadvantage state-space explosion

• Large state space is problematic to handle by humans.

• A complex system can be decomposed into simpler ones.

60
Actor Model for State Machines

61
Composition of State Machines
Synchronous

Concurrent Composition
Asynchronous

Composition of State Machines

Hierarchical State
Machines

62
Concurrent Composition
Synchronous Asynchronous
Side-by-side Side-by-side
composition – No composition – No
communication communication

Side-by-side Side-by-side
composition – composition –
communication through communication through
shared variables shared variables

Side-by-side Side-by-side
composition – composition –
communication through communication through
ports ports

63
Side-by-side composition – Disjoint actors

64
Side-by-side composition – Disjoint
actors (Synchronous) - example
• Under synchronous composition, a reaction of C is a simultaneous
reaction of A and B.

65
Side-by-side composition – Disjoint
actors (Synchronous) - example

66
Side-by-Side Asynchronous Composition
• Components react independently.
• Two possible interpretation to define how actor C reacts
• Semantic 1: A reaction of C is a reaction of one of A or B, where the choice is
nondeterministic – Interleaving semantics
• Semantics 2: A reaction of C is a reaction of A, B, or both A and B, where the
choice is nondeterministic. A variant of this possibility might allow neither to
react.

67
Side-by-Side Asynchronous Composition
- Example

Semantic 1: A reaction of C is a reaction of one of A or B, where the choice is

nondeterministic – Interleaving semantics

68
Side-by-Side Asynchronous Composition
- Example
• Question
• Given the example 5.3 in the reference text book, use semantic 2 which
describes an asynchronous side-by-side composition (A reaction of C is a
reaction of A, B, or both A and B, where the choice is nondeterministic.)
to produce the finite state machine of C.

69
Side-by-Side Composition through
Shared Variables
• The local variable from an extended state machine can be shared.

• The variable can be shared by different sub state machines.

• You would find this useful when modelling interrupts and

threads.

• The correct semantics for such system is often challenging.

70
Side-by-Side Composition through
Shared Variables- Example

Semantic 1: A
reaction of C is a
reaction of one of
A or B, where the
choice is
nondeterministic
– Interleaving
semantics

71
Cascade Composition

72
Cascade Composition – Question 1

?
The state machines that describe machine A and B are given in the diagram.

Show the combined FSM representation of machine C, assuming

synchronous semantics.

73
 Cascade Composition Question 2
• Remember the traffic light model. In this question, we add the
model of a pedestrian crossing light. To have a composite C that
looks as shown.

pedG, pedR
Pedestrian
sigR sigR

A B
C
• Again show the combined FSM representation of machine
C, assuming synchronous semantics.
74
General Composition

75
Hierarchical State Machines
• State refinement is the main idea behind understanding
the hierarchical state machines.
• The refinement is used to show hierarchy.

76
Hierarchical State Machines

77
Hierarchical State Machines
-Notable behaviour description
• Pre-emptive transition.
• Reset Transitions
• History transition

78
Pre-emptive transition and Reset transition.

79
History transition

80
Summary
• In this section we discussed the two forms of state
machine composition.
• Concurrent composition
• Hierarchical composition

• We covered both synchronous and asynchronous semantics

for concurrent composition.

• We also discussed several terms used to describe the semantics

of hierarchical composition.

81
Concurrent Model of computation
• Structure of Models
• Synchronous-Reactive Models
• Dataflow Models of Computation.

82
Concurrent Model of Computation
Semantic rules:
Concurrent composition of
actors
• Constituents
• Concurrency mechanism
• Communication mechanism
Synchronous
Semantic

Asynchronous
Semantic
83
MODEL STRUCTURE

84
Model
Side-by-side
structure composition

85
Exercis
e
• Transform the following actor into a feedback system by
rearranging the actors as shown in the previous slide.

86
Representation of actor network as
equations

87
Fixed-Point Semantics

88
Synchronous-Reactive
Models

89
Synchronous-Reactive Models

90
Synchronous-Reactive Models

91
 Well-Formed and Ill-formed Models
Ill-Formed Well-Formed

No fixed point
One fixed point
Multiple fixed point

92
Additional Example

93
Constructing a fixed point

94
Example – Constructive and non-constructive

95
Dataflow Models of
Computation

96
Dataflow Model of Computation
• The decision to when a reaction occurs can reside with
each individual actor.

• Reactions can be synchronous or asynchronous.

• Dataflow dependency between reactions.

• A model of computation where data dependencies are the key

constraints on reactions is called the dataflow model of
computation.

97
Dataflow principles
s

Token Token Token

A B
1 2 3

Actor

98
Dataflow principles
• Firing of actors are asynchronous.
• Tokens sent from one actor to the other must be buffered.
• Challenges of dataflow models:
• Unbounded executions with bounded buffers
• Deadlock
• Measures to ensure there is no buffer overflow for
unbounded execution.
• Scheduling policies are required to deliver bounded buffers.
• Delay actors can help prevent deadlock.

99
Synchronous Dataflow
• Synchronous dataflow (SDF) - Every firing consumes/produces a
fixed number.
• SDF is often referred to as static dataflow since it is not
synchronous in the sense of synchronous reactive models.

100
Synchronous Dataflow (SDF)

101
Dynamic Dataflow
• One limitation of SF is that it cannot directly express
conditional firing.
• E.g. firing a token when it has only a particular value.
• They dynamic dataflow (DDF) is used to support conditional firing.
• The DDF has two basic actors known as switch and select,
indicated with the symbols shown.

102
Structured Dataflow

103
 DESIGN
• Embedded processors
• Memory architectures
• Sensors and actuators
• Input and output
• Multitasking
• Scheduling

104
Embedded
Processors
• Processor Types
• Microcontrollers
• DSP
• Graphics Processors
• Parallelism
• Parallelism vs. Concurrency
• Pipelining
• Instruction-Level
Parallelism
• Multicore Architecture

105
Embedded Processors
• Instruction set Architecture (ISA)
• Abstract model of a computer.
• It defines the contract between software and hardware
• Functional definition of storage locations and operations.
• Types of operations performed e.g. addition, multiplication, load, store etc.
• Storage locations: memory, registers.
• It defines instructions such as the bit-patterns hardware interpret
as commands.
• Example of ISA, x86
• Chip
• The realization of the of the ISA.
• Multiple vendors for a given ISA.

106
Do you recognize any vendor?
•Motorola 6800 and intel 8080 architecture – 1974

•Intel 8051, 8 bit microcontroller – 1980.

•The 8051 ISA is supported by multiple vendors – Atmel,

Ifineon technologies, Dallas semiconductor, NXP, ST
Microcontrollers.

•ARM instruction set - currently made by Alcatel, Atmel,

Broadcom, Cirrus Logic, Freescale, LG, Marvell
Technology Group, NVIDIA, NXP, Samsung, Sharp, ST
Microcontrollers, Texas Instrument, VLSI technology, 107
Types of
Processors
• Microcontrollers
• small computer on a single integrated circuit consisting of a relatively
simple central processing unit (CPU)
• combined with peripheral devices such as memories, I/O devices, and timers
• Digital Signal Processor (DSP) are designed specifically to support
numerically intensive signal processing applications
• Signal is a collection of sampled measurements of the physical world, typically
taken at a regular rate called the sample rate, e.g., 44.1 kHz audio sample rate
of CDs
• Large amounts of data: samples in time, space
• Mathematical operations on the data, including filtering, system
identification, frequency analysis, machine learning, and feature extraction

• Graphic Processors - Graphic processing unit (GPU) – (Intel, NVIDIA, AMD)

108
 Parallelism vs.
Concurrency
• Concurrent execution: if different parts of the program conceptually
execute simultaneously
• Parallel execution: if different parts of the program physically
execute simultaneously.
• Task1: A, B, C Task 2: D, E, F
Parallelism Concurrency
Processor
Processor 1 Processor 2
A

A B
B

C
C D

E F
E

109
Hardware approaches to deliver parallelism
• Pipelining
• Instruction-level
Parallelism
• Multicore architectures

110
Pipelining
• Fetch stage of the pipeline: program counter (PC) provides an address
to the instruction memory
• Decode pipeline stage: extracts register addresses, opcode, … from
the instruction
• Execute pipeline stage: operates on the data fetched from the
registers using an arithmetic logic unit (ALU)

111
Pipelining
• Overlapping of instructions

• Data hazards and control hazards

• Pipeline bubbles: delay with no-ops
• Interlocks: forwarding information
• out-of-order execution: proceed with other independent instructions

112
 Instruction-Level Parallelism (ILP)
CISC (Complex Instruction Set
Computer)
• Instruction-Level Parallelism (ILP) means execution of multiple
independent operations in each instruction cycle
• CISC, Subword parallelism, superscalar, and VLIW.

• CISC Machines (complex instruction set computer) such as DSPs

support complex and specialized operations

• Disadvantages
• Difficult use for compiler
• Subtle timing issues (e.g., layout of data in memory)

113
Instruction-Level Parallelism
(ILP)
Subword Parallelism
• Wide ALU is divided into narrower slices enabling
simultaneous arithmetic or logical operations on smaller words
• Particular form of vector processing
• Many embedded applications operate on data types that
are considerably smaller than the word size of the processor
• The color of a pixel may be represented by three bytes in the
RGB format
• Wasteful of resources to use a 64-bit ALU to process a single
8-bit number

114
Instruction-Level Parallelism
(ILP)
Superscalar
• hardware can simultaneously dispatch multiple instructions
to distinct hardware units
• Basis is dataflow analysis to detect that such simultaneous
dispatch will not change the behavior
• Supports out-of order execution
• Disadvantage for embedded systems
• execution times may difficult to predict
• Unrepeatable in the context of multitasking (interrupts and threads)

115
Instruction-Level Parallelism (ILP)
VLIW (Very large instruction
word)
• More repeatable and predictable timing
• Multiple function units are used explicitly
• Each instruction specifies what each function unit should do in
a particular cycle
• VLIW instruction set combines multiple independent operations
into a single instruction
• Order and simultaneity of the execution is fixed in the software

116
Multicore
Architectures
• Combination of several
processors on a single chip
• Heterogeneous multicore
machines combine a variety of
processor types on a single chip
• Example: Texas
Instruments OMAP (open
multimedia application
platform)

117
Time-Triggered SoC

118
Memory Architecture
• Memory
Technologies
• Memory Hierarchy
• Memory Models

119
Memory Technologies
• RAM
• Non-Volatile Memory

120
Random Access Memory
SRAM
• RAM is a volatile memory
RAM

DRAM

• The SRAM is faster than the DRAM

• The SRAM occupies more space.
• DRAM is periodically refreshed.
• SRAM holds data as long as power is maintained.

121
Non-Volatile Memory
• Data is retained in memory after power is turned off.
• Early versions of non-volatile memory – magnetic core memory.
• Read-only memory (ROM) – most basic non-volatile memory
• EEPROM (Electrically-erasable programmable ROM) – A variant
of ROM that can be written into.
• Flash memory is a form of EEPROM with fast read times.
NOR

Flash memory
NAND
• Disk Memories
• Hard disk drive (HDD) vs Solid-state drive
(SSD)?
122
Memory Hierarchy
• Memory Maps
• Register Files
• Scratchpads and
Caches

123
Memory Hierarchy

124
Memory Map

125
Registers
• Tightly integrated memory in a processor

• They are usually temporal storage areas built into the processor.

• Each register in a file stores a word

• Registers may be implemented directly into the processor using

flip flops or collected into a single memory bank typically using
SRAM.

126
Microcontroller Architecture

127
Scratchpads and Caches
• The memories that are accessed first we refer to them as
close memories.
• SRAM is an example of a close memory
• A close memory that has distinct set of addresses such that a
program is responsible for moving data in or out of it to a
distant memory is called a scratchpad.
• If the close memory duplicates data in the distant memory with
called
the a [Link] handling the copying to and from, then
hardware Approximate number
it is of clock cycles to access
the various elements in
Cache or
Scratchpad
the memory hierarchy

128
Memory Models
• Memory Addresses
• Stacks
• Memory Protection Units
• Dynamic Memory Allocation

129
Memory Addresses
• Reference to a specific memory location

32 bit address

Assignment
Data alignment and byte order are two
major consideration for memory
addresses.

• What is the difference between the term

little endian and big endian?
• Hint: Course textbook and online resources

130
Stack
s
• A stack is a region inside a memory which is dynamically allocated
to a running program in a last-in,, first-out (LIFO) pattern.
• Stack pointer contains the addresses of the stack
• The stack frame is the data pushed onto a stack

131
Memory Protection Unit
• Memory protection widely realised in processor hardware.

• Simultaneous tasks cannot disrupt the execution of each other.

• Tasks are assigned specific address space.

• Illegal access is prevented and offending application is

terminated.

132
Dynamic Memory Allocation
• The memory is allocated from a data structure known as a heap, which
• facilitates keeping track of which portions of memory are in use by which
application.

• Memory management (malloc in C(Memory allocation) and free in

C(deallocates the memory)) can lead to many problems with embedded
systems

• Garbage collector: a task that runs either periodically or when memory gets
tight that analyzes the data structures that a program has allocated and
automatically frees any portions of memory that are no longer referenced
within the program

• Automatic techniques (“garbage collection or defragmentation”) typically

require stopping everything and reorganizing the allocated memory. This is
deadly for real-time programs.

133
Sensors and Actuators

134
Sensors and Actuators
• Sensors – devices used to measure physical quantities.
• Thermistors (Temperature sensor), IR sensors, Ultrasonic sensors,
Gyroscope sensor, e.t.c
• Actuators – Devices used to alter physical
quantities.
• Electric motors, solenoids, hard drive stepper motors e.t.c

135
Sensors and actuators
• Digital sensors are equipped with an Analog-to-Digital
Converters (ADCs)
• Analog sensors are not equipped with ADC’s
• Technologies that enable the connection of the physical world
with our digital perspective.

136
Technology enablers

137
Sensors and actuators
• Models of Sensors and Actuators
• Linear and Affine Models
• Range
• Dynamic range
• Quantization
• Noise
• Sampling
• Harmonic distortion
• Common Sensors
• Actuators

138
Models of Sensors and Actuators

Mercury-in-glass Thermometer Thermistor

139
Models of Sensors and Actuators

140
Models of Sensors and Actuators

141
 Quantizatio
n • A certain amount of bits are used by a digital sensor
Decimal Binary
(4- Bits) to represent the values of a physical quantity.
0 0000

1 0001
• For example let us say we have a 4 bit sensor.
2 0010 • The maximum amount of values that we can represent is giving as 2n,
which is 24 as n = 4, maximum representation is equal to 16.
3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001

10 1010

11 1011

12 1100

13 1101

14 1110

15 1111 • What is the impact of changing n = 3 to n= 4 in this example above?

142
Noise

143
Sampling

144
Harmonic distortion

145
Common Sensors
• Temperature Sensor
• Proximity Sensor
• Pressure Sensor
• Water Quality Sensor
• Chemical/Smoke & Gas Sensor Tachometer??
• Level Sensor ?
• IR Sensor
• Ultrasonic Sensor
• Image sensors
• Motion Detection Sensors
• Accelerometer Sensors
• Gyrometer Sensors
• Humidity Sensors
• Optical Sensors

146
Actuators
• An actuator is a component of a machine that is responsible for
moving and controlling a mechanism of system. For example,
lighting up and LED, opening a valve, controlling a motor etc.

Examples include
• Light-Emitting Diodes Motor control
• Motor Control Pulse-width Modulation?
• Relays
• Solenoid

147
Input and
Output

148
Input and Output
• Cyber-physical systems integrate computing and physical dynamics.
• Events in the physical world occur at the same time, but
software often assume a sequential operation.
• It is necessary to reconcile the interactions between sequential code
and concurrent events in the physical world.
• An embedded system must ensure that the interface between
the physical world and the computing platform meet the
required specification.

149
Input and Output
• I/O Hardware
• Pulse Width Modulation
• General-purpose digital I/O
• Serial Interfaces
• Parallel Interfaces
• Sequential Software in Concurrent
World
• Interrupts and Exceptions
• Atomicity
• Interrupt Controllers
• Modelling Interrupts

150
I/O
Hardware

151
ZedBoar
d

152
Pulse-width Modulation
• Pulse width modulation (PWM) is a technique for delivering a
variable amount of power efficiently to external hardware
devices that tolerate rapid and abrupt changes in voltage and
current.
• Can be used to control the speed of a motor, LED light,
temperature of a heating element.
• Any device whose response to changes in current or voltage is
slow compared to the frequency of the PWM signal is a candidate
for being controlled via PWM

153
PMW Explained
• Digital circuits, by design produce only two voltage levels.
• HIGH = 1, and LOW = 0
• The concept of PWM is the rapid switching between the high and
low signal.

Period = 1ms Period = 1ms Period = 1ms Period = 1ms Period = 1ms

154
General-Purpose Digital I/O
• General-Purpose I/O (GPIO)
• Enables system designers to connect custom hardware to
embedded processors.
• Many embedded processors have a number of general purpose
I/O pins (GPIO), which enable the software to either read or write
voltage levels representing a logical zero or one.
• An embedded system designers needs to understand the
specification of the device when interfacing hardware to GPIO
pins.
• Voltage and current levels
• Interfacing outside tolerance limits could cause failure.
• Electrical isolation between processor circuit and external devices
• Avoid the impact of noisy electrical characteristics from external devices to
the processor. 155
Serial Interfaces
• The Reduction in power consumption is critical for an embedded
systems designer.
• Hence, the number of pins of a processor are usually limited and must
be utilized efficiently.
• Information is often sent serially (one at a time) to efficiently utilize the
pins.
• An interface where information is sent of the pins as sequences of bits
is known as a serial interface.
• Serial interface standards
• RS-232
• Universal Serial Bus (USB)
• JTAG (Joint Test Action Group)
• 𝐼𝐼2𝐶𝐶 (Integrated circuit)
• SPI (Serial peripheral interface bus)
• PCI Express (Peripheral component interconnect express) 156
Parallel Interface
• A parallel interface uses multiple lines to simultaneously send bits.
• Each line of a parallel interface is also a serial interface, but the
logical grouping and coordinated action of these lines is what
makes the interface a parallel interface.
• Parallel interfaces
• IEEE-1284 printer port
• Parallel interfaces do not necessarily deliver better performance
that serial interfaces
• A major challenge of parallel interface is the maintenance
of synchrony across its constituent wires.
• As the physical length of the interconnection increases (increase
in complexity), it becomes more challenging to maintain
synchrony. 157
Sequential Software in Concurrent World
- Interrupts
• Events happen concurrently in the physical world but software
is intrinsically sequential.
• Interrupts is a mechanism used to bridge this mismatch.
• An interrupt is a mechanism for pausing execution of
whatever a processor is currently doing and executing a
pre-defined code sequence called an interrupt service routine
(ISR) or interrupt handler.
• An interrupts can be triggered by
• Hardware
• Software
• Exception
• There can be multiple interrupts configured for a processor.
Conflict is resolved by setting priorities. 158
Atomicity
• An atomic operation is one that appears to occur at a single
instant between its invocation and its response.
• An interrupt service routine can be invoked between any two instructions of
the main program (or between any two instructions of a lower priority ISR).
• The term “atomic” comes from the Greek work for “indivisible”.
• An atomic operation is an operation that will always be executed
without any other process being able to read or change state that
is read or changed during the operation

159
Interrupt Controllers
• A logic in the processor that handles interrupts.
• Multiple interrupts
• Provide support for priority levels for interrupts
• Each interrupt has an interrupt vectors
• The interrupt vector is the address of the interrupt service routine or index
into an array called the interrupt service vector table, which contains
address of all interrupt services routines.
• Level triggered
• Hardware asserting interrupts holds the voltage on the line
until acknowledgement is received.
• Edge triggered
• Hardware asserting interrupts changes voltage for a short time.

160
Modelling interrupts
• Interrupt logics are typically weakly described in the documentation
of a processor.

• A finite state machine can be used to precisely model interrupts.

• A proper modelling of interrupts (e.g. using FSM) can help

expose potential flaws in a program.

• A workaround can be done when a flaw is exposed, hence the

need for proper modelling of interrupts.

161
MULTITASKING

162
Multitasking
• Mid-level programs used by software to provide concurrency
in executing sequential code
• Reasons for the concurrent execution of sequential codes Concurrency
• Improve responsiveness
• Improve performance Processor
• Control of timing of external
A
interaction.
B

163
Multitasking
• Concurrency at different
layers

164
Multitasking
• Imperative Programs
• Threads
• Creating Threads
• Implementing Threads
• Mutual Exclusion
• Deadlock
• The problems with Threads.
• Processes and Message Passing

165
Multitasking – Imperative Programs
• What is an imperative programming language?
• A programming language that expresses a computation as a sequence of
operations is called an imperative language.
• Examples of Imperative Programming
• C, C++, Python, Java
• Example of dataflow programming
• VHDL (VHSIC-HDL, Very High Speed Integrated Circuit Hardware Description
Language)
• LabVIEW
• Lustre

166
Multitasking – Imperative
Programming example
• [Link]
• Scroll down to the main method.
• Please click on the link to use the compiler in [Link]
above.
• Open the exampleCode file, (You get this in moodle).
• Copy and paste the code in the tutorial point link.
• Execute the code.

167
Multitasking – Imperative Program
• A C program specifies a sequence of steps, where each step
changes the state of the memory in the machine.

• The state of the memory in the machine is represented by the values

of variables e.g. the variable numbcoffeeReady in our example
(Check the example code).

• Linked list - data structure for storing a list of elements that varies
in length during execution of a program.

168
Multitasking - Threads
• A thread is an imperative program that runs concurrently.
• Threads exist in the form of interrupts on almost all
microprocessors, even without any operating system at all (bare
iron).
• Creating a Thread
• API (Application Program Interface) – Pthread (POSIX Thread)
• Open this website on your browser-
[Link]
c
• Replace the contents in the code section of the website with the contents
in the file exampleCodePthread
• To ensure that the application compiles, click on Compiler args below
and add “-lpthread”.
• Click on Run or F8
169
• Run the program several times and observe the results.
Multitasking – Implementing Threads
• The decision on which thread to execute next is made by a
scheduler.
• A scheduler may allot equal opportunity (fairness) for every
active thread.
• A technique called cooperative multitasking is used to solve
the problem of how and when a scheduler is invoked.
• Threads are uninterrupted when executing except the threads make a call
to certain procedures.
• Other threads can be starved by an executing thread if the
calls (System calls) are not made timely.
• Most OS maintain an ISR that runs at fixed time interval to
avoid starvation.
• A jiffy is the time interval at which the system-clock ISR is invoked. 170
Multitasking – Mutual Exclusion
• Mutual Exclusion used to solve a race condition.
• A race condition is when two concurrent pieces of code (e.g.
threads) race to access the same resource (e.g. memory location),
and the exact order in which their accesses occur affects the result of
the program.
• Lock mechanism is used to ensure mutual exclusion which takes
care of the race condition.
• A lock variable is exchanged between competing concurrent code pieces.
• At any time the lock is held by only one concurrent code piece.
• Only the code piece that has access to the lock can access the resource.
• A mutual exclusion lock prevents any two threads from
simultaneously accessing or modifying a shared
resource.
171
Multitasking-Deadlock
• In concurrent computing, a deadlock is a state in which each
member of a group (e.g. multiple threads) waits for another thread,
including itself, to take action, such as sending a message or more
commonly releasing a lock that never happens.

• There are several ways to prevent deadlock

• Use of only one lock instead of multiple locks
• Enabling and disabling interrupts as a single global mutex.
• Establish an order in which every threads acquire the lock

172
Multitasking – Issues with Threads
• Multithreaded programs can be difficult to understand

• Multithreaded programs can yield insidious errors, race

conditions and deadlock.

• Deadlock can be hidden in a program for very long without

ever appearing.

• These issues taking seriously when designing cyber physical

systems which often involves safety and livelihood of humans

173
Multitasking – Processes and
message passing
• Processes are imperative programs with their own memory
space.

• The processes do not refer to each others’ variables

• Communication between processes must occur via

mechanism provided by the OS, microkernel, or library.
• Shared memory (File system)
• Message passing

174
SCHEDULING

175
Schedulin
g
• A scheduler is a software program that carries out scheduling
activities in which different works such as virtual computation
elements (threads, processes, or data flows) are scheduled onto
hardware resources (processors, network links, or expansion
cards).

• A scheduler is needed when there are fewer processors than tasks,

or when tasks must be performed at a certain time.

176
Operating Systems and Scheduling
• Responsibilities of an Operating
system
• Process management
• Interrupts
• Memory management
• File system
• Device drivers
• Networking
• Security
• I/O
• Responsibilities of a
Microkernel (a small, custom OS)
• Scheduling of threads or processes
• Creation and termination of threads
• Timing of thread activations
• Synchronization
• Semaphores and locks 177

• Input and output

Scheduling Decision
• Scheduling decision is based on the following:
• assignment: which processor should execute the task;
• ordering: in what order each processor should execute its tasks; and
• timing: the time at which each task executes.
• Fully-static scheduler makes all three decisions at design time
• mutual exclusion and precedence constraints can be ensured implicitly based
on timing
• difficulty for predicting execution time
• Fully-dynamic scheduler performs all decisions at run time

178
When can a new thread be dispatched?
• Under non-preemptive scheduling:
• When the current thread completes.
• Under Preemptive scheduling:
• Upon a timer interrupt
• Upon an I/O interrupt (possibly)
• When a new thread is created, or one completes.
• When the current thread blocks on or releases a mutex
• When the current thread blocks on a semaphore
• When a semaphore state is changed
• When the current thread makes any OS call
• file system access
• network access
•…

179
The Focus Today:
How to decide which thread to
schedule?
• Considerations:
• Preemptive vs. non-preemptive scheduling
• Arrival of tasks can be known beforehand or dynamic
• Periodic vs. aperiodic tasks
• Precedence constraints
• Fixed priority vs. dynamic priority
• Priority inversion anomalies
• Other scheduling anomalies

180
Task
Model

181
 Comparing
Schedulers
• All task executions meet their deadlines
• Schedule that accomplishes this is called a feasible schedule
• Optimality with respect to feasibility: Scheduler that yields a feasible schedule
for any task set for which there is a feasible schedule
• High achievable processor utilization (optimal scheduler, ≤100% is
sufficient)
• Maximum lateness allows to compare infeasible schedules

• Total completion time or

makespan

182
Rate Monotonic Scheduling

183
Rate Monotonic scheduler explained

184
 Showing Optimality of RMS:
Consider two tasks with different
periods
• Is a non-preemptive schedule feasible?

Scenario
example

Possible
Outcome

185
Showing Optimality of RMS:
Consider two tasks with different
periods
• What if we had a preemptive scheduling with higher priority for
red task?

186
 Earliest Deadline First
• Given n independent one-time tasks with deadlines
d1 , … , dn, schedule them to minimize the maximum lateness,
defined as
1≤i≤n {f − d }
Lmax = max i i

• where fi is the finishing time of task i. Note that this is negative

iff all deadlines are met.

•Earliest Due Date (EDD) algorithm: This strategy simply executes

the tasks in the same order as their deadlines, with the one with
the earliest deadline going first
•Note that this does not require preemption.
187
 Theorem: EDD is Optimal in the Sense
of Minimizing Maximum Lateness
• EDD does not support arrival of task, and hence does not support periodic
and task execution.
• Earliest deadline First (EDF) extends the EDD to support arrival of task.

•The EDF theorem thus states

188
Comparison of EDF and RMS
• Favoring RMS
• Scheduling decisions are simpler (fixed priorities vs. the dynamic priorities
required by EDF. EDF scheduler must maintain a list of ready tasks that is
sorted by priority.)
• Favoring EDF
• Since EDF is optimal w.r.t. maximum lateness, it is also optimal w.r.t.
feasibility. RMS is only optimal w.r.t. feasibility. For infeasible schedules,
RMS completely blocks lower priority tasks, resulting in unbounded
maximum lateness.
• EDF can achieve full utilization where RMS fails to do that
• EDF results in fewer preemptions in practice, and hence less overhead
for context switching.
• Deadlines can be different from the period.

189
ANALYSIS AND VERIFICATION

190
Invariants and Temporal Logic -
Introduction
• Specification : The requirements that an embedded system must
be designed to meet.
• “A design without specifications cannot be right or wrong, it can
only be surprising!” (paraphrased from Young et al. (1985)
• How do we then specify the requirements of a system ?
• Use of natural Language (e.g. Engliish language)
• Formal Specification (Use mathematical expression)
• Use of natural Language example from SpaceWire
communication protocol
1. “The ErrorReset state shall be entered after a system reset, after link
operation has been terminated for any reason or if there is an error
during link initialization.”
2. “Whenever the reset signal is asserted the state machine shall move
immediately to the ErrorReset state and remain there until the reset
signal is de-asserted.”
191
Invarian
t
• Invariant is a property of a system that holds for a system if it
remains true at all times during the operation of the system.
• Example of invariant property “there is no pedestrian crossing
when the traffic light is green (when cars are allowed to move)”

192
Linear Temporal Logic
•

193
Propositional Logic Formulas
• As mentioned, an atomic proposition is a statement about the
input, output, or states.
• A predicate that evaluates to true or false
• true Always true.
• false Always
•x false.
• x = present True if input x is
• y = absent present. True if input x
•b is present.
True if y is absent.
True if the FSM is in state
b

194
Example of Propositional Logic Formulas
Examples

195
Contrapositive of the former

196
LTL formulas

197
Counterexample
s
• To show that an LTL formula is false for an FSM, it is sufficient to
give one trace for which it is false.
• This traces is called the counter example

• To show that an LTL formula is true for an FSM, you must

demonstrate that it is true for all traces, which is often a much
complex task.

198
Temporal
Operators

199
Temporal
Operators

200
Temporal
Operators

201
Temporal
Operators

202
Examples – Try this out
• Consider the following state machine

• For each of the following LTL formulas, determine whether it is

true or false, and if it is false, give a counterexample:

203