Sub-Problem Extraction Method for Wiring Localized Congestion Areas in VLSI Wiring Design

The present invention relates generally to computerized methods for wiring VLSI designs, and more particularly to methods for wiring localized congestion areas following a failed VLSI global wiring attempt.

Wiring or "routing" is concerned with finding paths between points in a circuit which may represent the terminals of processing elements arranged at selected locations on a circuit substrate. For wiring complex circuits such as VLSI designs, automated wiring programs are used due to the tremendous complexity involved. Such designs include many thousands of signal paths arranged on multiple layers, with vias being provided between layers. FIG. 1 graphically illustrates a very simple wiring problem which is to be solved. Here a grid system is shown where at most one signal wire can be placed at each grid point. The grid is scaled so that the center to center distances for the wires meets the constraints imposed by technology ground rules. In FIG. 2, the layout is redrawn to indicate grid points which contain wires, referred to as blockages, by cross-hatched grid points. Assuming it is desired to find a path from A to B, it can be seen that this problem corresponds to that of finding a path through a maze. Conventional routing procedures attempt to find a minimal cost path in the maze between two points, if such a path exists. Cost can be quite general, and can depend on such factors as length, density, number of jogs and other parameters.

In some cases, determination of the minimum path length may be of paramount concern. In FIG. 2, starting with grid point A, cumulative cost values are assigned to successive unblocked grid points. This process terminates when grid point B is reached and the lowest cumulative cost value at that grid point is indentified. To find a path, grid points are retraced from B to A, as shown in FIG. 3. In other cases, the shortest path length is not always the optimum path between points in a circuit. Other design parameters, such as preferred wiring directions, the number of vias and other factors may influence determination of the optimum path. By strategically assigning cost or weight values corresponding to these design parameters, preferred direction routes can be quickly obtained. Such costs can include:

1. The cost of using an individual grid point. This cost could be a function of density.

2. The cost of moving one grid point in a preferred direction on a layer.

3. The cost of moving one grid point in a nonpreferred direction on a layer.

4. The cost of a via, i.e., of going from one layer to another.

In FIG. 4, a grid point a and three of its neighbors b, c, and d are shown. Assume the individual grid point costs CI.sub.b, CI.sub.c and CI.sub.d for grid points b, c and d are 3, 2 and 1, respectively. Assume further that the cost of moving one grid point in the preferred direction on layer 1 CP.sub.1 =1, the cost of moving one grid point in the nonpreferred direction on layer 1 CN.sub.1 =5, and the cost of a via C.sub.v =12. The cumulative costs CC.sub.b, CC.sub.c and CC.sub.d for grid points b, c and d are computed below, where the cumulative cost CC.sub.a at grid point a is 20:

From grid point a, moving to grid point b results in the least cost of any direction. Using automated procedures, multiple wiring directions based on least cost analysis can be tested until a final path of least cost is determined. Such procedures, however, rapidly increase in complexity as a function of the number of grid points between the points to be joined. Indeed, existing programs for wiring complex VLSI designs may require days of CPU time to run.

Given the processing demands inherent in global wiring efforts, it is desirable to limit the number of wiring attempts involving large circuit segments. Often, however, localized design changes are required as a result of repositioning circuit components. It would be advantageous to provide a method for effecting such design changes without rewiring the entire design. It is also often the case that a global wiring program fails to complete successfully as a result of localized wiring failures or "overflows". A overflow condition exists when a wiring assignment violates one or more design rules. When overflows result, conventional wiring programs typically resort to multi-pass rip out and rewire attempts to reduce overflow count in the congested areas. These rewire attempts are usually based on the original wiring attack plan or wire weighting scheme which does not change across the design. If all the wires cannot be automatically routed they must be "embedded" manually. Due to a lack of local optimization, this process can result in wires that exceed maximum acceptable length and may provide poor design operation (i.e., slow performance). Moreover, manual wiring is performed by a human operator who usually sits at a display terminal that graphically illustrates the congestion area. The embedding process is painstakingly slow and error prone. Wiring solutions that appear correct on the display screen may actually violate one or more design ground rules, thus requiring rip out.

