Designing and implementing embedded programs is different and more challenging than writing typical workstation or PC programs. Embedded code must not only provide rich functionality, it must also often run at a required rate to meet system deadlines, fit into the allowed amount of memory, and meet power consumption requirements.

Designing code that simultaneously meets multiple design constraints is a considerable challenge, but luckily there are techniques and tools that we can use to help us through the design process. Making sure that the program works is also a challenge, but once again methods and tools come to our aid.

Presented in this series of six articles we will contentrate on high-level programming languages, specifically the C language. High-level languages were once shunned as too inefficient for embedded microcontrollers, but better compilers, more compilerfriendly architectures, and faster processors and memory have made highlevel language programs common.

Some sections of a program may still need to be written in assembly language if the compiler doesn't give sufficiently good results, but even when coding in assembly language it is often helpful to think about the program's functionality in high-level form. Many of the analysis and optimization techniques that we study in this chapter are equally applicable to programs written in assembly language.

Future parts in this series will discuss (1)  the control/data flow graph as a model for high-level language programs (which can also be applied to programs written originally in assembly language) with a particular focus on design patterns; (2) the assembly and linking process; (3) the basic steps in compilation; (4) optimization techniques specific to embedded computing for energy consumption, performance and size.

Design Patterns
A design pattern is a generalized description of a way to solve a certain class of problems. As a simple example, we could write C code for one implementation of a linked list, but that code would set in concrete the data items available in the list, actions on errors, and so on.

A design pattern describing the list mechanism would capture the essential components and behaviors of the list without adding unnecessary detail. A design pattern can be described in the Unified Modeling Language (UML); it usually takes the form of a collaboration diagram, which shows how classes work together to perform a given function.

Figure 5-1 below shows a simple description of a design pattern as a UML class diagram. The diagram defines two classes: List to describe the entire list and List-element for one of the items in the list. The List class defines the basic operations that you want to do on a list.

The details of what goes in the list and so forth can be easily added into this design pattern. A design pattern can be parameterized so that it can be customized to the needs of a particular application. A more complete description of the pattern might include

• state diagrams to describe behavior and
• sequence diagrams to show how classes interact.

Figure 5-1. A simple description of a design pattern

Design patterns are primarily intended to help solve midlevel design challenges. A design pattern may include only a single class, but it usually describes a handful of classes.

Design patterns rarely include more than a few dozen classes. A design pattern probably will not provide you with the complete architecture of your system, but it can provide you with the architectures for many subsystems in your design:

By stitching together and specializing existing design patterns, you may be able to quickly create a large part of your system architecture.

Design patterns are meant to be used in ways similar to how engineers in other disciplines work. A designer can consult catalogs of design patterns to find patterns that seem to fit a particular design problem.

The designer can then choose parameters suited to the application and see what that implies for the implementation of the design pattern. The designer can then choose the design pattern that seems to be the best match for the design, parameterize it, and instantiate it.

• Design patterns can be of many different types. A few are listed below.
• The digital filter is easily described as a design pattern.
• Data structures and their associated actions can be described as design patterns.
• A reactive system that reacts to external stimuli can be described as a design pattern, leaving the exact state transition diagram as a parameter.
• Douglass [Dou99] describes a policy class that describes a protocol that can be used to implement a variety of policies.

Design Patterns for Embedded Systems
In this section, we consider design patterns for two very different styles of programs: the state machine and the circular buffer. State machines are well suited to reactive systems such as user interfaces, and circular buffers are useful in digital signal processing.

State machine style. When inputs appear intermittently rather than as periodic samples, it is often convenient to think of the system as reacting to those inputs. The reaction of most systems can be characterized in terms of the input received and the current state of the system. This leads naturally to a finite-state machine style of describing the reactive system's behavior.

Moreover, if the behavior is specified in that way, it is natural to write the program implementing that behavior in a state machine style. The state machine style of programming is also an efficient implementation of such computations.

Finite-state machines are usually first encountered in the context of hardware design.The programming example describe below shows how to write a finite-state machine in a high-level programming language.

Programming Example: A state machine in C
The behavior we want to implement is a simple seat belt controller [Chi94]. The controller's job is to turn on a buzzer if a person sits in a seat and does not fasten the seat belt within a fixed amount of time. This system has three inputs and one output.

The inputs are a sensor for the seat to know when a person has sat down, a seat belt sensor that tells when the belt is fastened, and a timer that goes off when the required time interval has elapsed. The output is the buzzer. Shown below is a state diagram that describes the seat belt controller's behavior.

