Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-09-11
2001-11-06
Grant, William (Department: 2121)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C700S108000, C700S109000, C700S110000, C700S112000, C700S117000, C700S121000, C438S005000, C438S010000, C438S011000, C438S012000, C438S464000, C716S030000, C716S030000
Reexamination Certificate
active
06314547
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to circuit fabrication. More particularly, it relates to a method for improving the location assignment of circuits during fabrication.
2. Prior Art
The process of assigning circuits to locations in, e.g., a chip, frequently includes a stage where all the circuits have been assigned locations, but the assignments are not optimal from either a wiring or timing perspective. For example, certain nets may be on the critical path, and as a result may have delays that are too large. A determination may then be made as to what sets of motions (i.e., assigning a subset of gates to different locations) decrease the sum of the capacitances of the nets on the critical path, with or without weights for the different nets.
Circuit synthesis has traditionally operated on optimized netlists. These optimizations have included both boolean and electrical optimizations. Placement algorithms, on the other hand, have focused primarily on the spatial domain, such as minimizing the total net length or a weighted average of net lengths. With the emergence of sub-micron technologies, there is a need for synthesis and placement algorithms to work seamlessly across all three domains, i.e., boolean, electrical and spatial.
Generally, physical designs have focused on spatial optimizations where the locations of netlist objects are selected with the goal of optimizing a given parameter, e.g., timing, wireability, etc. Recently, synthesis-like electrical optimizations have been implemented into placement subsystems. These electrical optimizations typically operate on the netlist and primarily use the spatial domain only to estimate wire capacitance/RC using a wire length estimator such as a Steiner estimator. Unfortunately, these optimizations do not make significant changes in the locations of the objects.
In view of the foregoing, there is also a need for placement synthesis algorithms to understand the location domain primarily from two main perspectives: 1) correct modeling of the spatial domain; and 2)optimization along the spatial domain. With respect to the correct modeling of the spatial domain, even if one were to focus on only the electrical and boolean domains, in order for the synthesis optimizations to be useful, they would have to model the interconnection correctly. This modeling requires the spatial information. Current techniques in synthesis for modeling interconnection which, for example, estimate wire capacitances as a function of fanouts, are inaccurate.
Examples of optimization along the spatial domain would be moving and rearranging the placement of circuits so as to improve the quality of the circuit for aspects such as timing and wireability. Synthesis has typically dealt with the two dimensions of boolean and electrical optimizations. Various combinations of algorithms are applied, each optimization creating possibilities for further boolean or electrical optimizations or a combination of both. Examples of boolean optimizations are factoring, redundancy removal, etc., while fanout correction/buffer insertion and sizing are examples of electrical optimizations. In later stages of synthesis (known as timing correction), mostly electrical optimization with some boolean optimizations are applied. With the increase in the capacitance/RC of interconnects with sub-micron technologies, synthesis must now consider the spatial domain, and therefore, optimizations now have to operate in all three domains.
As shown in
FIG. 1
, the synthesis and physical design are separate aspects of the fabrication. Thus, there is a need for an overall strategy of integrating the physical design and synthesis by creating a common framework in which electrical, boolean and location (spatial) optimizations can be performed simultaneously.
SUMMARY OF THE INVENTION
In one embodiment of the present invention, the placement of the individual cells of a circuit are manipulated to improve the overall timing of the circuit. The changes in such locations can be done in concert with resizing, buffer insertion, re-mapping and other such standard synthesis electrical and boolean transformations.
We consider the physical image in terms of an array of bins, each of which can hold a collection of gates. We assume that each gate has a known area and that for each bin, we know the available area. It is possible to have more sophisticated measures, such as wiring tracks available, so as to measure the wiring requirements. We consider Bin Circuit Count as the equivalent area required by the circuits and Bin Capacity as the equivalent area available for circuits.
The two criteria of interest in the present invention are wireability and timing. For coarse placement, wireability can either be directly estimated or one can use simpler measurements such as Bin Circuit Count vs. Bin Capacities, and Total Wire Length.
According to an embodiment of the invention, the method for improving circuit location assignment comprises the steps of determining the critical path of assigned circuit locations; generating a list of nets on the critical path; generating a list of motions for each net on the critical path; generating a set of motions for a complete path; testing each move to determining and improvement in slack for all gates participating in the move, and executing the move that provides the greatest improvement.
The selection of nets to be worked upon may use a different process than the one described here. In addition, the path that is given by the above process may be selected differently. This invention embodies all possible approaches, and is primarily concerned with the selection of motions after a net or a set of nets has been selected, and this is one example of a process by which the nets and path can be selected.
The applications envisioned for the present invention are improving a critical path, improving a critical section of the circuit (i.e., a DAG), improving wireability, resolving a bin overflow situation after moving circuits for timing, and resolvig.
During fabrication, the less often a complete timing analysis must be performed the better. The basic strategy is that when one works on improving wireability, they allows only nets with relatively large slack to increase in wire length and no critical or near-critical net is allowed to increase in wire length. When working on timing improvements, one may want to make sure that a significant improvement has been obtained. After this, the total picture may change so much that a complete timing analysis may need to be performed for further improvement.
Thus far, timing and timing improvements have been discussed. However, the present invention is applicable whenever there is a need for shortening selected nets. This can include, for example, placement for wireability, noise, or power.
REFERENCES:
patent: 5105362 (1992-04-01), Kotani
patent: 5208765 (1993-05-01), Turnbull
patent: 5241465 (1993-08-01), Oba et al.
patent: 5499192 (1996-03-01), Knapp et al.
patent: 5654903 (1997-08-01), Reitman et al.
patent: 5778386 (1998-07-01), Lin et al.
patent: 5841660 (1998-11-01), Robinson et al.
patent: 5844802 (1998-12-01), Lepper et al.
patent: 5856923 (1999-01-01), Jones et al.
patent: 5940300 (1999-08-01), Ozaki
patent: 5974245 (1999-10-01), Li et al.
patent: 6014506 (2000-01-01), Hossain et al.
patent: 6032531 (2000-03-01), Roszhart et al.
Donath Wilm E.
Kudva Prabhakar N.
F. Chau & Associates LLP
Grant William
International Business Machines - Corporation
Patel Ramesh
LandOfFree
Method for improving the assignment of circuit locations... 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 for improving the assignment of circuit locations..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for improving the assignment of circuit locations... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591677