Safe FSM

[alb]

Hi everyone,

I have an FSM of some (sigh) 150 states and Synplify Pro (from
the Libero suite) is not able to recognize it as an FSM since it
accepts 128 states max. The code simulates and works well on the
target, but we are all aware that the implementation is not
protected against non described states.

Since we cannot rely on the tool capability to implement a safe FSM,
I thought the easier way to implement a safe FSM would be to
declare 2^n states explicitly and force the tool to preserve all
states that are not reachable by design but could be triggered by
an external event (say some heavy ion).

Another possibility would be to encode a one hot FSM and monitor
the state vector with another process responsible for checking
any violation of the one hot coding.

Are those reasonable paths? I'm excluding the possibility to split
the FSM in hierarchical FSM since it will be a lot of work and
raise more questions.

Oh by the way, why the heck synthesis tools decide to neglect the
"when others" closer unless I specify the safe FSM option?
Couldn't they simplify follow the hdl description.


Any suggestion/comment is appreciated.

Al


----Android NewsGroup Reader----
http://usenet.sinaapp.com/

 

[Andy]

You can use a syn_preserve attribute on the state register signal to disable fsm compiler and other optimizations (such as due to reachability analysis). Then a "when others" choice can assign a legal state value if none of the other choices (presumably all the legal states) match. Without syn_preserve, the when others choice is usually ignored unless you actually assign a value (including upon reset) that is not covered by an explicit when choice.

Note that this does not detect an illegal transition to a legal state (such as due to an SEU or an improperly synchronized input).

Detecting all possible illegal states for a one-hot FSM is expensive. However, a simple parity check will detect single bit errors in one-hot FSMs (one-hot by definition is odd parity).

I would also seriously consider breaking up a state machine with that many states...

Andy

 

[Jim Lewis]

Hi Al,
I think the most reasonable answer is the one proposed by @rickman, partition the statemachine into multiple statemachines, each with < 128 states.

Since we cannot rely on the tool capability to implement a safe FSM,
I thought the easier way to implement a safe FSM would be to
declare 2^n states explicitly and force the tool to preserve all
states that are not reachable by design but could be triggered by
an external event (say some heavy ion).
If you want a safe FSM, then you need hamming distance between the states. Hence you will need at least 2^(n+1). Code your states as constants that have a hamming distance and use syn_preserve to keep redundancy from being removed. Use the when others condition to detect illegal transitions or if you use a hamming distance of at least 2, you can add the error recovery into the code.

This is going to get real tedious and be interesting to debug if you run into issues. You will need to simulate your error recovery to prove you did it right. You will probably be wishing you had enumerated states just for debug - you could create them and create a mapping between them and the constant values just to assist with debug.

All of this is alot of work. I would expect the better answer to be to spring for the pay version of the tool. Yes expensive, but it may give you some additional options the free tool does not have - like a hamming distance between states rather than one-hot. I agree with Andy that it is going to be expensive to do recovery with a one-hot safe statemachine.

Another possibility would be to encode a one hot FSM and monitor
the state vector with another process responsible for checking
any violation of the one hot coding.
My recommendation is don't. I have yet to see someone's one-hot VHDL statemachine code actually be a true one-hot statemachine. The problem is that if you use a case statement to decode your states, most synthesis tools will decode all bits rather than the one bit that determines the state, and hence, the state decoding is huge. The start of getting a synthesis tool to get it right is to assign all outputs to a default value and use an if-end if structure that only decodes a single bit in the state vector and only assigns outputs to the opposite value of the default value. The only vector value allowed in the structure is next state (or current state if you use a single process statemachine). Next state needs to be defaulted to all zeros and a state update may only assign a single bit to a '1'.

The code gets complicated, ugly, and unreadable by most, hence, my recommendation, if you need one-hot, you need the tool to understand your statemachine as a statemachine and for it to implement it as a one-hot statemachine.

Oh by the way, why the heck synthesis tools decide to neglect the
"when others" closer unless I specify the safe FSM option?
Couldn't they simplify follow the hdl description.
Commercial needs the speed, so those who need the safe option have to work harder to make it happen. A cruel, but fair balance to the problem.

Jim

 

[rickman]

On 3/29/2015 4:12 PM, alb wrote:

Hi everyone,