The present invention is directed to a computer implementable method for wiring congested areas in a VLSI design following a failed global wiring attempt. Additionally, the method can be used to rewire areas of localized design modification. In accordance with a preferred embodiment, overflows indicating an area of congestion in the VLSI design are detected and a bounding area is defined around the area of congestion. An "overflow" occurs when two points in a circuit cannot be wired because of blockages caused by circuit components or other wires. 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. Each wiring parameter corresponds to a direction that a wire can take and each weight represents a cost associated with taking that direction. Typical direction parameters include north-south, east-west, up-down (vias between layers), positive-negative diagonal and jogs. 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 "establish" or "map" wire paths through the sub-design using the assigned wire weights. In subsequent steps, selected wire weights are changed over a range of values above and below the starting value. Successive attempts are made to wire the sub-design using the new wire weight values. The process continues in this manner until a wiring attempt completes successfully, that is, until zero overflows remain. The wired solution for the sub-design is then placed back into the VLSI design.

FIGS. 1-4 illustrate a simple wiring problem to be solved by assigning cost values to different wiring directions in accordance with conventional wire routing methodologies.

FIG. 5 is a flow diagram illustrating a sub-problem extraction method in accordance with the present invention.

FIG. 6 is a diagrammatic view of a circuit board showing an area containing congestion overflows.

FIGS. 7A and 7B represent a flow diagram illustrating a method for changing wire weights in accordance with the present invention.

FIG. 8 is a diagrammatic illustration of the circuit board of FIG. 6 showing correction of the wiring overflow congestion area.

The sub-problem extraction method of the present invention is intended to operate externally of, and provide input data sets to, a conventional global wiring tool for wiring VLSI designs. Virtually any global wiring tool that operates by assigning wire weights corresponding to selected wiring parameters can be used. However, some of the parameters used by the sub-problem extraction method described herein may have to be modified to correspond to those used by the global wiring program. In practice, the sub-problem extraction method is implemented as a computer software program which could be written in any number of conventional programming languages including the Pascal language. It will be appreciated that a program written in accordance with the invention could be advantageously run on a variety of computer hardware platforms including the IBM line of 370 mainframe systems running under the MVS or VM operating systems, or a work station running under the UNIX or AIX operating systems. In this environment, the sub-problem extraction method generates successive data sets and iteratively calls the global wiring program to attempt a wiring solution using input wire weights, until a zero overflow solution is achieved.

Referring now to FIG. 5, components of a preferred sub-problem extraction method are illustrated diagramatically. As will be appreciated from the disclosure hereinafter set forth, the method adopts a divide and conquer approach to solving wiring congestion errors by identifying local problem areas and then modifying wire weight parameters until a unique solution is found for that sub-area. These weights are advantageously adjusted depending on specific local attributes such as physical layout of the high density areas. In a first step of the process a global wiring program is activated and one or more wiring attempts are made across the entire VLSI design using a set of general wire weights to complete as much of the wiring as possible, as shown in process step 100 of the flow diagram of FIG. 1. In the design of a VLSI chip, the global wiring program may require 10 to 20 CPU hours run time. Local areas of failure are usually not known to exist until several long wire runs have been completed. These local areas may remain non-wirable even after initial attempts are made to change the placement of wired items on the chip.

Following the one or more global wiring attempts, areas of congestion can be identified from the output of the global wiring program which conventionally includes row and column information (x and y coordinates) corresponding to areas of local congestion, a list of completed nets, a list of circuit node pairs to be wired and blockage data showing the placement of circuit components. An example of a congestion area is illustrated graphically in FIG. 6.

The selection of a sub-problem extration area occurs in process step 110. This step can be advantageously implemented as a computer software routine that extracts relevant information from the output of the global wiring program for the determination of a usable sub-area containing one or more overflow nets (a net is a wiring connection between two points or nodes in a circuit).

