# embedded architectures

## **Design of Autonomous Systems**
### csci 6907/4907-Section 86
### Prof. **Sibin Mohan**

---

## what is an "embedded system"?

---

## what is an "embedded system"?

- like autonomy, no _exact_ definition

---
## what is an "embedded system"?

- like autonomy, no _exact_ definition
- systems created for **specific functionality**

---

## what is an "embedded system"?

- like autonomy, no _exact_ definition
- systems created for **specific functionality**
- fixed/operational for **years**, decades even!

---

## tradeoff between 
<div class="multicolumn">
<div>
<br>
<br>

**performance** vs
</div>
</div>

---

## tradeoff between

**performance** vs
</div>
<div>
<ul>
    <li>power/battery life</li>
</ul>
</div>
</div>

---

## tradeoff between

**performance** vs
</div>
<div>
<ul>
    <li>power/battery life</li>
    <li>less memory</li>
</ul>
</div>
</div>

---

## tradeoff between

**performance** vs
</div>
<div>
<ul>
    <li>power/battery life</li>
    <li>less memory</li>
    <li>fewer peripherals</li>
</ul>
</div>
</div>

---

## tradeoff between

**performance** vs
</div>
<div>
<ul>
    <li>power/battery life</li>
    <li>less memory</li>
    <li>fewer peripherals</li>
    <li>limited applications</li>
</ul>
</div>
</div>

---

## tradeoff between

**performance** vs
</div>
<div>
<ul>
    <li>power/battery life</li>
    <li>less memory</li>
    <li>fewer peripherals</li>
    <li>limited applications</li>
    <li>smaller operating systems</li>
    <li><em>etc.</em></li>
</ul>
</div>
</div>

---

main reason?

## **predictability**

---

## predictability

**guarantee** the system works,

---

## predictability

**guarantee** the system works,
- correctly
- **safely**

---

## predictability

**guarantee** the system works,
- correctly
- **safely**

essentially → must be easy to **certify** the system

---

## the **wcet** problem

---

## the **wcet** problem

"worst-case execution time"

---

## the **wcet** problem

"worst-case execution time"

> **longest** execution time for a program <br>

---

## the **wcet** problem

"worst-case execution time"

> **longest** execution time for a program <br>
> on a **specific hardware platform**

---

## the **wcet** problem

"worst-case execution time"

> **longest** execution time for a program <br>
> on a **specific hardware platform**

must consider → **all possible inputs**

---

## wcet | used to ensure...

- "_schedulability_"
- resource requirements 
- performance limits

of embedded and real-time programs

---

## wcet approaches