I have an FSM of some (sigh) 150 states and Synplify Pro (from
the Libero suite) is not able to recognize it as an FSM since it
accepts 128 states max. The code simulates and works well on the
target, but we are all aware that the implementation is not
protected against non described states.

Since we cannot rely on the tool capability to implement a safe FSM,
I thought the easier way to implement a safe FSM would be to
declare 2^n states explicitly and force the tool to preserve all
states that are not reachable by design but could be triggered by
an external event (say some heavy ion).

Another possibility would be to encode a one hot FSM and monitor
the state vector with another process responsible for checking
any violation of the one hot coding.

Are those reasonable paths? I'm excluding the possibility to split
the FSM in hierarchical FSM since it will be a lot of work and
raise more questions.

Oh by the way, why the heck synthesis tools decide to neglect the
"when others" closer unless I specify the safe FSM option?
Couldn't they simplify follow the hdl description.


Any suggestion/comment is appreciated.

Perhaps you can explain what you mean by a "safe" FSM? I have never
heard this term.

You might consider redesigning your machine as several smaller machines.
Then the tool will recognize each of them since they will have less
than 128 states.

--

Rick

 

[alb]

hi Rick,

rickman <gnuarm@gmail.com> wrote:
[]

Perhaps you can explain what you mean by a "safe" FSM? I have never
heard this term.

a safe FSM is an FSM that does not get stuck in an undefined state.

You might consider redesigning your machine as several smaller machines.
Then the tool will recognize each of them since they will have less
than 128 states.

Even if I understand this is the best approach, we are talking about a
4.5 KLOC code that took three months to develop and many more to verify
and validate on the hardware. I'm not sure I'd want to embark on such a
nightmare.

The problem is not in coding, is in the architecture of the FSM itself.
At the architecture review somebody should have coughed a little harder
when looking at the number of states and raise a hand before designers
started hammering the code.

Now I'm trying to get out of the dirt with the minimum amount of impact.

Al

 

[alb]

Hi Andy,

Andy <jonesandy@comcast.net> wrote:

You can use a syn_preserve attribute on the state register signal to
disable fsm compiler and other optimizations (such as due to
reachability analysis). Then a "when others" choice can assign a legal
state value if none of the other choices (presumably all the legal
states) match. Without syn_preserve, the when others choice is usually
ignored unless you actually assign a value (including upon reset) that
is not covered by an explicit when choice.

I'm not sure it is even needed the syn_preserve, since the tool does not
recognize the FSM at all (they admitedly reported the tool has a 128 bit
limit for FSM state vector).

Considering the 'when others' is not wiped out by their FSM compiler,
maybe we are better off than thought.

Note that this does not detect an illegal transition to a legal state
(such as due to an SEU or an improperly synchronized input).

That is correct, that's why I'd feel more confortable if states were
decoded with a hamming distance greater than 1. We are talking about an
implementation that is already 'TMRed', so chances of a double failure
causing a transition to a legal state might be very small.

Nevertheless SET on combinatorial logic that is not TMRed might give you
troubles. The transient may be just enough to have the triplified
register to get the wrong value on a perfect triple copy!

Detecting all possible illegal states for a one-hot FSM is expensive.
However, a simple parity check will detect single bit errors in
one-hot FSMs (one-hot by definition is odd parity).

This is what I thought. One-hot and odd parity check (no need to verify
overflow for cases like '...010101...' since they are too rare to be a
real concern).

I would also seriously consider breaking up a state machine with that
many states...

As mentioed in a different post in this thread, there's no simple
breaking. We would need to get the architecture and shake it a bit
before being able to split the number of states in several FSMs.

On top of it there's a lot of verification that needs to be re-run as
well, also on the real hardware (since long sequences were not verified
in simulation).

But as you said, maybe splitting, in the end, would be simpler that any
other supposedly 'cheaper' alternative.

 

[alb]

Hi Jim,

Jim Lewis <jim@synthworks.com> wrote:
[]

I think the most reasonable answer is the one proposed by @rickman,
partition the statemachine into multiple statemachines, each with
128 states.

I'm kinda repeating to myself that as well, but I keep having everyone
against since it is too 'expensive'.

Since we cannot rely on the tool capability to implement a safe FSM,
I thought the easier way to implement a safe FSM would be to
declare 2^n states explicitly and force the tool to preserve all
states that are not reachable by design but could be triggered by an
external event (say some heavy ion).

