Monolithic state machine or structured state machine?

[vax,3900]

I am designing a state machine that will be fit into a CPLD (Xilinx XC95xx).
The state machine needs to wait certain number of clockes here and there (
for example, 80 clockes here, and 160 clockes there ). If I design
everthing with hand, I whould choose structured state machine; that is, a
state machine plus a counter. But since I am using VHDL, and the compiler
would take care of everything, I think I might be able to make a monolithic
state machine with the counter built in ( that is, to add 80 states here,
and 160 states there ). Excluding the counter, the state machine has about
100 states.

My question is, which approach is better, for a CPLD? The monolithic design
will require less FF's, maybe. Have you guys met this question in your
projects?

 

[Jim Lewis]

Hi,

But since I am using VHDL, and the compiler
would take care of everything, ...
The compilers are not as smart as you think.

They are good and take care of many tedious problems,
but there are things you still must manage. My
opinion is that this is one of them. I recomment that
you stay with your old approach.

Code all arithmetic resources separately from your
statemachine. Synthesis & Optimization bring many reasons
for doing this.
1) Random logic (statemachines) and structured logic
(Arithmetic) are optimized using different synthesis
algorithms. For some tools you may get better quality of
results if the arithmetic is in a separate entity (file).
2) Writing your code explicitly, the counters can be
shared explicitly. This is even more important when the
counters are potentially different sizes (7 bits vs 8 bits).
It gets much more difficult (if not impossible) for a
synthesis tool to share resources that are different sizes.

When you are counting resources, don't forget your end detect
(zero detect) logic is a resource and should be coded separately
from your statemachine.

I have mostly used ASICs and FPGAs, so I cannot address the
specifics of a CPLD, but with a big statemachine, FPGA/CPLD tools
tend to make them one hot - one register bit per state.
With counters, there is one bit per log2 states. With
ASICs and FPGAs, counters tend to be more efficient than
statemachines.

Cheers,
Jim

vax,3900 wrote:

I am designing a state machine that will be fit into a CPLD (Xilinx XC95xx).
The state machine needs to wait certain number of clockes here and there (
for example, 80 clockes here, and 160 clockes there ). If I design
everthing with hand, I whould choose structured state machine; that is, a
state machine plus a counter. But since I am using VHDL, and the compiler
would take care of everything, I think I might be able to make a monolithic
state machine with the counter built in ( that is, to add 80 states here,
and 160 states there ). Excluding the counter, the state machine has about
100 states.

My question is, which approach is better, for a CPLD? The monolithic design
will require less FF's, maybe. Have you guys met this question in your
projects?

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jim Lewis
Director of Training mailto:Jim@SynthWorks.com
SynthWorks Design Inc. http://www.SynthWorks.com
1-503-590-4787

Expert VHDL Training for Hardware Design and Verification
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

[James Morrison]

Actually Jim, what you wrote below is not really true. I'm most familiar with Xilinx tools but I've used Altera's in the past and I believe they work the same.

For FPGA's where there is an abundance of flip-flops state machines default to one-hot encoding. However for CPLD's where there is lots of logic resources available but not many flip-flops the synthesis defaults to minimise the number of flip-flops used and encodes the state as bit patterns (usually gray codes). It is possible to override this behaviour either by spelling out the state encoding specifically or by setting a tool option somewhere.

Personally, I separate the logic out from the state transitions normally for the following reasons:
1) I find it easier to see where logic may be reused. Synthesis takes care of this but its good to have a gut feel.
2) I find it easier to understand when I come back to the design a long time later. Having logic embedded into state transitions and definitions is confusing. It may save a few resources and make something fit but if you can afford the small inefficienty (although that is debatable) the increase in maintainability is huge.

Just my $0.02.

James.

~

Jim Lewis<Jim@SynthWorks.com> 5/10/2004 2:15:32 PM
Hi,

I have mostly used ASICs and FPGAs, so I cannot address the
specifics of a CPLD, but with a big statemachine, FPGA/CPLD tools
tend to make them one hot - one register bit per state.
With counters, there is one bit per log2 states. With
ASICs and FPGAs, counters tend to be more efficient than
statemachines.

 

[Jim Lewis]

James,

what you wrote below is not really true
Confusing way to start when you agree with the

the approach I recommended. Ok so the correction
is only FPGA tools like one-hot, CPLD tools prefer
other implementations.

The key thing is that we both agree that be it an ASIC,
FPGA, or CPLD, code arithmetic resources (counters)
separately from the statemachines.