Each overflow net can be thought of as including two portions or segments, ISEGs (invalid net segments) and VSEGs (valid net segments). The VSEGs are valid wire sub-sections of the overflow net. The ISEGs are invalid wire sub-sections of the overflow net since they have ground rule violations. They indicate the path that the net would like to take and which is taken during the global wiring attempt in order to wire the overflow net. Ground rule violations occur when the net intersects another net on the same plane or when some other design parameters (e.g. minimum net spacing) are violated.

FIG. 6 illustrates a congestion area having two wiring layers. Wires in the first layer are shown as being (relatively) wide and wires in the second layer are shown as being (relatively) thin. There are four overflow nets shown in FIG. 6. A first overflow net extends between points a and a', a second overflow net extends between points b and b', and a third overflow net extends between points c and c', and a fourth overflow net extends between points d and d'.

The overflow net wired between points a and a' includes a series of valid and invalid segments. A first segment 200 is valid. The net becomes invalid at segment 202 because it must use a layer change to the second layer which is already being used. Segment 204, like 202, is also invalid because it overlies another wire that was previously positioned in the second layer. Segments 206, 208, 210, 212, 214, 216, 218 and 220 are all valid and contain no ground rule violations.

The overflow net between points b and b' also includes a series of valid and invalid segments. A first segment 230 is valid. A second segment 232 is invalid because it overlies a previously placed net in the second layer. The segment 234 is valid. The next segment 236, however, is invalid because it overlies a previously placed net in the first layer. Remaining segments 238 and 240 are both valid.

In the third net between points c and c' are additional valid and invalid segments. The segment 250 is valid. The succeeding two segments 252 and 254 are invalid. The subsequent segment 256 is valid. Segments 258 and 260 are both invalid while the final segment 262 is valid. In the fourth net between points d and d' the initial segment 270 is valid while the final segment 272 is invalid.

The coordinate size of the local or bounding area to be extracted can be specified based on the expected run time of the sub-area, which is preferably less than one second. In FIG. 6, a VLSI congestion area containing a minimum sub-area 300 could be based on extension and expansion of the ISEGS to the edge of the Figure. A slightly larger rectangular area 310 containing all of the VSEG net segments allows more possible net paths yet keeps the problem size small enough to create a complete solution. This allows conventional wiring techniques such as simulated evolution, simulated annealing or semi-exhaustive iteration to be applied to solve each of the sub-areas.

Following the determination of a suitable sub-area in process step 110, process steps 120 and 130 are performed to fix wire locations on the sub-area perimeter and to generate a net list of ordered node pairs requiring connection within the sub-area. In process step 120, the wire locations for the non-failed nets are fixed on the bounding box for the area using the coordinate positions that the net wires cross the box as determined from the output of the global wire run. Preferably, the box will be large enough to allow all nets that pass into or out of the box to be allocated to a location on the perimeter. In process step 130, the overflow nets are allocated to the edge of the identified sub-area box using the coordinate positions of the VSEG portions of the overflow nets as determined from the output of the global wiring run. In process step 140, blockage data including the coordinate location and size of circuit components are captured inside the sub-area.

Once the sub-area net wire points and blockage data are identified, iterative techniques are used to solve each sub-problem. In process step 150, the sub-area problem as defined by the local net list and blockage data are input to the global wiring program. In process step 160 of the flow diagram, a first pass of a global wiring program is made using initialized values for wire weights corresponding to wire direction, wire jogs, level changes, maximum wire length, via count, via direction, net list order or other parameters as desired. These initial values are provided as input by the user and are empirically determined based on design constraints set by the user. For example, it may be a design goal to minimze overall wire length. The initial wire weight values are selected to best achieve that goal. Other design optimization goals could result in the selection of different initial wire weight values. For example, the net list may be arranged in a preferred initial order of decreasing or increasing length. Following the selection of these initial input values, and upon determining that a zero overflow solution was not produced, the wire weights are adjusted in process step 165 and the global wiring program is again executed. This iterative process proceeds one or more times as necessary in process steps 160 and 165 until a zero overflow solution is produced.