If you want a safe FSM, then you need hamming distance between the
states. Hence you will need at least 2^(n+1). Code your states as
constants that have a hamming distance and use syn_preserve to keep
redundancy from being removed. Use the when others condition to
detect illegal transitions or if you use a hamming distance of at
least 2, you can add the error recovery into the code.

I haven't understood the 'add the error recovery into the code'. I would
have done something like this:

<code>
process(clk, rst)
begin
if rst = '1' then
-- reset all output signals and state vector here
elseif rising_edge(clk) then
-- define all legal states here
case state is
when "ABC" =>
-- set output here
-- set next state here
when "DEF" =>
-- set output here
-- set next state here
when others =>
-- set output here
-- set safe state here
end case;
end if;
end process;
</code>

the only place where I can recover from an illegal state would be in the
'when others' branch.

This is going to get real tedious and be interesting to debug if you
run into issues. You will need to simulate your error recovery to
prove you did it right. You will probably be wishing you had
enumerated states just for debug - you could create them and create a
mapping between them and the constant values just to assist with
debug.

We normally force the state vector to show what it'll do in the event of
an illegal state, this is standard practice, but not in post-synth sims.
We do analyze the synthesis report to verify that implementation is
correct. Seldom we do analyze the netlist as well. But very rarely we
perform post-synth sims.

All of this is alot of work. I would expect the better answer to be
to spring for the pay version of the tool. Yes expensive, but it may
give you some additional options the free tool does not have - like a
hamming distance between states rather than one-hot. I agree with
Andy that it is going to be expensive to do recovery with a one-hot
safe statemachine.

unfortunately the tool is the main issue here. Synplify Pro, no matter
if paid or not, does not recognize more than 128 bit FSMs (if I
understood it correctly). So we cannot really count on it.

Another possibility would be to encode a one hot FSM and monitor
the state vector with another process responsible for checking any
violation of the one hot coding.

My recommendation is don't. I have yet to see someone's one-hot VHDL
statemachine code actually be a true one-hot statemachine. The
problem is that if you use a case statement to decode your states,
most synthesis tools will decode all bits rather than the one bit that
determines the state, and hence, the state decoding is huge. The
start of getting a synthesis tool to get it right is to assign all
outputs to a default value and use an if-end if structure that only
decodes a single bit in the state vector and only assigns outputs to
the opposite value of the default value. The only vector value
allowed in the structure is next state (or current state if you use a
single process statemachine). Next state needs to be defaulted to all
zeros and a state update may only assign a single bit to a '1'.

I see your point. It is possible that we have always used one-hot
encoding ending with an enormous amount of resources because of the
decoding logic.

The code gets complicated, ugly, and unreadable by most, hence, my
recommendation, if you need one-hot, you need the tool to understand
your statemachine as a statemachine and for it to implement it as a
one-hot statemachine.

One-hot is not mandatory, a hamming distance of, say, 2 would be
sufficient.

Oh by the way, why the heck synthesis tools decide to neglect the
"when others" closer unless I specify the safe FSM option? Couldn't
they simplify follow the hdl description.

Commercial needs the speed, so those who need the safe option have to
work harder to make it happen. A cruel, but fair balance to the
problem.

fair enough...we do it 'not because is easy, but because is hard'!

Al

 

[rickman]

On 3/30/2015 3:01 AM, alb wrote:

hi Rick,

rickman <gnuarm@gmail.com> wrote:
[]
Perhaps you can explain what you mean by a "safe" FSM? I have never
heard this term.

a safe FSM is an FSM that does not get stuck in an undefined state.

You might consider redesigning your machine as several smaller machines.
Then the tool will recognize each of them since they will have less
than 128 states.

Even if I understand this is the best approach, we are talking about a
4.5 KLOC code that took three months to develop and many more to verify
and validate on the hardware. I'm not sure I'd want to embark on such a
nightmare.

The problem is not in coding, is in the architecture of the FSM itself.
At the architecture review somebody should have coughed a little harder
when looking at the number of states and raise a hand before designers
started hammering the code.

That's what splitting it into multiple FSMs would be, an architecture
change.


> Now I'm trying to get out of the dirt with the minimum amount of impact.

