Automatic layout design method of wirings in integrated circuit using hierarchical algorithm

• US 5,583,788 A
• Filed: 04/21/1995
• Issued: 12/10/1996
• Est. Priority Date: 12/27/1991
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Kuribayashi, Mototaka
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/427,979
• Time in Patent Office: 599 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/468, 437/51, 357/45, 357/40, 257/499, 257/503, 257/208, 257/923
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: Y10S 257/923 with means to optimize electrical conductor current carrying capacity, e.g. particular conductor aspect ratio

Abstract

A method, according to a hierarchical processing used for a computer-aided design system, for automatically wiring a circuit by dividing a region into a plurality of coarse global grids. The automatic wiring method includes the steps of: setting up and calculating an evaluation function having therein a plurality of evaluation terms for indicating selectability by which the cut-line is preferentially selected so that a wiring congestion is most relaxed; giving weights to the respective plurality of evaluation terms and defining an evaluation function which totals the plurality of the evaluation terms; dividing the region into two by a cut-line having a minimum value in the evaluation functions; determining a position to cross all nets crossing the cut-line; and performing the above steps recursively and hierarchically until the divided regions become a predetermined minimum size.

Claims

1. A method for automatically wiring a circuit by dividing a region into a plurality of coarse global grids and by dividing cut-lines which are inserted and set on boundaries of the global grids and are crossed by a wiring net, the method, according to a hierarchical processing used for a computer-aided design system, comprising the steps of:

setting up and calculating an evaluation function having therein a plurality of evaluation terms for indicating selectability by which the cut-line is preferentially selected so that a wiring congestion is most relaxed;

giving weights to the respective plurality of evaluation terms and defining an evaluation function which totals the plurality of the evaluation terms, wherein the evaluation terms include

a first evaluation term which is weighted such that a cut-line is more likely to be selected when a shape of the divided regions is close to a square; and

a second evaluation term which is weighted such that a cut-line having a most congested wiring is likely to be selected, based on a number of nets crossing the cut-line and a number of wirings capable of passing therethrough;

dividing the region into two by a cut-line having a minimum value of the evaluation function;

determining a position to cross all nets crossing the cut-line; and

performing the above steps recursively and hierarchically until the divided regions become a predetermined minimum size.

2. The method of claim 1, wherein the evaluation terms further comprise:

a third evaluation term in which a cut-line not involving a wiring-prohibited area is likely to be selected when there exists the wiring-prohibited area occupying the region.

3. The method of claim 2, wherein the evaluation terms further comprise:

a fourth evaluation term in which a cut-line not involving a wiring-prohibited area and having a greater degree of being away from the wiring-prohibited area is likely to be selected when there exists the wiring-prohibited area occupying the region.

4. The method of claim 2, wherein the third evaluation term is characterized in either that a cut-line involving the prohibited area is likely to be selected or that a cut-line closer to a center of the prohibited area is likely to be selected.

5. The method of claim 1, wherein the setting up and calculating, giving weights and defining the evaluation function, and dividing steps comprise the steps of:

(a) calculating a wire capacity of each grid boundary;

(b) obtaining all cut-lines in the region;

(c) calculating an evaluation function involving an aspect ratio of the region;

(d) calculating an evaluation function involving a number of cut-nets and a total wire capacity on a cut-line, a cut-net being a net which is involved with a single cut-line;

(e) calculating an evaluation function involving a prohibited area if any;

(f) calculating a value of total cost obtained by the above steps;

(g) selecting the cut-line having a most favorable value of an evaluation function and dividing the region with the selected cut-line; and

(h) determining a position of a net crossing the selected cut-line.

6. A method for automatically wiring a circuit containing a macro-block, the circuit comprising first and second layers for wiring, wiring being prohibited in the macro-block on the first layer, by dividing by a cut-line a region having the macro-block into a plurality of coarse global grids and by dividing the circuit by cut-lines which are inserted and set on boundaries of the global grids and are crossed by a wiring net, the method, according to a hierarchical processing used for a computer-aided design system, comprising the steps of:

generating a segment passing from an end to another end of the macro-block on a net which involves the cut-lines crossing the macro-block when wiring in the macro-block on the second layer is permitted;

regarding both ends of the generated segment as pseudo terminals; and

performing the above steps recursively and hierarchically until the divided regions become a predetermined minimum size.