Programmable Logic

High-Speed State Machine Design

Three methods can be used to describe state flows. While each has its own list of pros and cons, a composite method could provide the answer.

by Stephen L. Wasson

High-performance state machine design has two primary objectives: to ensure that the state machine performs the way the designer wants, and performs the way the designer wants.

Getting one's way means transcribing a complete and proper state flow model. Getting one's performance means the model's implementation will actually run at the speed desired. Of three contemporary ways to describe state flow­flowcharts, HDLs, and bubble diagrams­all focus on transcription performance, none on implementation performance. The following reviews some strengths and weaknesses of each method and then presents a composite methodology for high-performance state-machine design.

The designer's first objective in state-machine design is writing a complete and proper model. A complete model accounts for all the possible stimuli; a proper model rationalizes all the directed responses. State machine models typically suffer three kinds of errors: holes, conflicts, and being just plain wrong. Holes occur when no response is directed for a given stimulus condition. Conflicts occur when multiple responses are specified for the same stimulus condition. Although most of the current state-machine entry tools catch the conflicts, and most are getting more intelligent about assuming the unspecified-else conditions, few compel a complete accounting at entry of a proper state-flow model. Things that are wrong could have any number of root problems, and will require detective work.

The second objective in state-machine design is to generate an implementation that satisfies the required performance criteria and does so repeatedly. State machine performance is a function of both the next-state and the output functions. In both cases, in today's FPGAs, the speed of these functions is determined by the number of logic levels traversed. Although some tools are getting more intelligent about logic-level reduction, none adequately address repeat performance.

Compilable flowcharts Dating back to programming in the '60s, flowcharts provide an environment of old-world familiarity. They are easy to learn, and they present state flow in a modestly manageable format. Figure 1 depicts the state flow for the PCI Target IDLE state and its exit decisions. These schematic symbols are merely macro calls to lower-level primitives. Figure 2 shows the compiled gate equivalent: the state bit becomes a single flip-flop, and each decision becomes a pair of "yes/no" gates.

Figure 1. Shown is one possible flowchart representation for the PCI Target IDLE State.

However, as design demands increase, compilable flowchart advantages decrease. Note in Figure 2 that successive decisions incur successive delays­the nested-if problem. And similar to if-then-else code, the transitions are decision-order dependent which can result in impossible exit conditions. Without a post-processing tool to check for next-state holes, conflicts, or impossible exits, compilable flowcharts are the least viable state-machine implementation option.

Figure 2. After compilation, the flowchart in Figure 1 reduces to this circuit. Note that NS_BKOF is already three logic levels deep. This is also the kind of logic that if-then-else code produces.

HDLs Borrowed from programming (where the H stands for hardware, not high-level), HDLs are time-tested state-machine modeling mechanisms. Such text-based tools­including equation entry tools­enjoy the advantages of terse entry and rapid synthesis. Listing 1 shows the PCI Target IDLE and BUSY state equations (more compactly and accurately than Figure 1). Overall state flow is obscure, however. With simple equation entry tools, the more equations there are, the more obscure the state flow becomes; with HDLs, more code means more obscure logic levels.

Listing 1
PCI Target equations



