State Machines....

S

stan

Guest
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are $5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan
 
The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time
Click to expand...
I think you do need to find another job with a better manager! An error in
scheduling made by an engineer doesn't deserve a pay cut. If anyone deserves
a pay cut, it's a manager who didn't know a basic management rule: take an
engineer's estimate, multiply it by 2 and then use the next available unit
:) If he knew the rule he would celebrate the work finished way faster than
expected!


/Mikhail
 
"stan" <stanandsue2000@yahooREMOVE.com> wrote in message
news:3fbb8795.3574357@news.compuserve.com...

[...]
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.
Click to expand...
I don't know of any really free tools, but isn't there
still a state chart editor in the Xilinx tools? However...

Obviously I don't know the insides of your application, but
100-200 states sounds like a real behemoth. Isn't there
some way you could partition it and make it hierarchical?
Alternatively, it might make sense to think in terms of
a microcoded solution - a custom state sequencer engine,
and a little ROM containing the sequence information.

Way back in the bad old days of the late 80s there was
a nifty little thing from AMD called the 29PL141 that
would probably have helped. One of my "must do one of
these fine days" jobs is to write an HDL implementation
of that - I still have all the original AMD docs on
one of my bookshelves at home.

Anyhow, here's my main point: state diagrams are supposed
to be clear and self-evident; if they're too big to be clear
and self-evident, then perhaps they are the wrong tool for the
problem at hand. Similarly, if you have a state diagram of
modest size, converting it into VHDL or Verilog is pretty
much a no-brainer.

Now, if you managed to get this leviathan to work first
time, you obviously know what you're doing and I'm sure
you thought of these things for yourself. So, can you
offer a clue about *why* your state machines needed to
be so huge? and *why* you couldn't make them hierarchical?
It would be very interesting to hear your experiences.

Cheers
--
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, Hampshire, 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.
 
On Wed, 19 Nov 2003 15:33:46 GMT, stanandsue2000@yahooREMOVE.com
(stan) wrote:

<<good state machine story snipped>>

I've tried Statecad, which I believe is the progenitor of today's
Xilinx state machine graphical entry tool. Rather than saving me
time, the tool made me guess as to just what I'd have to do to get
what I wanted in hardware. Maybe if you spent more time at it than I
did it'd be worth it, but I find it easier to design in Verilog. The
fewer tools between you and the hardware, the better.

I'd have to agree with others who said that you probably should have
given more thought to decomposing your FSMs into smaller ones. This
is more art than science, and I don't know of any good references that
explain how to do this; most people learn from someone else, or from
experiences such as yours, after which they vow, "No more huge state
machines."

You're to be congratulated on doing a thorough enough job on design
that debug went smoothly. Perhaps you deserve a better manager.

Bob Perlman
Cambrian Design Works
 
stan wrote:
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are $5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan
Click to expand...
My first rules, when describing a complex fsm, is to try to minimize the
number of signal generated by one fsm, and to write many concurrent fsm.

One process for one generated signal, and multiply the process.

Normal fsm construction can have two or three process. Then for one fsm
do not generate more than 3-5 signals (or vector).

If you have to generate 100 signals, I will write 20 concurrent fsm.

Laurent
www.amontec.com
 
stan wrote:
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are $5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan
Click to expand...
My first rules, when describing a complex fsm, is to try to minimize the
number of signal generated by one fsm, and to write many concurrent fsm.

One process for one generated signal, and multiply the process.

Normal fsm construction can have two or three process. Then for one fsm
do not generate more than 3-5 signals (or vector).

If you have to generate 100 signals, I will write 20 concurrent fsm.

Laurent
www.amontec.com
 
Stan -

I agree with Jonathan that 200 states is nuts. Very error prone and
probably very difficult to maintain/modify. Were you parsing the
incoming data stream and making state decisions based on that? If so, a
programmable communications processor or an embedded processor (like
Nios for Altera) is a much better and more flexible choice. Some tasks
just aren't meant to be done in hardware, and parsing data streams is
one of them.