If you just need to have the FSM handle the remaining 2^N-M states why
not specify them explicitly? I assume you identify a start state and
all the undefined states transition unconditionally to that start state.
That can be coded in the "otherwise" clause of a case statement very
easily. Or if you aren't using a case statement you can just surround
the existing state code with an IF (all the undefined states) go to
reset ELSE normal operation ENDIF

--

Rick

 

[KJ]

On Sunday, March 29, 2015 at 6:08:23 PM UTC-4, Jim Lewis wrote:

My recommendation is don't. I have yet to see someone's one-hot VHDL
statemachine code actually be a true one-hot statemachine. The problem is
that if you use a case statement to decode your states, most synthesis tools
will decode all bits rather than the one bit that determines the state, and
hence, the state decoding is huge. The start of getting a synthesis tool to
get it right is to ...

Do you have an example of this? I just looked at a recent design and what I see is different number of fanout for the various state bit signals in the fitter report which indicates to me that the logic is using only those state bits that it needs. The report doesn't blast out all of the logic equations to validate the final usage but it would seem that if what you say was true, then the fanout for each state bit would at least have to be the same.

Kevin Jennings

 

[Thomas Stanka]

Am Sonntag, 29. März 2015 22:12:32 UTC+2 schrieb alb:

Since we cannot rely on the tool capability to implement a safe FSM,
I thought the easier way to implement a safe FSM would be to
declare 2^n states explicitly and force the tool to preserve all
states that are not reachable by design but could be triggered by
an external event (say some heavy ion).

The easiest way to ensure Synplify keeps all defined states is using 2^n states and cycle at least once (after reset) through all "unused" states.

In all other cases you might end up with a result different from your intention.

bye Thomas

 

[KJ]

On Monday, March 30, 2015 at 9:05:12 AM UTC-4, KJ wrote:

On Sunday, March 29, 2015 at 6:08:23 PM UTC-4, Jim Lewis wrote:
My recommendation is don't. I have yet to see someone's one-hot VHDL
statemachine code actually be a true one-hot statemachine. The problem is
that if you use a case statement to decode your states, most synthesis tools
will decode all bits rather than the one bit that determines the state, and
hence, the state decoding is huge. The start of getting a synthesis tool to
get it right is to ...

Do you have an example of this? I just looked at a recent design and what I see is different number of fanout for the various state bit signals in the fitter report which indicates to me that the logic is using only those state bits that it needs. The report doesn't blast out all of the logic equations to validate the final usage but it would seem that if what you say was true, then the fanout for each state bit would at least have to be the same.

Kevin Jennings

Or did you perhaps mean to say "yet to see someone's one-hot VHDL SAFE statemachine code actually be a true one-hot statemachine". If you did mean to only refer to 'safe' state machines with your comment, then decode of all of the bits would likely be part of the implementation of 'safe'.

Kevin Jennings

 

[rickman]

On 3/30/2015 3:51 AM, alb wrote:

Hi Jim,

Jim Lewis <jim@synthworks.com> wrote:
[]
I think the most reasonable answer is the one proposed by @rickman,
partition the statemachine into multiple statemachines, each with
128 states.

I'm kinda repeating to myself that as well, but I keep having everyone
against since it is too 'expensive'.


Since we cannot rely on the tool capability to implement a safe FSM,
I thought the easier way to implement a safe FSM would be to
declare 2^n states explicitly and force the tool to preserve all
states that are not reachable by design but could be triggered by an
external event (say some heavy ion).

If you want a safe FSM, then you need hamming distance between the
states. Hence you will need at least 2^(n+1). Code your states as
constants that have a hamming distance and use syn_preserve to keep
redundancy from being removed. Use the when others condition to
detect illegal transitions or if you use a hamming distance of at
least 2, you can add the error recovery into the code.

I haven't understood the 'add the error recovery into the code'. I would
have done something like this:

code
process(clk, rst)
begin
if rst = '1' then
-- reset all output signals and state vector here
elseif rising_edge(clk) then
-- define all legal states here
case state is
when "ABC" =
-- set output here
-- set next state here
when "DEF" =
-- set output here
-- set next state here
when others =
-- set output here
-- set safe state here
end case;
end if;
end process;
/code

the only place where I can recover from an illegal state would be in the
'when others' branch.

