huge fsm

[Mai]

hello,
I am programming a state machine with more than 50 states but less than
100, i am wondering if it will take a lot of space in the design of the
FPGA? (and I have a lots of others in the total program on one chip) If
yes, which solutions?

Thanks

 

[fabbl]

The bigger the state machine, the deeper the combinatorial logic. The deeper
the logic, the more delay. I would consider breaking this up using "if"
statements instead in seperate processes.


"Mai" <mai@hide> wrote in message
news:f676815f686ef550a3795da705204561@localhost.talkaboutprogramming.com...

hello,
I am programming a state machine with more than 50 states but less than
100, i am wondering if it will take a lot of space in the design of the
FPGA? (and I have a lots of others in the total program on one chip) If
yes, which solutions?

Thanks

 

[Mai]

You mean a lot of little state machines instead of a big one?
Do you know how i could calculate the space a state machine takes on a
FPGA (with the number of states)? I know it exists...
I am afraid my FPGA will be full with my code, but I just don t know how
to compare them?!

 

[Jonathan Bromley]

On Thu, 22 Jul 2004 05:22:43 -0400, "Mai" <mai@hide> wrote:

You mean a lot of little state machines instead of a big one?

It's possible to do this, but it can become tricky to design.

Do you know how i could calculate the space a state machine takes on a
FPGA (with the number of states)? I know it exists...

Some aspects are easy to calculate. In particular, it's easy to
decide how many flip-flops (registers) are needed. However,
the amount of combinational logic required is much harder to
estimate.

Synthesis tools generally can recognise state machines in your code,
and they perform some automatic transformations in an attempt to
make them more efficient. One of the most common transformations
is to use one-hot coding for the state. If you allow the synthesis
tool to do this, you will get one flip-flop for each state
(N states => N flip-flops). This sounds bad, but in fact it can
be very helpful because it usually makes the combinational logic
simpler. In some situations this saves logic. More important, it
usually makes the state machine faster (higher maximum clock rate).

Alternatively, you can ask the synthesis tool to binary-encode the
state. This gives you the minimum possible number of flip-flops.
If the state register contains F flip-flops, then it can represent
a maximum of 2**F different states. For example, a state machine
with 100 states needs only 7 flip-flops using binary coding
(2**7 = 128) but using one-hot coding it would need 100 flip-flops.
However, the combinational logic for a binary-coded state machine
is probably much more complicated than for one-hot. This increased
complexity will partly offset the saving of flip-flops in an FPGA,
because every piece of combinational logic has a flip-flop
associated with it and therefore you will end up with many
wasted flip-flops. It will also make the logic slower, in most
cases.

Every synthesis tool I know of has some kind of option to
determine how state machines are coded. Try it!

I am afraid my FPGA will be full with my code, but I
just don t know how to compare them?!

In practice, I suspect, you will have no problem. If you
need 100 states in your FSM, then it probably controls a large
amount of other logic. In most designs, the datapath logic
is much bigger than its controlling FSM.

Once again: Try it! Ask your synthesis tool to produce an
area report! Read ALL the synthesis tool's output - it will
tell you about all the registers it creates.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[J. op den Brouw]

Jonathan Bromley wrote:

Synthesis tools generally can recognise state machines in your code,
and they perform some automatic transformations in an attempt to
make them more efficient. One of the most common transformations
is to use one-hot coding for the state. If you allow the synthesis
tool to do this, you will get one flip-flop for each state
(N states => N flip-flops). This sounds bad, but in fact it can
be very helpful because it usually makes the combinational logic
simpler. In some situations this saves logic. More important, it
usually makes the state machine faster (higher maximum clock rate).

Synthesis tools for FPGA will use one-hot encoding because they
have a huge amount of FF's on board. Of course you can override that
but you don't want to.

You can also set timing constraints so the synthesizer will comply
to some minimum clock frequency.

Alternatively, you can ask the synthesis tool to binary-encode the
state. This gives you the minimum possible number of flip-flops.
If the state register contains F flip-flops, then it can represent
a maximum of 2**F different states. For example, a state machine
with 100 states needs only 7 flip-flops using binary coding
(2**7 = 128) but using one-hot coding it would need 100 flip-flops.
However, the combinational logic for a binary-coded state machine
is probably much more complicated than for one-hot. This increased
complexity will partly offset the saving of flip-flops in an FPGA,
because every piece of combinational logic has a flip-flop
associated with it and therefore you will end up with many
wasted flip-flops. It will also make the logic slower, in most
cases.

--Jesse