REGISTER  |  SIGN IN
United States Patent6591407
Kaufman , ; et al.July 8, 2003
Title
Method and apparatus for interconnect-driven optimization of integrated circuit design
Abstract
A method and an apparatus are provided for post-layout optimization of an integrated circuit. In one instance, only local transformations accomplished by incremental changes to placement and routing are provided, so as to avoid the costly design iteration loop that requires re-synthesis, re-place and re-route. Optimization can be provided in multiple optimization phases each accomplishing a specified set of transformations. Static timing analysis is performed at the end of each set of local transformations to determine if further optimization steps are required. In one instance, the physical design is first scanned for mismatch between drivers and loads. Then, in a second optimization phase, "hot spots" in the physical design are identified for local transformation using a "bidirectional combinational total negative slack" (BCTNS) algorithm. In subsequent phases, optimization based on meeting setup times and hold times in a critical path are performed.
Inventors:Kaufman; Douglas (Menlo Park, CA), Almusa; Hazem  (San Jose, CA), Srinivas; Vinay  (Redwood City, CA), Organ; Donald V.  (Saratoga, CA), Ke; Larry  (San Jose, CA), Li; Wei  (Milpitas, CA), Singh; Japinder  (Santa Clara, CA), Mathews; Robert  (Los Altos, CA)
Assignee:Sequence Design, Inc. (Santa Clara, CA)
Appl. No.:516489
Filed:March 1, 2000
Current U.S. Class:716/10 716/2 716/3 716/9 
Current International Class:G06F 17/50 (20060101)
Field of Search:716/2,3,10,9
U.S. Patent Documents
5629859May 1997Agarwala et al.
5663662September 1997Kurosawa
5726903March 1998Kerzman et al.
5901063May 1999Chang et al.
5923564July 1999Jones, Jr.
5984510November 1999Guruswamy et al.
6058252May 2000Noll et al.
6145117November 2000Eng
6263478July 2001Hahn et al.
6360356March 2002Eng
6381730April 2002Chang et al.
6470486October 2002Knapp
Other References
NN950127 ("Algorithm for Incremental Timing Analysis", IBM Technical Disclosure Bulletin, vol. 38, No. 1, Jan. 1995, pp. 27-34 (18 pages)..~
Primary Examiner: Smith; Matthew
Assistant Examiner: Kik; Phallaka
Attorney, Agent or Firm:Kwok; Edward C. MacPherson Kwok Chen & Heid LLP
Claims

We claim:
1. A method for post-layout optimization of an integrated circuit, comprising: providing a logic description of said integrated circuit; synthesizing, from said logic description, a netlist of said integrated circuit including instances from a standard cell design library; placing and routing said instances to provide a physical design of said integrated circuit; extracting, from said physical design, models of parasitic impedance of interconnect in said physical design; and optimizing said physical design by modifying said physical design according to said models of parasitic impedance.

2. A method as in claim 1, wherein said optimizing comprises: identifying, using a static timing analyzer, locations in said physical design where timing violations occur; and when a timing violation is identified: (a) applying one or more local transformations to said physical design to correct said timing violation; and (b) returning to said identifying.

3. A method as in claim 2, wherein said static timing analyzer computes a slack for each terminal of said physical design.

4. A method as in claim 3, wherein, to compute said slack, both a forward sweep and a backward sweep of said physical design are performed.

5. A method as in claim 4, wherein said backward sweep computes a required signal arrival time.

6. A method as in claim 4, wherein said forward sweep computes a latest signal arrival time.

7. A method as in claim 2, wherein said local transformation comprises replacing an instance of a first standard cell in said physical design by an instance of a second standard cell within the function group of said first standard cell, and wherein said second instance is selected on the basis of its operating range of loads.

8. A method as in claim 2, wherein said identifying step identifies instances at which a driver mismatches with an output load.

9. A method as in claim 2, wherein said identifying step ranks instances according to a descending order of potential timing improvement.

10. A method as in claim 2, wherein said local transformation comprises node off-loading.

11. A method as in claim 2, wherein said local transformation corrects a hold time violation.

12. A method as in claim 2, wherein said local transformation identifies instances along a critical, path.

13. A method as in claim 2, wherein said local transformation is performed only when a resulting timing improvement exceeds a predetermined threshold.

14. A method as in claim 4, wherein said identifying comprises: computing, for each of said instances, a potential improvement value; during said forward sweep, based on said potential improvement value, computing for each terminal of each instance a forward priority value; and during said backward sweep, based on said potential improvement value, computing for each terminal of each instance a backward priority value; and computing, for each terminal of each instance, an equivalent priority value based on said forward and backward priority values.

15. A method as in claim 4, wherein said forward sweep begins at primary input terminals of said physical design and propagates said slack towards primary output terminals of said physical design.

16. A method as in claim 4, wherein said backward sweep begins at primary output terminals of said physical design and propagates said slack towards said primary input terminals of said physical design.

17. A method as in claim 1, further comprising analyzing said standard cell library to provide, for each output driver in said standard cell library, an operating range of loads for which said output driver can optimally drive.

18. A method as in claim 17, wherein said analyzing step includes applying a metric for trading-off speed performance for silicon area.

19. A method as in claim 18 wherein said metric comprises a ratio between change of silicon area and change of speed performance.

20. A method as in claim 17, wherein said analyzing step comprises grouping standard cells in said standard cell library into function groups, each function group consisting of logically equivalent members made up of standard cells in said standard cell library.

21. A method as in claim 1, wherein said models of parasitic impedance are obtained using an asymptotic waveform evaluation technique.

22. A method as in claim 1, further comprising a clock tree analysis.

23. A method as in claim 1, wherein said models of parasitic impedance comprise a .pi.-model.

24. A method as in claim 23, further comprising computing, from said p-model, an effective load capacitor.

25. A method as in claim 24, further comprising computing, from said p-model and said effective load capacitor, an input transition time at an input terminal of a cell instance.

26. A method for post-layout optimization of a physical design of a circuit, comprising: extracting, from said physical design, parasitic models of interconnect in said physical design; applying a plurality of optimization steps, each of said optimization steps transforming said physical design to achieve a desired performance based on area or delay, said optimization steps being applied in order of potential intrusiveness to said physical design.

27. A method as in claim 26, wherein one of said optimization steps comprises: identifying, in said physical design, a cell instance mismatched to an output load driven by said cell instance; and replacing said cell instance by a second cell instance matched to said output load.

28. A method as in claim 26, wherein one of said optimization steps comprises: computing a potential improvement in slack for each cell instance in said physical design; selecting, from said physical design, cell instances having potential improvement in slack exceeding a predetermined value; and applying transformations to said selected cell instances to achieve said potential improvement in slack.

29. A method as in claim 28, wherein said selecting further comprises: performing a forward sweep of said physical design to provide for each cell instance a forward priority value; performing a backward sweep of said physical design to provide for each cell instance a backward priority value; calculating for each cell instance an equivalent priority value based on a corresponding forward priority value and a corresponding backward priority value; and ranking cell instances in said physical design according to said equivalent priority value.

30. A method as in claim 28, wherein said transformation comprises one or more of cell instance downsizing, cell instance upsizing, and node off-loading.

31. A method as in claim 26, wherein one of said optimization steps selects circuits in said physical design for optimization according to a metric based on a path-based algorithm.

32. A method as in claim 31, wherein said circuits are selected using a critical path algorithm.

33. A method as in claim 31, wherein said one of said optimization steps applies one of cell instance downsizing, cell instance upsizing, node off-loading, cell instance input-swapping, and logic duplication.

34. A method as in claim 26, wherein one of said optimization steps provides a transformation of said physical design to ensure said physical design meet hold time requirements.

35. A method as in claim 34, wherein said transformation comprises inserting buffers to increase signal arrival time at a state element.

36. A method as in claim 26, wherein each optimization step invokes a timing analyzer for computing a slack value at a terminal of a cell instance or an interconnect.

37. A method as in claim 36, wherein said timing analyzer comprises a static timing analyzer.

38. A method as in claim 37, wherein said static timing analyzer performs incremental timing analysis.

39. A method as in claim 26, further comprising characterizing a standard cell library from which cell instances of said physical design were selected.

40. A method as in claim 39, said characterizing comprises assigning an operating range of output load to each cell in said standard cell library.

41. A method as in claim 40, wherein said operating range of output load being assigned based on a metric involving area and delay.

42. A method as in claim 41, further comprising, prior to said extracting step, generating said physical design using a layout directive that results in at least a predetermined percentage of said cell instances not meeting timing requirements, when computed under a wire load model.

43. A method as in claim 26, wherein the last of said optimization steps comprises: identifying in said physical design a cell instance meeting timing requirements and mismatched to an output load driven by said cell instance; and replacing said cell instance by a second cell instance matching said output load and having a smaller silicon area than the silicon area of said cell instance.

44. A method for selecting a cell from a library to perform a given logic function and to drive a given load capacitance, comprising: dividing cells in said library into a plurality of groups, such that cells within each of said groups perform substantially the same logic function; within each of said groups, assigning to each of selected ones of cells an operating range of loads; selecting one of said groups by matching said given logic function to the logic function performed by cells in said selected group; and selecting said cell from said selected group by matching said given load capacitance to said operating range of said cell.

45. A method as in claim 44, wherein said assigning step assigns said operating range of loads to a cell in said library according to a metric relating an area of said cell to a delay of said cell.

46. A method as in claim 45, wherein said metric compares two cells within one of said group according to a difference between the areas of said cells and a difference between delays in said cells.

47. A method as in claim 46, wherein said difference between the areas of said cells is normalized by a mean area of cells within the group of said two cells.

48. A method as in claim 46, wherein said difference between the delays of said cells is normalized by a mean delay of cells within the group of said two cells, under a zero-load condition.

49. A method as in claim 44, wherein each said group comprises: a cell performing said logic function; and a combination including a cell performing said logic function and a buffer.

50. A method as in claim 44, wherein each said group comprises: a cell performing said logic function; and a combination including a cell performing a logic function complement to said logic function and an inverter.

51. A method for identifying in a post-layout circuit a cell instance for optimization, comprising: computing, for each cell instance in said post-layout circuit, a potential improvement value; during a forward sweep of said post-layout circuit, based on said potential improvement value, computing for each terminal of each instance a forward priority value; and during a backward sweep of said post-layout circuit, based on said potential improvement value, computing for each terminal of each instance a backward priority value; computing, for each terminal of each instance, an equivalent priority value based on said forward and backward priority values; and selecting among instances of said post-layout circuit the cell instance having the highest equivalent priority value.

52. A method as in claim 51, wherein said selecting step sorts instances in said post-layout circuit in descending order of equivalent priority value.

53. A method as in claim 51, wherein in said forward sweep, an output terminal of an instance in said circuit area receives a forward priority value substantially equal to the sum of forward priority values in input terminals of said instance.

54. A method as in claim 51, wherein in said forward sweep, at each divergence point on an interconnect encountered, each output branch of said divergence point receives a forward priority value substantially equal to a forward priority value of an input terminal of said interconnect.

55. A method as in claim 51, wherein at a merged point on an interconnect encountered in said forward sweep, each output terminal of said interconnect receives a forward priority value substantially equal to the sum of forward priority values in input terminals of said interconnect.

56. A method as in claim 51, wherein in said backward sweep, each input terminal of an instance in said circuit area receives a backward priority value substantially equal to a backward priority value in an output terminal of said instance.

57. A method as in claim 51, wherein in said backward sweep, at each divergence point on an interconnect encountered, each input branch of said divergence point receives a forward priority value substantially equal to a forward priority value of an output terminal of said interconnect.

58. A method as in claim 51, wherein at a merged point on an interconnect encountered in said backward sweep, each input terminal of said interconnect receives a backward priority value substantially equal to a backward priority value of an output terminal of said interconnect.

59. A method as in claim 51, wherein each of said equivalent priority values is used to compute a slack value.

60. A method as in claim 59, wherein said slack value is provided by interpolation procedure using a table of said equivalent priority values according to the size of an output load of said selected instance.
Description
BACKGROUND OF THE INVENTION

1. Field of the.Invention

The present invention relates to a tool for integrated circuit design. In particular, the present invention relates to a tool for optimizing the physical design of a standard cell-based integrated circuit for performance.

2. Discussion of the Related Art

A standard cell-based integrated circuit is designed using a library of building blocks, known as "standard cells." Standard cells include such elements as buffers, logic gates, registers, multiplexers, and other logic circuits ("Macros").

FIG. 1a shows a typical design process or "flow" 100 that an integrated circuit designer would use to design a standard cell-based integrated circuit. As shown in FIG. 1a, at step 101, the designer provides a functional or behavioral description of the integrated circuit using a hardware description language. In addition, the designer specifies timing and other performance constraints (109) with which the integrated circuit must comply. Then, at step 102, the designer selects a standard cell library to implement the design. Typically, the standard cells in the library are designed to the requirements of a target manufacturing technology. Often, each cell is also characterized to provide performance parametric values such as delay, input capacitance and output drive strength.

At step 103, the designer uses a "synthesis tool" to create from the functional or behavioral description a functionally equivalent logic gate-level circuit description known as a "netlist." The elements of the netlist are instances of standard cells selected by the synthesis tool from the standard cell library in accordance with functional requirements and the performance constraints. At this stage, the synthesis tool uses the characteristic parametric values of each standard cell and a model of input and output loads ("wire load model" or "WLM") to attempt to meet performance requirements.

At step 104, a "place and route" tool creates a "physical design" by placing the standard cell instances of the netlist onto the "silicon real estate" and routes conductor traces ("wires") among these standard cell instances to provide for interconnection. Typically, the placement and routing of these standard cell instances are guided by cost functions, which minimize wiring lengths and the area requirements of the resulting integrated circuit.

At step 105, with the wires of the integrated circuit having been routed at step 104, a more accurate set of parasitic impedance values in the wires can be extracted. Using the extracted parasitic impedance values, a more accurate timing analysis can be run at step 106 using a static timing analyzer (STA). If the physical design meets timing constraints, the design process is complete (step 108). Otherwise, steps 103-106 are repeated after appropriate modifications at step 107 are made to the netlist and the performance constraints.

Design process 100 suffers from a number of disadvantages. First, WLM is a crude model based on statistics. Because of the inaccurate model, a designer typically uses an "80.sup.th percentile WLM" (i.e., 80% of the nets will have a capacitance less than predicted by the WLM). As a result, the drivers for many nets are unnecessarily large, while other driver are too weak. Additionally, designers tend to provide 30% or more additional safety margins to accommodate other inaccuracies in the design flow. Such over-design represents inefficiencies in both silicon area and performance. Second, under this typical method, whenever a non-trivial modification is made to the design to meet a performance requirement, the design is re-synthesised, re-placed and re-routed, which are very time-consuming and costly steps, even when timing is met in a majority of nets. Typically, at each iteration, the physical design undergoes major changes that may introduce new sub-optimal nets requiring another iteration of synthesis, placement and routing to correct.

The inefficiency in the prior art method results in both high cost and long development time in engineering, time-to-market and manufacturing.

SUMMARY

The present invention provides methods and systems for optimizing a post-layout design without requiring re-synthesis. In these methods and systems, accurately extracted timing information from the physical design drives transformation of the physical design, thereby avoiding the inaccuracy of wire load models of the prior art. Further, methods and systems of the present invention apply local transformations to the physical design, thereby maintaining substantial integrity (i.e., validity and accuracy) in the interconnect models during the transformation process. Accurate models of parasitic impedance can be obtained using an asymptotic waveform evaluation technique.

According to one embodiment of the present invention, one method for post-layout optimization of an integrated circuit includes: (a) providing a logic description of the integrated circuit; (b) synthesizing from the logic description a netlist of the integrated circuit using instances of cells from a standard cell design library; (c) placing and routing the instances to provide a physical design of the integrated circuit; (d) extracting from the physical design models of parasitic impedance of interconnect in the physical design; and (e) optimizing the physical design by modifying the physical design according to the models of parasitic impedance. Under that method, in one embodiment, the optimization iteratively (a) identifies, using a static timing analyzer, locations in the physical design where timing violations occur and (b) applies one or more local transformations to the physical design to correct the timing violation.

In one implementation, the method performs a forward sweep and a backward sweep of the physical design to compute a required signal arrival time and a latest signal arrival time, respectively.

In accordance with another aspect of the present invention, a library analysis step provides characterization of the standard cell library to allows accurate timing and load driving ability analyses. In particular, one method enables a cell to be selected from a library to perform a given logic function and to drive a given load capacitance. That method includes: (a) dividing the cells in the library into groups, such that cells within each of the groups perform substantially the same logic function; (b) within each group, assigning to selected cells each an operating range of loads; and (c) selecting a cell by matching the logic function and the given load capacitance to the operating range of the cell. In one implementation, the operating range of loads to a cell in the library are assigned according to a metric relating an area of the cell to a delay of the cell. In one implementation, each group contains not only cells performing the given function, but also combinations of such cells and buffers of appropriate drive strengths, and combinations of cells providing a complementary logic function and inverters.

According to another aspect of the present invention, a method of the present invention includes: (a) extracting from the physical design parasitic models of interconnect in the physical design; and (b) applying optimization steps, each optimization step transforming the physical design to achieve a desired performance based on area or delay. In one embodiment, the optimization steps are applied in order of potential intrusiveness to the physical design. Thus, the present invention allows the less complex modifications to be accomplished first. Typically, a large portion of the potential optimization can be achieved by these minimally intrusive modifications to the physical design, leaving the physical design to be substantially optimized even before the more intrusive optimization steps are applied.

In one implementation, an initial optimization step identifies in the physical design a cell instance mismatched to an output load driven by the cell instance; and replaces the cell instance by a second cell instance matched to the output load. Then, a second optimization step computes a potential improvement in slack for each cell instance in the physical design, selects from the physical design cell instances having the largest potential improvements in slack, and applies transformations to the selected cell instances.

In that second optimization step, a bidirectional combinational total negative slack (BCTNS) ranking method of the present invention is used. The BTCNS ranking method identifies "hot spots" in the physical design, which are locations where performance improvements with the highest potential impact. The BTCNS method includes: (a) performing a forward sweep and a backward sweep of the physical design to provide for each cell instance a forward priority value and a backward priority value; (b) calculating an equivalent priority value based on the forward priority value and the backward priority value; and (c) ranking cell instances in the physical design according to the equivalent priority value.

Following the second step of optimization, a third optimization according to a metric based on a path-based algorithm (e.g., a critical path algorithm). The path-based optimization can be used to correct hold and set-up time violations. In that method, the last optimization step identifies in the physical design a cell instance meeting timing requirements but mismatched to an output load driven by the cell instance, and replaces the cell instance by a second cell instance matching the output load and having a smaller silicon area.

In one implementation, the method of the present invention takes advantage of a static timing analyzer capable of performing incremental timing analysis, and an extraction tool capable of performing incremental extraction of parasitic impedance in the interconnect.

The local transformations in the present invention include cell instance upsizing, cell instance downsizing, node off-loading, input swapping and logic duplication.

In one embodiment of the present invention, a system for post-layout design optimization, includes: (a) a library interface for access to a standard cell library; (b) a timing analyzer interface for accessing a static timing analyzer; (c) a design tool interface for accessing a place and route design tool; (d) a design database for storing a physical design of an integrated circuit composed of instances of standard cells from the standard cell library. The system provides routines for traversing the instances in accordance with predetermined orders, a control program for obtaining timing information of the instances from the static timing analyzer, a control program for applying local transformations of the instances guided by the timing information.

The present invention is better understood upon consideration of the detailed description below and the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1a shows a typical design flow 100 that an integrated circuit designer would use to design a standard cell-based integrated circuit.

FIG. 1b shows design flow 150, in accordance with one embodiment of the present invention.

FIG. 2 shows design flow 200, representing the operations of step 109b of FIG. 1b, in one embodiment of the present invention.

FIG. 3 is an overview of optimization tool 300 in one embodiment of the present invention.

FIG. 4 is flow diagram 400 representing library analysis step 201 of FIG. 2.

FIG. 5a shows the drive strengths of cells 501-504.

FIG. 5b shows, in the operating range of interest (i.e., 0 to 2 pf), process flow 400 found cells 501-503 which cover the entire operating range with their individual operating ranges 0 to C.sub.1, C.sub.1 to C.sub.2, and C.sub.2 to 2pf.

FIG. 6 shows a network model 600 used in STA 308.

FIG. 7 is a flow diagram 700 that illustrates the operations of delay calculator 307.

FIG. 8 is a flow diagram 800 showing the operations of Phase 1 optimization, according to one embodiment of the present invention.

FIG. 9a is a flow diagram 900 providing an overview of the optimization steps in Phase 2A.

FIG. 9b is a flow diagram 900 providing an overview of the optimization steps in Phase 2B.

FIG. 10 is a flow diagram 1000 showing the operations of BCTNS sort step 904 of FIG. 9a.

FIG. 11a shows cell instance 1101 with its output "effective load" modeled by capacitor. 1102 (C.sub.L) and input and output signal transition times 1104, 1105 and 1106, as computed by delay calculator 307.

FIG. 11b shows assumed operating conditions necessary to achieve a largest possible delay improvement of cell instance 1101.

FIG. 12a is a flow diagram 1250 showing the operations of backward propagation of PV values at step 1008 of FIG. 10.

FIG. 12b shows a backward column PV table initialization step 1200, used in output pin initialization step 1253 of FIG. 12a.

FIG. 12c shows a flow diagram 1280 that sets forth the steps for backward propagation of values of a PV table to a divergence point.

FIG. 12d shows a flow diagram 1260 that illustrates the steps for backward propagation of values of a PV table to a merged point.

FIG. 13a shows backward propagation of PV values over a parasitic model that is driven by multiple input terminals.

FIG. 13b shows backward propagation of PV values over a cell instance having multiple input terminals.

FIG. 13c shows backward propagation of PV values from multiple output terminals of a parasitic model to a single input terminal.

FIG. 14a is a flow diagram 1450 showing forward propagation of PV values at step 1009 of FIG. 10.

FIG. 14b shows a forward column PV table initialization step 1400, used in input pin initialization step 1453 of FIG. 14a.

FIG. 14c shows a flow diagram 1480 that sets forth the operations for forward propagation of values of a PV table to a divergence point.

FIG. 14d shows a flow diagram 1460 that illustrates the steps for forward propagation of values of a PV table to a merged point.

FIG. 15a shows forward propagation of PV values over a parasitic model that is driven by multiple input terminals.

FIG. 15b shows forward propagation of PV values over a cell instance having multiple input terminals.

FIG. 15c shows forward propagation of PV values from a single input terminal of a parasitic model to multiple output terminals.

FIG. 16 shows flow diagram 1600, which illustrates the steps for computing EPV for each cell in the cluster.

FIG. 17 shows flow diagram 1700, which illustrates the operations for optimization step 907 (i.e., cell downsizing).

FIG. 18 shows flow diagram 1800, which illustrates the operations for optimization step 908 (i.e., cell upsizing).

FIG. 19 shows flow diagram 1900, which illustrates the operations for optimization step 909 (i.e., node off-loading).

FIG. 20 is a flow diagram 2000, which provides an overview of the optimization steps in Phase 3.

FIG. 21 shows flow diagram 2100, which illustrates "input swapping" optimization step 2011 of Phase 3.

FIG. 22 shows flow diagram 2200, which illustrates "logic duplication" optimization step 2012 of Phase 3.

FIG. 23 provides an example of circuit optimization by logic duplication.

FIG. 24 shows flow diagram 2400, which illustrates a buffer insertion technique for addressing hold time violations.

FIG. 25 shows flow diagram 2500 which illustrates a process for reducing overall silicon area

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present invention provides a design tool and a method for optimizing a standard-cell based integrated circuit after placement and routing are performed, without requiring complete re-synthesis of the integrated circuit design. The present invention optimizes the integrated circuit design based on accurate extraction and modeling of the interconnect network.

FIG. 1b shows an overview of design flow 150 in one embodiment of the present invention. Unlike the prior art, in the present invention, the integrated circuit design steps of synthesis, initial placement and initial routing are not re-iterated. Instead, modifications to the physical design are performed incrementally. After completing HDL description, synthesis, place and route, extraction and timing analysis steps 101b-106b, which can be substantially the same as corresponding steps 101-106
of FIG. 1a, the timing problems uncovered by timing analysis step 106b are addressed by an interconnect optimization step 109b. Step 109b fixes some or all of the timing problems using the local transformation techniques described below. These local transformations are realized at step 110b by providing incremental place and route directives to the corresponding place and route tools. At step 111b, an incremental extraction of parasitic impedance is performed on the revised physical design. Process flow 150 then returns to timing analysis step 106b to determine if the revised physical design meets all timing requirements. If not, step 109b, 110b and 111b are repeated.

FIG. 2 shows in further detail step 109b of FIG. 1b. As shown in FIG. 2, at step 201; a standard cell library (e.g., a ".lib" file of a format supported by Synopsys Corp.) is analyzed and characterized. Under step 201, cells are classified according to their logic functions (e.g., NAND gates of different drive strengths are grouped), and each cell's operating characteristics (e.g., drive strength at each output terminal and capacitance at each input terminal) are estimated, as explained in further detail below. The results are included in an augmented library file (in a suitable format, such as Copernicus Library Format or "CLF").

At step 202, the design database is prepared for receiving an input netlist. The design database provides data structures, described in additional detail below, for facilitating the optimization steps in FIG. 2. The synthesized, placed and routed physical design is then read into the database. The design is typically provided, for example, in the LEF and DEF file formats supported by Candence Design Systems Inc. In addition, timing and other constraints (expressed, for example, in an industry standard format, such as those formats used in the "Primetime" tool from Synopsys, Inc. or the "DesignCompiler" tool from synopsys Inc.) are also read into the database.

At step 203, parasitic impedance models ("parasitic" models) of interconnect wires are incorporated into the database. Parasitic models are provided by parasitic extractor 204, which can be implemented by, for example, the extraction tool "Columbus", which is available from Frequency Technology, Inc., Santa Clara, Calif. The parasitic models are incorporated into the initial netlist. Such parasitic models can include such circuit elements as resistors, capacitors and inductors.

At step 205, a clock tree analysis is performed by clock tree analyzer 206 to identify clock signals and clock signal paths. Clock tree analyzer 206 can be provided internally, or by an external clock tree analyzer (e.g. "Cartier" from Frequency Technology, Inc.) interfaced to the design tool of the present invention. The extracted clock information is incorporated into the design database.

At step 207, based on the clock analysis, the extracted parasitic models, the operational characteristics of the cell instances in the physical design, and the performance constraints of the physical design, an initial timing analysis is performed. In this embodiment, the initial timing analysis is performed by a static timing analyzer (STA), which is described in further detail below. In this static timing analysis step, the "slack" of each electrical terminal, or "pin," is calculated. On a pin, the term "slack" refers to the time difference between the latest signal arrival time and a required signal arrival time. A cell instance can also be assigned a slack, which is typically the least slack selected from the cell instance's input and output terminals.

Based on the slack values, the design tool of the present invention provides one or more optimization steps. To simplify presentation, only optimization steps 208 and 209 are explicitly shown in FIG. 2. In one embodiment of the present invention, four optimization steps (identified below as Phases 1-4 and described in further detail below) are provided in the design tool. In each optimization step, the physical design is modified by a number of local transformations--i.e., each transformation affects only a small number of closely related cell instances and nets. In one embodiment, the local transformations are reported and implemented by providing incremental placement and routing directives to a placement and routing tool (e.g., steps 210-212). At the end of each optimization step, a static timing analysis is performed, using the same STA mentioned above. If the timing constraints are met, further optimization is not necessary.

As mentioned above, in one embodiment, four optimization steps ("phases") are provided. In one embodiment, described below, the first three phases are arranged in such a manner that each phase has a potential for resulting in greater modification to the post-layout circuit than the previous phase (i.e., increasing "intrusiveness"). In the first phase ("Phase 1"), which is a "clean-up" optimization step, the physical design is inspected for load-driver mismatches. A load-driver mismatch occurs when a driver drives a load outside of the driver's optimal range. In Phase 1, to correct a load-driver mismatch, a cell instance can be upsized or down-sized to meet the required timing constraints (i.e., the mismatched cell instance can be replaced by a logically equivalent cell instance with more or less drive strength, or longer or shorter propagation delay).

In the second phase ("Phase 2"), "hot spots" are identified in the physical design. A "hot spot" is a cell with a potential timing improvement that can result in a substantial improvement in timing performance both locally and along signal paths that include this cell. In one embodiment, Phase 2 consists of two phases, referred to below as Phase 2A and Phase 2B. Phase 2A is based on a "total negative slack" calculation at each terminal. Negative slack at a terminal is the amount of time by which the expected signal arrival time at the terminal fails to meet the required arrival time, taking into consideration all timing paths leading to the terminal. "Total negative slack (or "TNS")" at a terminal is the cumulative negative slacks over all timing end points of interest. An endpoint having a positive slack is ignored. More detailed information regarding TNS can be obtained, for example, from Synopsys Inc. Depending on the nature of the hot spot, one or more local transformations can be applied to realize the timing improvements.

Because only local transformations are applied at Phases 1 and 2, the resulting modified physical-design does not require re-synthesis. In many physical designs, a very high percentage of all timing violations can be corrected by the local transformations of Phases 1 and 2. Thus, optimization of these physical designs can be achieved without reiteration of the time-consuming re-synthesis, placement and routing loop, thereby reducing the cost of an integrated circuit design.

In the embodiment mentioned above, in addition to Phases 1 and 2 described above, a third phase ("Phase 3") also applies local transformations to minimize worst negative slake (WNS), in signal paths. In a first part of a fourth phase ("Phase 4A "), "hold" timing violations in signal propagation paths are corrected. A "hold" time violation occurs when a signal transition at a clocked element (i.e., a sequential element, such as a flip-flop) occurs prior to the previous logic value of the signal is latched by the clocked element. A "setup" timing violation occurs when the clocked element latches a signal prior to the signal's arrival.

Finally, in the second part of the fourth phase. ("Phase 4B"), the physical design is examined to minimize overall silicon area, by downsizing appropriate cell instances.

In the present invention, because highly accurate parasitic models are used in the optimization steps, a more aggressive design style can be used. For example, a 50% WLM target can be set in the synthesis step, so as to leave a larger portion of the timing violations to be corrected by the optimization steps. Under such an arrangement, over-design in the final physical design is reduced, resulting in a lower silicon area and a more timing-efficient integrated circuit. Because the present invention applies local transformations, rather than relying on a global re-synthesis, changes to the placed and routed physical design are incremental and minimally intrusive. Physical design optimization can therefore be achieved much more quickly than in the prior art.

FIG. 3 is an overview of optimization tool 300 in one embodiment of the present invention. Design tool 300 includes an overall control program 301, which controls and sequences the process flow 200 in FIG. 2, for example. In optimization tool
300, design database ("design graph") 305 contains the data structures representing the physical design at all times. Some examples of objects in design graph 305 includes: a. "Macro"--a representation of a standard cell in the standard cell library; b. "MacroPin"--a terminal of a Macro; c. "Timing Arc"--a data structure representing the propagation delay between two MacroPins; d. "Node"--an instance of a Macro; e. "NodePin"--a terminal in a Node; f. "Net"--a net connecting two or more NodePins; g. "TransformFactory"--a data structure representing a collection of Net and Node changes to transform the design graph; and h. "Transform"--an instance of a transformation in a TransformFactory.

To import the placed and routed physical design and the timing and performance constraints, interfaces 310-314 are provided. Interfaces 310-314 each translate design data or constraints expressed in an industry standard data format to internal data structure of design graph 305.

The physical design can be exported to an external tool to perform further design activities, such as to perform incremental placement and routing, or to perform more accurate extraction of parasitic impedance. Interface 304 translates selected data structures of design graph 305 into industry standard formats accepted by the external tool.

Algorithms 315 include routines for traversing design graph 305, thus allowing application programs in optimization tool 300 to extract information in design graph 305 in specified orders. Some examples of such routines include routines for returning a cluster, a cell, a net or a path in depth-first, breadth-first or another ranked order. (A cluster is a group of combinational logic elements between two clocked elements in common or related clock domains.) Specifically, algorithms 315
provide routines for a "forward sweep" and a "backward sweep" of a cluster. These operations are explained in further detail below. Algorithms 315 provide an internal interface between functional modules (e.g., transformation routines 309, described below) and design graph 305.

FIG. 3 shows four functional modules: optimization module 302, transform module 309, STA 308 and delay calculator 307. Delay calculator 307, which is described in further detail below, computes a delay in a given net using an "asymptotic waveform evaluation" (AWE) method. STA 308 performs both the initial static timing analysis (e.g., step 207 of FIG. 2) and the static timing analysis after each optimization step (e.g., steps 208-209), as mentioned above. To compute delay at a net, STA
308 invokes delay calculator 307. Transformation module 309 includes all programs for transforming a Node. During an optimization step, transformation module 309 invokes STA 308 to evaluate each applicable transformation. Optimization module 302
includes all programs for executing the optimization steps (e.g. Phases 1-5). Optimization module 302 invokes transformation module 309 to implement local transformations.

Library analysis step 201 in FIG. 2 computes the appropriate operational output load ranges for the standard cells of each logic function. FIG. 4 is a flow diagram 400 representing library analysis step 201 of FIG. 2 in one embodiment. As shown in flow diagram 400 of FIG. 4, a user provides a desired relative "delay to area" tradeoff ratio (".alpha..sub.desired ") 402, the basic driver 403 of the given technology (typically, a small buffer cell in the library), a "load increment" .DELTA.C.sub.L value 404 (i.e., the finest load capacitance resolution for the library analysis), and the standard cell library file (.LIB) 405, including all performance characterization data. A relative "delay to area" tradeoff ratio (denoted .alpha..sub.i,j,k) is used to control cell selection. .alpha..sub.i,j,k is a measure of the delay advantage gained by replacing cell i by cell j under the condition of an output load k. Generally, a lower .alpha..sub.i,j,k results in a design optimized towards higher speed performance. Conversely, a higher .alpha..sub.i,j,k results in a design optimized towards reducing silicon area.

At step 401, the standard cells are grouped according to logic functions (e.g., NAND, OR, NOR, AND, XOR, etc.). Standard cells included in the same logic function group are interchangeable with respect to logic function. Two cells belong to the same function group if they have the same number of input and output terminals or "pins", perform the same logic function and provide, at each output pin, the same output "sense"--i.e., negative or positive logic. In addition, among the logic function groups., groups that perform "complementary" logic functions (e.g., AND and NAND) are identified. Standard cells in complementary logic function groups are interchangeable by the insertion of an inverter. Step 401 further identifies: (a) buffers, inverters, and primary input and output cells (i.e., registers, flip-flops and other state elements) in the cell library; (b) for each state element, clock signal terminals and the timing requirement between the clock terminal and each input or output terminal of the state element; (c) for each cell, the area of the cell, the drive strength--i.e., delay as a function of load--of each output terminal and the loading of each input terminal; and (d) for each combinational logic cell, a propagation delay.

After the function groups are identified, library analysis step 201 examines all function groups individually (i.e., step 406 of FIG. 4). For each function group (selected at step 408), a zero-load cell delay is calculated for each standard cell within the function group (step 409). In the following, the delay for a standard cell i driving an output load C.sub.L is denoted by D(i, C.sub.L). Under this convention, the zero-load cell delay for cell i is denoted D(i, 0). The zero-load cell delay D(i, 0) of a given standard cell i can be obtained, for example, using delay calculator 307 of FIG. 3 by evaluating the standard cell's delay response when driven by basic driver 403 with an ideal rising or falling transition. In one embodiment,-the standard cell's delay responses are estimated for both rising and falling transitions. Delay calculator 307 is discussed in further detail below.

At step 410, the mean value D.sub.m (0) of all zero-load delays in a function group and the mean area A.sub.m of all cells in that function group are computed. At step 411, the cells in the function group are sorted according to their drive strengths (e.g., in order of increasing area). The next steps (i.e., steps 412-421) find the operating ranges of the cells in the function group. The operating range of each cell is defined between a "low load" operating point (C.sub.LL) and a "high load" operating point (C.sub.HL)

The smallest driver (i.e., the driver with the smallest area) is examined first (step 412). This smallest driver is assigned a C.sub.LL of 0 pf (step 413) Beginning with a trial C.sub.HL value of .DELTA.C.sub.L, the C.sub.HL of the cell is found iteratively by calculating, at step 415, the .alpha..sub.i,j,k 's between the current cell i and all other stronger drive cells (j being the running index for these stronger drive cells) under the condition of an output load value k=C.sub.HL. After each iteration of steps 415 and 416, the value of C.sub.HL is increased by .DELTA.C.sub.L (step 417).

An .alpha..sub.i,j,k is calculated according to the following equation: ##EQU1##

in which, D(i,k) and D(j,k) are respectively the delays of cells i and j under a load k, D.sub.m (0) is the mean value of all zero-load delays for cells in logic function group, A(i) and A(j) are the areas of cells i and j, and A.sub.m is the mean area of all cells in the function group, as mentioned above.

If a cell j is found such that .alpha..sub.i,j,k exceeds .alpha..sub.desired, the current C.sub.HL is the "high load" operating point for cell i (step 418). Cell j, which has the largest .alpha..sub.i,j,k that exceeds .alpha..sub.desired, is selected (step 419) as the cell to operate in the next operating range, with a C.sub.LL value assigned the current C.sub.HL value (step 420), and an initial C.sub.HL equaling the current C.sub.HL plus .DELTA.C.sub.L (step 414). The next function group is selected (step 406) after all the cells in the present function group providing coverage for the operating ranges of interest are identified (as determined by step 421). Library analysis step 201 completes after all function groups are processed (step 407).

FIGS. 5a and 5b illustrate the results of applying process flow 400 to compute the operating ranges for standard cells in a NAND group. FIG. 5a shows the drive strengths of standard cells 501-504.

As shown in FIG. 5b, using process flow 400, the operating range of interest, zero to 2 pf, are found covered by standard cells 501-503, with operating ranges (0,C.sub.1), (C.sub.1,C.sub.2), and (C.sub.2, 2) pf.

As mentioned above, in one embodiment, timing analysis is provided by STA 308 of FIG. 3. STA 308 can be called upon to compute path delays in circuits that can include state elements and combinational logic elements. In one embodiment of the present invention, cell instances in the design database that are inserted or modified since the last timing analysis are marked. Incremental timing analysis is achieved by computing timing for these marked instances and instances whose timing is affected by such marked instances. Suitable techniques for providing this incremental timing analysis capability can be found, for example, in "An Algorithm for Incremental Timing Analysis," by Lee et al., published in The Proceedings of the 32.sup.nd ACM/IEEE Design Automation Conference (1995). FIG. 6 shows a network model 600 used in STA module 308. The signal arrival time at input terminal 602 is provided by an "entry delay" relative to a clock signal 606, based on an assumption that the input signal is driven by an output driver of an upstream state element 604. Similarly, the required signal arrival time at output terminal 603 is provided by an "exit delay", relative to clock signal 612, based on an assumption that the output signal is fed into an input terminal of second state element 605. Entry and exit delays are computed from clock terminals identified by a clock analysis step, such as clock analysis step 206 of FIG. 2. To accommodate interacting clocks, clock skews and offset between clocks are modeled in STA 308.

STA module 308 can use a primary input terminal, a clock terminal in a state element, or a terminal with user-specified constraints as a start timing point. Similarly, STA 308 can use a primary output terminal, a terminal with a defined setup time or a terminal with user-specified constraints as a timing end point.

Circuit 601 includes clusters 607 and 610, which are each a combinational circuit that couples an output terminal of a first state element and an input terminal of a second state element. Cluster 607 is a combinational circuit between flip-flops
604 and 608, and cluster 610 is a combinational circuit between flip-flops 608 and 609. Timing within a cluster is calculated "stage" by "stage" using, for example, delay calculator 307, which is mentioned above. A stage begins at the input terminals of a driver cell instance providing output signals, and ends at the input terminals of receiver cell instances receiving the driver cell instance's output signals. Instead of delay calculator 307, commercial timing calculators, such as "PrimeTime", from Synopsys Corporation, or the "Central Delay Calculator", from Cadence Design Systems can also be used.

To allow signal timing through a stage to be calculated, STA 308 requires (a) pin-to-pin cell delays from the cell library, which can be estimated, for example, in library analysis step 201 of FIG. 2, as mentioned above, and (b) interconnect parasitic models, which can be extracted, for example, by parasitic extraction step 204 of FIG. 2, as mentioned above. STA 308 also accepts from a user a list of false paths, which guides the timing analysis and allows more accurate results. STA 308
computes (a) for each input and output terminal, a "worst" slack value, (b) for each cell instance, a cell delay, and (c) at each output
 
Copyright 2006-2008 Patent Looker, LLC