Method of estimating wire length including correction and summation of estimated wire length of every pin pair

• US 6,099,578 A
• Filed: 03/02/1998
• Issued: 08/08/2000
• Est. Priority Date: 08/25/1997
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Itoh, Toshiaki
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): JOYCE, MARGARET M
• Application Number:
  US09/033,934
• Time in Patent Office: 890 Days
• Field of Search: 395/500.05, 395/500.06, 395/500.07, 395/500.11, 395/500.13, 395/500.14, 716/4, 716/5, 716/6, 716/10, 716/12, 716/13
• US Class Current: 716/108
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

In a method of estimating wire length allowing highly precise estimation of the estimated wire length of a net, an object net is selected. Thereafter, the object net is developed into pin pairs. For each of the pin pairs, a subcircuit satisfying a prescribed relation with the pin pair is extracted from the semiconductor integrated circuit. From the subcircuit, information necessary for estimating wire length of the pin pair (number of nets in the subcircuit and total area of macro cells in the subcircuit) is extracted. Based on the extracted information of the subcircuit, estimated wire length of the pin pair is estimated. Based on the estimated wire length of the pin pair, estimated wire length of the object net is estimated.

Claims

1. A method of estimating wire length, comprising the steps of:

defining a net on a semiconductor integrated circuit and extracting pin pairs from said net, said pin pairs represented by an edge between any pair of nodes of a complete graph in which macro cells on the net serve as nodes;

estimating wire length of each of said pin pairs; and

estimating wire length of said net based on the estimated wire length of each of said pin pairs;

wherein

said step of estimating the estimated wire length of each pin pair includes the steps of

extracting a subcircuit satisfying a prescribed relation with a pin pair which is an object of processing, and

estimating wire length of said object pin pair based on a characteristic of said subcircuit.

2. The method of estimating wire length according to claim 1, wherein:

said step of extracting said subcircuit includes the steps of

extracting, as the subcircuit, said object pin pair and a macro cell connected to said object pin pair, said subcircuit including an externally connected cell connected to a pin pair outside said subcircuit,

extracting a macro cell connected to said externally connected cell,

classifying the macro cell connected to said externally connected cell into an already-searched macro cell or a not-yet-searched macro cell,

determining whether a number of said already-searched macro cell and a number of said not-yet-searched macro cell satisfy a prescribed relation,

completing processing using the already-searched macro cell and a pin pair as the subcircuit for said object pin pair when said prescribed relation is satisfied, and

adding a pin pair and a macro cell classified as a not-yet-searched macro cell to the subcircuit and returning to said step of extracting when said prescribed relation is not satisfied,

wherein the pin pair added in said adding step connects the macro cell classified as not-yet searched with an outer peripheral cell in the subcircuit.

3. The method of estimating wire length according to claim 2, wherein:

said step of determination includes the steps of

determining that said prescribed relation is satisfied when number of said already-searched macro cell is larger than number of said not-yet-searched macro cells, and

determining that said prescribed relation is not satisfied when the number of said already-searched macro cell is not larger than the number of said not-yet-searched macro cells.

4. The method of estimating wire length according to claim 1, wherein:

said step of estimating wire length of said object pin pair includes the steps of

based on number of pin pairs of the net in said subcircuit and total sum of areas of macro cells in said subcircuit, calculating minimum area allowing placement and wiring of said macro cells in said subcircuit, and

based on said minimum area, obtaining a value changing in proportion to boundary length of a rectangle having said minimum area as the estimated wire length of said object pin pair.

5. The method of estimating wire length according to claim 1, wherein said step of estimating wire length of said net includes:

removing from the extracted pin pairs pin pairs not corresponding to designated wiring portions,

estimating a total sum of wire lengths between said pin pairs and

subtracting from said total sum an estimated wire length portion corresponding to wire length portions shared by said pin pairs.

6. The method of estimating wire length according to claim 1, further comprising the steps of:

based on the estimated wire length of said pin pair, calculating resistance value of said pin pair;

based on the estimated wire length of said net, calculating capacitance value of said net; and

based on the resistance value of said pin pair and the capacitance value of said net, calculating delay time when a signal passes through a signal path on said net.

7. The method of estimating wire length according to claim 6, further comprising the step of:

comparing said delay time with a constraint value determined based on design rule, and extracting any signal path not satisfying the design rule.

8. The method of estimating wire length according to claim 1, further comprising the steps of:

based on the estimated wire length of said net, calculating capacitance value of said net; and

based on the capacitance value of said net and a prescribed net signal change rate, calculating power consumption of said net.

9. The method of estimating wire length according to claim 1, further comprising the steps of:

calculating total sum of estimated wire lengths of said net existing in said semiconductor integrated circuit; and

based on the total sum of the estimated wire lengths of said net and areas of aluminum patterns occupied by macro cells in said semiconductor integrated circuit, calculating minimum area allowing placement and wiring of said macro cells in said semiconductor integrated circuit.

10. The method of estimating wire length according to claim 1, further comprising the steps of:

classifying said net in accordance with fan out number of said net; and

calculating an expected value of estimated wire length of said net for each fan out number, in accordance with a prescribed rule.

11. A method for estimating wire length on a semiconductor integrated circuit, comprising the steps of:

selecting an object net of which wire length is to be estimated, the object net including a plurality of macro cells and at least one wire interconnecting said macro cells;

extracting at least one pin pair from said object net, wherein each pin pair represents an edge between nodes of a complete graph derived from said macro cells which serve as nodes of the complete graph;

selecting an object pin pair from said object net;

extracting all macro cells externally connected by said pin pairs to said first and second macro cells;

classifying said extracted macro cells included in said subcircuit as already-searched macro cells, and said extract macro cells not included in said subcircuit as not-yet-searched macro cells;

comparing a first number of said already-searched macro cells and a second number of not-yet-searched macro cells, and

determining said object pin pair and two macro cells connected thereto as a subcircuit if said first number is larger than said second number and completing the process, otherwise returning to said object pin selecting step to select another pin pair from said net.