from IDLE
1 goto IDLE if
FRAME#
2 goto BUSY if !FRAME# * !Hit
3 goto DATA if !FRAME# * Hit
*(Term + Term * Ready) * (FREE + LOCKED * LOCK#)
4 goto BKOF if !FRAME# * Hit
*(Term * !Ready + LOCKED * !LOCK#)
from BUSY
5 goto BUSY if (!FRAME# + IRDY#) * !Hit
6 goto IDLE if FRAME#
7 goto DATA if (!FRAME# + !IRDY#) * Hit
*(!Term + Term * Ready) * (FREE + LOCKED *
L_lock#)
8 goto BKOF if (!FRAME# + !IRDY#) * Hit
*( Term * !Ready + LOCKED * !L_lock#)

Of course, respectable HDL tools will find holes, conflicts, or impossible combinations; and, if one's equations are correct, good tools can correctly assume the unspecified-else conditions. Still, some synthesis tools tend to optimize their HDL modules with immutable blocks and hard boundaries; that is, with blocks that may not integrate optimally with other modules. Such "hard" modules are frequently a source of performance degradation in FPGA implementations. Moreover, with HDLs, provisions for complete up-front flow verification and proper logic-level control are less than optimal for high-performance implementations.

Bubble diagrams With the benefits of both flowcharts and equation entry, bubble diagrams depict both state flow and functionality compactly and quickly. Figure 3 illustrates the whole flow of the PCI Target state machine (where numbered transition arrows correspond to the numbered lines in Listing 1). While it is true that, on paper, transition and output equations may clutter up the drawing, this detraction is more manageable with up-and-coming state-machine generators like the FSM tool from Escalade (Sunnyvale, CA), or StateCAD from Data I/O (Redmond, WA). Bubble diagram tools alone, however, still reliant on equations, unspecified-else assumptions, and logic synthesis, neither compel rigorous entry analysis nor control logic level reduction.

Figure 3. The numbered transitions correspond to the numbered line equations in Listing 1.

A composite methodology Rapid entry has been the primary focus of state machine tools thus far. Preliminary verification has consisted mostly of conflict resolution, and pre-implementation logic-level reduction has been largely unaddressed.

There are four key steps in outlining a composite methodology for entry and verification of state flow and functionality with logic-level reduction prior to synthesis or simulation:

1. ) Enter state flow using bubble diagrams.

2. ) Specify next-state transitions using equations.

3. ) Analyze next-state equations using Karnaugh maps.

4. ) Optimize next-state logic using common sense.

Next-state analysis After depicting all state flow and specifying all next-state transitions, one can make a complete analysis of next-state equations by simple application of Karnaugh maps. Filling in the maps will immediately and unambiguously resolve all transition holes and conflicts (without unspecified-else assumptions). Although Karnaugh maps are most manageable for five or fewer variables, simple reduction and factoring techniques make them effective in complex equations of six or more variables. This apparent limitation is even a perfect match with fine-grained FPGA architectures in which the function generators have five or fewer inputs.

For example, assuming the state flow of bubble diagram Figure 3 with the transition equations given in Listing 1, the next-state analysis for state IDLE may be represented by the hierarchical Karnaugh map in Figure 4. Since the transition equations consist of seven variables, it is convenient (and easy) to factor out the two dominant variables, FRAME# and Hit. These two variables are mapped into the primary map such that three possibilities simply point to next-state IDLE or BUSY , and the fourth possibility­at !FRAME# * Hit ­hierarchically points to the secondary map. Then, given that FREE and LOCKED are dependent variables­ LOCKED = !FREE ­a secondary map of four variables completes the full and proper specification of the remaining transitions from state IDLE.

Figure 4. This Karnaugh map shows the next-state transitions from the PCI Target IDLE State for the equations given in Listing 1 and the state flow depicted in Figure 3.

Transitions from state BUSY do not seem to be as well specified. In Figure 5, the dominant variables are again factored out: FRAME#, IRDY# , and Hit comprise the primary map. But this time, ambiguities are immediately evident in the two squares mapped to the term FRAME# * !IRDY . For FRAME# * !IRDY * !Hit , simultaneous transitions are specified both to IDLE and to BUSY ; for FRAME# * !IRDY * Hit , simultaneous transitions are specified both to IDLE and to the secondary map. However, these ambiguities can be resolved if, in Listing 1, line six, after " goto IDLE ," the " if " statement is amended to read FRAME# * IRDY# .

Figure 5. Next-state assignments mapped at FRAME# * !IRDY are in conflict illustrating the incompletely specified equation line 6 of Listing 1.

Next-state optimization The primary goal of next-state optimization is logic-level reduction; a secondary goal in FPGAs is to map in flexibility. Current implementation tools obscure these efforts. Whereas state flow is best described with the " from-goto " construct, next-state optimization is best facilitated with the opposite " goto-from " construct. Note the " from-goto " bias of all the aforementioned tools. Only the bubble diagram is readily interpretable in either point of view. One can rearrange equation descriptions easily enough to accommodate next-state optimization, but flowcharts are of little value in this analysis.

The initial step in next-state optimization consists of gathering up all the next-state terms. This is equivalent to accounting for all the transitions into a state bubble. For example, in contrast to Listing 1, next-state IDLE entry equations would be gathered up as follows:

goto IDLE

from IDLE if...

from BUSY if...

from TNAR if...

Then, in the absence of a sophisticated optimization tool with constraint hooks for such factors as signal margins (how much of the clock period has already been consumed by the time a signal arrives at a function) or expansion terms (how many more inputs may be added to a particular term), apply common sense.

In an FPGA, applying common sense may mean duplicating terms if that contributes to better mapping and hence to logic-level reduction. Common sense may also suggest one rearrange equation terms to balance input signal margins by moving "late" arrivals forward (toward the clocked element input) and by moving "early" arrivals back. For example, in a "slow" PCI Target, the Hit term may be registered, and therefore may be moved to the rear of most next-state logic chains; but, in "medium" PCI Target implementations, Hit is likely to be a late combinatorial signal and therefore should be moved forward. Common sense also dictates that optimizing for an FPGA means matching equation term sizes to function generator widths, with considerations for future expansions. Attention to such detail promotes predictable, repeat, high performance.

Output function optimization Neither Mealy nor Moore outputs are optimal for high-performance, synchronous FPGA designs. Instead, registered outputs derived from next-state inputs yield higher performance. Logic-level reduction issues and techniques are similar to those discussed for next-state optimizations with the additional note that it will benefit output function performance to duplicate the entire next-state logic cloud (see "Design Notes").

Future FSM generations Of course, all of these fine-grained manipulations should be done automatically, and someday they will be. Bubble diagram tools are an excellent start, but they need to be expanded to provide hierarchical modeling to facilitate more complex, hierarchical state machines and to accommodate more rigorous next-state analysis. Designers should be able to push through bubble trees down to leaf nodes that contain interactive Karnaugh maps. These maps should be automatically filled in from the initial next-state equation specifications, and all holes, conflicts, and else-assumptions should be clearly indicated. At this level, the designer should be able to perform map manipulations that automatically back-annotate the next-state equations.

Both next-state and output equations should also have some graphical representation which quickly illustrates their equation-term hierarchy and thereby their logic-level costs. This representation should also be manipulable to exploit term associative properties­parentheses re-arrangements­to facilitate early and late signal margins and to accommodate future term expansions without impacting logic-levels­all matched to FPGA function generator granularity. Output functions should be able to replicate easily next-state terms for independent logic-level reduction.

Stephen L. Wasson is a principal of HighGate Design Inc. (Saratoga, CA), consultants specializing in FPGA implementations.

To voice an opinion on this or any Integrated System Design article, please e-mail your message to: michael@asic.com.

integrated system design  July 1995