In the preferred methodology, the strategy for responding to an overflow solution is to first swap each pair of nets with the same length and rewire the sub-area until all pairs of each length have been tested. This net list adjustment can be rapidly performed using a software routine that swaps the successive net list pairs and iteratively invokes the global wiring program to operate on the new input values. The swapping of net list pairs may produce a zero overflow case. If not, then iteration on the other wire weights, which may include a maximum total weight value, is performed until a zero overflow solution is found. By starting with a "best guess" at the wire weights and slowly increasing the maximum allowable wire weighted distance (global weight value) before rip out and rewire, a solution may be rapidly produced. If not, the wire weights are successively adjusted over a range of values above and below the starting wire weight values. Once zero overflows are found, the result is captured as a solution subset. The captured result is provided in process step 170 as a sub-cell of the design and "interconnected" to the initial incomplete wire image by incorporating the solution subset in the global design. If additional congestion areas exist, the process returns via path 180 to step 110. Once all areas have been completed, and the final design is completely wired with no overflows, the sub-problem extraction process is terminated in step 190.

Referring now to FIGS. 7A and 7B, a procedure for altering wire weight values as performed in process step 165 is illustrated in more detail. This procedure is also shown in pseudocode form in Appendix A hereto. It is intended for operation with any conventional global wiring program which utilizes wire weight values including weight values indicating wire direction, jogs, level changes and wire length. The wire weighting procedure starts in process step 400 and proceeds to initialization step 410. In step 410, the program reads a previously generated master test file TEST containing initial wire weight values. A sample TEST file is illustrated below. It is generated using empirically determined wire weight values provided by a user, and contains wire weight information for a VLSI design consisting of two levels identified as "plane 1" and "plane 2". The wiring parameters of interest in this example are NS=north-south, EW=east-west, UP=up, DN=down, PD=positive diagonal, ND=negative diagonal, and J=jog. There is also a maximum total weight value (shown in line four of the TEST file). The TEST file is arranged in the following format:

In line (3) of the TEST file, an "L" character indicates that the numerical value in line (4) represents a maximum length of a wire. If line (3) contains an "F" character, the value in line (4) is the factor by which the "manahattan" (minimum) distance between the nodes is multiplied, to obtain the maximum length. The "L" character sets a maximum length for all nets. The "F" character allows a maximum length to be set for each net.

The initialization step 410 is illustrated in lines 4-15 of the pseudocode in Appendix A. In process step 420, a direction value "u" is read to indicate the direction to change the global weight value during the wiring iteration process. This process step spans lines 16-25 of the pseudocode in Appendix A. Lines 26-38 of the pseudocode represent process step 430 wherein the wire weight iteration range values are set. These range values represent the amounts the wire weights will be incremented and decremented during the process. As indicated in the pseudocode, the two 45 degree wire weights PD and ND are not utilized in the example shown but could be added if desired. In process step 440, represented by lines 39-54 of the pseudocode of Appendix A, the starting maximum wire length and wire weight values are obtained from the TEST file. In line 41 of the pseudocode, the sixth line of the TEST file, representing the wire weights for wiring plane 1, are assigned to the variables sr1 sr2 sr3 sr4 sr5 sr6 and sr7. Similarly, in line 42 of the pseudocode, the wire weights shown on the eleventh line of the TEST file are assigned to the variables sg1 sg2 sg3 sg4 sg5 sg6 and sg7. Headings for the various weight values are printed out in line 45 of the pseudocode.