The idle state is in force when there is no person in the seat. When the person sits down, the machine goes into the seated state and turns on the timer. If the timer goes off before the seat belt is fastened, the machine goes into the buzzer state. If the seat belt goes on first, it enters the belted state. When the person leaves the seat, the machine goes back to idle.

To write this behavior in C, we will assume that we have loaded the current values of all three inputs ( seat , belt , timer ) into variables and will similarly hold the outputs in variables temporarily ( timer_on , buzzer_on ). We will use a variable named state to hold the current state of the machine and a switch statement to determine what action to take in each state. The code follows:

 #define IDLE 0
 #define SEATED 1
 #define BELTED 2
 #define BUZZER 3

This code takes advantage of the fact that the state will remain the same unless explicitly changed; this makes self-loops back to the same state easy to implement.

This state machine may be executed forever in a while(TRUE) loop or periodically called by some other code. In either case, the code must be executed regularly so that it can check on the current value of the inputs and, if necessary, go into a new state.

Data stream style. The data stream style makes sense for data that comes in regularly and must be processed on the fly. The FIR filter of the example shown above is a classic example of stream-oriented processing. For each sample, the filter must emit one output that depends on the values of the last n inputs.

In a typical workstation application, we would process the samples over a given interval by reading them all in from a file and then computing the results all at once in a batch process. In an embedded system we must not only emit outputs in real time, but we must also do so using a minimum amount of memory.

The circular buffer is a data structure that lets us handle streaming data in an efficient way. Figure 5-2 below illustrates how a circular buffer stores a subset of the data stream. At each point in time, the algorithm needs a subset of the data stream that forms a window into the stream.

The window slides with time as we throw out old values no longer needed and add new values. Since the size of the window does not change, we can use a fixed-size buffer to hold the current data.

Figure 5-2. A circular buffer for streaming data

To avoid constantly copying data within the buffer, we will move the head of the buffer in time. The buffer points to the location at which the next sample will be placed; every time we add a sample, we automatically overwrite the oldest sample, which is the one that needs to be thrown out.

When the pointer gets to the end of the buffer, it wraps around to the top. Described below is an example of an efficient implementation of a circular buffer.

Programming Example: A circular buffer for an FIR filter
Appearing below are the declarations for the circular buffer and filter coefficients, assuming that N , the number of taps in the filter, has been previously defined.

 int circ_buffer[N]; /* circular buffer for data */
 int circ_buffer_head = 0; /* current head of the buffer */
 int c[N]; /* filter coefficients (constants) */

To write C code for a circular buffer-based FIR filter, we need to modify the original loop slightly. Because the 0th element of data may not be in the 0th element of the circular buffer, we have to change the way in which we access the data. One of the implications of this is that we need separate loop indices for the circular buffer and coefficients.

The above code assumes that some other code, such as an interrupt handler, is replacing the last element of the circular buffer at the appropriate times. The statement 1buff = (ibuff == (N " 1) ? 0 : ibuff++) is a shorthand C way of incrementing ibuff such that it returns to 0 after reaching the end of the circular buffer array.

To read Part 2 , go to "Models of program, assemblers and linkers."
To read Part 3, go to  "Basic Compilation Techniques"
To read Part 4, go to  "The creation of procedures"
To read Part 5, go to  "Register allocation and scheduling"
To read Part 6, go to  "Analysis and optimization of execution time"
To read Part 7, go to  "Trace-Driven Performance Analysis"
To read Part 8, go to  "Analysis and optimization of energy and power."
To read Part 9, go to  "Program validation and testing."

Used with the permission of the publisher, Newnes/Elsevier, this series of nine articles is based on copyrighted material from "Computers as Components: Principles of Embedded Computer System Design" by Wayne Wolf. The book can be purchased on line.

Wayne Wolf  is currently the Georgia Research Alliance Eminent Scholar holding the Rhesa "Ray" S. Farmer, Jr., Distinguished Chair in Embedded Computer Systems at Georgia Tech's School of Electrical and Computer Engineering (ECE). Previously a professor of electrical engineering at Princeton University, he worked at AT&T Bell Laboratories. He has served as editor in chief of the ACM Transactions on Embedded Computing and of Design Automation for Embedded Systems.

References:
[Dou99] Bruce Powell Douglas, Doing Hard Time: Developing  Real Time Systems with UML. Addison Wesley, 1999.
[Chi94] M.Chiodo, et. al., "Hardware/software codesign of Embedded Systems," IEEE Micro, 1994