What FSM should I use ?

[Thor Phersen]

I have this large design which eventually has been redesigned from huge
blocks of combinatorial logic, to a rather elegant code with 9 finite state
machines, all talking to each other.

But what kind of state machine is teh best implementation in an FPGA ? I
started out with the common two-process design, that did not work, ISE found
lots of "clock-signals" and suggested that I should buffer them.

I then tried the 3-process design suggested in the ISE manual, but that did
not work either.

Finally, I tried to write the code as one-process FSM designs, as described
in ISE manual, and hurray ! It compiles fine in ISE, it is recognised as
FSM's ! And it work too !


I just wonder, since one- process FSM-coding works, what is the point with
two-process FSM coding ?
One-process coding is more is easier to read, less time-consuming to write,
and is easier to read for others.

Using two-process coding just seems like a waste of time-.

 

[Mike Treseler]

Finally, I tried to write the code as one-process FSM designs, as described
in ISE manual, and hurray ! It compiles fine in ISE, it is recognised as
FSM's ! And it work too !

I just wonder, since one- process FSM-coding works, what is the point with
two-process FSM coding ?
Tradition.

One-process coding is more is easier to read, less time-consuming to write,
and is easier to read for others.

You're preaching to the choir

-- Mike Treseler

 

[Thor Phersen]

You're preaching to the choir

What do you mean by "You're preaching to the choir?" That I am trying to
convert the already converted or something ?

I think one shuld not drag religion into this matter, after all, it's jus a
matter of computer programming. Religious stuff are for the heavy thinks in
life, like bearth an death.
Man skal vise litt respekt for slike ting.

 

[Mike Treseler]

What do you mean by "You're preaching to the choir?" That I am trying to
convert the already converted or something ?

I mean that I agree with you and that
I expect that several other frequent
posters here probably agree also.

The symbol implies humorous rather than
serious intent.

-- Mike Treseler

 

[Thor Phersen]

I mean that I agree with you and that
I expect that several other frequent
posters here probably agree also.

The symbol implies humorous rather than
serious intent.

My reply was also meant i a humourus way ;-) but I am still pussled about
the fact that most text-books promote two or even three process FSM designs,
when the one process design are so obvious much more simple an elegant ? I
just don't get it. Maybe I'm stupid or something.

 

[Mike Treseler]

My reply was also meant i a humourus way ;-) but I am still pussled about
the fact that most text-books promote two or even three process FSM designs,
when the one process design are so obvious much more simple an elegant ? I
just don't get it. Maybe I'm stupid or something.

If that's stupid, I'm really stupid because
I use one process per entity.

http://home.comcast.net/~mike_treseler/

 

[Jonathan Bromley]

I am still pussled about
the fact that most text-books promote two or even three process FSM designs,
when the one process design are so obvious much more simple an elegant ? I
just don't get it. Maybe I'm stupid or something.

No, you get it OK.

It is definitely *not* crazy to add a process to your FSM to describe
combinational decoding of the state, generating output signals that
are a function of the state. In the overwhelming majority of cases,
such combinational logic is rather simple and doesn't cause any
serious trouble with timing closure; and it may be appropriate and
convenient to add it to the state machine. Personally I like to do
it a slightly different way, so that I keep my single process; but
I really believe there is a sensible choice here.

What is truly crazy (in my opinion) is the endless promotion of
true Mealy-style state machine architectures, with a genuine
combinational path from inputs to outputs. That also requires
the FSM to be described as at least two processes; but I can
never recommend it, because of the risks it poses of introducing
combinational feedback paths (what happens when you have
two Mealy FSMs interacting???!!!) and the problems it's likely
to cause with timing closure and timing predictability.

Three-process coding of any FSM is unconditionally insane.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
(e-mail address removed)
http://www.MYCOMPANY.com

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

 

[Thor Phersen]

No, you get it OK.