Nice reward for delivering a working design. I hope you find a way to
exit that situation.

Robert

"stan" <stanandsue2000@yahooREMOVE.com> wrote in message
news:3fbb8795.3574357@news.compuserve.com...
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are $5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan
Click to expand...
 
There is an April 2001 TechXclusives "Using leftover multipliers and
BlockRAMs" that describes a surprisingly simple structure for a state
machine with up to 256 states. I never got any feedback on this idea.
There is no software tool, but it's pretty straightforward, and "pencil
and paper" might suffice...
http://support.xilinx.com/xlnx/xweb/xil_tx_home.jsp

Peter Alfke, Xilinx Applications
=============================
Robert Sefton wrote:
Stan -

I agree with Jonathan that 200 states is nuts. Very error prone and
probably very difficult to maintain/modify. Were you parsing the
incoming data stream and making state decisions based on that? If so, a
programmable communications processor or an embedded processor (like
Nios for Altera) is a much better and more flexible choice. Some tasks
just aren't meant to be done in hardware, and parsing data streams is
one of them.

Nice reward for delivering a working design. I hope you find a way to
exit that situation.

Robert

"stan" <stanandsue2000@yahooREMOVE.com> wrote in message
news:3fbb8795.3574357@news.compuserve.com...
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are $5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan
Click to expand...
 
"Peter Alfke" <peter@xilinx.com> ha scritto nel messaggio
news:3FBBB033.E8A6616A@xilinx.com...

There is an April 2001 TechXclusives "Using leftover multipliers and
BlockRAMs" that describes a surprisingly simple structure for a state
machine with up to 256 states. I never got any feedback on this idea.
There is no software tool, but it's pretty straightforward, and "pencil
and paper" might suffice...
http://support.xilinx.com/xlnx/xweb/xil_tx_home.jsp
Click to expand...
Just read the article... I like the idea, I'll try to remember the trick
next design.

Makes medium/big fsm simplicity itself: no routing issues, etc.. very
clever.
But... too much work for translating to numeric "init" format...

Why don't you try to "whisper" a bit at the ears of ISE StateCad mantainers
?

Maybe outputting INIT tables from a StateCad graph could boost the use of
this particular trick.
 
stan wrote:
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) ,
Click to expand...
Some hardware objects are not efficiently
described as a state machine.
For example, an 8 bit shift register could be
described using a single variable assignment or as a case
of 256 variable states.

Complex sequential logic is easiest for me to
describe using clocked processes with
lots of local variables.

The state machine model is a clocked process
with a single enumerated local variable or signal.
With a state editor as your design entry, this is all you can do.

With synthesis tools, you can have many
local variables of many types in a single clocked process.
You might have a local counter register and a shift register, etc.
One page of clear code replaces pages of circles and arrows.


The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job
Click to expand...
I expect that he could not really find anyone faster.
Keep honing your skills, and politely ignore the
"schedule as whip" tactic.

-- Mike Treseler
 
In article <21Qub.58264$hV.2182491@news2.tin.it>,
Antonio Pasini <NOSPAM_pasini.a@tin.it> wrote:

Makes medium/big fsm simplicity itself: no routing issues, etc.. very
clever.
But... too much work for translating to numeric "init" format...
Click to expand...
Do what I did when I had to implement the Rijndael S-boxes: Write a
small program that takes an abstract representation and dumps the init
strings. Heck, I may end up having to write one myself, if so, I'd
release it.

--
Nicholas C. Weaver nweaver@cs.berkeley.edu
 
Using RAM/ROM for a FSM is about as basic as it gets. I remember using
that method some 20 years ago about the same time fuse PLDs were
starting to appear. Back then fuse ROMs were just about this same
size.


