Large scale finite state machines

1. A computer implemented method of determining finite state machines, comprising:

accessing, via a computer system, a dataflow graph that represents an expression, wherein each variable and operator in the expression is represented by a node in the dataflow graph;

performing a cost analysis of computing sub-expressions of the expression corresponding to subsets of the dataflow graph;

determining probabilities that ones of the sub-expressions evaluates as true based on input values to respective ones of the sub-expressions;

splitting the dataflow graph into a plurality of dataflow graphs based on the respective cost for each of the sub-expressions and the probabilities that ones of the sub-expressions evaluates as true; and

determining a plurality of finite state machines corresponding to said plurality of dataflow graphs.

2. The method of claim 1 , further comprising:

combining said plurality of finite state machines during a simulation by using an output of a first of said plurality of finite state machines as an input to a second of said plurality of finite state machines.

3. The method of claim 1 , wherein said performing comprises determining whether a cost of calculating a finite state machine for a subset of the dataflow graph is greater than a threshold value.

4. The method of claim 3 , wherein said threshold value is a pre-determined value.

5. The method of claim 3 , wherein said threshold value is input from a user.

6. The method of claim 3 , wherein said threshold value is adjustable.

7. The method of claim 1 , wherein said performing comprises:

determining a number of input values that are possible for each input node of the dataflow graph;

determining a number of possible combinations of said input values that exist for each of said sub-expressions;

determining a number of possible output values that exist for each of said sub-expressions; and

determining a cost for each of the sub-expressions based on the possible combinations of the input values and the output values.

8. The method of claim 1 , wherein said splitting the dataflow graph into a plurality of dataflow graphs based on the respective cost for each of the sub-expressions and the probabilities that ones of the sub-expressions will be true comprises determining whether a probability that one of the sub-expressions evaluates as true is below a threshold percentage.

9. The method of claim 1 , further comprising collapsing multiple states to a single state in ones of said finite state machines by merging states that transition to a common state and for which inputs and outputs are identical.

10. The method of claim 9 , further comprising traversing said ones of said finite state machines from end to start to collapse additional states.

11. A system comprising a processor and a computer readable medium coupled to a bus, wherein said computer readable medium has stored thereon instructions that when executed on said processor implement a method for determining finite state machines for a dataflow graph, said method comprising:

accessing a dataflow graph that represents an expression, wherein each variable and operator in the expression is represented by a node in the dataflow graph;

performing a cost analysis of computing sub-expressions of the expression corresponding to subsets of the dataflow graph;

determining probabilities that ones of the sub-expressions evaluates as true based on input values to respective ones of the sub-expressions;

splitting the dataflow graph into a plurality of dataflow graphs based on the respective cost for each of the sub-expressions and the probabilities that ones of the sub-expressions evaluates as true; and

determining a plurality of finite state machines corresponding to said plurality of dataflow graphs.

12. The system of claim 11 , wherein said method further comprises:

combining said plurality of finite state machines during a simulation by using an output of a first of said plurality of finite state machines as an input to a second of said plurality of finite state machines.

13. The system of claim 11 , wherein said performing comprises determining whether a cost of calculating a finite state machine for a subset of the dataflow graph is greater than a threshold value.

14. The system of claim 13 , wherein said threshold value is a pre-determined value.

15. The system of claim 13 , wherein said threshold value is input from a user.

16. The system of claim 13 , wherein said threshold value is adjustable.

17. The system of claim 11 , wherein said b) of said method comprises:

determining a number of input values that are possible for each input node of the dataflow graph;

determining a number of possible combinations of said input values that exist for each of said sub-expressions;

determining a number of possible output values that exist for each of said sub-expressions; and

determining a cost for each of the sub-expressions based on the possible combinations of the input values and the output values.

18. The system of claim 11 , wherein said splitting the dataflow graph into a plurality of dataflow graphs based on the cost for each of the sub-expressions and the probabilities that ones of the sub-expressions will be true comprises determining whether a probability that one of the sub-expressions will be true is below a threshold percentage.

19. The system of claim 11 , wherein said method further comprises collapsing multiple states to a single state in ones of said finite state machines of said method by merging states that transition to a common state and for which inputs and outputs are identical.

20. The system of claim 19 , wherein said method further comprises traversing said ones of said finite state machines from end to start to collapse additional states.