Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-03-09
2002-07-16
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C717S152000
Reexamination Certificate
active
06421815
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the optimization of finite state machines (FSMs) synthesized from hierarchical high-level descriptions. More specifically, the present invention relates to determining partitions of a hierarchical high-level description which will lead to greater optimization when synthesized into an FSM.
BACKGROUND OF THE INVENTION
To tackle the exponential growth in the complexity of digital circuits, designers are moving to higher levels of abstraction in the design process. In control dominated applications, several abstractions are popular for managing the complexity of the design of sequential control logic. These techniques use an input language whose level of abstraction is above explicit FSM (finite state machine) design techniques that use state transition tables or RTL (register transfer level) HDL (hardware description language) descriptions.
In these abstractions, the high-level controller description is typically described in a hierarchical fashion as depicted by the tree in FIG.
1
. The nodes of the tree, which are stored in the memory of a data processing system, represent the compositional operators of the control abstraction. For example, a particular node might indicate the sequencing or the concurrent execution of the sub-behaviors represented by the node's children (or sub-nodes).
Synthesis of circuits from these hierarchical high-level abstractions involves the translation of the high-level controller description into an initial FSM (FIG.
1
). Typically, the synthesis is performed as an initial translation step (in which a high-level description
100
is translated into an unoptimized FSM
101
) followed by optimization steps (which transform FSM
101
into optimized FSM
102
). High-level description
100
is hierarchical in the sense that it has a top-level node
100
, with child nodes
105
and
104
. This hierarchical organization follows, recursively, for each of the child nodes. Initial FSM
101
comprises, in a general sense, functional logic
106
and register bits
107
, wherein all register bits
107
receive the same clock signal. Optimized FSM
102
comprises functional logic
108
and register bits
109
. Functional logic
108
is simpler than functional logic
106
and/or register
109
has fewer bits than register
107
. Both FSMs
101
and
102
provide the same functionality with respect to the primary inputs and outputs of the FSM.
The translation ensures correct implementation of the high-level semantics into an FSM, and the subsequent optimizations aim to reduce the cost of the implementation while preserving the observable sequential behavior. In conventional systems, the optimizations are performed without any additional guidance from the structure of the high-level description.
For example, classical FSM optimization techniques include state minimization, state assignment, state encoding and sequential circuit level optimizations such as retiming. This separation of the translation and optimization phases leads to the loss of information about the high-level description that is useful for optimization.
Other known methods for optimizing FSMs generated from high-level descriptions use the structure of the high-level representation to determine an over-approximate reachable state set, but do not use the structure of the high-level language directly in the optimization strategy. Some known techniques do in fact use the structure of the input description, however, information about the global reachability and observability is unknown, thus the optimizations are generally local in scope.
It would therefore be desireable to have a method for automatically optimizing FSMs synthesized from high-level descriptions which uses the structure of the high-level description in conjunction with global reachability information in order to select sub-FSMs for optimization which achieve circuits that are more highly optimized.
It would further be desireable to have a method which achieves greater optimization of sub-FSMs by using global reachability information while optimizing a selected sub-FSM.
SUMMARY OF THE INVENTION
In circuit synthesis software in accordance with a preferred embodiment of the present invention, finite state machines (FSMs) are translated from hierarchical high-level descriptions and optimized. Optimization involves partitioning. With respect to the hierarchical high-level description a partition is the subtree defined by a selected node. With respect to the translated FSM, a partition is a subset of the next state functions, a subset of the output functions and a subset of the state variables corresponding to the selected subset of functions. 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, the software selects certain partitions for optimization. Optimization of a partition can include the steps of converting the partition to a state graph, state graph minimization, state assignment (also known as re-encoding) and conversion back to an FSM. Any hierarchical high-level language is suitable for use with 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.
In general, the invention comprises the following method, the steps of which are performed by a data processing system: scanning at least one node of a hierarchical description of a finite state machine; assigning, for each node of the hierarchical description scanned, a metric determined from a reachability function of the finite state machine; and selecting, according to the metric, certain nodes of the hierarchical description as defining a partition of the finite state machine for optimization.
The invention also comprises the following method, the steps of which are performed by a data processing system: generating at least one state or state transition of a state graph from a finite state machine; and determining whether the state or state transition is valid from the reachability function of the finite state machine.
Furthermore, the invention comprises the following method, the steps of which are performed by a data processing system: assigning a property to an input description; translating the input description into a first finite state machine, wherein the first finite state machine comprises at least a second finite state machine; generating at least one state or state transition of a state graph from the second finite state machine; and determining whether the state or state transition is valid from the property of the input description.
REFERENCES:
patent: 5140526 (1992-08-01), McDermith et al.
patent: 5469367 (1995-11-01), Puri et al.
patent: 5513122 (1996-04-01), Cheng et al.
patent: 5537580 (1996-07-01), Giomi et al.
patent: 5539680 (1996-07-01), Palnitkar et al.
patent: 5680332 (1997-10-01), Raimi et al.
patent: 5774370 (1998-06-01), Giomi
patent: 5920711 (1999-07-01), Seawright et al.
patent: 6035109 (2000-03-01), Ashar et al.
Gerard Berry and Georges Gonthier, “the Esterel synchronous programming language: design, semantics, implementation”, in Science of Computer Programming, vol. 19 (No. 2), pp. 87-152, Nov. 1992.
Olivier Coudert, Christian Berthet and Jean Christophe Madre, “Verification of Synchronous Sequential Machines Based on Symbolic Execution”, in Automatic Verification Methods for Finite State Systems, International Workshop, Grenoble France, vol. 407, Lecture Notes in Computer Science, Springer Verlag, pp. 365-373, Jun. 1989.
Andrew Crews and Forrest Brewer, “Controller Optimization for Protocol Intensive Applicatio
Howrey Simon Arnold & White , LLP
Kaplan Jonathan T.
Smith Matthew
Synopsys Inc.
Thompson A. M.
LandOfFree
Method and apparatus for optimized partitioning of finite... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for optimized partitioning of finite..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for optimized partitioning of finite... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2879073