Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-04-06
2001-11-20
Phan, Trong (Department: 2818)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06321362
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer-aided design of digital electronic circuits, and more particularly relates to a method of reformulating static circuit optimization problems in order to reduce size, degeneracy, and/or redundancy.
2. Brief Description of the Prior Art
As digital electronic circuits increase in size and complexity, automatic optimization of performance-critical designs increases in importance. Such automatic optimization can lead to better circuits and enhanced productivity. Static circuit optimization implies the determination of optimal transistor and wire sizes, on a static timing basis, while simultaneously taking into account all paths through the logic. The advantages of static optimization include increased designer productivity, since an optimal circuit is automatically determined; higher quality circuits, that is, faster, smaller, and/or lower power consumption; and the fact that all paths through the logic are simultaneously considered.
Reference should be had to
FIG. 1
, which depicts the flow of a typical prior art circuit optimization method. As shown at Block
102
, a description of the circuit (or netlist) which is to be optimized can initially be prepared. “Netlist” is a generic term for a file containing a description of a circuit. The circuit description can then be read, as in Block
104
, and a timing graph can be created based on the circuit description which has been read, as shown in Block
106
. Timing constraints can then be formulated which correspond to the circuit description, as shown at Block
108
, and then additional constraints and objective functions can be added as necessary, per Block
109
. Finally, the circuit can be optimized as per Block
110
.
Block
106
is optional, as a timing graph need not always be created, instead, the timing constraints associated with the problem statement can be formulated directly. In this case, the constraints formulated in Block
108
will correspond to the problem statement. When a timing graph is employed, per Block
106
, Block
108
can include formulating constraints which correspond to the timing graph. Any additional constraints and objective functions which are necessary can be added per Block
109
, as above.
One exemplary method of static circuit optimization is disclosed in U.S. patent application Ser. No. 950,782 of Strenski, filed Oct. 15, 1997, the disclosure of which is expressly incorporated herein by reference. Although the Strenski method is advantageous, and achieves the benefits set forth above, there are still problems with the Strenski method, and indeed, with all known prior art methods of circuit optimization. Chief among these is computational complexity. Large digital circuits, with many components, can result in extremely complex optimization problems which may require many hours of CPU time to solve. Accordingly, it would be highly desirable to improve prior art methods.
Further, in prior art methods, the formulation of the optimization problem suffers from numerical disadvantages such as redundancy and degeneracy. In a degenerate case, a LaGrange multiplier associated with an active constraint is zero. In a redundant case, removal of a constraint without any other manipulation doesn't change the problem. All active redundant constraints give rise to a degenerate problem. However, there are degenerate problems without redundant constraints. From an optimization perspective, these types of problems often have multiple equivalent solutions and are relatively difficult to solve.
In view of the foregoing, there is a need in the prior art for a method of reformulating static optimization problems for digital circuits which can reduce the size of problem, as well as potentially reducing degeneracy and redundancy.
SUMMARY OF THE INVENTION
The present invention, which addresses the needs identified in the prior art, provides a method of pruning an initial timing graph for static optimization of a digital circuit. The method is employed when a timing graph is constructed for the digital circuit which it is desired to optimize. The timing graph has a plurality of nodes corresponding to arrival times of signals in the digital circuit, and also has a plurality of directed edges corresponding to propagate segments in the digital circuit. Those of the edges which are directed into a given node are referred to as fan-ins for that node, and are connected to associated fan-in nodes. Similarly, those of the edges which are directed out of a given node are referred to as fan-outs for that node and are connected to associated fan-out nodes. The method includes the steps of examining a first group of the nodes; pruning the first group of nodes; and repeating the examining and pruning steps for a substantial number of additional groups of nodes. More specifically, in the examining step, the first group of nodes includes at least a first one of the nodes in the initial timing graph, and the examination is conducted in order to determine whether every node of the first group is prunable. In the pruning step, the pruning of the first group is conducted by pruning every node in the first group, if every node of the first group is indeed prunable, and if the pruning would be beneficial. In the step of repeating the examining and pruning steps, the repetition is typically conducted for a substantial number of additional groups, each of which includes at least one additional node, so as to create a pruned timing graph which has enhanced qualities with respect to the initial timing graph. The enhanced qualities include at least one of enhanced numerical qualities, such as reduced redundancy and degeneracy, as well as compactness, i.e., reduced size.
The invention also includes a program storage device readable by machine, which tangibly embodies a program of instructions executable by the machine to perform the method steps for pruning an initial timing graph, as just described.
Yet further, the present invention includes a method for static optimization of a digital circuit, with the method including the steps of creating a description of the digital circuit; creating an initial timing graph based on the description of the digital circuit, the timing graph being as described previously; pruning the initial timing graph as just described; listing timing constraints corresponding to the pruned graph; adding additional constraints and objective functions as necessary; and then optimizing the digital circuit based on the timing constraints corresponding to the pruned graph. The present invention further includes a digital circuit which has been optimized by the process just described.
The present invention yet further provides an alternative method for problem restatement, similar to the method of pruning described above, but wherein the arrival times and constraints are not explicitly represented in timing graph form. Accordingly, this alternative method provides a method of restating an initial statement of a circuit optimization problem for static optimization of a digital circuit. The problem statement has a plurality of arrival times of signals in the digital circuit and a plurality of constraints. The method includes the steps of examining all those of the constraints in which at least a first group of the arrival times occur; manipulating the constraints; and then repeating the examining and manipulating steps for a substantial number of additional arrival time groups, so as to create a pruned restatement of the optimization problem.
More specifically, in the examining step, all of those constraints in which at least a first group of the arrival times occur are examined to determine if the constraints in which the first group of arrival times occur can be algebraically manipulated in a manner corresponding to pruning of the first group of arrival times. In the manipulating step, the constraints in which the first group of arrival times occur are manipulated if such such manipulation is possible so as to prune the first gr
Conn Andrew R.
Visweswariah Chandramouli
International Business Machines - Corporation
Otterstedt Paul J.
Phan Trong
LandOfFree
Method of reformulating static circuit optimization problems... 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 of reformulating static circuit optimization problems..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of reformulating static circuit optimization problems... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579875