Tightloop method of timing driven placement

Details Tightloop method of timing driven placement Tightloop method of timing driven placement

2000-03-14

2003-07-29

Garbowski, Leigh M. (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

Reexamination Certificate

active

06601226

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the field of electronic design automation (EDA). More specifically, the present invention relates to a method for the tightloop timing driven placement of cells used in the design and fabrication of integrated circuit devices.
BACKGROUND OF THE INVENTION
The rapid growth in the complexity of modem electronic circuits has forced electronic circuit designers to rely upon computer programs to assist or automate most steps of the design process. Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually. Hence, circuits are almost always designed with the aid of an electronic design automation (EDA) system. Basically, an EDA system is a computer software system used for designing integrated circuit (IC) devices. The EDA system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.) and translates this high level design language description into netlists of various levels of abstraction. At a higher level of abstraction, a generic netlist is typically produced based on technology independent primitives. The generic netlist can be translated into a lower level technology-specific netlist based on a technology-specific library that has gate-specific models for timing and power estimation. A netlist describes the IC design and is composed of nodes (elements) and edges (e.g., connections between nodes) and can be represented using a directed graph structure having nodes which are connected to each other with signal lines. A single node can have multiple fan-ins and multiple fan-outs. The netlist is typically stored in computer readable media within the EDA system and processed and verified using many well known techniques. One result is a physical device layout in mask form which can be used to directly implement structures in silicon to realize the physical IC device.
The process used to automate the design of electronic circuits entails first producing a high-level description of the circuit in a hardware description language such as Verilog or VHDL. Next, this high-level description is converted into a netlist using a computer implemented synthesis process, such as a the “Design Compiler” by Synopsys of Mountain View, Calif. A netlist is a description of the electronic circuit which specifies what cells compose the circuit and which pins of which cells are to be connected together using wires (“nets”). Importantly, the netlist does not specify where on a circuit board or silicon chip the cells are placed or where the wires run which connect them together. Determining this geometric information is the function of an automatic placement process and an automatic routing process, both of which are typically computer programs.
Next, the designer supplies the netlist into the computer implemented automatic cell placement process. Placement in a VLSI design is the task of assigning X,Y positions to a set of cells, typically a numbering in the tens of thousands or more, such that they do not overlap each other, and that it is possible to route wires among their pins. Overlap is an absolute constraint and it can be determined immediately by inspecting the design; no cell can overlap another or the chip will not work. Thereupon, the designer supplies the netlist and the cell location data structure, generated by the placement program, to a computer implemented automatic wire routing process. This computer program generates wire geometry within data structure. The wire geometry data structure and cell placement data structure together are used to make the final geometric database needed for fabrication of the circuit.
The placement process can yield any number of different, unique solutions. Some of the placement solutions are better than other solutions in terms of timing. Timing is becoming ever more critical because it affects the speed at which a chip can operate. Faster chips can be sold at a premium price. Indeed, some designs are so timing critical that even though a certain placement solution is found, that particular placement might not meet certain timing specifications. As a result, it is important to consider timing constraints when placing cells.
The goal then is to how best to augment the placement algorithm to produce a placement that has good timing characteristics. First, it is necessary to provide some background on timing driven placement (TDP). Any placement of cells results in some nets that are long, and others that are short. In the standard metric, only the total length of nets is counted, so it does not particularly matter which nets are long and which are short. But to achieve high timing performance, it is important that timing critical nets are short, and it is fine if nets that are not timing critical are longer, as long as the total wirelength is not unreasonable. The “classic” approach to timing driven placement starts by doing a timing analysis on the circuit before placement. The timing results are analyzed, and a set of critical nets is identified. These nets are then given high “weights”, and placement runs in such a way as to minimize the weighted sum of net lengths. This classic approach can be used with either slicing or non-slicing placers.
One problem with the “classic” approach is that the placement itself can greatly influence the timing analysis. Hence, the analysis and weights obtained at the beginning of placement can be irrelevant, or even counterproductive toward the end of placement. Note that only the X,Y positions at the end of placement have any value; all intermediate results are discarded. Before proceeding, it is worthwhile to consider the question: how was it possible that “classic” ever worked? After all, if net capacitances change radically with placement, it would seem impossible that the net weights at the beginning could be accurate enough to have value. Net weights are only valuable if the timing analysis used to generate them is accurate, and timing analysis is inaccurate if the capacitance estimates that drive it are inaccurate. Capacitance estimates are determined directly by X,Y coordinates of cells, so error in the X,Y coordinates results in errors in the capacitance estimates which results in errors in the timing analysis which results in errors in the weights. In fact, the “classic” approach does work on some circuits, but does poorly on others. This is probably because in some circuits there are many usable placement solutions with different placements and different net delays, but with overall good wirelength and timing. In such circuits, at least one solution exists where the set of net weights at the end was close to the set predicted by wireload models. (e.g., paths with many stages tend to be critical).
Thus, there exists a need in the prior art for a method which optimizes the placement of cells from a timing driven perspective. The present invention provides a unique, novel solution by implementing a tightloop method of timing driven placement.
SUMMARY OF THE INVENTION
The present invention pertains to a tightloop method of timing driven placement. Basically, the present invention interleaves timing analyses and updates net weights based on the timing analyses as part of the cell location refinement processes of a placement algorithm. In a placement algorithm, the placement of cells are successively refined until a final placement solution is achieved. The cell locations are moved during each refinement pass based on certain weighting factors. Rather than running a single timing analysis just at the beginning to identify critical nets and assigning a high weight to the critical nets, the present invention recognizes that the timing characteristics change each time a cell is moved. Consequently, a new timing analysis is performed for each pass. Based on the timing analysis, the weighting for the nets is altered accordingly. This weighting affects the way by which cell locations are modified in successive passes. Ther

Affiliated with

Also associated with

Rating

Tightloop method of timing driven placement does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Tightloop method of timing driven placement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tightloop method of timing driven placement will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3090166