Characteristics of embedded computing algorithms

Embedded computing systems may provide sophisticated functionality.

Properties

Embedded vs General Purpose Systems

System design flow

Requirements → Specification → Architecture → Components → Integration

Summary

Embedded computing, while fun, is often very complex. This is mostly due to the strict constraints that must be satisfied. Trying to hack together a complex embedded system probably won't work, so a design process is needed. Features such as being able to perform to certain deadlines, consuming very little power, be of a certain size and more are very common in embedded systems. Both top-down and bottom-up processes of design might be needed to successfully develop an embedded system.

Computer architecture

A computer usually has one of two architectures. Either von Neumann or Harvard. Both architectures has a CPU, but the memory design is different. The von Neumann architecture has one shared memory for data and programs, connected to the CPU by a bus. In this architecture the CPU has one internal register which is the program counter (PC), which keeps track of what part of the memory is run. The PC is then updated to run a different instruction from memory. Harvard on the other hand, has one memory for programs and one for data which are both connected to the CPU. One effect of the Harvard architecture is that it's harder to write self modifying programs, since the data is completely separate from the program. Harvard architecture is widely used today for one very good reason – it allows for higher performance when it comes to digital signal processing. Since there are two ports for memory management you get a higher bandwidth. It also makes it easier to move the data at the correct times.

A microcontroller is defined as a single-chip computer that includes a processor, memory and programmable I/O devices.

Assembly languages

Another axis in which one can see computer architecure relates to their instruction set and how they are executed. Many early computers had an instruction set which today is known as CISC (complex instruction set computers). This involves many instructions which can do all sorts of things like finding a substring in a string, having loads and loads of instructions with varying length and so on. Another way of making computers is known as the RISC (reduced instruction set computers). This architecture tended towards having fewer and simpler instructions. RISC machines tended to use the load/store instruction set. This means that you can't do data manipulation directly in memory, but have to load data into registers and store it back in memory when the task is done. RISC instructions were chosen so they could be efficiently pipelined in the processor and was heavily optimized. Early RISC machines substantially outperformed CISC machines, though this has narrowed slightly in recent years.

Some other characteristics of assembly languages are:

There are different assembly languages per computer architecture, but they usually share the same basic features:

• One instruction appears per line.
• Labels, which give names to memory locations, start in the first column.
• Instructions must start in the second column or after to distinguish them from labels.
• Comments run from some designated comment character to the end of the line.

Multi-instruction execution

In some cases, where multiple executions have no dependencies, the CPU can execute several instructions simultaneously. One technique to achieve this (used by desktop and laptop computers), is by using superscalar execution. A superscalar processor scans the program during execution to find sets of instructions that can be executed together. Another technique to achieve simultaneous instruction execution, is by using very long instruction word (VLIW) processors. These processors rely on the compiler to identify sets of instructions that can be executed in parallel.

ARM

ARM is a family of RISC (Reduced instruction set computer) architectures. ARM instructions are written as follows:

        LDR r0,[r8] ; comment goes here
label:  ADD r4,r0,r1W

We can see that ARM instructions are written one per line, and that comments begin with a semicolon and continue to the end of the line. The label gives a name to a memory location, and comes at the beginning of the line, starting in the first column.

ARM assembly can also use C-like comments and block comments.

        LDR r0,[r8] ; comment goes here
        // and here
label:  ADD r4,r0,r1W
        /* and even
         * here
         */