It is definitely *not* crazy to add a process to your FSM to describe
combinational decoding of the state, generating output signals that
are a function of the state. In the overwhelming majority of cases,
such combinational logic is rather simple and doesn't cause any
serious trouble with timing closure; and it may be appropriate and
convenient to add it to the state machine. Personally I like to do
it a slightly different way, so that I keep my single process; but
I really believe there is a sensible choice here.

What is truly crazy (in my opinion) is the endless promotion of
true Mealy-style state machine architectures, with a genuine
combinational path from inputs to outputs. That also requires
the FSM to be described as at least two processes; but I can
never recommend it, because of the risks it poses of introducing
combinational feedback paths (what happens when you have
two Mealy FSMs interacting???!!!) and the problems it's likely
to cause with timing closure and timing predictability.

In my opinion, mealy state machines are not really state machines at all,
just huge clusters of logic.

Three-process coding of any FSM is unconditionally insane.

I tend to agree with you on that, but there has to be some reason for Xilinx
to promote three-process FSM designs in the XST- manual ( 7.1)

 

[Andy Peters]

What is truly crazy (in my opinion) is the endless promotion of
true Mealy-style state machine architectures, with a genuine
combinational path from inputs to outputs. That also requires
the FSM to be described as at least two processes; but I can
never recommend it, because of the risks it poses of introducing
combinational feedback paths (what happens when you have
two Mealy FSMs interacting???!!!) and the problems it's likely
to cause with timing closure and timing predictability.

The day the textbooks drop the words "Mealy" and "Moore" from the state
machine chapter is the day we know that true progress has been made.

I'm sure that's the day that the universe will implode.

If I interview a job candidate for an FPGA position and he uses the
words "Mealy" or "Moore," I know right then that he has zero practical
experience.

-a

 

[Ben Jones]

The day the textbooks drop the words "Mealy" and "Moore" from the state
machine chapter is the day we know that true progress has been made.

I'm sure that's the day that the universe will implode.

If I interview a job candidate for an FPGA position and he uses the
words "Mealy" or "Moore," I know right then that he has zero practical
experience.

Hmmm. I remember interviewing for a job straight out of college (company
shall remain nameless) and one of the things I was asked was to explain the
difference between the Mealy and Moore models of state machines. This took
me off my guard somewhat.

My answer was along the lines of "I vaguely remember learning about those
three years ago... something about how the outputs are calculated... but
they're functionally equivalent, I remember that. And *real* state machines
don't really look like either of them, do they?"

I got blank looks. I wasn't offered the job. I don't think I would've taken
it anyway.

Since then I have designed an awful lot of real state machines, and the
Mealy/Moore question never came up once.

-Ben-

 

[Jonathan Bromley]

Since then I have designed an awful lot of real state machines, and the
Mealy/Moore question never came up once.

Great!

I used to regard it as a matter for some pride that I couldn't
even remember which was which.

Depressingly, these days I *can* remember that. Not many
other things, though :-(
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
(e-mail address removed)
http://www.MYCOMPANY.com

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

 

[Ben Jones]

Great!

I used to regard it as a matter for some pride that I couldn't
even remember which was which.

Aren't Moore state machines the ones that double in complexity every 18
months?

-Ben-

 

[Jim Lewis]

My reply was also meant i a humourus way ;-) but I am still pussled about
the fact that most text-books promote two or even three process FSM designs,
when the one process design are so obvious much more simple an elegant ? I
just don't get it. Maybe I'm stupid or something.

With one process all output of the process are registered.

With two process, you have a choice as to whether to
register your outputs or not. As you found out this
added flexibility has a hazard of potentially creating
latches. You can avoid this by initializing all of your
outputs to a default state. As Jonathan points out in
a later thread, two process also has the hazard of
creating combinational logic feedback with multiple
statemachines handshaking.

With a one process, if you need combinational logic
you can easily add it with code outside of the process.
In this case, however, it becomes as much like a two
process as a one process.