Peter Alfke wrote:
There is an April 2001 TechXclusives "Using leftover multipliers and
BlockRAMs" that describes a surprisingly simple structure for a state
machine with up to 256 states. I never got any feedback on this idea.
There is no software tool, but it's pretty straightforward, and "pencil
and paper" might suffice...
http://support.xilinx.com/xlnx/xweb/xil_tx_home.jsp

Peter Alfke, Xilinx Applications
=============================
Robert Sefton wrote:

Stan -

I agree with Jonathan that 200 states is nuts. Very error prone and
probably very difficult to maintain/modify. Were you parsing the
incoming data stream and making state decisions based on that? If so, a
programmable communications processor or an embedded processor (like
Nios for Altera) is a much better and more flexible choice. Some tasks
just aren't meant to be done in hardware, and parsing data streams is
one of them.

Nice reward for delivering a working design. I hope you find a way to
exit that situation.

Robert

"stan" <stanandsue2000@yahooREMOVE.com> wrote in message
news:3fbb8795.3574357@news.compuserve.com...
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are $5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan
Click to expand...
--

Rick "rickman" Collins

rick.collins@XYarius.com
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX
 
I am not asking for the Nobel prize. I just wonder whether this is a
practical, compact, cheap, fast and easy way to build a state machine
inside an FPGA...
Peter Alfke
=============================
rickman wrote:
Using RAM/ROM for a FSM is about as basic as it gets. I remember using
that method some 20 years ago about the same time fuse PLDs were
starting to appear. Back then fuse ROMs were just about this same
size.

Peter Alfke wrote:

There is an April 2001 TechXclusives "Using leftover multipliers and
BlockRAMs" that describes a surprisingly simple structure for a state
machine with up to 256 states. I never got any feedback on this idea.
There is no software tool, but it's pretty straightforward, and "pencil
and paper" might suffice...
http://support.xilinx.com/xlnx/xweb/xil_tx_home.jsp

Peter Alfke, Xilinx Applications
=============================
Robert Sefton wrote:

Stan -

I agree with Jonathan that 200 states is nuts. Very error prone and
probably very difficult to maintain/modify. Were you parsing the
incoming data stream and making state decisions based on that? If so, a
programmable communications processor or an embedded processor (like
Nios for Altera) is a much better and more flexible choice. Some tasks
just aren't meant to be done in hardware, and parsing data streams is
one of them.

Nice reward for delivering a working design. I hope you find a way to
exit that situation.

Robert

"stan" <stanandsue2000@yahooREMOVE.com> wrote in message
news:3fbb8795.3574357@news.compuserve.com...
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are $5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan

--

Rick "rickman" Collins

rick.collins@XYarius.com
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX
Click to expand...
 
Hey Peter -

I think it's a great solution, especially with the large number of
outputs that can be generated. I also like the multiplier as
barrel-shifter. I designed a 32-bit barrel shifter running at 27MHz in
an XC4000 part ten years ago and it took up the whole part.

Robert

"Peter Alfke" <peter@xilinx.com> wrote in message
news:3FBBFCC8.E3A34A0D@xilinx.com...
I am not asking for the Nobel prize. I just wonder whether this is a
practical, compact, cheap, fast and easy way to build a state machine
inside an FPGA...
Peter Alfke
Click to expand...
 
=============================
rickman wrote:

Using RAM/ROM for a FSM is about as basic as it gets. I remember using
that method some 20 years ago about the same time fuse PLDs were
starting to appear. Back then fuse ROMs were just about this same
Click to expand...
Some even included registers, to make single chip state engines ...

"Peter Alfke" <peter@xilinx.com> wrote in message
news:3FBBFCC8.E3A34A0D@xilinx.com...
I am not asking for the Nobel prize. I just wonder whether this is a
practical, compact, cheap, fast and easy way to build a state machine
inside an FPGA...
paste>> > There is no software tool, but it's pretty straightforward, and
Click to expand...
"pencil
and paper" might suffice...
Click to expand...
It is a good idea, but the SW tool side could need work to help it take
off.. :)
It should be FAST, and quite tolerant of state code revisions - with good
tools,
the state table could be revised without a P&R :)

