Method and apparatus for optimized partitioning of finite state machines synthesized from hierarchical high-level descriptions

摘要

Finite state machines (FSMs) are synthesized from hierarchical high-level descriptions and optimized. Partitions of the FSM are selected by scanning the nodes of the hierarchical description and assigning to each suitable node a metric based upon the reachability function of the FSM. The metric is an indicator of the desirability of using the partition of the FSM, corresponding to the node, as a region of the FSM upon which to apply FSM optimization techniques. Based upon the metric, certain partitions are selected for optimization. Optimization of a partition can include the steps of converting the partition to a state graph, state graph minimization and conversion back to an FSM. Any hierarchical high-level language is suitable for the present invention, provided that a correspondence between nodes of the high-level description and partitions of the FSM can be determined. Conversion of an FSM partition for the purposes of optimization is performed with pruning functions also derived from the FSM's reachability function.