ldr r3, [fp, #-24]
lsl r2, r3, #2
ldr r3, [fp, #-28]
and r3, r3, #15
orr r3, r2, r3
str r3, [fp, #-44]

if (a > b) {
    a = 5;
} else {
    b = 3;
}

.L1:
    ;r2=a r3=b
    ldr r2, [fp, #-24]
    ldr r3, [fp, #-28]
    cmp r2, r3

    ; jump if true
    bgt .L3

    ; false block
    mov r3, #3
    str r3, [fp, #-28]
    b .L4

.L3:
    ; true block
    mov r2, #5
    str r2, [fp, #-24]

.L4:
    ; continue here

r1 = 0x00 0xfe 0x00 0xfe
r2 = 0x11 0x01 0x10 0x01

simd_add r1, r1, r2
r1 = 0x11 0xff 0x10 0xff

Input and output mechanisms.

I/O-devices typically have several registers, data registers and status registers.

It is very common for a devices status and data registers to be mapped into the main memory. Some architectures (Intel x86) provide a seperate address space for I/O devices and special instructions for reading/writing from/to devices.

STATUS    = 0x40006080

; Read from status register
LDR r0, =STATUS
LDR r1, [r0]

; Write to data register
STR r1, [r0, #0x4]

#define STATUS 0x40006080

// Reading
uint32_t status_val = *STATUS;

// Writing
*(++STATUS) = status_val;

Supervisor mode, exceptions, and traps

Memory system mechanics

The clock speeds of processors are increasing at a much higher rate than what the memory access rate is. It is therefore useful to have ways to narrow the gap between processing speeds and memory reading/writing speeds.

Performance and power consumption of CPUs.

Buses

A bus provides a common connection between the CPU and the memory and/or I/O devices. The word bus refers to both the physical connection and the protocol by which the connection is established. Signals transmitting on the bus contains the data itself, addresses, a clock and some control signals.

The primary task of a bus is to provide an interface to memory. Every bus has a bus master, assuring that only one process is active on the bus. In a typical bus, the CPU functions as the bus master.

Most buses utilize the four-cycle handshake, which ensures a safe connection. This works in the following way: Device 1 signals that it’s ready to transmit, device 2 signals that it’s ready to receive, device 2 signals that it has received the data, device 1 ends the transmission.

Data can be transmitted in different ways on the bus. A burst transfer refers to transmitting data repeatedly without going through all the steps required to transmit each piece of data in a separate transaction. A disconnected transfer refers to requesting the transfer, and then completing it later, freeing the processor in the meantime.

Direct Memory Access (DMA) refers to a bus operation that allows reading and writing data without the use of the CPU. This is established through a two-step process: First, the DMA controller sends a bus request to the CPU. Then, the CPU sends a bus grant to the DMA controller. When this is done, the DMA can act as a bus master. The CPU enables DMA by writing to registers in the DMA controller; when the DMA operation is complete, the CPU receives an interrupt. Since the CPU can’t access the bus while the DMA is active, cyclic scheduling of DMA requests is frequently used, meaning that the DMA occupies the bus for only a few cycles at a time.

Multiple bus configurations are used, since the purpose of the bus may differ. Smaller buses have fewer connections and less risk of being occupied. Larger buses can access more of the system. Also, the higher the speed of the bus, the higher the cost. It is therefore common to connect different buses together. Interconnected buses utilize a bridge to communicate with each other. The bridge acts as a master for one bus, and a slave for the other.

Bus bandwidth refers to the data capacity of the bus. The transfer time in clock cycles can be measured with the two following formulas:

$$ T_{basic}(N) = (D + O) \frac{N}{W} $$ (for basic transfers, where N is data size in bytes, D is clock cycles the data transfer requires, O is overhead both before and after the data, and W is the width of the set of bytes)

$$ T_{burst}(N) = (BD + O) \frac{N}{BW} $$ (for burst transfers, where N is data size in bytes, D is clock cycles the data transfer requires, O is overhead per burst, B is the number of transfers, and W is the size in bytes of each transfer)

Memory

Choosing a computing platform

When choosing a computing platform for your embedded system, you should adapt both the CPU, bus, memory and I/O devices to what suits your needs. You should also choose the right software to run on your system.

Consumer electronic devices

Consumer electronics should abide to both functional and non-functional requirements. The first are technical specifications that the system should support. The latter are things like battery life, looks and price.

Circular buffers and stream-oriented programming

Many embedded systems, especially DSP-based ones, do work on streams of data. A circular buffer is a memory efficient data structure for handling such streams. If we assume our algorithm needs a certain subset of the the data stream to process the next output, we can use a circular buffer to contain a window into the data stream at a current time. Since the size of this window doesn't change, the buffer can also be of constant size.

In practice, a circular buffer is implemented as an array and a position variable pointing to the start of the current window in the array.

data: 1 2 3 4 5
time  --->

buf = 1 2 3 4

buf = 5 2 3 4

Models of programs

A control/data flow graph (CDFG) is used as a unifying way of modeling programs. It allows us to describe program behaviour regardless of what programming language is utilised or what platform it is supposed to run on. A typical CDFG consists of components describing both data and control operations.

Assembly, linking and loading

+----------------------+   +--------+   +-------------+   +---------+
|High level source code|-->|Compiler|-->|Assembly code|-->|Assembler|
+----------------------+   +--------+   +-------------+   +---------+
                                                               |
                                                               ▼
                                                         +-----------+
                                                         |Object code|
                                                         +-----------+
                                                               |
                                                               ▼
         +---------+    +------+    +-----------------+    +------+
         |Execution|<---|Loader|<---|Executable binary|<---|Linker|
         +---------+    +------+    +-----------------+    +------+

Cyclomatic complexity

A simple measure of a programs control complexity is it's cyclomatic complexity. Cyclomatic complexity is the number of linearly independent paths through the execution of a program. It is calculated as follows:

$M = E - N + 2P$

Where E is the number of edges in the programs CDFG, N is the number of nodes and P is the number of connected components.

Processes

A process is a single execution of a program, and has its own state that includes registers and memory for that process. If multiple processes share the same address space, they are called threads.

Asynchronous input refers to input that does not coincide with a timer or at a certain rate; like a button in an app that can be pressed at any time.

A multirate system refers to a system that is required to perform tasks which differ in computational speed or rate, e.g. a camera that is capable of both taking pictures and shooting video. Multirate embedded computing systems like this camera are very common.

The operating system considers a process to be in one of three basic states: waiting, ready or executing. Only one process can execute at the CPU at any time, unless you have a multicore processor.

How much of the CPU time is used doing actual processing? This is called utilization, and can be found with the following formula: $ U = \frac{\text{CPU time for useful work}}{\text{total available CPU time}} $

or more generally

$ U = \frac{C}{T} = \frac{\text{Computation time}}{\text{Period}} = \frac{\text{Active}}{\text{Active} + \text{Idle}} $

Processes in embedded systems often have timing requirements. The most common requirements are initiation time, deadline and rate. The first refers to the time it takes for a process to go from the waiting state to the ready state. The next refers to a certain time when the process must be completed; failure to do so can have fatal consequences. The last specifies how quickly a process must be initiated.

Virtual memory

The computer's operating system, using a combination of hardware and software, maps memory addresses used by a program, called virtual addresses, into physical addresses in computer memory. Main storage, as seen by a process or task, appears as a contiguous address space or collection of contiguous segments. The operating system manages virtual address spaces and the assignment of real memory to virtual memory. Address translation hardware in the CPU, often referred to as a memory management unit (MMU), automatically translates virtual addresses to physical addresses. Software within the operating system may extend these capabilities to provide a virtual address space that can exceed the capacity of real memory and thus reference more memory than is physically present in the computer.

A benefit to virtual memory is freeing applications from having to manage a shared memory space, increased security due to memory isolation, and being able to conceptually use more memory than might be physically available, using the technique of paging.

Real-time Operating Systems

Preemptive OS-es can switch processes at any time (usually when a higher priority task is issued), while non-preemptive OS-es waits for the process to complete or for the process to yield control to the kernel. Another term for non-preemptiveness is cooperative multitasking. The kernel is the part of the OS that defines the running process and performs process switches.

Low priority tasks running on preemptive platforms may still refuse to yield control with the use of critical sections.

Context switching is another word for process switching, since the set of registers that defines a process is known as its context.

Shared resources refer to parts of the system that should only be accessed by one process at any time. If not secured properly, multiple accesses can result in race conditions, meaning that the data of a process is overwritten by another process. To prevent this, we can use semaphores, which acts as a stop sign for the other processes while a process is accessing a resource. After completion, the semaphore is removed, signaling that processes again can safely access the resource. A resource that can impose race conditions is often called a critical region.

Comment: Removed? I think this section is mixing up mutal exclusion (mutex) and semaphores, although neither is "removed" rather than respectively posted/waited locked/unlocked. Semaphores (or even recursive mutexes) are incremented and decremented based on the amount of accesses permitted.

OS performance depends on several factors. The most important are context switching time and interrupt latency, referring to the time it takes to perform context switches and interrupt service routines, respectively.

Scheduling

A scheduling policy defines how processes are selected for promotion from the ready state to the execution state, AKA context switching. Different algorithms exist for this purpose. However, we must consider scheduling overhead, which is the execution time required to perform these algorithms and also perform the actual process switch.

Here are the most used priority-based scheduling algorithms:

Interprocess Communication

In general, processes can communicate with each other in two ways: Blocking or nonblocking. The first means that the process enters the waiting state while requesting a response. The latter means that the process can continue executing while waiting for a response.

Two major styles of communicating is shared memory and message passing. Both is logically equivalent. The first means that the communication happens through reading and writing to registers on a shared resource. The latter means that a message is actively sent to another process. A FIFO queue is commonly used for this purpose.

For UNIX, signals can also be used for interprocess communication. A signal is sent directly to the other process, without passing data except for the signal itself.

A mailbox is a simple mechanism for receiving messages. Some systems integrate a mailbox into the process itself. A mailbox can contain a message and a mail ready bit. When the message is delivered, mail ready is set to true. When the process reads the message, mail ready returns to false.