Re the OP of large state machines, some form of nested engines might be a
better idea
- 200 states is plausible, but they are not likely to have fully random
path-links, so a
simpler 'umbrella state', with waits from 'task states' could be easier to
manage...

-jg
 
Did you think my comment was a criticism? It clearly is a good way to
implement a complex or even not so complex FSM. As long as you won't
miss the block RAM I can't see anything wrong. It would be very easy to
set up a simple table of present state, next state with outputs. In
fact, any time I design a complex FSM, I do that anyway. HDL is nice,
but often a table makes the output assignments a lot more clear.



Peter Alfke wrote:
I am not asking for the Nobel prize. I just wonder whether this is a
practical, compact, cheap, fast and easy way to build a state machine
inside an FPGA...
Peter Alfke
=============================
rickman wrote:

Using RAM/ROM for a FSM is about as basic as it gets. I remember using
that method some 20 years ago about the same time fuse PLDs were
starting to appear. Back then fuse ROMs were just about this same
size.

Peter Alfke wrote:

There is an April 2001 TechXclusives "Using leftover multipliers and
BlockRAMs" that describes a surprisingly simple structure for a state
machine with up to 256 states. I never got any feedback on this idea.
There is no software tool, but it's pretty straightforward, and "pencil
and paper" might suffice...
http://support.xilinx.com/xlnx/xweb/xil_tx_home.jsp

Peter Alfke, Xilinx Applications
=============================
Robert Sefton wrote:

Stan -

I agree with Jonathan that 200 states is nuts. Very error prone and
probably very difficult to maintain/modify. Were you parsing the
incoming data stream and making state decisions based on that? If so, a
programmable communications processor or an embedded processor (like
Nios for Altera) is a much better and more flexible choice. Some tasks
just aren't meant to be done in hardware, and parsing data streams is
one of them.

Nice reward for delivering a working design. I hope you find a way to
exit that situation.

Robert

"stan" <stanandsue2000@yahooREMOVE.com> wrote in message
news:3fbb8795.3574357@news.compuserve.com...
hi ... I have a question for the experts , I am doing a post mortem of
my last project , it was a communication processor that was basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out the
control and drawing the state diagrams and then coding them into VHDL
for Quartus and into a Stratix .. it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a while.
Yes I know some say start right with typing VHDL but I find that hard
to comceptualize. Since this is a small company big $$ tools are out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are $5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan

--

Rick "rickman" Collins

rick.collins@XYarius.com
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX
Click to expand...
--

Rick "rickman" Collins

rick.collins@XYarius.com
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX
 
I am not asking for the Nobel prize. I just wonder whether this is a
practical, compact, cheap, fast and easy way to build a state machine
inside an FPGA...
Click to expand...
I think it's a great idea. But I'm probably biased because I
learned hardware back in the days when people built that sort
of state machine out of real ROMs and various gates and I think
writing that type of firmware is fun.

(Registered ROMs were a big advance - they saved a whole chip.)

I think the main advantage of this approach is that it changes
a hardware problem (state machine) into a software problem
(microcode). At some level of complexity (number of states
or instructions) it just seems easier to think about the
problem as software.

Your idea would probably get used a lot more if there was
an example all worked out. In particular, you need an assembler
so that other people can use it as a skeleton. And as others
have mentioned, you need an example that shows how the microcode
gets through the tool chain and merged into the FPGA bit stream.

What's a good toy example? Can we think of something semi-useful
(toy) that would run on a demo board? It would need 50-100 states.
I might be willing to hack together some software if somebody would
do the rest of the work.

Has anybody considered using LUT sized ROMs for state machines?
It doesn't seem likely to be practical but might make an interesing
exercise. The classic traffic light controller or vending machine
might fit.

--
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.
 
If you have an FPGA with lots of RAM, doing it in microcode is surely
feasable.

