UPGRADE YOUR BROWSER

We have detected your current browser version is not the latest one. Xilinx.com uses the latest web technologies to bring you the best online experience possible. Please upgrade to a Xilinx.com supported browser:Chrome, Firefox, Internet Explorer 11, Safari. Thank you!

cancel
Showing results for 
Search instead for 
Did you mean: 
Explorer
Explorer
1,119 Views
Registered: ‎12-07-2018

Efficient State Machine Design

Jump to solution

Hello, I was looking a few papers on the web:

http://www.sunburst-design.com/papers/CummingsICU2002_FSMFundamentals.pdf

page 17

 

and the paper

 

http://www.sunburst-design.com/papers/CummingsSNUG2003SJ_SystemVerilogFSM.pdf

page 10 and 11

I also found this in the book, "
RTL Modeling with SystemVerilog for Simulation and Synthesis: Using SystemVerilog for ASIC and FPGA Design 1st Edition
by Stuart Sutherland (Author)"  page 314-315.

For some time I coded my state machine as described on page 11 until I came across these documents. I mentioned this to a co-worker and he said that page 10 is too confusing and page 11 is easier to read. He also said that with today's faster processors and better compilers you should not need to worry about the speed with one-hot encoding verses other implementations. I would like to ask the forum members for their comments one writing state machines.

 

Thank

0 Kudos
1 Solution

Accepted Solutions
Highlighted
Scholar markcurry
Scholar
998 Views
Registered: ‎09-16-2009

Re: Efficient State Machine Design

Jump to solution

I've noticed that Vivado no longer recognizes my state machines.  Perhaps they never worked in Vivado at all, I know they did in ISE, but I don't look for these sorts of things too closely.   I'll perhaps look into in it one day and figure out why not.  Maybe not, - it's a whole lotta "meh" in my opinions these days.  The area savings and/or performance are just so much in the noise to be a don't care for most designs. 

As to the robustness, and safety in the light of "soft-errors"?  I fail to see much benefit in implementing soft-error tolerance in what, 3-6 Flip flops (per state machine).  These are such a small set of all the FFs in my design.  Sure, that's great those FFs have soft-error fault redundancy - what about the rest of the FFs in the design? Any set of FFs with random logic can be considered a state machine if you squint your eyes...

To the OP - in my opinion find a coding style that you like that codes things CLEARLY.  That's the number one goal.

Regards,

Mark

6 Replies
Teacher xilinxacct
Teacher
1,110 Views
Registered: ‎10-23-2018

Re: Efficient State Machine Design

Jump to solution

@joe306

One hot encoding is still the most 'efficient' in terms of 'time' (not space)... It has a constant cost across the condition. It also has the benefit of detecting invalid states. It is true, that most modern synthesizers/optimizer will use the one hot encoding, if the user has not coded in such a way to preclude it. However, those same tools will convert it choices when the size gets larger, to optimize more for space. So, there is a sweet spot. 

The 'faster' compute argument, doesn't sound valid, as the one hot will take advantage of that improvement as well.

So, If you want to take control, choose your method, rather than the system.

Hope that helps

If so, Please mark as solution accepted.

0 Kudos
Historian
Historian
1,098 Views
Registered: ‎01-23-2009

Re: Efficient State Machine Design

Jump to solution

First - in an FPGA it is somewhat debatable if a one-hot state machine is in fact faster. The basic combinatorial cell in an FPGA is the LUT6, and it is just as fast doing a 6 input function as a 2 input function (at least within a few picoseconds). So with a fully encoded state machine if you have an 8 state state-machine with 3 inputs, then the entire state machine can be coded in 3 LUTs - one LUT for each "next_state" bit, each using 6 inputs; the 3 existing state bits and the three inputs. If you code this as one hot, you will use a minimum of 8 LUTs (one for each one-hot state bit), and will be no faster...

But, all that aside...

The modern synthesis tools all do "state machine extraction" - they identify state machines, and determine the best way to code the state values - they can choose fully encoded, Gray, one hot, or allow the user to control it. As a result, you should probably never code one hot state machines - describe the state machine in the easiest way (which is fully encoded) and then let the synthesis tool determine the state coding. So don't use either page 10 or 11 - use page 9.

I won't go further and discuss the advantages of disadvantages of the 1, 2, or 3 process state machine...

Avrum

0 Kudos
1,090 Views
Registered: ‎09-17-2018

Re: Efficient State Machine Design

Jump to solution

As mentioned,

For Xilinx FPGA device fabric, one-hot FSM are the most likely to be implemented and deliver the best results (area, speed).  That said, there are situations where you need to specify a different implementation through the use of directives in synthesis (pragmas).

Of greater importance, is to code safe state machines (no hidden states, and a recovery state so it cannot get 'stuck').

In some cases, if you are at 45K feet (or in space) your state machine must be robust enough to work through soft error upsets (state might have SECDED coding, or at least a parity or sanity check, in which case, it is not a one hot FSM any longer).

Many answers here, like this one?

https://www.xilinx.com/support/answers/51237.html

Just search these forums using the search icon above on this page for finite state machines or safe finite state machines.

External guides likely represent an individual's view, or experience, and may be old, obsolete, or just plain wrong.

Teacher xilinxacct
Teacher
1,064 Views
Registered: ‎10-23-2018

Re: Efficient State Machine Design

Jump to solution

To put the icing on the cake...

quoting Xilinx Design Guide...

“One-hot encoding allows you to create state machine implementations that are more efficient for FPGA architectures. You can create state machines with one flip-flop per state and decreased width of combinatorial logic. One-hot encoding is usually the preferred method for large FPGA-based state machine implementation. For small state machines (fewer than 8 states), binary encoding may be more efficient. To improve design performance, you can divide large (greater than 32 states) state machines into several small state machines and use the appropriate encoding style for each. “

Hope that helps

0 Kudos
Xilinx Employee
Xilinx Employee
1,028 Views
Registered: ‎05-22-2018

Re: Efficient State Machine Design

Jump to solution
0 Kudos
Highlighted
Scholar markcurry
Scholar
999 Views
Registered: ‎09-16-2009

Re: Efficient State Machine Design

Jump to solution

I've noticed that Vivado no longer recognizes my state machines.  Perhaps they never worked in Vivado at all, I know they did in ISE, but I don't look for these sorts of things too closely.   I'll perhaps look into in it one day and figure out why not.  Maybe not, - it's a whole lotta "meh" in my opinions these days.  The area savings and/or performance are just so much in the noise to be a don't care for most designs. 

As to the robustness, and safety in the light of "soft-errors"?  I fail to see much benefit in implementing soft-error tolerance in what, 3-6 Flip flops (per state machine).  These are such a small set of all the FFs in my design.  Sure, that's great those FFs have soft-error fault redundancy - what about the rest of the FFs in the design? Any set of FFs with random logic can be considered a state machine if you squint your eyes...

To the OP - in my opinion find a coding style that you like that codes things CLEARLY.  That's the number one goal.

Regards,

Mark