I never thought three process statemachines made any sense.
A three process statemachine is like have one bubble diagram
for the present state - next state transitions and a separate
bubble diagram for output logic. If you like this, then
go for it.

In the end all techniques seem to produce reasonable results.
So find the one that suits you.

Two process may suit you well if you like creating your
hardware in separate pieces (separate processes or assignments).
This way you can choose if you register the outputs or not.
I don't like registering a signal that goes directly to the
load enable of a register.

One process will suit you well if you like creating the
statemachine and the code it controls in a single process.
For a good example of this, see Mike's code.

Methodologies will change with time to adjust for the
biggest problem of the time. Is it area, timing, power, ...

I don't like one process as it does not work well for all
people. I have worked on projects where someone inherited
a one process statemachine and was unable to effectively
maintain it. As a result it was an issue. This may be a
rare occurrence, I don't know. I think we all avoid
things that caused problems for us or our projects in the
past - hence we gravitate toward slightly different
methodologies.


Cheers,
Jim
SynthWorks

 

[KJ]

With one process all output of the process are registered.

Mike Tressler would disagree with this statement for sure. You can use
variables and create combinatorial outputs. Personally I don't use this
technique but it does work.

With two process, you have a choice as to whether to
register your outputs or not. As you found out this
added flexibility has a hazard of potentially creating
latches. You can avoid this by initializing all of your
outputs to a default state. As Jonathan points out in
a later thread, two process also has the hazard of
creating combinational logic feedback with multiple
statemachines handshaking.

The two process style causes you to
- Write more code (2 process style will always have more statements than 1
process), more chances for error.
- Manually check (this means you, not the machine) for coding errors that
will cause the simulation to behave differently than the synthesized version
and yet both will run to completion without an 'error'. This is caused by
things like: incomplete sensitivity lists and unhandled cases in the
combinatorial process which creates latches). None of this happens with the
one process approach. Combinatorial outputs should live either in
concurrent statements outside the process or, using Mike's style, as
assignments at the very end of the process after all of the variables have
been updated.

With a one process, if you need combinational logic
you can easily add it with code outside of the process.
In this case, however, it becomes as much like a two
process as a one process.

In a theoretical sense "becoming much like a two process" is true...the
other way to look at it is that the statements that are outside the 'one
process' are the combinatorial outputs, the ones that are inside are
clocked...and many times simply glancing at the code to discern this is
almost all you need to debug some problem. For example, when you look at
the signal assignment being made in the clocked process and immediately know
why it is happening one clock cycle too late in the simulation.

Personally I tend to break up my 'one process' into multiple processes all
clocked by the clock and have all the combinatorial stuff outside all of the
processes in concurrent statements. The multiple processes all clocked by
the clock signal while not strictly necessary allows for physical grouping
of 'related' signals into chunks of code that are easier to read since they
will tend to fit on a screen as opposed to a single monolithic process where
one may have to page back and forth when reviewing the code to debug some
problem. In any case, my multiple clocked processes are one virtual process
so I definitely come down in the 'one process' camp.

I never thought three process statemachines made any sense.
A three process statemachine is like have one bubble diagram
for the present state - next state transitions and a separate
bubble diagram for output logic. If you like this, then
go for it.

In the end all techniques seem to produce reasonable results.
So find the one that suits you.

That's some bum advice. I'll accept that some people for whatever reasons
prefer the two process approach (and maybe three who knows) but the one
process approach is superior from the standpoint of designer productivity.
I contend that the new person starting out would end up being more
productive (i.e. working and tested lines of code per time period) with the
one process approach because of the two fundamental drawbacks I mentioned
earlier regarding the two process approach (more code and manual checks).

I'd even go so far as to say that a fair percentage (probably not all
though) of those who today prefer the two process method would be more
productive if they changed their mindset and tried the one process way and
worked on it a bit and gave it a chance. I base this on comments seen here
and elsewhere of people that have converted from two process to one process
and said how much easier it now seems and NEVER having seen a report of
anyone switching from one process to two process and making the same claim.
The two process people seem to prefer that approach because either that is
the way they were trained and they are now 'used to it', or the company they
work for requires it for reasons that even the two process poster admits he
does not understand...but he values his job soooo.....

