Embedded Systems - Advanced Operating Systems - Appunti

Politecnico di Milano

Master of Computer Science and Engineering

Embedded Systems - Notes

Covered Courses:

Advanced Operating Systems

Embedded Systems 1

Contents

1 Introduction To Embedded Systems 1

1.1 Features of an Embedded System . . . . . . . . . . . . . . . . 1

1.1.1 Example: take a picture . . . . . . . . . . . . . . . . . 1

1.1.2 Relevant aspects . . . . . . . . . . . . . . . . . . . . . 2

1.2 Designing Embedded Systems . . . . . . . . . . . . . . . . . . 3

1.2.1 Dependability and efficiency . . . . . . . . . . . . . . . 3

1.2.2 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Architecture and Design 5

2.1 PCB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 System-on-Chip . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.1 Dark Silicon . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . 8

2.3.1 Wireless sensor network . . . . . . . . . . . . . . . . . 8

2.4 Development platforms . . . . . . . . . . . . . . . . . . . . . . 8

2.5 The Multi-Core Revolution . . . . . . . . . . . . . . . . . . . . 9

2.5.1 On-chip interconnect architecture . . . . . . . . . . . . 10

2.6 On-chip bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.7 Network-on-Chip . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.7.1 Nomenclature and metrics . . . . . . . . . . . . . . . . 12

2.7.2 Cache coherence protocols . . . . . . . . . . . . . . . . 13

2.7.3 Granularity overview . . . . . . . . . . . . . . . . . . . 14

2.7.4 Baseline wormhole router architecture . . . . . . . . . 15

2.7.5 Head of line blocking . . . . . . . . . . . . . . . . . . . 16

2.7.6 Virtual channel wormhole router . . . . . . . . . . . . 17

2.7.7 Buffer management and flow control . . . . . . . . . . 18

2.7.8 Router datapath . . . . . . . . . . . . . . . . . . . . . 19

3 [AOS] Scheduling for Uniprocessor Systems 20

3.1 Scheduler characteristics . . . . . . . . . . . . . . . . . . . . . 20

3.1.1 Types of scheduling . . . . . . . . . . . . . . . . . . . . 21

3.1.2 The dispatcher . . . . . . . . . . . . . . . . . . . . . . 21

3.1.3 Scheduling criteria . . . . . . . . . . . . . . . . . . . . 21

3.2 Scheduling algorithms . . . . . . . . . . . . . . . . . . . . . . 22

3.2.1 First-Come, First-Served . . . . . . . . . . . . . . . . . 22

3.2.2 Shortest Job First . . . . . . . . . . . . . . . . . . . . . 22

3.2.3 Highest Response Ratio Next . . . . . . . . . . . . . . 23

3.2.4 Round-Robin . . . . . . . . . . . . . . . . . . . . . . . 23

3.2.5 Other algorithms . . . . . . . . . . . . . . . . . . . . . 23

I

3.2.6 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 24

4 DSE and Metrics 25

4.1 Design metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.1.1 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.1.2 Fidelity . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1.3 Cost metrics . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1.4 Performance metrics . . . . . . . . . . . . . . . . . . . 26

4.1.5 Other factors affecting system design . . . . . . . . . . 27

4.2 Design Space Exploration . . . . . . . . . . . . . . . . . . . . 27

5 Power Management 29

5.1 Power Consumption in CMOS Devices . . . . . . . . . . . . . 29

5.2 Power Reduction Approaches . . . . . . . . . . . . . . . . . . 30

5.2.1 Clock gating . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.2 Multi Vdd . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.3 Power gating . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.4 Power management techniques . . . . . . . . . . . . . . 31

5.2.5 Linux frameworks for PM . . . . . . . . . . . . . . . . 31

5.2.6 ACPI . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

6 Communication 33

6.1 Serial communication . . . . . . . . . . . . . . . . . . . . . . . 33

6.2 Standard serial protocols and buses . . . . . . . . . . . . . . . 33

2

6.2.1 I C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6.2.2 SPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.2.3 Protocols analysis . . . . . . . . . . . . . . . . . . . . . 34

6.2.4 CAN bus . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.3 Parallel communication . . . . . . . . . . . . . . . . . . . . . . 34

6.3.1 Parallel protocols . . . . . . . . . . . . . . . . . . . . . 35

6.4 Wireless communication . . . . . . . . . . . . . . . . . . . . . 35

7 [AOS] Interfacing 36

7.1 Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.1.1 Polling . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.1.2 Interrupt . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.1.3 DMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

8 Hardware Technologies 39

8.1 ASIC Prototyping Technologies . . . . . . . . . . . . . . . . . 40

8.1.1 The planar process . . . . . . . . . . . . . . . . . . . . 40

II

8.1.2 Standard cell and gate array technologies . . . . . . . . 41

8.1.3 Full custom . . . . . . . . . . . . . . . . . . . . . . . . 41

8.2 Programmable Technologies . . . . . . . . . . . . . . . . . . . 41

