The basics of programming embedded processors: Part 1

Wayne Wolf

July 24, 2007

Wayne Wolf

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