Subject: FSM Enhancement Goals and Thoughts
From: Clifford E. Cummings (cliffc@sunburst-design.com)
Date: Tue Dec 11 2001 - 16:45:04 PST
Hi, All
In our SystemVerilog conference call of 12/10/01, Simon raised a number of
points concerning designing FSMs at a higher level. I would like to pursue
an email discussion of those points.
Simon and Co-Design have proposed an FSM syntax to enable architectural
exploration of FSM designs; to design at a higher level. This is a worthy
goal and should be tackled by this committee. Simon also discouraged
continued design at the gate-level, which I believe is not always appropriate.
Goals
I believe the goals of a new FSM syntax should address the following:
· Architectural exploration without making state assignments
· An enumerated style to facilitate state-name display in a waveform
viewer
· Facilitate design of hierarchical FSMs (although we need a great
example to prove this is important - if anyone has a good hierarchical FSM
design description or state diagram(s), I would appreciate that the
description or state diagrams be sent to me by email or FAX (503-641-8486)
and I will commit to coding the design in existing Verilog and
SystemVerilog for comparison - we are sorely lacking a good example to show
the need and advantage of this capability)
· A more concise syntax if possible
· Simple transition to an RTL style with state encodings
· Simple transition to other important FSM styles that offer
synthesis and implementation advantages
· Ability to efficiently control output assignments
VHDL Complaints About Verilog FSM Coding
Whenever you teach VHDL coders to do Verilog FSM design, they have two big
complaints:
(1) State assignments must be made (no enumerated types) - this is the
same issue that Simon raised yesterday.
(2) To display state names in a Verilog waveform display, the state
names must be assigned to variables declared like "reg [6*8:1] statename;
// ASCII display register" and then displayed as a string format in the
waveform viewer. This requires a significant amount of additional code to
make all of the ASCII statename assignments.
Both of the above issues are solved using VHDL enumerated types.
VHDL Problems With Onehot FSM Coding
VHDL coders still have problems with an efficient onehot FSM coding style.
An efficient onehot coding style is accomplished by turning the enumerated
state type into an index into the state register instead of the onehot
encoding itself.
In Verilog, the efficient onehot coding style uses:
// The parameters represent an index into the onehot state vector
parameter S0 = 0, // not 0...0001
// note S0 does not equal onehot state encoding
S1 = 1, // not 0...0010
// note S1 does not equal onehot state encoding
S2 = 2, // not 0...0100
// note S2 does not equal onehot state encoding
S3 = 3, // not 0...1000
// note S3 does not equal onehot state encoding
...
Sn = n-1; // not 1...0000
reg [n-1:0] state, next;
...
// Must add parallel_case directive to
// avoid an unnecessary priority encoder
case (1'b1) // 1-bit comparisons, not n-bit comparisons
state[S0]: ... // 1-bit comparison
state[S1]: ... // 1-bit comparison
state[S2]: ... // 1-bit comparison
state[S3]: ... // 1-bit comparison
...
state[Sn]: ... // 1-bit comparison
endcase
In VHDL, the parameters are replaced with enumerated types and the case
(1'b1) comparisons are replaced with parallel "if state(n) ..." statements.
Architectural Exploration Without Making State Assignments
The issue that Simon seemed to raise most often in the discussion yesterday
was having the capability to design a state machine without thinking about
or making state assignments. I agree. In early architectural exploration,
making state-encoding assignments is typically not warranted.
This can be accomplished by using enumerated types. The advantage of using
enumerated types is that state assignments can be added later if state
encodings do become important, or they can be left unassigned for
behavioral simulation or left unassigned if a separate FSM tool is used to
make the state assignments.
An Enumerated Style To Facilitate State-Name Display In A Waveform Viewer
Enumerated types address most of the issues related to waveform displays.
As long as the enumerated types represent state encodings, displaying state
names in a waveform viewer is easily accomplished.
A capability missing from the enumerated types (as described above for VHDL
onehot FSMs) is an enumerated type that addresses designs of a onehot
nature. Enumerated types work fine for encoded states, but they are unable
to display state information when the enumeration is an index into the
state vector as opposed to an encoded state.
There is opportunity here to really enhance SystemVerilog. Perhaps make two
different enumerated types: the keyword enum for the typical enumerated
type and a new keyword enum_onehot for onehot enumerated types. More on
this idea in the proposals section at the bottom of this message.
Facilitate Design Of Hierarchical FSMs
Again, a useful example is needed here. Simon referred to a hierarchical
PCI bus FSM that engineers worked on when he was at Virtual Chips. The PCI
spec is not proprietary to any one company, so if Simon can remember the
design problem, perhaps he could send it out. I would be willing to code
the example for comparison purposes.
Simon kept talking about not needing to require output assignments in an
FSM design. I think that statement might be applicable to a hierarchical
FSM design, where one FSM simply detects the state of the other FSM instead
of handshaking an output signal from one FSM to an input signal of another
FSM. In this I could see a potentially more concise coding style using the
proposed FSM enhancements.
Hierarchically referencing a state instead of passing an output signal from
that state to another FSM works well if each output is unique to just one
state. Now all we have to do is recognize that the state was entered
instead of examining an output from the other state machine.
If the output is set in multiple states, then referencing the multiple
states from the other state machine can actually become more verbose than
if a simple output signal is tested that is set in all of the other states.
This is FSM dependent, so now we are going to coerce multiple coding styles
based on an engineering judgement of how many states set specific outputs.
A useful example is needed!
A More Concise Syntax If Possible
The goal of a more concise syntax is a worthy goal.
The problem with the proposed syntax enhancements is that only synchronous
resets benefit from the "state (...) iff posedge clk;" syntax. Change the
reset from synchronous to asynchronous and you now have to add in the old
Verilog code.
In Verilog, synchronous and asynchronous FSMs use just three almost
identical lines of Verilog to code the state register:
always @(posedge clk <or negedge rst_n>)
if (!rst_n) state <= IDLE;
else state <= next;
That's it! add the negedge rst_n to the sensitivity list and synchronous
reset becomes asynchronous. That's it! This is not terribly verbose! If
there is an elegant way to do this even more concisely with a new syntax, I
am not opposed to reducing three more lines of code, but these three lines
of code do not impact my RTL coding schedule.
Enumerated types will remove the requirement to make separate state and
next declarations. Enumerated types will also make statename display easier
(most of the time) which again reduces diagnostic coding efforts.
Enumerated types are one step in the direction of a more concise syntax.
Simple Transition To An RTL Style With State Encodings
As a problem, architectural exploration pales to the problem of timing
closure in a high speed design. I have yet to find a synthesis tool that
can take a general purpose coding style, push the onehot button, and beat
the size and speed of a Verilog design coded with the case 1'b1 syntax.
I know of no synthesis tool that automatically infers the high-speed
registered output-encoded style.
Synplicity has a "safe FSM" setting that is not "safe" (although it is
generally fast because it is a modified onehot style with one state
assigned the state encoding of all zeros - I referred to this style in one
of my conference papers as a "onehot with 0-Idle" style).
Any satellite circling the Earth with a Synplicity "safe" coding style
might have to be periodically reset to re-allign the rest of the hardware
to the state machine. Any medical-implant company that uses the Synplicity
"safe" coding style could kill their patients! Synplicity has addressed the
minor problem of a onehot state machine losing a bit and therefore going to
a known state of all 0's. Unless the all 0's state is an error state that
resets the rest of the logic to the same known state, the FSM thinks it is
in one state while the rest of the hardware might think it is in another
state with dire consequences.
If a onehot FSM turns on an extra bit, then extra hardware activity will
occur if or until the FSM is restored to a onehot state. This type of state
machine would require significant extra logic to test for multiple bits
being set, effectively killing the objective of using a onehot FSM to
reduce combinational logic circuitry and increase overall speed (especially
in an FPGA design).
A truly "safe" FSM coding style would require encodings that would employ a
SEC/DED (Single Error Correct / Double Error Detect) encoding to fix the
introduction of single bit changes and detect double bit changes and then
go to an error recovery-reset state.
Onehot (or onehot with 0-Idle) FSMs should not be used for any design where
there is danger of state bits changing value. As language designers, we can
sit back and blame the FSM synthesis tools but that is of little comfort to
the guy whose pacemaker malfunctioned due to a poor synthesized FSM
implementation.
Simple Transition To Other Important FSM Styles
This is lacking in the enhanced FSM syntax proposal.
But quite frankly, this is also a problem in Verilog. When transitioning
from a binary-encoded FSM to the efficient onehot style, there are about 10
coding changes that have to be made to transition the standard
binary-encoded style to a onehot style. It would be nice if it were as easy
as changing "enum" to "enum_onehot" and "case(state)" to case_onehot(state)."
Ability To Efficiently Control Output Assignments
I believe the value of this capability was entirely overlooked in the
enhanced FSM syntax proposal.
Sometimes FSM outputs are also ASIC outputs. Sometimes FSM outputs are
control-logic outputs. And sometimes outputs must be registered to avoid
output glitching. My Boston SNUG-2000 paper addressed reasons for and
techniques to register FSM outputs.
PROPOSALS
enum - works great as is.
If we do want a separate state type, I suggest:
enum_state - to at least get away from the commonly used identifier name of
"state."
NEW! Add an enumeration type that would benefit onehot logic. This would be
a true enhancement over both Verilog and VHDL. Add either:
enum_onehot
enum_state_onehot
Waveform viewers would now treat the onehot enumeration as an index as
opposed to an actual encoding.
Probably would also require:
case_onehot(state)
IDLE: ... ->> S0; // treated the same as:
// case(1'b1)
// state[IDLE]: ... next[S0] = 1'b1;
Using something like the aobove syntax would make the transition from
binary to one hot as simple as changing "enum" to "enum_onehot" and "case"
to "case_onehot." And the waveform viewer will now look at which index bits
are hot to determine which statename to display.
Note: state machines are not the only hardware that use onehot codes. Wide
fast multiplexers are often coded using onehot selects wired to tristate
drivers that drive a common bus. Control logic is often coded as either
encoded or onehot, for the latter each control bit does not have to first
be decoded.
Just some additional thoughts on goals and techniques.
Regards - Cliff
//*****************************************************************//
// Cliff Cummings Phone: 503-641-8446 //
// Sunburst Design, Inc. FAX: 503-641-8486 //
// 14314 SW Allen Blvd. E-mail: cliffc@sunburst-design.com //
// PMB 501 Web: www.sunburst-design.com //
// Beaverton, OR 97005 //
// //
// Expert Verilog, Synthesis and Verification Training //
//*****************************************************************//
This archive was generated by hypermail 2b28 : Tue Dec 11 2001 - 16:45:20 PST