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

Claim 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.

Claim 2

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.

Claim 7

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.

Claim 8

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.