In process step 450, represented by lines 55-70 of the pseudocode in Appendix A, the NewWeight routine is called to adjust the wire weights. The NewWeight routine is set forth in pseudocode form in Appendix B hereto. As shown in the pseudocode of Appendix A, the NewWeight routine is called in a series of nested wire weight adjustment loops each corresponding to one of the wire weight values to be adjusted. For each of the wire weight parameters, NewWeight is called a number of times that equals the range value established in step 430. Each time NewWeight is called, a previous value for the wire weight of interest is passed to the NewWeight routine along with an index value. Depending on the index value, the wire weight is incremented and decremented by successively greater amounts over a range of values above and below the initial wire weight value until the associated wire weight range value is reached. The adjusted wire weight value is passed back to the pseudocode routine of Appendix A as a variable "rr.sub.-- ".

Once the NewWeight routine is initially called for each of the wire weight values, the returned wire weight values (which are unchanged from the initial TEST values the first time NewWeight is called) are placed back in the TEST file in process step 460, as illustrated in lines 71-73 of the pseudocode in Appendix A (subsequent calls to NewWeight will change the wire weight values). In process step 470, commencing at line 81 of the pseudocode of Appendix A, the allowable maximum total weight value associated with the sub-area is incremented (or decremented) by an index value as determined in process step 420. The iterative adjustment of the maximum total weight value represents an innermost loop of the wire weighting procedure. Each time the maximum total weight value is adjusted, the global wiring program is called in process step 480, represented by lines 95-104 of the pseudocode of Appendix A. In process step 490, the results of the wiring program are tested to determine whether a zero overflow solution has been found, as shown in lines 105-111 of the pseudocode of Appendix A. If a solution is found, the results are printed in process step 500 and the program terminates in process step 510, as illustrated in lines 107-110 of the pseudocode of Appendix A.

If no zero overflow condition is found, the procedure returns to process step 470 (line 81 of the pseudocode of Appendix A) where the maximum total weight value is again incremented (or decremented). The incrementation of the maximum total weight value proceeds for a specified number of iterations in process step 520 which are shown by way of example as equalling fifty in line 81 of the pseudocode of Appendix A. Following iteration on the maximum total weight value, and with no zero overflow solution being found, the procedure returns to step 450 and calls NewWeight to adjust one of the wire weight values. Iteration then begins again on the maximum total weight value. This iterative procedure is repeated in process step 530 until each of the nested wire weight adjustment loops has run over the range of wire weight values specified in process step 430.

At that point, if no solution has been found, the program ends at process step 540. The next step would be to expand the ranges set forth in step 430 and repeat the procedure. Preferably, however, the process terminates in step 510 and there is generated a zero overflow solution. This zero overflow solution will be characterized by various design attributes such as via count, overall length, blockage count and other design values produced as output by the global wiring program that are indicative of the quality of the wiring solution. Based on design goals, the zero overflow solution can be assigned a figure of merit representing a level of optimization of one or more selected design parameters. This figure of merit is empirically determined based on specific optimization goals. Thus, different figures of merit could be calculated for each non-overflow solution depending on the desired optimization values.

The figure of merit is used to compare successive zero overflow solutions generated by changing one or more initial wire weight parameters in the TEST file and rerunning the subwiring program described above. Each time the subwiring program determines a zero overflow solution, the solution can be assigned a figure of merit representing the effect of changing wire weights on one or more values such as overall length, via count, blockage count and congestion within the sub-design. Wire weight changes having the effect of decreasing the figure of merit can be abandoned while changes having the effect of increasing the figure of merit can be continued. Eventually, a listing of zero overflow solutions can be generated and a desired solution representing an optimization of selected design parameters may be chosen for insertion into the final design. An example of such a listing, representing outputs of the pseudocode process of Appendix A, is shown in Appendix C hereto.

Accordingly, a novel sub-problem extraction method for wiring localized congestion areas in VSLI wiring designs has been shown and described. Advantageously, the method provides a novel solution for solving large wiring problems quickly and completely. While several preferred embodiments of the invention have been disclosed, it should be understood that modifications and adaptations thereof will occur to persons skilled in the art. Therefore, the protection afforded the invention should not be limited except in accordance with the spirit of the following claims. ##SPC1##