초록 ▼

Large-scale finite state machines. An implementation is a method of splitting FSMs in which a dataflow graph is accessed that represents an expression. A cost analysis of computing sub-expressions of the expression corresponding to subsets of the dataflow graph is performed. Based on the cost analys

Large-scale finite state machines. An implementation is a method of splitting FSMs in which a dataflow graph is accessed that represents an expression. A cost analysis of computing sub-expressions of the expression corresponding to subsets of the dataflow graph is performed. Based on the cost analysis, the dataflow graph is split into separate dataflow graphs. A finite state machine is determined for each of the dataflow graphs.

대표청구항 ▼

What is claimed is: 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

What is claimed is: 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.