FSM Safe Design

Proposal Details

• Who Updates: Brent Hayhoe
• Date Proposed: 2014-02-24
• Date Last Updated:
• Priority:
• Complexity:
• Focus:

Overlapping Concerns

-- JimLewis - 2014-03-27

The IEEE 1076.6-2004 attribute FSM_COMPLETE addresses some of what you are discussing below. It was proposed as FSM_SAFE, however, the name was changed during the process of the working group. I have uploaded 1076.6-2004 to the working group private documents page so you can further research this.

I note most of the attributes proposed in 1076.6-2004 went largely unimplemented in vendor tools. This tells us a couple of things. To make any venture into the synthesis attributes, we need to get vendor buy in, so make sure to invite them to participate. Maybe it means that the packages containing the attribute declarations need to be defined by 1076 rather than 1076.6. It also means we have the opportunity to change the names of the attributes if there is a compelling reason.

Current Situation

State machine design in VHDL can be performed in quite an elegant manner. That is using the provision of enumerated types.

However, there is a problem which some people are still unaware of.

I remember questioning various vendors about safe FSM design in the late Nineties and only one had any sort of provision for it at that time. The situation has since improved (slightly).

The classic VHDL problem is this:

   type   my_fsm_type   is (a, b, c);
   signal my_fsm_signal  : my_fsm_type;
...
   case my_fsm_signal is
      when a => if (start = true) then my_fsm_signal <= b; end if;
      when b => my_fsm_signal <= c;
      when c => my_fsm_signal <= a;
   end case;

Given this trivial example, the problem is one of synthesis mapping. Three states have to be mapped into a minimum of four states and how do you perform the equivalent of a 'when others' catch-all clause to ensure a safe state machine design.

If you put this clause in the source code, the compiler, quite rightly, will tell you that it is not required and it will be ignored. It may also generate warning massages.

Most clients that I have worked for require that all state machines must have 2**N states in order to ensure safe design and their coding standards ban the use of 'one-hot' FSM implementation. This is a solution, but goes against abstraction design techniques.

Implementation details

Although there are methods of adding synthesis attributes to handle this, it would be nice to incorporate it within the language semantics as it is more of a design requirement rather than a straightforward implementation synthesis constraint, e.g;

   when others my_fsm_signal  <= safe(a);

This new 'safe' function could reside in the ENV package and part of its use would implicitly define an equivalent synthesis pragma (or 'synthesis check' in the case of simulators) in order to control the safe design mapping. It would then be an allowable statement in a 'when others' clause even if logically not required. No warnings would then be generated by the compiler.

Code Examples

The 'safe' function could be something like:

   pure function safe
      generic(type t)
      parameter(a : t) is
   begin
      return a;
   end function safe;

which would then require the user to instantiate it as:

   function safe is
      new safe
         generic map(t => my_fsm_type);

It would be nice if the function could implement a pragma for synthesis purposes.

Trawling through the latest 1076.6 specification, there is indeed a pragma defined for this purpose - FSM_COMPLETE - and it relies on the 'when others' clause.

Use Cases

Arguments FOR

Arguments AGAINST

General Comments

Email Reflector Comments

From: JakkoVerhallen (Thu Feb 20 2014 - 00:47:08 PST)

What I usually do to avoid the warnings is:

    case my_fsm_signal is
       when a => if (start = true) then my_fsm_signal <= b; end if;
       when b => my_fsm_signal <= c;
       when others => my_fsm_signal <= a;
    end case;

In that way, you should be able enforce the tool to make an arc from the non-described D state to the A state.

If for some reason (timing issue e.g.) the state D is reached, but it does not have an ARC, you get stuck in a deadlock.

I do like your idea to handle it in the language, and not in the way you write your case statements, without pragmas/directives/attributes, but in plain VHDL.

Regards, Jakko

Brent Hayhoe: - Jakko, whatever you do with the 'when others' clause, the compiler only knows that there are 3 and only 3 states defined for the enumerated type. It knows nothing about mapping these enumerated values into real world bits. That is a synthesis task. - /Brent Hayhoe:/