So even though either approach produces 'reasonable results', I don't think
you toss out designer productivity as being a reason to not prefer the one
process method to the newbie.

I don't like one process as it does not work well for all
people. I have worked on projects where someone inherited
a one process statemachine and was unable to effectively
maintain it. As a result it was an issue.

I'm betting that this was the monolithic one process approach. The virtual
one process where you try to group 'related' things together to create
clocked processes that all fit on a screen would've helped. Having the
single monolithic process tends to cause people to put many unrelated things
together where they are not really appropriate (but it does 'work'...under
certain conditions). In any case, what you've described is totally
unrelated to one or two process...it was simply poorly written (but probably
at one time working) code. It would've been just as unsupportable if the
person that wrote that used two processes because the person that wrote the
code didn't have a sense of how to write clean code. Clear thinkers can
write clearly.

Kevin Jennings

 

[Mike Treseler]

Mike Treseler would disagree with this statement for sure. You can use
variables and create combinatorial outputs. Personally I don't use this
technique but it does work.

The only time I actually used a combinational
node in a synchronous process was as an example
for a usenet discussion in 2005.

http://home.comcast.net/~mike_treseler/single_process.vhd
http://home.comcast.net/~mike_treseler/single_process.pdf

This shows that a synchronous process and
a combinational *nodes* can coexist, but note that all of
the resulting outputs are in fact registered.

I have so far never needed a combinational output
pin at the device level and internally and I prefer
functions to describe complex boolean expressions.

-- Mike Treseler

 

[Andy]

I don't often use combinatorial outputs period, but when I do, I now
use the signal assignment from an expression of variables after the
clock clause in a synchronous process.

Using a single process for a state machine allows one to use variables
for the state, ensuring that the state cannot be directly read anywhere
else (a bad design practice, IMHO). If something needs to be known
externally about the status of a state machine, I generate an output
signal to indicate that. This isolates state machine implementation
details from outside influences. This could be done with signals if you
code the two process state machine inside a block, with the state
signal declared inside the block. But not many people are willing to do
that.

Andy

 

[KJ]

I don't often use combinatorial outputs period,

Many handshaking protocols require this...Wishbone, Avalon being two
examples where the 'wait' signal needs to be returned on the same clock
cycle as the read or write command. Other protocols may give you the luxury
of being able to pipeline such a handshake signal, but many times this may
come at the expense of throughput since the latency in the handshake
effectively decreases overall performance. Performance on moving data
(whether external to the chip or within blocks inside a single FPGA/ASIC
design) is important.

but when I do, I now
use the signal assignment from an expression of variables after the
clock clause in a synchronous process.

While usually workable, I find that approach to be confusing since you'll
have a process with clock as the signal in the sensitivity list and one
might rightly ask "What happens if the clock isn't running?". Those
combinatorial outputs will only work correctly if the inputs that cause the
outputs to change also happen to be outputs of a flip flop. When you
originally write that code you'll probably be aware of this and design will
work as intended, but if the block of code is picked up by someone else who
just wants to 'use' that code they may plop it down into an environment
where this is not the case.

In that situation, you could blame it on the user for not using the code
properly, but when it comes right down to it, it would be hard to justify
why the code was written in such a manner to have that sort of fragility
built into it that it could not properly implement a combinatorial function
without a clock.

I suppose it's also possible that synthesis tools might implement the
combinatorial function properly but it will simulate differently in the
absence of a clock. Granted in order for all this to occur you probably
have to the situation where you're implementing a combinatorial function
between primary design inputs and outputs at the top level of the
design...but that situation does occur since that is the place where you
interface to the outside world, and you might just have to be doing just
that.