8.2.1 FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8.3 Feasibility Study . . . . . . . . . . . . . . . . . . . . . . . . . 42

9 Software Design And Testing 44

9.1 Writing The Code . . . . . . . . . . . . . . . . . . . . . . . . . 44

9.2 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10 Sensors and Batteries 47

10.1 Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

10.1.1 Real and ideal sensors . . . . . . . . . . . . . . . . . . 47

10.1.2 MEMS . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

10.1.3 Energy scavenging . . . . . . . . . . . . . . . . . . . . 48

10.2 Batteries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

III

1 Introduction To Embedded Systems

Everyday we are surrounded by thousands of electronic devices provided

with microprocessors. They are mostly invisible and quite hidden, but they

interact deeply with the environment where they are located. These digital

systems are often called embedded.

The embedded systems are an essential part of any product whose main

purpose is to interact with the world and gather data. They are about half the

cost of the final product in a large set of business areas such as automotive,

avionics, health care, consumer and telecommunication.

1.1 Features of an Embedded System

A personal computer is a general purpose machine used for a broad scope.

On the other hand, an embedded system is characterized by a strong opti-

mization in terms of architecture and computing power. Optimizing means

to reduce the cost of the final product. The designer has to optimize the

hardware, the software, the time to market, the energy and the power con-

sumption of the product and he has to make some choices regarding the

reuse: in house development and platforms on the market are both available.

As we can see, it’s not so easy to standardize the architecture of an em-

bedded system. The engineer has to pinpoint all the functional requirements

and the constraints of the application and use different solutions to design

the product: there are ASICs (Application Specific Integrated Circuits) and

FPGAs (Field Programmable Gate Arrays) with different performance and

cost. The requirements has to converted from natural language to formal

specifications identifying sub-blocks. Most of the time, software solutions

are preferred over hardware solutions due to the short time available for

development.

1.1.1 Example: take a picture

There are different ways to take a picture. First of all we have to point out the

application areas, the functional requirements and the project constraints.

We are trying to identify the set of feasible solutions which will drive our

decisions.

Here some acceptable use cases:

• it’s the most common use and

Camera for consumer electronics:

the camera is created for this purpose only. Therefore the objective is

that to provide a great quality of the picture, high resolution, small

1

response time and a user interface made up of physical buttons and a

tiny screen to have a picture preview.

• as far as a smartphone is concerned, the cam-

Smartphone camera:

era should not have a crucial role. The quality of the picture is not

so high and the user interface has few buttons. Moreover the size is

moderate and the zoom could be only digital.

• a webcam is a very dumb piece of elec-

PC or notebook webcam:

tronics which can only work if connected to a computer. The interface

is provided by a software application and the resolution is low due to

its restricted scope.

The previous analysis is really useful as a driver in terms of hardware and

software architecture development and to scale out the processing, the com-

munication and the storing of the final product.

1.1.2 Relevant aspects

The following are relevant aspects for any embedded system project:

• the final volume of the production is a decisive factor as

Volumes:

far as the technology is concerned. Large volumes could make ASICs

affordable while smaller volumes require FPGAs and COTS (Compo-

nents Off The Shelf ) that can be customized to meet the needs.

• there are different available solutions

Communication interfaces:

that make use of both physical cables and radio signals, such as Blue-

tooth, to move data from one place to another. By reference to the

camera example, we may find a memory card and furthermore a TV

OUT. Nevertheless this will not be present on the smartphone.

• it can be physical and tangible or achieved through

User interfaces:

a software application.

• it’s an essential factor which can influence the

Energy requirement:

choice of the suitable technology. The ASICs are particularly optimized

and some microcontrollers for embedded application have a really effi-

cient power consumption.

• the use of mechanical parts may increase the size of the

Dimensions:

product, especially if a state of the art quality is required.

2

• the time-to-market is the time gap

Time to market and lifetime:

between the beginning of the prototyping phase and the distribution

of the product over the market. What is of primary importance in

order to maximize the profits is that the product must be ready to be

sold when the market asks for it. The lifetime of a product is another

essential factor: some products are disposable while others can last

more than 8 years. For the latter may exist a way in order to have

their software up to date and this could be a significant investment for

the manufacturer.

After this in-depth analysis, all we have to do is to combine the use cases con-

straints with the application functionality in order to carry out the optimum

architecture for our product.

1.2 Designing Embedded Systems

Designing an embedded system is a deep multidisciplinary activity which

introduces a computing power into the final product. Most of the time we

have to deal with sensors, data processing, actuators and potentially with a

user interface.

1.2.1 Dependability and efficiency

The systems should be designed in order to be dependable, in the sense of

reliable, considering the following aspects:

• it is the probability the system stops working after a

Reliability:

certain amount of time.

• it is the chance to fix a non-working system within

Maintainability:

a reasonable time.

• it is the probability the systems is up and alive when

Availability:

someone needs it.

• the ability of a system to be safe even if it is broken down.

Safety:

