cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 
nyashwanth
Visitor
Visitor
8,062 Views
Registered: ‎11-03-2009

Number of states in FSM

I am trying to synthesis an FSM using Xilinx ISE Release 10.1.03 Application Version K.39 on Virtex 5 LX155T device. The number of the states in the FSM is 175 and the synthesis tool is reporting that it is unable to synthesize the design. Is there any limit on the number of states which can be used in a FSM?
0 Kudos
11 Replies
tembridis.com
Explorer
Explorer
8,056 Views
Registered: ‎07-14-2008

Hm, could you be more specific? What kind of FSM encoding have you selected and at what frequency are you running that FSM? 175 states sound alot for one single FSM.
0 Kudos
bassman59
Historian
Historian
8,046 Views
Registered: ‎02-25-2008


nyashwanth wrote:
I am trying to synthesis an FSM using Xilinx ISE Release 10.1.03 Application Version K.39 on Virtex 5 LX155T device. The number of the states in the FSM is 175 and the synthesis tool is reporting that it is unable to synthesize the design. Is there any limit on the number of states which can be used in a FSM?

The limit is determined by the resources available in your target FPGA.

 

175 states sounds unmaintainable. Are you sure that your machine needs this many states? 

----------------------------Yes, I do this for a living.
0 Kudos
nyashwanth
Visitor
Visitor
7,971 Views
Registered: ‎11-03-2009

I have succesfully synthesized some other module which had a FSM having 95 states along with some other logic within 150 slices on Virtex 5 LX155T. I dont see any reason why it cant synthesize 175 states if it can fit in 95 states. Is this some problem related to synthesis tool in terms of system memory it requires in order to synthesize larger FSMs.

0 Kudos
tembridis.com
Explorer
Explorer
7,941 Views
Registered: ‎07-14-2008

Like bassman said, it might be unmaintainable in terms of resources on the fpga. Of course that depends on things like the desired frequency and what kind of FSM encoding you chose. For example, with one-hot encoding you end up having a 175 bit deep state register. You may run into timing problems with that.

 

But out of curiousity, why would you need that many states?

0 Kudos
nyashwanth
Visitor
Visitor
7,924 Views
Registered: ‎11-03-2009


I ended up with a FSM with a large number of states to achieve some particular requirements. I will try to give brief description of what I am trying to do. 

 

The FSM needs to control some data processing and incoming data is of 4 to 5 varieties and depending on the type of data a particular process needs to be followed. In the first state depending on the type of data a 'sub- FSM' is started. Initially these sub-FSMs had a very few states a lot of logic resided in every state of the FSM and I did not have a fine cycle level control over the data processing and also because of lot of logic sitting in every state the timing was not very good. 

 

http://picasaweb.google.com/lh/photo/ZHr8mdIKPv5EsPiuxA0ovQ?feat=directlink

 

I removed almost all the logic inside each state of the FSM and most of the states in the FSM look like this -

 

...

 

STATE_1:

begin

    signal_a = 1'b1;

    signal_b = 1'b1;

    nxt_state = STATE_2;

end

 

STATE_2:

begin

   signal_b = 1'b1;

   signal_c = 1'b1;

   nxt_state = STATE_3;

end

 

.....

 

As a result of this change in implementation i am able to achieve good timing as there is hardly any logic in the states of the FSM and number of states in the FSM increased considerably. I am able synthesize FSM with number of states upto 125 comfortably now, but it did not work when i tried an FSM with 175 states.

 

 

0 Kudos
tembridis.com
Explorer
Explorer
7,921 Views
Registered: ‎07-14-2008

Good morning. Well, to remove logic from within FSM state scope is always a recommendable effort.

 

Have you considered to split your FSM apart into several trully separated FSM with one main FSM controlling them? Like for example, main FSM determines the type of data processing necessary and then starts/enables the respective sub-FSM. That way you could keep each FSM's state in a seperate state register, thus reducing size.

 

Also, what type of state encoding did you choose in your project synthesis options?

0 Kudos
nyashwanth
Visitor
Visitor
7,917 Views
Registered: ‎11-03-2009

Initially i had thought of having multiple FSM having smaller number of states but all these FSMs need to control the same data path, for example if there are 3 FSMs and each of them are generating a output_valid signal, there will be three such signals, output_valid_fsm1, output_valid_fsm2, output_valid_fsm3 and my final output_valid will become

 

assign output_valid = output_valid_fsm1 || output_valid_fsm2 || output_valid_fsm3;

 

and I have few more such signals. So i thought this approach may not be a good one.

 

FSM encoding option is set to 'Auto', i have observed that when the number of states are small the tool uses one-hot and if the number of states are more it uses some other method not sure exactly which one.

 

 

 

 

 

 

0 Kudos
tembridis.com
Explorer
Explorer
7,914 Views
Registered: ‎07-14-2008

I see. Seems like it is going to be a trade-off then. Though you are better off with a few big multixplers than having one big FSM that fails.
0 Kudos
bassman59
Historian
Historian
7,908 Views
Registered: ‎02-25-2008


nyashwanth wrote:

Initially i had thought of having multiple FSM having smaller number of states but all these FSMs need to control the same data path, for example if there are 3 FSMs and each of them are generating a output_valid signal, there will be three such signals, output_valid_fsm1, output_valid_fsm2, output_valid_fsm3 and my final output_valid will become

 

assign output_valid = output_valid_fsm1 || output_valid_fsm2 || output_valid_fsm3;

 

and I have few more such signals. So i thought this approach may not be a good one.

 

FSM encoding option is set to 'Auto', i have observed that when the number of states are small the tool uses one-hot and if the number of states are more it uses some other method not sure exactly which one.

 

Just a thought -- whenever I have considered doing such a large state machine, I look for an alternate solution. Perhaps something like a PicoBlaze processor makes more sense?

----------------------------Yes, I do this for a living.
0 Kudos
nyashwanth
Visitor
Visitor
3,489 Views
Registered: ‎11-03-2009

bassman59,

 

Can you elaborate a little more on how can Picoblaze can be used to solve my problem??

0 Kudos
bassman59
Historian
Historian
3,478 Views
Registered: ‎02-25-2008


nyashwanth wrote:

bassman59,

 

Can you elaborate a little more on how can Picoblaze can be used to solve my problem??


Well, depending on the problem -- which we don't know -- a sequential processor might just be a better option. You can easily set up loops with counters, and of course it can respond to external inputs.

 

You just have to look at the problem from a different angle.

----------------------------Yes, I do this for a living.
0 Kudos