Using concurrent statements to implement combinatorial outputs is just much
more straight forward of what the design intent actually is in my
opinion...so I guess we disagree a bit on this.

Using a single process for a state machine allows one to use variables
for the state, ensuring that the state cannot be directly read anywhere
else (a bad design practice, IMHO). If something needs to be known
externally about the status of a state machine, I generate an output
signal to indicate that.

Why? An entity/architecture is (or should be) implementing a specific
function and everything should be pulling together to implement this and
creating a new signal as a flag to indicate when you're in a state gives
opportunities to be less than clear. For example, using your approach the
process that needs to know when you're in a specific state would have code
something like...

if (Were_In_The_Important_State = '1') then
.....
whereas if the state variable is available throughout the
entity/architecture it would be
if (Current_State = The_Important_State) then

The difference is that there will be the tendency to 'fix' things by
changing what is being implemented by the signal
'Were_In_The_Important_State' from being a simple decode of (Current_State =
The_Important_State) into something completely different. Whether that
happens or not is up to personal discipline by the designer but the root
cause of the code degenerating in this manner is the hiding of useful data
to other processes within the same entity/architecture that are needed to
implement the overall function required by the entity....so why hide?

If the design is properly designed and the breakdown of what each entity is
supposed to do is done properly, I haven't found much use in hiding things
inside the entity/architectures from other processes. There is value in
hiding them from external entities but that is the whole point of a good top
level design.

Kevin Jennings

 

[Mike Treseler]

Why? An entity/architecture is (or should be) implementing a specific
function and everything should be pulling together to implement this and
creating a new signal as a flag to indicate when you're in a state gives
opportunities to be less than clear. For example, using your approach the
process that needs to know when you're in a specific state would have code
something like...

if (Were_In_The_Important_State = '1') then
....
whereas if the state variable is available throughout the
entity/architecture it would be
if (Current_State = The_Important_State) then ...

In a single process entity, all variables
including state variables *are* available everywhere.
It can't be simpler than that.

-- Mike Treseler

 

[KJ]

In a single process entity, all variables
including state variables *are* available everywhere.
It can't be simpler than that.

-- Mike Treseler

Replace 'variable' with 'signal' and the same statement regarding scope pops
out....and typing 'signal' takes 2 fewer keystrokes than 'variable'.

Kevin Jennings

 

[Andy]

Maybe you're not understanding what happens in a signal assignment from
an expression of variables, after the clocked clause, in a clocked
process.

The references to the variables in the expression will always be
registered. Thus it is exactly the same thing as if you assigned the
variables to signals just inside the clocked clause, and then in a
separate, combinatorial process, applied those signals to the same
expression. If the clock stops, all the inputs to the expression stop,
and so does the output. There will be a delta of time difference
between the two implementations, with the former version's output
updating one delta sooner than the latter.

Since you can only use variables in such an expression, you cannot
create a combinatorial path, from input to output, through a clocked
process.

As for "protecting" state variables, suppose you modified your state
machine to where two different states were deemed "Important_States"?
Since the decode is in the same process, it is relatively easy to find,
instead of searching through the rest of the code in the entity to find
out where you used it, and what it was compared to.

I usually don't separate related counters, shifters, etc. from a
controlling state machine, preferring to code them in one process.
Rather than setting a flag in a given state that tells another chunk of
code to increment the counter, I just increment the counter from within
the state. However, I prefer to use separate processes for separate
state machines, if for no other reason than to avoid combinatorial
control loops between them. That's where I most commonly use flags
instead of direct state decoding in the other state machine.

Even in a single process entity, one can use blocks around chunks of
sequential code, with an enclosed declarative region to define local
variables, visible only within that block.

I prefer not to have to use entities to hide implementation details,
especially when lightweight processes with variables can give me the
same benefits with less code. Entities tend to be on more structural
boundaries in my designs.

But if all of us designed alike, it'd be an awfully boring world.

Andy