lots of approaches to computing the WCET, _e.g.,_
- [dynamic/empirical](https://www.cs.fsu.edu/~whalley/papers/tecs07.pdf) → run program lots of times  on the platform 
- [static](https://www.cs.fsu.edu/~whalley/papers/tecs07.pdf) → _compile time_ analysis to compute the _worst-case paths_ 
- [hybrid](https://sibin.github.io/papers/2008_NCSU-Dissertation_CheckerMode_SibinMohan.pdf) → a combination of the two
- [probabilistic](https://people.ac.upc.edu/fcazorla/articles/jabella_ecrts2014_2.pdf) → combine dynamic analysis+statistical methods
- [ML-based methods](https://dl.acm.org/doi/10.1145/3570361.3615740) → applying machine-learning to the problem

---

## so what's the "problem"?

---

## so what's the "problem"?

at a high-level, the execution time distributions of applications:

Note: we see that the various methods either underestimate or overestime the wcet. the former affects the safety, the latter wastes resources

---

### wcet analysis is a hard problem!

structural problems (in hardware/software) make it more difficult!

---

## consider this example

```c
void main()
{
    int max = 10 ;
    int sum = 0;
    for( int i = 0 ; i < max ; ++i)
        sum += i ;
}
```

---

## consider this example

```c
void main()
{
    int max = 10 ;
    int sum = 0;
    for( int i = 0 ; i < max ; ++i)
        sum += i ;
}
```

how do you compute the WCET for this code?

---

## need additional information

---

## need additional information

first, define the **processor** it runs on → say, "**P**"

---

## need additional information

first, define the **processor** it runs on → say, "**P**"
- how long each instruction takes to execute on P

---

## need additional information

first, define the **processor** it runs on → say, "**P**"
- how long each instruction takes to execute on P
- how many loop iterations?

---

## need additional information

first, define the **processor** it runs on → say, "**P**"
- how long each instruction takes to execute on P
- how many loop iterations?
- what is the startup/cleanup times for the program on P?

---

### adding in all that information, we have...

```c [1|3|4|5-6|7]
void main()         // startup cost = 100 cycles
{
int max = 15 ;  // 10 cycles
int sum = 0;    // 10 cycles 
for( int i = 0 ; i < max ; ++i) // 5 cycles, once
sum += i ; // 20 cycles each iteration
}                   // cleanup cost = 120 cycles
```

---

### to calculate the wcet

```c
1   void main()         // startup cost = 100 cycles
2   {
3       int max = 15 ;  // 10 cycles
4       int sum = 0;    // 10 cycles 
5       for( int i = 0 ; i < max ; ++i) // 5 cycles, once
6            sum += i ; // 20 cycles each iteration
7   }                   // cleanup cost = 120 cycles
```

$$
wcet = line_1 + line_3 + line_4 + line_5 + (line_6 * max)
$$

---

### to calculate the wcet

$$
wcet = line_1 + line_3 + line_4 + line_5 + (line_6 * max)
$$

which is fine for this simple example

---

Now consider this slight change to the above code:
```c [3]
void main( int argc, char* argv[] )
{
    int max = atoi( argv[1] ) ;     // convert the command line arg to max
    int sum = 0; 
    for( int i = 0 ; i < max ; ++i) // how many iterations?
        sum += i ;
}
```

---

previous equation **fails**!

---

previous equation **fails**!

no longer know the value of `max` → arbitrary wcet!

---

let's make another change to the code:
```c [1-6|10-16]
#define VERY_LARGE_ARRAY+SIZE 1>>18

void main()
{
    int first_array[VERY_LARGE_ARRAY_SIZE] ;
    int second_array[VERY_LARGE_ARRAY_SIZE] ;

int sum_first = 0;
    int sum_second = 0;
    for( int i = 0 ; i < VERY_LARGE_ARRAY_SIZE * 2 ; ++i)
    {
        if( i%2 )
            first_sum += first_array[i/2] ;
        else
            second_sum += second_array[(int)((i/2)+1)] ;
    }
}
```

---

let's make another change to the code:
```c [10-16]
#define VERY_LARGE_ARRAY+SIZE 1>>18

void main()
{
    int first_array[VERY_LARGE_ARRAY_SIZE] ;
    int second_array[VERY_LARGE_ARRAY_SIZE] ;

can we compute wcet easily (using previous equation)?

**note:** maximum size of loop is known → `VERY_LARGE_ARRAY_SIZE * 2`

Note: pause and ask students what, if anything can go wrong?

---

### let's see what happens in each iteration

---

### let's see what happens in each iteration

| iter | operation | cache state | reason |
|--------|----------------------------|-------------------|---------------------------------------------|
| 1 | `first_array` loaded | miss | evicts whatever was previously in cache |

---

### let's see what happens in each iteration

| iter | operation | cache state | reason |
|----------------|----------------------------|-------------------|---------------------------------------------|
| 1 | `first_array` loaded | miss | evicts whatever was previously in cache |
| 2 | `second_array` loaded | miss | **evicts `first_array`** due to lack of space |

---

### let's see what happens in each iteration

---

program will _constantly_ sufffer cache misses!

---

program will _constantly_ sufffer cache misses!

### loop's execution time blows up!

---

program will _constantly_ sufffer cache misses!

### loop's execution time blows up!

<br>

now we need to model → **cache behavior** for program/data

---

### further complications from

other hardware features, _e.g.,_

- processor pipelining
- prefetching
- branch prediction
- multithreading
- multicore systems
- memory buses
- networks-on-chip
- and too many others to recount here...

---

processor feature → improves performance → *bad for wcet analysis*!

---

processor feature → improves performance → *bad for wcet analysis*!

### embedded/real-time systems prefer **simpler** processors

---

## embedded processors

come im myriad shapes and sizes:
1. Microcontrollers
2. Digital Signal Processors
3. Microprocessors
4. System-on-a-Chip
5. Embedded accelerators
6. ASICs and FPGAs

---

so, we focus on:

---

## Microcontrollers

---

## Microcontrollers

from [Wikipedia](https://en.wikipedia.org/wiki/Microcontroller),
>   "A microcontroller (MC, UC, or μC) or microcontroller unit (MCU) is a small computer  <br>
> on a single integrated circuit."

---

## Microcontrollers

- most common type of "processors" in embedded systems
- **[more than 55%](https://www.embedded.com/the-two-percent-solution/)** of the world's processors!

---

## Microcontrollers

- most common type of "processors" in embedded systems
- **[more than 55%](https://www.embedded.com/the-two-percent-solution/)** of the world's processors!
- **small, yet critical**, systems

---

## Microcontrollers

- most common type of "processors" in embedded systems
- **[more than 55%](https://www.embedded.com/the-two-percent-solution/)** of the world's processors!
- **small, yet critical**, systems 
    - car engine control
    - implantable medical devices
    - thermal monitoring
    - millions (billions?) of other applications!

---

## microcontroller hardware features

---

## microcontroller hardware features

| component | details |
|-----------|---------|
| one CPU core | typically simple `4` or `8` bit chips |

---

## microcontroller hardware features

| component | details |
|-----------|---------|
| one CPU core | typically simple `4` or `8` bit chips |
| small pipelined architectues | sometimes `2` or `4` stage pipelines |

---

## microcontroller hardware features

| component | details |
|-----------|---------|
| one CPU core | typically simple `4` or `8` bit chips |
| small pipelined architectues | sometimes `2` or `4` stage pipelines |
| some limited memory | typically a few hundred kilobytes, perhaps in the form of EEPROMs or FLASH |

---

## microcontroller hardware features

---

## microcontroller hardware features [contd.]

| component | details |
|-----------|---------|
| low operating frequencies | e.g., `4 KHz`; simpler/older processors, yet more predictable |

---

## microcontroller hardware features [contd.]

---

## microcontroller hardware features [contd.]

| component | details |
|-----------|---------|
| low operating frequencies | e.g., `4 KHz`; simpler/older processors, yet more predictable |
| low power consumption | in the **milliwatts** or **microwatts** ranges; might even be **nanowatts** when the system is _sleeping_ |
| interrupts (some programmable) | often _real-time_ (ficed/low latency) |

---

## microcontroller hardware features [contd.]

---

## microcontroller hardware features [contd.]

---

### **Additional features** found on some microcontrollers:

---

### **Additional features** found on some microcontrollers:

| component | details |
|-----------|---------|
| analog to digital (ADC) convertors | to convert incoming (real-world, sensor) data to a digital form that the uC can operate on |

---

### **Additional features** found on some microcontrollers:

| component | details |
|-----------|---------|
| analog to digital (ADC) convertors | to convert incoming (real-world, sensor) data to a digital form that the uC can operate on |
| digital-to-analog (DAC) convertor | to do the opposite, convert from digital to analog signals to send outputs in that form |

---

### **Additional features** found on some microcontrollers:

---

### **Additional features** [contd.]:

| component | details |
|-----------|---------|
| pulse width modulation (PWM) | so that the CPU can control **motors** (significant for us in autonomous/automotive systems), power systems, resistive loads, etc. |

---

### **Additional features** found on some microcontrollers:

---