From: BrianDrummond (Thu Feb 20 2014 - 04:15:51 PST)

I like the intent, but I wouldn't want to add reserved words or syntax to the language to handle it.

Adding an attribute "safe" or "full_case_coverage" to the enumerated type and using a plain "when others" case seems more appropriate.

Define a standard attribute for the purpose, establish its intent, (namely, to suppress "redundant clause" optimisations and implement full coverage. A warning describing the excess resources over "optimal" solution might be appropriate) Then work with (at least some) tool vendors to support it, and let peer pressure bring the rest on board.

If there already is a named standard attribute for the purpose, ... then all I can say is, there isn't enough noise about it yet!

- Brian

Brent Hayhoe: - Brian, I think we need something in the language as it is a design requirement rather than just an implementation constraint. This is why I'm suggesting the addition of a new 'safe' function to insert in the 'when others' clause.

There does already seem to be a pragma defined for these constraints - FSM_COMPLETE - and is one of the reasons why I started the Email thread here IEEE P1076.6 Status - /Brent Hayhoe:/

Brian Drummond : - Having seen the "code example" above where the implementation is simply a generic function, my objection no longer applies.

From: DanielKho (Thu Feb 20 2014 - 09:26:10 PST)

All, Adapting from Brent's, let's say we have the following typical FSM description:

< type my_fsm is (a, b, c);
> ...
>     case my_fsm_signal is
>        when a => if (start = true) then my_fsm_signal <= b; end if;
>        when b => my_fsm_signal <= c;
>        when c => my_fsm_signal <= a;
>        when others => my_fsm_signal <= a;
>     end case;

Perhaps it's a good idea to coerce synthesis tools to implicitly implement safe statemachines whenever the designer explicitly writes the "when others" clause.

I bumped into these issues as well, and my solutions at that time were to explicitly write extra logic that implements the catch-all condition (either using if-else statements, or using synthesis attributes), but I admit these solutions are ugly as they tend to clutter the code and make the design less readable.

I would very much prefer if synthesis tools, by default, are intelligent enough to implement safe statemachines on its own.

Best regards, Daniel

From: DanielKho (Thu Feb 20 2014 - 09:45:51 PST)

These days, I would usually write the same example like this:

type my_fsm is (a, b, c);
  ...
     case my_fsm_signal is
        when b => my_fsm_signal <= c;
        when c => my_fsm_signal <= a;
        when others => if (start = true) then my_fsm_signal <= b; end if;
     end case;

which effectively makes State A a catch-all state. Still, I feel that by doing so, it makes the FSM description "look" incomplete (missing the "a" state), and adds confusion to others.

I used to do something like this before, but I believe this just adds unnecessary complexity:

if my_fsm_signal/=a and my_fsm_signal/=b and my_fsm_signal/=c then
my_fsm_signal <= a;
else
     case my_fsm_signal is
        when a => if (start = true) then my_fsm_signal <= b; end if;
        when b => my_fsm_signal <= c;
        when c => my_fsm_signal <= a;
     end case;
end if;

regards, daniel

Brent Hayhoe: - Daniel, as I pointed out to Jakko above, the enumerated type definition means that no matter what you do with a 'when others' clause, there are no other states for the compiler to assign. Some synthesis engines can indeed automatically assign a safe state as that defined for reset, but in general terms this may not be what the user requires. Using the 'safe' function explicitly states that this is what the user wants implemented during synthesis. - /Brent Hayhoe:/

DanielKho - 2015-01-04 @Brent, I like the intent, but my question still remains. Can we make this requirement implicit, i.e. to coerce tools to automatically infer safe FSMs whenever "when others" is used, rather than explicitly specifying additional synthesis attributes? In my last example, similar to Jakko's, only two out of three states were defined, while a "default" state (the "when others") is used as a catch-all state. So in our cases, the compiler will indeed implement the default state, that is to say, the compiler will implement all states, because the catch-all state includes the third state (State A) which was not explicitly written. In these cases, if we were to apply the "safe" attribute, how would the compiler behave?

