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