• it is the property of a system to protect data and verify

Security:

their validity.

These dependability aspects have different relevance depending on the appli-

cation area they involve.

There are some other factors which are remarkably important to describe

the efficiency of a system and they are: weight and size, cost, consumption,

code size, performances, time to market and flexibility.

3

1.2.2 Evolution

In order to understand the evolution of an embedded system, the three affect-

ing dimensions have to be analyzed: industry, market and technology. These

three perspectives are not independent. The final user can ask for some fea-

tures (market-pull) or new technologies allow new solutions to be spread on

the market (technology-push). Moreover the designers have to face a growing

problem called productivity gap: the technology evolution has allowed to ex-

ponentially increase the density of components inside integrated circuits; the

designers’ productivity has increased too thanks to a more abstracted proto-

typing level, but a gap between the technology evolution and productivity is

widening with the risk not to exploit the integration potentiality completely.

Furthermore the productivity of a team of designers can be represented as

a down parabola whose vertex is the maximum productivity. Therefore the

productivity cannot be increased indefinitely only by raising the number of

the team members. 4

2 Architecture and Design

Defining the architecture is the most critical aspect of any embedded system.

The whole prototyping activity can be summed up in the following phases:

1. definition of the system architecture;

2. repartition in hardware, software and communication;

3. implementation of hardware, software and communication;

4. manufacturing.

Some of the most useful and common architectural solutions are: PCB,

System-on-Chip, Distributed Systems and the use of development platforms.

2.1 PCB

The systems based on printed circuit boards integrate discrete components

that can be available on the market (COTS) or specifically manufactured.

The above-mentioned components can be: passive components (switches/resistors/capacitors),

power supplies, filters and converters (ADC/DAC), sensors, displays and RF

components.

Each component has several intrinsic characteristics:

we distinguish between PTH - plated-through-hole

mounting technique:

- and SMD - surface-mount-device - components. In the first case,

the leads of the components are inserted into holes on the board and

soldered while in the second case the components are directly soldered

on the surface where they are mounted.

each component has a specific package with a certain num-

pins position:

ber of pins configured in a particular position.

the package can be manufactured used different mate-

package material:

rials: the most commonly used are ceramic and plastic.

With respect to the package of a component, we can define the efficiency as

the relationship between the die area and the package area. Moreover other

important characteristics are the pin count, the space between one pin and

◦

another (pitch) and the thermal resistance measured in .

C /W

The followings are the design phases when the PCB is selected as an

architectural solution:

1. Selection of components based on schematics;

5

2. Manufacturing of the support for the chosen components. It is the

PCB itself made of three different materials: a conductor (e.g.: cop-

per), an insulator to separate the tracks and provide a support for the

components (e.g.: fiberglass epoxy resin) and a glue, typically called

pre-preg to keep the different layers together. The main phases of the

PCB production are:

• Preparation of the dielectric supports;

• Conductive tracks manufacturing;

• Assembly of the insulating layers that are alternated with pre-preg

layers;

• Drilling the board to create through-via, blind-via and buried-via

holes;

• Manufacturing of the external layers of the board using conductive

materials;

• Finishing of the board with a thin insulating external layer.

3. Board testing to check the interconnections. Sometimes the boundary

scan technique is used: several flip-flops and multiplexers are connected

together in a chain in order to provide and read data with respect to a

particular pin of the system;

4. The components are finally mounted and soldered on the printed circuit

board.

Some remarkable facts to take into account during the PCB design are:

• The more the pins of a component, the higher the complexity of the

board;

• Signals with very high bandwidth should not be brought on the PCB,

but it is more advisable keep the communicating sections inside a single

chip;

• The latency and the delay of the signals running on the PCB tracks

can be very high.

2.2 System-on-Chip

With this term we identify a complete system with all its parts integrated

on a single silicon chip. Some of them cannot be integrated due to their

mechanical characteristics, therefore a SoC is a device carrying out the main

functionality of a system. Some relevant features are being analyzed:

6

• integrating most of the functionality on a single mi-

System cost:

crochip, the final board is smaller and less complex while the total cost

will be affordable if the volumes are significant.

• as far as the size is concerned, signal lines are not used

Performance:

to be found ensuring signal integrity.

• nowadays the complexity of the systems requires a

Input/Output:

large number of input and output signals. If they are gathered on

different chips, this could lead to packages characterized by a huge

number of pins, a bigger size and a higher cost.

• this is a very relevant aspect because we want to protect

Security:

our product from reverse engineering and competitors. Moreover, if

the system elaborates sensitive data, it is necessary to protect them

from unauthorized accesses.

A System-on-Chip is always made up of a minimum set of functional blocks:

• One or more processors such as microcontrollers, general purpose, net-

work and digital signal processors;

• Different kinds of memories (e.g.: RAM, ROM, EPROM, EEPROM,

Flash);

• Some specific and application-relevant digital blocks;

• Other types of blocks such as timer blocks, power supply blocks and

some analog/digital interfaces.

As far as