256 states
3 possible next states for each state (8 additional bits per "possible new
state").
100 outputs (will have 4 additional bits so 104 outputs is OK)

256 * (104 + (3 * 8)) = 256 * 128 = 32768 bits or 4 KB.

If there is not extremely high clock frequencies, you can build the state
machine
using deeper SRAMs.

512 * 64 @ 2 clocks per state machine update
1024 * 32 @ 4 clocks per state machine update
2048 * 16 @ 8 clocks per state machine update
4096 * 8 @16 clocks per state machine update

The update will read the SRAM to a shadow register, one slice at the time
and will update the outputs simultaneously during the last clock.
The next state is determined from the inputs which will select
one of the three possible "next" states (S1,S2,S3) by controlling a 3->1
multiplexer.
The output of the multiplexer can be written to the "state" register.
If you want to stay in the same state, then you do not write to the state
register.

You can reduce the number of inputs you react to by having additional output
bits in the RAM which controls input multiplexers.
You need to figure out the maximum number of inputs any state will react to
and create that many input multiplexers.

The outputs of those muxes, and the "current" state
can then be used as an address a second 4 bit SRAM.
The output is used to select the next state (Keep,S1,S2,S3).

Lots of SRAM and very little Logic.
Would work with an 5 k gate FPSLIC...


--
Best Regards
Ulf at atmel dot com
These comments are intended to be my own opinion and they
may, or may not be shared by my employer, Atmel Sweden.

"Peter Alfke" <peter@xilinx.com> wrote in message
news:3FBBFCC8.E3A34A0D@xilinx.com...
I am not asking for the Nobel prize. I just wonder whether this is a
practical, compact, cheap, fast and easy way to build a state machine
inside an FPGA...
Peter Alfke
=============================
rickman wrote:

Using RAM/ROM for a FSM is about as basic as it gets. I remember using
that method some 20 years ago about the same time fuse PLDs were
starting to appear. Back then fuse ROMs were just about this same
size.

Peter Alfke wrote:

There is an April 2001 TechXclusives "Using leftover multipliers and
BlockRAMs" that describes a surprisingly simple structure for a state
machine with up to 256 states. I never got any feedback on this idea.
There is no software tool, but it's pretty straightforward, and
"pencil
and paper" might suffice...
http://support.xilinx.com/xlnx/xweb/xil_tx_home.jsp

Peter Alfke, Xilinx Applications
=============================
Robert Sefton wrote:

Stan -

I agree with Jonathan that 200 states is nuts. Very error prone and
probably very difficult to maintain/modify. Were you parsing the
incoming data stream and making state decisions based on that? If
so, a
programmable communications processor or an embedded processor (like
Nios for Altera) is a much better and more flexible choice. Some
tasks
just aren't meant to be done in hardware, and parsing data streams
is
one of them.

Nice reward for delivering a working design. I hope you find a way
to
exit that situation.

Robert

"stan" <stanandsue2000@yahooREMOVE.com> wrote in message
news:3fbb8795.3574357@news.compuserve.com...
hi ... I have a question for the experts , I am doing a post
mortem of
my last project , it was a communication processor that was
basicly a
lot of dataflow paths controlled by several rather complex state
machines ( 100-200 states ) , I did the design by thinking out
the
control and drawing the state diagrams and then coding them into
VHDL
for Quartus and into a Stratix .. it worked , after handing over
the
design to the test department they loaded a board and signed off
on
the design within a week. My fellow engineers were rather
impressed
since they knew how complex the control was.

The downside here was the state machines became complex and took
quite
a while to figure out ... then transcibing them into VHDL and also
drawing a pretty state chart for documenting the design took a
while.
Yes I know some say start right with typing VHDL but I find that
hard
to comceptualize. Since this is a small company big $$ tools are
out
of the question.

So my question ... are there tools out there that can make this
process faster ? like drawing the state charts on the screen and
outputing VHDL ? or other suggestions ??? again if these are
$5-10K
tools I won't be getting them in this company so shareware or <$1K
tools are preferred even if they lack in some areas.

The bigger downside here is that since the state machines took
longer
than I expected ( I scheduled 3 weeks of design, project took 6
weeks
) my manager has warned me to find another job ( fat chance ) as
he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

thanks for any constructive feedback , stan

--

Rick "rickman" Collins

rick.collins@XYarius.com
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX
Click to expand...
 
Hal Murray wrote:
[...]
Your idea would probably get used a lot more if there was
an example all worked out. In particular, you need an assembler
so that other people can use it as a skeleton. And as others
have mentioned, you need an example that shows how the microcode
gets through the tool chain and merged into the FPGA bit stream.

What's a good toy example? Can we think of something semi-useful
(toy) that would run on a demo board? It would need 50-100 states.
I might be willing to hack together some software if somebody would
do the rest of the work.
Click to expand...
How about something better than just a toy, but nearly as easy to
describe? Something that could be donated to opencores and would
actually be reused would surely be more worth someones time (while still
useful to students and/or others wanting to see a real world example of
this). I'd be interesting in helping on a project like that.

Here is my idea that takes up a non-trivial amount of space in an FPGA:

Ethernet (especially GbE) has the ability to send PAUSE frames (I'll
just call them packets since that is what many call them). While a
device is receiving one of these packets, it must verify that it is
valid (say 16 bits at a time, for 64 bytes, including CRC). Once
verified, it outputs a hold signal for the amount of time specified in
the PAUSE packet. The hold signal can be used to stop transmitting data
in the opposite direction.

This is a simple state machine and could easily be put into BRAM(s),
using the BRAM to compare and validate each 16 bit word. There are
actually two different packets that are valid to receive (they differ
only in the first six bytes), hence there there are two valid states for
the first couple words, after which they will recombine to a single
valid state thereafter.

Now imagine this for a multi-port system. 24 ports aren't uncommon on
systems anymore, and you'd need a state machine for each port (or one
larger [and much faster] one that does context switches) to verify the
reception of the packets (possibly simultaneously).

