The basics of programming embedded processors: Part 1

Program Design and Analysis

By Wayne Wolf
Embedded.com
(07/24/07, 01:00:00 AM EDT)
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.
Page 1of 6 Embedded Systems Design - Embedded.com
10/3/2010 mhtml:file://L:\Areas%20of%20Interest\Emb%20Systems\The%20basics%20of%20progr...
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.
Figure 5-1. A simple description of a design pattern
Page 2of 6 Embedded Systems Design - Embedded.com
10/3/2010 mhtml:file://L:\Areas%20of%20Interest\Emb%20Systems\The%20basics%20of%20progr...
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
Page 3of 6 Embedded Systems Design - Embedded.com
10/3/2010 mhtml:file://L:\Areas%20of%20Interest\Emb%20Systems\The%20basics%20of%20progr...

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.
Page 4of 6 Embedded Systems Design - Embedded.com
10/3/2010 mhtml:file://L:\Areas%20of%20Interest\Emb%20Systems\The%20basics%20of%20progr...
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.
i nt ci r c_buf f er [ N] ; / * ci r cul ar buf f er f or dat a */
i nt ci r c_buf f er _head = 0; / * cur r ent head of t he buf f er */
i nt c[ N] ; / * f i l t er coef f i ci ent s ( const ant s) */
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.
Figure 5-2. A circular buffer for streaming data
Page 5of 6 Embedded Systems Design - Embedded.com
10/3/2010 mhtml:file://L:\Areas%20of%20Interest\Emb%20Systems\The%20basics%20of%20progr...


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.
Next in Part 2: Models of programs.
Used with the permission of the publisher, Newnes/ Elsevier, this series of
six 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
Page 6of 6 Embedded Systems Design - Embedded.com
10/3/2010 mhtml:file://L:\Areas%20of%20Interest\Emb%20Systems\The%20basics%20of%20progr...