From: JoanneDegroat (Thu Feb 20 2014 - 10:12:53 PST)

I will add some comment at this point as I am teaching this topic this semester.

My solution when the state machine is incompletely specified resulting in states that are essentially don't cares it to Use the when others. I some cases you can fix it to a next state but to get optimized logic I have used

when others => null;

Xilinx and Altera want cases where all the states are enumerated so you need the when others.

Joanne

Brent Hayhoe: - Joanne, ditto as per my comments to Daniel and Jakko regarding the 'when others'. I don't think that I've actually come across Xilinx or Altera tools actually requiring all states to be defined, but I certainly have come across synthesis warnings about unreachable(?) generated states. - /Brent Hayhoe:/

DanielKho - 2015-01-04 One way to make a safe FSM is to have a catch-all state which covers one of the predefined states, just like what Jakko and I have done. In my example, this catch-all state ("when others") covers State A as well as any other undefined states. In my other real-world designs, it would usually include the IDLE state. Since the "when others" covers the IDLE state, I would deliberately leave out explicitly defining this state, which makes the FSM safe.

From: MartinThompson (Fri Feb 21 2014 - 01:48:46 PST)

My understanding is that the problem goes much further than just non-power-of-two state counts.

Even if you have (for example) 4 states in your state machine, the tools will (often) pick an encoding with redundant states. Especially in FPGA-land, where one-hot encoding is popular for efficiency reasons, a 4-state FSM would have 4 flipflops, and therefore 12 "redundant" (and unpredictably behaved) states!

I agree that a well-defined standard attribute would be useful to handle this behaviour, as the two synthesisers I am familiar with (XST and Synplify) currently operate in different ways.

XST has

  attribute safe_implementation of
      entity_name|component_name|signal_name}:entity|component|signal is "{yes|no}}";

along with

  attribute safe_recovery_state: string; 

for when you need control over which state to "recover to". If unused, XST will include logic to return to the reset (or startup, if no reset logic is present) state if any undefined states are entered.

Synplify offers:

   attribute syn_safe_case of architectureName : architecture is TRUE;

along with separate error monitoring functionality

and

   attribute syn_fsm_correction of architectureName : architecture is "hamming3";

which provides single bit error correction.

The only overlap there is the function to provide a "safe" encoding, but the mitigation actions are also different between the tools.

My current feeling is that an XST-like approach (where safe-encodings are produced along with a defined return to a particular state) would be a useful standardised functionality, vendors are still free to provide further attributes for more complex functions.

Cheers, Martin

From: AndyJones (Fri Feb 21 2014 - 08:05:59 PST)

Some synthesis tools perform reachability analysis on state machines (including counters), and if they determine that other states are unreachable per the described logic behavior, the logic attributed to those unreachable states is optimized, whether you have a "when others" choice or not. This does not depend on whether an enumerated or explicit vector type is used for the state. Some synthesis tools will warn you if the "when others" choice is not synthesized.

There is usually an attribute (tool specific) to disable the optimization, allowing synthesis of such a "when others" choice. However, such an attribute has no effect on the RTL simulation, and the when others choice is not testable unless fault insertion/simulation is used (and probably only in gate-level simulation), or you include at least one defined but not used state in the enumerated type.

For Synplify, the appropriate method is syn_preserve = true, applied to the state register signal. This prevents their FSM compiler from taking over, and also prevents the reachability optimizations.

Then you can use syn_enum_encoding on the enumerated state type to define whatever encoding you want. Note that there is no way to access that encoding in your RTL code, but the "when others" choice will detect any value not defined in the encoding.

Andy D Jones Electrical Engineering Lockheed Martin Missiles and Fire Control Dallas TX

From: JimLewis - 2014-03-27

It is interesting to note that IEEE 1076.6 defines an FSM_COMPLETE attribute that is intended to be FSM_SAFE (was named that during the initial proposal).

Supporters

-- Brent Hayhoe - 2014-02-24

-- BrianDrummond - 2014-02-27

-- MartinThompson - 2014-03-03

Add your signature here to indicate your support for the proposal