Sub-problem extraction method for wiring localized congestion areas in VLSI wiring design

Claim 2

A computer implementable method for wiring congested areas in a VLSI design following a failed global wiring attempt, comprising the steps of detecting a congested area containing one or more identified invalid net segments in the VLSI design using the output of a global wiring program which has produced the failed global wiring attempt and which output contains a listing of said one or more identified invalid net segments; determining a bounding area for the congested area which is larger in size than said congested area; fixing perimeter attachment points at locations where wires cross the bounding area; extracting the bounding area and the perimeter attachment points as a sub-problem extraction area from the VLSI design; associating wiring parameters with the sub-problem extraction area; setting wire weights for the wiring parameters; wiring the sub-problem extraction area to derive a wired solution by: (a) attempting to wire the sub-problem extraction area in accordance with the wire weights, (b) in response to the wiring attempt completing unsuccessfully, changing at least one of the wire weights, (c) repeating sub-steps (a) and (b) until a wiring attempt completes successfully; and placing the wired solution for the sub-problem extraction area back into the VLSI design.

Claim 3

A computer-implementable method as recited in claim 1, wherein the congested area is detected by identifying blockages in the VLSI design.

Claim 4

A computer-implementable method as recited in claim 1, wherein the bounding area is in the shape of a rectangle.

Claim 5

A computer-implementable method as recited in claim 1, wherein a minimum bounding area is determined by identifying invalid net segments (ISEGs).

Claim 6

A computer-implementable method as recited in claim 1, wherein an enlarged bounding area is determined using valid net segments (VSEGs).

Claim 7

A computer-implementable method as recited in claim 1, wherein circuit blockages are captured inside the bounding area.

Claim 8

A computer-implementable method as recited in claim 1, wherein sub-step (a) further includes ripping out and rewiring portions of the sub-problem extraction area as required to successfully wire the sub-problem extraction area.

Claim 9

A computer-implementable method as recited in claim 1, wherein the wire weights include any of wire directions, wire jogs, level changes, wire level, maximum wire length, via count, via adjacency rules and net list order.

Claim 10

A computer-implementable method as recited in claim 1, further comprising, after the sub-step of wiring the sub-problem extraction area, a step of determining a figure of merit, the figure of merit being a function of the effect of the wire weights on one or more values representing overall wire length, via count, blockage count, or congestion within the sub-problem extraction area.

Claim 11

A computer-implementable method as recited in claim 9, wherein the sub-step of setting wire weights includes the step of changing the wire weights responsive to trends in the figure of merit, such that changes having the effect of globally decreasing the figure of merit are abandoned while changes having the effect of increasing the figure of merit are continued.

Claim 12

A computer-implementable method for wiring congested areas in a VLSI design following a failed global wiring attempt, comprising the steps of: detecting a congested area containing one or more identified invalid net segments in the VLSI design using the output of a global wiring program which has produced the failed global wiring attempt and which output contains a listing of said one or more identified invalid net segments; determining a bounding area for the congested area which is larger in size than said congested area; fixing perimeter attachment points at locations where wires cross the bounding area; extracting from said VLSI design the bounding area and the perimeter attachment points as a sub-problem extraction area; associating wiring parameters with the sub-problem extraction area; generating initial weight values for the wiring parameters including a maximum total weight value associated with the sub-problem extraction area; setting wire weight iteration range values; modifying in a series of iterative nested loops the maximum total weight followed by selected other wire weight values, and during each wire weight modification iteration, performing the following steps: (a) running said global wiring program based on the modified wire weight values; (b) testing for a zero overflow solution; (c) if a zero overflow solution is found, outputting one or more attributes associated with the zero overflow solution; and (d) if a zero overflow solution is not found, repeating sub-steps (a)-(d) using a next modified wire weight parameter.

Claim 13

A computer-implementable method for wiring congested areas in a VLSI design following a failed global wiring attempt, comprising the steps of: detecting a congested area containing one or more identified invalid net segments in the VLSI design using the output of a global wiring program which has produced the failed global wiring attempt and which output contains a listing of said one or more identified invalid net segments; determining a bounding area for the congested area which is larger in size than said congested area; fixing perimeter attachment points at locations where wires cross the bounding area; extracting from said VLSI design the bounding area and the perimeter attachment points as a sub-problem extraction area; associating wiring parameters with the sub-problem extraction area; generating initial weight values for the wiring parameters including a maximum total weight value associated with the sub-problem extraction area; setting wire weight iteration range values; modifying in a series of iterative nested loops the maximum total weight followed by selected other wire weight values, and during each wire weight modification iteration, performing the following steps: (a) running said global wiring program based on the modified wire weight values; (b) testing for a zero overflow solution; (c) if a zero overflow solution is found, outputting one or more attributes associated with the zero overflow solution; and (d) if a zero overflow solution is not found, repeating sub-steps (a)-(d) using a next modified wire weight parameter.