Not sure what you mean by this. Why do you care if it is the "only"
place in the code? This one phrase covers *all* possible states not
previously described as valid states. If there are some error states
you want to recover from differently then they can be broken out as
their own clauses in the case.

This is going to get real tedious and be interesting to debug if you
run into issues. You will need to simulate your error recovery to
prove you did it right. You will probably be wishing you had
enumerated states just for debug - you could create them and create a
mapping between them and the constant values just to assist with
debug.

We normally force the state vector to show what it'll do in the event of
an illegal state, this is standard practice, but not in post-synth sims.
We do analyze the synthesis report to verify that implementation is
correct. Seldom we do analyze the netlist as well. But very rarely we
perform post-synth sims.

All of this is alot of work. I would expect the better answer to be
to spring for the pay version of the tool. Yes expensive, but it may
give you some additional options the free tool does not have - like a
hamming distance between states rather than one-hot. I agree with
Andy that it is going to be expensive to do recovery with a one-hot
safe statemachine.

unfortunately the tool is the main issue here. Synplify Pro, no matter
if paid or not, does not recognize more than 128 bit FSMs (if I
understood it correctly). So we cannot really count on it.


Another possibility would be to encode a one hot FSM and monitor
the state vector with another process responsible for checking any
violation of the one hot coding.

My recommendation is don't. I have yet to see someone's one-hot VHDL
statemachine code actually be a true one-hot statemachine. The
problem is that if you use a case statement to decode your states,
most synthesis tools will decode all bits rather than the one bit that
determines the state, and hence, the state decoding is huge. The
start of getting a synthesis tool to get it right is to assign all
outputs to a default value and use an if-end if structure that only
decodes a single bit in the state vector and only assigns outputs to
the opposite value of the default value. The only vector value
allowed in the structure is next state (or current state if you use a
single process statemachine). Next state needs to be defaulted to all
zeros and a state update may only assign a single bit to a '1'.

I see your point. It is possible that we have always used one-hot
encoding ending with an enormous amount of resources because of the
decoding logic.

One hot should provide very simple decode other than the error state.
The error state could be detected simply by adding all the bits in a
simplified adder which knows three states, 0, 1 and "more than one".
Only the 1 output is not an error. I doubt the tool is smart enough to
synthesize this though. It is something you can add separate from the
case statement.

The code gets complicated, ugly, and unreadable by most, hence, my
recommendation, if you need one-hot, you need the tool to understand
your statemachine as a statemachine and for it to implement it as a
one-hot statemachine.

One-hot is not mandatory, a hamming distance of, say, 2 would be
sufficient.

I see the conversation has added this "Hamming" distance to the
requirements. If you need a Hamming distance of 2 between valid states
one-hot encoding gives you that automatically. If you need more than 2
one-hot is not possible.

I don't know if the tools automatically give you a Hamming distance of 2
even if they recognize your design as a FSM, but it is easy enough to do
by specifying the state values.

--

Rick

 

[rickman]

On 3/30/2015 9:47 AM, Thomas Stanka wrote:

Am Sonntag, 29. März 2015 22:12:32 UTC+2 schrieb alb:
Since we cannot rely on the tool capability to implement a safe FSM,
I thought the easier way to implement a safe FSM would be to
declare 2^n states explicitly and force the tool to preserve all
states that are not reachable by design but could be triggered by
an external event (say some heavy ion).

The easiest way to ensure Synplify keeps all defined states is using 2^n states and cycle at least once (after reset) through all "unused" states.

In all other cases you might end up with a result different from your intention.

I'm not clear on what it means to "preserve" states...? The states are
there, legal or illegal. You can't get rid of them. Are you saying the
tool can remap the values of the state variable to mean something other
than what you intend?

If you want the efficiency of one-hot encoding you don't have to use a
case statement. Instead of designing it as one state machine of N
states and a state variable of N bits, consider each bit to be an
independent state machine with entry and exit conditions. These
conditions can be put in functions so that they are reused between the
exit condition of one state and the entry condition of another.