You also need a "multi-port" timer that signals when it is ok to start
transmitting data again. Having 24 stand-alone timers seems like quite
a waste (although they can be quite slow since the unit of measure of
the "pause time" field is 409.6 ns at GbE rates).

Has anybody considered using LUT sized ROMs for state machines?
It doesn't seem likely to be practical but might make an interesing
exercise. The classic traffic light controller or vending machine
might fit.
Click to expand...
I'm not sure why it wouldn't be practical, except that the amount of
resources saved (a couple LUTS) may not be worth the effort involved
(unless there was a program that just spit out the LUT contents for you,
as you have been discussing).

Marc
 
MM <mbmsv@yahoo.com> wrote in message
news:bpg3er$1neeon$1@ID-204311.news.uni-berlin.de...
The bigger downside here is that since the state machines took longer
than I expected ( I scheduled 3 weeks of design, project took 6 weeks
) my manager has warned me to find another job ( fat chance ) as he
has handed in a review requesting a 20% pay cut ... but my real
question is about the tools so I may do better next time

I think you do need to find another job with a better manager! An error in
scheduling made by an engineer doesn't deserve a pay cut. If anyone
deserves
a pay cut, it's a manager who didn't know a basic management rule: take an
engineer's estimate, multiply it by 2 and then use the next available unit
:) If he knew the rule he would celebrate the work finished way faster
than
expected!
Click to expand...
Especially bearing this in mind...

"it worked , after handing over the
design to the test department they loaded a board and signed off on
the design within a week. My fellow engineers were rather impressed
since they knew how complex the control was"

This would seem to demonstrate that careful up front design
saved time in test and verification. I'd point that out to
your 'manager' and his boss before telling him where to shove his
job (after you've found something better).


Nial

------------------------------------------------
Nial Stewart Developments Ltd
FPGA and High Speed Digital Design
www.nialstewartdevelopments.co.uk
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top