Claim 14

A computer-implementable method as recited in claim 11, wherein the congested area is detected by identifying blockages in the VLSI design.

Claim 15

A computer-implementable method as recited in claim 11, wherein the bounding area is in the shape of a rectangle.

Claim 16

A computer-implementable method as recited in claim 11, wherein a minimum bounding area is determined by identifying invalid net segments (ISEGs).

Claim 17

A computer-implementable method as recited in claim 11, wherein an enlarged bounding area is determined using valid net segments (VSEGs).

Claim 18

A computer-implementable method as recited in claim 11, wherein circuit blockages are captured inside the bounding area.

Claim 19

A computer-implementable method as recited in claim 11, wherein the step of modifying wire weight values further includes ripping out and rewiring portions of the sub-problem extraction area as required to successfully wire the sub-problem extraction area.

Claim 20

A computer-implementable method as recited in claim 11, wherein the wire weights include any of wire directions, wire jogs, level changes, wire level, maximum wire length, via count, via adjacency rules and net list order.

Claim 21

A computer-implementable method as recited in claim 11, further comprising, after the step of finding a zero overflow solution, a step of determining a figure of merit, the figure of merit being a function of the effect of the wire weight values on one or more values representing overall wire length, via count, blockage count or congestion within the sub-problem extraction area.

Claim 22

A computer-implementable method as recited in claim 19, wherein the sub-step of generating initial values for wire weight parameters includes the step of generating wire weight values responsive to trends in the figure of merit, such that changes having the effect of globally decreasing the figure of merit are abandoned while changes having the effect of increasing the figure of merit are continued.

Claim 23

A computer-implementable method for wiring congested areas in a VLSI design following a failed global wiring attempt, comprising the steps of: detecting a congested area containing one or more identified invalid net segments in the VLSI design using the output of a global wiring program which has produced the failed global wiring attempt and which output contains a listing of said one or more identified invalid net segments, said congested area having a plurality of net pairs of varying length; determining a bounding area for the congested area which is larger in size than said congested area; fixing perimeter attachment points at locations where wires cross the bounding area; extracting the bounding area and the perimeter attachment points as a sub-problem extraction area from the VLSI design; associating wiring parameters with the sub-problem extraction area; setting empirically determined, starting wire weight values for the wiring parameters; commencing a sub-problem extraction area wiring attempt by executing said global wiring program using said starting wire weight values as input: if said sub-problem extraction area remains congested, adjusting said wire weights by swapping selected net pairs in said sub-problem extraction area with a same length and rewiring the sub-problem extraction area until all net pairs of each length have been tested; and if said sub-problem extraction area still remains congested, iteratively adjusting other wire weight values over a range of values above and below the starting weight values in a series of nested loops until a zero overflow solution is found.

Claim 24

A computer-implementable method for wiring congested areas in a VLSI design following a failed global wiring attempt, comprising the steps of: detecting a congested area containing one or more identified invalid net segments in the VLSI design using the output of a global wiring program which has produced the failed global wiring attempt and which output contains a listing of said one or more identified invalid net segments, said congested area having a plurality of net pairs of varying length; determining a bounding area for the congested area which is larger in size than said congested area; fixing perimeter attachment points at locations where wires cross the bounding area; extracting the bounding area and the perimeter attachment points as a sub-problem extraction area from the VLSI design; associating wiring parameters with the sub-problem extraction area; setting empirically determined, starting wire weight values for the wiring parameters; commencing a sub-problem extraction area wiring attempt by executing said global wiring program using said starting wire weight values as input: if said sub-problem extraction area remains congested, adjusting said wire weights by swapping selected net pairs in said sub-problem extraction area with a same length and rewiring the sub-problem extraction area until all net pairs of each length have been tested; and if said sub-problem extraction area still remains congested, iteratively adjusting other wire weight values over a range of values above and below the starting weight values in a series of nested loops until a zero overflow solution is found.