Designing and implementing embedded programs isdifferent and more challenging than writing typical workstation or PCprograms. Embedded code must not only provide rich functionality, itmust also often run at a required rate to meet system deadlines, fitinto the allowed amount of memory, and meet power consumptionrequirements.
Designing code that simultaneously meets multipledesign constraints is a considerable challenge, but luckily there aretechniques and tools that we can use to help us through the designprocess. 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 willcontentrate on high-level programming languages , specifically the C language.High-level languages were once shunned as too inefficient for embeddedmicrocontrollers, but better compilers, more compilerfriendlyarchitectures, and faster processors and memory have made highlevellanguage programs common.
Some sections of a program may still need to bewritten in assembly language if thecompiler doesn't give sufficientlygood results, but even when coding in assembly language it is oftenhelpful to think about the program's functionality in high-level form.Many of the analysis and optimization techniques that we study in thischapter are equally applicable to programs written in assembly language.
Future parts in this series will discuss (1) the control/data flow graph as amodel for high-level language programs(which can also be applied to programs written originally in assemblylanguage) with a particular focus on design patterns ; (2) theassemblyand linking process; (3) the basicsteps in compilation; (4)optimization techniques specificto embedded computing for energyconsumption, performance and size.
A design pattern is a generalized description of a way to solve a certain class ofproblems. As a simple example, we could write C code for oneimplementation of a linked list, but that code would set in concretethe data items available in the list, actions on errors, and so on.
A design pattern describing the list mechanism would capture theessential components and behaviors of the list without addingunnecessary detail. A design pattern can be described in the UnifiedModeling Language (UML); itusually takes the form of a collaboration diagram, which shows howclasses 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 thebasic operations that you want to do on a list.
The details of what goes in the list and so forth canbe easily added into this design pattern. A design pattern can beparameterized so that it can be customized to the needs of a particularapplication. A more complete description of the pattern might include
- state diagrams to describe behavior and
- sequence diagrams to show how classes interact.
|Figure5-1. A simple description of a design pattern|
Design patterns are primarily intended to help solvemidlevel design challenges. A design pattern may include only a singleclass, but it usually describes a handful of classes.
Design patterns rarely include more than a few dozenclasses. A design pattern probably will not provide you with thecomplete architecture of your system, but it can provide you with thearchitectures for many subsystems in your design:
By stitching together and specializing existingdesign patterns, you may be able to quickly create a large part of yoursystem architecture.
Design patterns are meant to be used in ways similarto how engineers in other disciplines work. A designer can consultcatalogs of design patterns to find patterns that seem to fit aparticular design problem.
The designer can then choose parameters suited to theapplication and see what that implies for the implementation of thedesign pattern. The designer can then choose the design pattern thatseems to be the best match for the design, parameterize it, andinstantiate it.
- Design patterns can be of many different types. Afew are listed below.
- The digital filter is easily described as a designpattern.
- Data structures and their associated actions canbe described as design patterns.
- A reactive system that reacts to external stimulican be described as a design pattern, leaving the exact statetransition diagram as a parameter.
- Douglass [Dou99] describes a policy class thatdescribes a protocol that can be used to implement a variety ofpolicies.
Design Patterns for Embedded Systems
In this section, we consider design patterns for two very differentstyles of programs: the state machine and the circular buffer. Statemachines are well suited to reactivesystems such asuser interfaces, and circular buffers are usefulin digital signal processing.
State machinestyle . When inputs appear intermittently rather than asperiodic samples, it is often convenient to think of the system asreacting to those inputs. The reaction of most systems can becharacterized in terms of the input received and the current state ofthe system. This leads naturally to a finite-statemachinestyle 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 astate machine style. The state machine style of programming is also anefficient implementation of such computations.
Finite-state machines are usually first encounteredin the context of hardware design.The programming example describebelow shows how to write a finite-state machine in a high-levelprogramminglanguage.
Programming Example: A state machine in C
The behavior we want to implement is a simple seat belt controller[Chi94] . The controller's jobis to turn on a buzzer if a person sitsin a seat and does not fasten the seat belt within a fixed amount oftime. This system has three inputs and one output.
The inputs are a sensor for the seat to know when aperson has sat down, a seat belt sensor that tells when the belt isfastened, and a timer that goes off when the required time interval haselapsed. The output is the buzzer. Shownbelow is a state diagram thatdescribes the seat belt controller'sbehavior.
The idle state is in force when there is no person inthe seat. When the person sits down, the machine goes into the seatedstate and turns on the timer. If the timer goes off before the seatbelt is fastened, the machine goes into the buzzer state. If the seatbelt goes on first, it enters the belted state. When the person leavesthe seat, the machine goes back to idle.
To write this behavior in C, we will assume that wehave loaded the current values of all three inputs ( seat , belt ,timer ) into variables and will similarly hold the outputs in variablestemporarily ( timer_on , buzzer_on ). We will use a variable namedstate to hold the current state of the machine and a switch statementto 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 statewill remain the same unless explicitly changed; this makes self-loopsback to the same state easy to implement.
This state machine may beexecuted forever in a while(TRUE) loop or periodically called by someother code. In either case, the code must be executed regularly so thatit can check on the current value of the inputs and, if necessary, gointo a new state.
Data streamstyle. The data stream style makes sense for data thatcomes in regularly and must be processed on the fly. The FIR filter ofthe example shown above is a classic example of stream-orientedprocessing. For each sample, the filter must emit one output thatdepends on the values of the last n inputs.
In a typical workstation application, we wouldprocess the samples over a given interval by reading them all in from afile and then computing the results all at once in a batch process. Inan embedded system we must not only emit outputs in realtime, but we must also do so using a minimum amount of memory.
The circular buffer is a data structure that lets ushandle streaming data in an efficient way. Figure 5-2 below illustrates how acircular buffer stores a subset of the data stream. At each point intime, the algorithm needs a subset of the data stream that forms awindow into the stream.
The window slides with time as we throw out oldvalues no longer needed and add new values. Since the size of thewindow does not change, we can use a fixed-size buffer to hold thecurrent 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 thelocation at which the next sample will be placed; every time we add asample, we automatically overwrite the oldest sample, which is the onethat needs to be thrown out.
When the pointer gets to the end of the buffer, itwraps around to the top. Described below is an example of an efficientimplementation of a circular buffer.
Programming Example: A circular buffer for anFIR filter
Appearing below are the declarations for the circular buffer andfilter coefficients, assuming that N , the number of taps in thefilter, has been previouslydefined.
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 FIRfilter, we need to modify the original loop slightly. Because the 0thelement 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 theimplications of this is that we need separate loop indices for thecircular buffer and coefficients.
The above code assumes that some other code, such as an interrupthandler, is replacing the last element of the circular buffer at theappropriate times. The statement 1 buff = (ibuff == (N ” 1) ? 0 : ibuff++) is ashorthand C way of incrementing ibuff such that it returns to 0 afterreaching the end of the circular buffer array.
To read Part 2 , go to “Modelsof program, assemblers and linkers.”
To read Part 3, go to “BasicCompilation Techniques“
To read Part 4, go to “The creation ofprocedures“
To read Part 5, go to “Registerallocation and scheduling“
To read Part 6, go to “Analysis andoptimization of execution time“
To read Part 7, go to “Trace-DrivenPerformance Analysis”
To read Part 8, go to “Analysisand optimization of energy andpower.“
To read Part 9, go to “Program validation andtesting.”
Usedwith the permission of the publisher, Newnes/Elsevier, this series ofnine articles is based on copyrighted material from “Computersas Components: Principles of Embedded Computer System Design“ by Wayne Wolf. The bookcan be purchased on line.
Wayne Wolf is currently the GeorgiaResearch Alliance Eminent Scholar holding the Rhesa “Ray” S. Farmer,Jr., Distinguished Chair in Embedded Computer Systems at Georgia Tech'sSchool of Electrical and Computer Engineering (ECE). Previously aprofessor of electricalengineering at Princeton University, he worked at AT&T BellLaboratories. He has served as editor in chief of the ACM Transactionson Embedded Computing and of DesignAutomation for Embedded Systems.
[Dou99] BrucePowell Douglas, Doing Hard Time: Developing Real Time Systemswith UML. Addison Wesley, 1999.
[Chi94] M.Chiodo, et. al., “Hardware/software codesign of Embedded Systems,”IEEE Micro, 1994