If you don't factor out arithmetic resources, then there
are both potential quality of result issues and
readability/reusability issues.

Cheers,
Jim


James Morrison wrote:

Actually Jim, what you wrote below is not really true. I'm most familiar with Xilinx tools but I've used Altera's in the past and I believe they work the same.

For FPGA's where there is an abundance of flip-flops state machines default to one-hot encoding. However for CPLD's where there is lots of logic resources available but not many flip-flops the synthesis defaults to minimise the number of flip-flops used and encodes the state as bit patterns (usually gray codes). It is possible to override this behaviour either by spelling out the state encoding specifically or by setting a tool option somewhere.

Personally, I separate the logic out from the state transitions normally for the following reasons:
1) I find it easier to see where logic may be reused. Synthesis takes care of this but its good to have a gut feel.
2) I find it easier to understand when I come back to the design a long time later. Having logic embedded into state transitions and definitions is confusing. It may save a few resources and make something fit but if you can afford the small inefficienty (although that is debatable) the increase in maintainability is huge.

Just my $0.02.

James.

~


Jim Lewis<Jim@SynthWorks.com> 5/10/2004 2:15:32 PM

Hi,
I have mostly used ASICs and FPGAs, so I cannot address the
specifics of a CPLD, but with a big statemachine, FPGA/CPLD tools
tend to make them one hot - one register bit per state.
With counters, there is one bit per log2 states. With
ASICs and FPGAs, counters tend to be more efficient than
statemachines.

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jim Lewis
Director of Training mailto:Jim@SynthWorks.com
SynthWorks Design Inc. http://www.SynthWorks.com
1-503-590-4787

Expert VHDL Training for Hardware Design and Verification
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

[Mike Treseler]

vax3900 wrote:

I am designing a state machine that will be fit into a CPLD (Xilinx XC95xx).
The state machine needs to wait certain number of clocks here and there (
for example, 80 clocks here, and 160 clocks there ). If I design
everything with hand, I would choose structured state machine; that is, a
state machine plus a counter. But since I am using VHDL, and the compiler
would take care of everything, I think I might be able to make a monolithic
state machine with the counter built in ( that is, to add 80 states here,
and 160 states there ).

Consider making the counter a separate
variable. Saying n:= n + 1 in a
few places is much cleaner than
describing hundreds of extra state transitions.

I said variable because I would write
this controller in a single process.
A counter signal and multiple processes would
work fine too.

Excluding the counter, the state machine has about
100 states.

See if you can't pull out a few other
count, shifter, mode or boolean variables to reduce
the number of states and clarify
the logic description.

My question is, which approach is better, for a CPLD? The monolithic design
will require less FF's, maybe.

Maybe, maybe not.
To answer the utilization question, you would have
to try it both ways and see. I would expect
little difference.

I have found that a clean description is a likely to
fit as any other.

-- Mike Treseler

 

[Brian Drummond]

On 10 May 2004 16:13:55 -0700, mike_treseler@comcast.net (Mike Treseler)
wrote:

vax3900 wrote:

I am designing a state machine that will be fit into a CPLD (Xilinx XC95xx).
The state machine needs to wait certain number of clocks here and there (
for example, 80 clocks here, and 160 clocks there ). If I design
everything with hand, I would choose structured state machine; that is, a
state machine plus a counter. But since I am using VHDL, and the compiler
would take care of everything, I think I might be able to make a monolithic
state machine with the counter built in ( that is, to add 80 states here,
and 160 states there ).

Consider making the counter a separate
variable. Saying n:= n + 1 in a
few places is much cleaner than
describing hundreds of extra state transitions.

You need only say n:= n + 1 (I tend to use n - 1) in one place, as the
default action in the state machine process. On entering states where
you need a delay, this is over-ridden with n := delay_length. Then n=0
is simply one of the conditions for leaving the state.

If you use a signal for n, you can use an external "n_eq_z <= '1' when n
= 0 else '0';" or some such to help the synthesiser avoid replicating
the zero detection logic, but I would hope not nowadays!

- Brian

 

[Hal Murray]

The key thing is that we both agree that be it an ASIC,
FPGA, or CPLD, code arithmetic resources (counters)
separately from the statemachines.

There is one case where that might not hold. Consider
a ROM based state machine. If you have lots of unused
states maybe you don't need a counter.

--
The suespammers.org mail server is located in California. So are all my
other mailboxes. Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's. I hate spam.