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

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.

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.