They can all still be described in the same process (quite hairy in the
case of the OP's huge FSM). Here is an example...

FSM : process (Clk, Rst)
begin
if ('1' = Rst) then
StateA <= '1';
StateB <= '0';
StateC <= '0';
StateD <= '0';
.
.
.
StateZ <= '0';
elsif (rising_edge(Clk)) then
if ('0' = StateA) then
StateA <= -- insert your state entry conditions here;
else
StateA <= not -- insert your state exit conditions here
end if; -- (if StateA)

if ('0' = StateB) then
StateB <= -- insert your state entry conditions here;
else
StateB <= not -- insert your state exit conditions here
end if; -- (if StateB)
.
.
.
end if; -- (if Rst)
end process FSM;

It is still the same FSM, but coded to minimize the decoding logic
without any issues of what the tool will do.

--

Rick

 

[Thomas Stanka]

Am Dienstag, 31. März 2015 03:51:55 UTC+2 schrieb rickman:

The easiest way to ensure Synplify keeps all defined states is using 2^n states and cycle at least once (after reset) through all "unused" states.

In all other cases you might end up with a result different from your intention.

I'm not clear on what it means to "preserve" states...? The states are
there, legal or illegal. You can't get rid of them. Are you saying the
tool can remap the values of the state variable to mean something other
than what you intend?

Assume you have 10 user states and fill up to 16 by adding unused_state10-15 than write "when others => state <= idle;"
This would logically ensure you recover from all states. On RTL simulation you could even set the fsm by force command to unused state and see the FSM recovers. But Synplify extracts during synthesise step, that you could not reach the unused states and therefore starts optimising them in a way that you might find later on a state from which your FSM cannot recover if it get stuck there.

The same is valid if you use an counter from 0-9 "if counter < 10 then ... else counter <= 0;". This statement can be optimised by Synplify to code that might stuck, if your counter ever reaches value 14 due to SEE.

For One-Hot situation is even worse, if you consider states not reachable by normal operation, but you reach by accident (SEE, metastability,...), like states with zero or two '1's.

regards, Thomas

 

[KJ]

On Tuesday, March 31, 2015 at 11:50:03 AM UTC-4, rickman wrote:

I suspect the method of one-hot coding I have described would prevent
such optimization since each state is an independent FSM, it would be
much harder to analyze and determine the various "impossible" states
based on the logical analysis.

One hot encoding is exactly the case one can generate a large number of 'impossible states'. If you have a four state state machine, and it is implemented as one-hot, then you will have four flip flops. Those four flip flops can theoretically be in any of 16 states; four 'legit' and 12 'impossible'.

Optimized logic that uses the state bit(s) would only look at the individual bit to see if a particular state is active (since that is the primary reason for using a one-hot encoding in the first place) and would ignore the other state bits. Those state bits can only be interpreted as 'independent FSMs' if you ignore the possibility of actually getting into 'impossible states', which given a stray energetic space particle hit could happen therefore it is not impossible.

Bottom line is that one hot encoding definitely does not prevent any vendor optimization of the issue being discussed. In fact, the vendor optimization to use one-hot (if not explicitly told to not use), creates more potentials for this problem (witness a four state machine having 12 impossible states).

Kevin Jennings

 

[KJ]

On Tuesday, March 31, 2015 at 1:28:42 PM UTC-4, rickman wrote:

I can't say I follow your reasoning. If the vendor's tools look across
all logic for sequential logic that depends on other sequential logic
and combines it into a FSM that can be optimized, then nearly every
design would be treated as a single FSM. What makes this approach a
group of separate FSMs which aren't optimized by the tools is that they
are separate signals. How exactly do the tools decide what is a FSM and
what is not?

We could be talking different things since I didn't say anything about looking across all logic... For FSMs, I think we're talking about the following type of coding:

type t_My_States is (Idle, Do_Something, Do_Something_Important, Done);
signal Current_State: t_My_States;
....
case Current_State is
when Idle=> ...
when Do_Something => ...
when Do_Something_Important=> ...
when Done => ...
end case;

The synthesis tools don't have to look to far to see that 'Current_State' is a single signal. The tool can then choose to implement that single signal as one-hot in which case it will use four flip flops which, in theory, have 16 different combinations. Only 4 of the 16 are 'valid' in that they are described by the code that was written. The other 12 are 'impossible', 'not valid' etc. that can only be reached by things such as an SEU, timing problem, voltage problem and other things that 'should not happen'.

Although the implementation of 'Current_State' is in four flops, those four are not independent. The logic that gets synthesized takes advantage of the fact that it is choosing to implement Current_State as one-hot so any dependent logic will only have to look at one bit to decide if it is a particular state or not. If some downstream logic depends on being in the 'Idle' state than the boolean logic that actually gets implemented will depend on 'Current_State.Idle' (a single bit), as opposed to using all four bits 'Current_State[3..0]'.

If you then take the above code and add 'when others=> Current_State <= Idle' to the case statement as a method to cover those 'impossible' states, synthesis tools will generally ignore it because I have already covered all of the possible cases in an earlier 'when ...'.

Of course I haven't tested this. But then I have never seen a tool
perform optimization that throws out valid logic that has inputs and
outputs.

I don't know what you're talking about here.

Kevin Jennings

 

[rickman]

On 3/31/2015 4:30 AM, Thomas Stanka wrote:

Am Dienstag, 31. März 2015 03:51:55 UTC+2 schrieb rickman:
The easiest way to ensure Synplify keeps all defined states is using 2^n states and cycle at least once (after reset) through all "unused" states.

In all other cases you might end up with a result different from your intention.

I'm not clear on what it means to "preserve" states...? The states are
there, legal or illegal. You can't get rid of them. Are you saying the
tool can remap the values of the state variable to mean something other
than what you intend?

Assume you have 10 user states and fill up to 16 by adding unused_state10-15 than write "when others => state <= idle;"
This would logically ensure you recover from all states. On RTL simulation you could even set the fsm by force command to unused state and see the FSM recovers. But Synplify extracts during synthesise step, that you could not reach the unused states and therefore starts optimising them in a way that you might find later on a state from which your FSM cannot recover if it get stuck there.

The same is valid if you use an counter from 0-9 "if counter < 10 then ... else counter <= 0;". This statement can be optimised by Synplify to code that might stuck, if your counter ever reaches value 14 due to SEE.

For One-Hot situation is even worse, if you consider states not reachable by normal operation, but you reach by accident (SEE, metastability,...), like states with zero or two '1's.

I was not aware that the tools would perform that level of analysis.
Where did you learn this? Is this from the vendor's optimization?

I suspect the method of one-hot coding I have described would prevent
such optimization since each state is an independent FSM, it would be
much harder to analyze and determine the various "impossible" states
based on the logical analysis.

--

Rick

 

[rickman]

On 3/31/2015 1:10 PM, KJ wrote:

On Tuesday, March 31, 2015 at 11:50:03 AM UTC-4, rickman wrote:

I suspect the method of one-hot coding I have described would prevent
such optimization since each state is an independent FSM, it would be
much harder to analyze and determine the various "impossible" states
based on the logical analysis.


One hot encoding is exactly the case one can generate a large number of 'impossible states'. If you have a four state state machine, and it is implemented as one-hot, then you will have four flip flops. Those four flip flops can theoretically be in any of 16 states; four 'legit' and 12 'impossible'.

Optimized logic that uses the state bit(s) would only look at the individual bit to see if a particular state is active (since that is the primary reason for using a one-hot encoding in the first place) and would ignore the other state bits. Those state bits can only be interpreted as 'independent FSMs' if you ignore the possibility of actually getting into 'impossible states', which given a stray energetic space particle hit could happen therefore it is not impossible.

Bottom line is that one hot encoding definitely does not prevent any vendor optimization of the issue being discussed. In fact, the vendor optimization to use one-hot (if not explicitly told to not use), creates more potentials for this problem (witness a four state machine having 12 impossible states).

I can't say I follow your reasoning. If the vendor's tools look across
all logic for sequential logic that depends on other sequential logic
and combines it into a FSM that can be optimized, then nearly every
design would be treated as a single FSM. What makes this approach a
group of separate FSMs which aren't optimized by the tools is that they
are separate signals. How exactly do the tools decide what is a FSM and
what is not?

Of course I haven't tested this. But then I have never seen a tool
perform optimization that throws out valid logic that has inputs and
outputs.

--

Rick

 

[rickman]

On 3/31/2015 3:31 PM, KJ wrote:

On Tuesday, March 31, 2015 at 1:28:42 PM UTC-4, rickman wrote:

I can't say I follow your reasoning. If the vendor's tools look across
all logic for sequential logic that depends on other sequential logic
and combines it into a FSM that can be optimized, then nearly every
design would be treated as a single FSM. What makes this approach a
group of separate FSMs which aren't optimized by the tools is that they
are separate signals. How exactly do the tools decide what is a FSM and
what is not?


We could be talking different things since I didn't say anything about looking across all logic... For FSMs, I think we're talking about the following type of coding:

type t_My_States is (Idle, Do_Something, Do_Something_Important, Done);
signal Current_State: t_My_States;
....
case Current_State is
when Idle=> ...
when Do_Something => ...
when Do_Something_Important=> ...
when Done => ...
end case;

The synthesis tools don't have to look to far to see that 'Current_State' is a single signal. The tool can then choose to implement that single signal as one-hot in which case it will use four flip flops which, in theory, have 16 different combinations. Only 4 of the 16 are 'valid' in that they are described by the code that was written. The other 12 are 'impossible', 'not valid' etc. that can only be reached by things such as an SEU, timing problem, voltage problem and other things that 'should not happen'.

Although the implementation of 'Current_State' is in four flops, those four are not independent. The logic that gets synthesized takes advantage of the fact that it is choosing to implement Current_State as one-hot so any dependent logic will only have to look at one bit to decide if it is a particular state or not. If some downstream logic depends on being in the 'Idle' state than the boolean logic that actually gets implemented will depend on 'Current_State.Idle' (a single bit), as opposed to using all four bits 'Current_State[3..0]'.

If you then take the above code and add 'when others=> Current_State <= Idle' to the case statement as a method to cover those 'impossible' states, synthesis tools will generally ignore it because I have already covered all of the possible cases in an earlier 'when ...'.

This is exactly my point. Don't code like this. Code the one hot
states independently and the tool won't be able to see it as one large
FSM. Instead each state will appear as a separate FSM with nothing to
be optimized out. Error detection will consist of adding the state bits
and if the count is not exactly one, go to a safe state, a signal that
sets all the separate state bits to the appropriate value. I supplied
code for this earlier, but here is a version I like better based on the
transition specification rather than the present state value.

FSM : process (Clk, Rst)
begin
if ('1' = Rst) then
StateA <= '1';
StateB <= '0';
StateC <= '0';
StateD <= '0';
.
.
.
StateZ <= '0';
elsif (rising_edge(Clk)) then
if ( /state transition condition from X to A/ ) then
StateX <= '0';
StateA <= '1';
end if;

if ( /state transition condition from A to B/ ) then
StateA <= '0';
StateB <= '1';
end if;
.
.
.
if ( error condition ) then
StateA <= '0';
StateB <= '0';
... all state signals defined ...
StateZ <= '0';
end if; -- Error recovery
end if; -- (if Rst)
end process FSM;

It would be trivial to create and maintain this from a state diagram.
There is a one to one mapping of the state transitions to the functional
sections of code. Rather than have a huge process, this could be
simplified by writing each transition as a procedure. Unfortunately
this might be a bit awkward to maintain as each procedure will require a
custom list of inputs and outputs in two places in the code. But it
might lend itself to some reuse of functions.

An advantage of the previous state oriented method is that each signal
is only controlled from a single IF statement so there is no interaction
between the different sections. In the transition oriented code each
state signal is set in one IF statement and reset in another so that
there may be some mixing of conditions because the order in which they
occur implies priority. Just thinking out loud here...

Of course I haven't tested this. But then I have never seen a tool
perform optimization that throws out valid logic that has inputs and
outputs.

I don't know what you're talking about here.

I believe someone mentioned that if cases were included for the error
states that because the tool understands these states can not be reached
it removes the logic for transitioning to "safe" states. I've never
seen this behavior. I have only seen logic optimized away because it
has either the input or output disconnected.

--

Rick

 

[Thomas Stanka]

Am Dienstag, 31. März 2015 17:50:03 UTC+2 schrieb rickman:

I was not aware that the tools would perform that level of analysis.
Where did you learn this? Is this from the vendor's optimization?

Just perform structural equivalence check of designs synthesised by Synplify (without synkeep or similar), ask yourself why the tool finds differences even in rather simple counters and than verify the equivalence check pattern is right by simulating the netlist.

This is not necessary happen the first 1-2 designs, but if you do this several times you learn what to expect.

best regards,

Thomas