how to deal with real big FSMs?

[Markus Hagen]

Hello!

I'm about to describe a big state machine in Verilog. Most of the
states (let's call them "opcodes") need more than one clock cycle to
finish. So each of theese states do have a number of 'sub-states' on
it's own (let's call them "ticks").

To accomplish this i've come up with two design ideas:
1) The state is a concatenation of {opcode,tick} and leads to one big
FSM with many states with some of them undefined.

case {opcode,tick}
{add,0}: ... next <= {add,1}
{add,1}: ... next <= {add,2}
{add,2}: ... next <= {fetchOP,0}
{sub,0}: ... next <= {sub,1}
...
default:
endcase


2) The other solution i found is to create a reg "tick" which counts up
each clock cycle if not otherwise set to zero. The states of the FSM
now only consist of {opcode} thus it is smaller and undefined opcodes
could be avoided. The inferred hardware in each state depends on the
actual tick:

case opcode
add:
if (tick == 0) ...
else if (tick == 1) ...
else if (tick == 2) ...
else ...
tick <= 0
sub:
...
default:
endcase


Now i'm curious what hardware theese designs infer and which of them is
the better one. Maybe booth are crap and there's a much more clever way
to achieve this (i would like to know .

Even a FSM with a 15 bit wide state register (binary coded) is reencoded
by the synthesis tool as one-hot. My target is an FPGA, but there are
32K possible states at 15 bit!

Does anyone know a source on this?


Regards,
Markus

 

[Kai Harrekilde-Petersen]

"Markus Hagen" <turboschlumpf@arcor.de> writes:

I'm about to describe a big state machine in Verilog. Most of the
states (let's call them "opcodes") need more than one clock cycle to
finish. So each of theese states do have a number of 'sub-states' on
it's own (let's call them "ticks").

To accomplish this i've come up with two design ideas:
1) The state is a concatenation of {opcode,tick} and leads to one big
FSM with many states with some of them undefined.

case {opcode,tick}
{add,0}: ... next <= {add,1}
{add,1}: ... next <= {add,2}
{add,2}: ... next <= {fetchOP,0}
{sub,0}: ... next <= {sub,1}

When I designed an FDDI Line State Monitor FSM - which looks quite
like what you are describing - many years (around '91 I guess) ago as
part of a Uni project, I found that splitting the LSM into a distinct
FSM + a 3bit counter was vastly superior to writing a mashed-together
FSM in terms of area, synthesis time, and timing.

It might have improved since then, but I wouldn't bet my money on it.

BR,


Kai
--
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>

 

[Ralf Hildebrandt]

Markus Hagen schrieb:

2) The other solution i found is to create a reg "tick" which counts up
each clock cycle if not otherwise set to zero. The states of the FSM
now only consist of {opcode} thus it is smaller and undefined opcodes
could be avoided.

To go one step further the counter (or "sub-state machine") can disable
the clock of the big state machine (or "master-state machine").

Note that clock-gating reduces power consumption a lot but may lead to
problems with clock skew.


Even if I can't use clock gating. I try to use a counter for the
sub-states. To be more precise: I use a decrementer. If it counts over
zero (detectable by the carry-out) then the master-state changes and the
counter is loaded with the appropriate value for the next master-state.


Ralf

 

[Ulf Samuelsson]

Markus Hagen wrote:

Hello!

I'm about to describe a big state machine in Verilog. Most of the
states (let's call them "opcodes") need more than one clock cycle to
finish. So each of theese states do have a number of 'sub-states' on
it's own (let's call them "ticks").

....

Now i'm curious what hardware theese designs infer and which of them
is the better one. Maybe booth are crap and there's a much more
clever way to achieve this (i would like to know .

Even a FSM with a 15 bit wide state register (binary coded) is
reencoded by the synthesis tool as one-hot. My target is an FPGA,
but there are 32K possible states at 15 bit!

Would it not be better to use a ROM for this?
Should be possible to implement in BlockRAM
or if it does not need to be that fast, an external parallel flash memory.

Does anyone know a source on this?


Regards,
Markus

--
Best Regards,
Ulf Samuelsson
ulf@a-t-m-e-l.com
This message is intended to be my own personal view and it
may or may not be shared by my employer Atmel Nordic AB