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

• US 5,673,201 A
• Filed: 03/21/1996
• Issued: 09/30/1997
• Est. Priority Date: 09/29/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Malm, Richard LaVerne, Meiley, Charles L.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/621,258
• Time in Patent Office: 558 Days
• Field of Search: 364/489, 364/490, 364/491, 364/488, 364/550, 364/551.01, 395/500, 395/779, 395/133, 395/523
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A computer-implementable method for wiring congested areas in a VLSI design detects overflows indicating an area of congestion in the VLSI design and defines a bounding area around the area of congestion. Attachment points are created at locations where wires cross the bounding area and the entire bounding area, with the attachment points, is extracted from the VLSI design as a sub-design. Initial wire weights are assigned to wiring parameters associated with the sub-design. Thereafter, an iterative process is commenced to derive a wiring solution for the sub-design. In a first step of the iterative process, an attempt is made to wire the sub-design with the assigned wire weights. In subsequent steps, at least one wire weight is changed and a new attempt is made to wire the sub-design using the new wire weight values. The process continues in this manner until a wiring attempt completes successfully. The wired solution for the sub-design is then placed back into the VLSI design.

Claims

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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