JP3068892B2 - Automatic wiring method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a wiring method for a semiconductor integrated circuit or a printed circuit board, and more particularly to an automatic wiring method using a computer.

[0002]

2. Description of the Related Art At present, an automatic wiring program is an essential design tool for a layout design of a large-scale integrated circuit (LSI) in order to shorten a design period and increase a circuit scale. Many methods have been proposed so far as automatic wiring algorithms. Typical examples are Lee's maze algorithm, line search algorithm, channel wiring algorithm, and hierarchical algorithm.

[0003] Among these methods, Lee's maze algorithm is the oldest, and methods that speed up the original version have been widely used. One of the reasons is that it has an excellent search ability to always find a wiring route if a solution exists, and that the solution can be obtained as the shortest wiring route.

[0004] However, it takes a long processing time, and if this algorithm is applied to a large-scale chip wiring area, an enormous amount of time of several days to several weeks is required.
Further, there is a demerit that the entire wiring cannot be completed depending on the method of determining the wiring order, such as a case where the wiring becomes impossible depending on which one of the plurality of nets is selected and wired in order.

[0005] On the other hand, the hierarchical wiring algorithm is much faster than the Lee algorithm in terms of processing time, and has the advantage that the result is independent of the processing order because the wiring target nets are handled simultaneously. is there. Those that fall into the classification of hierarchical algorithms having this feature include Burstein's method [1983] and Lauther's method [1988] as wiring from the top down and Marek-Sadowsk as wiring from the bottom up.
Ak's method [1984] has been proposed.

In the future, with the further automation of LSI design technology and the progress of process technology, a larger circuit will become one.
When a chip is mounted on a chip, the data scale handled by the wiring program increases, and the processing time increases accordingly. Therefore, an increasingly faster wiring algorithm is required to obtain a result in a practical time. Against this background, a hierarchical wiring algorithm is one of the most important algorithms for future large-scale data wiring because of its high speed.

However, since this hierarchical algorithm cannot see information on local wiring congestion, wiring cannot be performed in a certain hierarchy as the hierarchy goes down (top down) or up (bottom up). You may encounter the situation. Further, when the two terminals are in a linear positional relationship and are located at both ends of the chip, it takes a lot of time to obtain the result of wiring in a straight line. Further, when the obtained wiring results are viewed, compared with the result of the sequential wiring, there is a drawback that a redundant wiring path may have an unnecessary number of bends in many cases.

Hereinafter, the Lauter's algorithm which repeats two divisions for a wiring region is selected as an example of a hierarchical algorithm, and a conventional wiring method will be described using this algorithm as an example.

In general, the wiring problem is divided into two stages, detailed wiring and schematic wiring. In the rough wiring, a rough wiring grid is set on the entire surface of the chip to determine a rough wiring path of each net. In the detailed wiring, based on the result of the schematic wiring, wiring is performed in a wiring area of a part of the chip in consideration of via setting, design rule restrictions, and the like. The general wiring will be described below without loss of generality, but the same can be applied to the detailed wiring.

Now, as shown in FIG. 30A, a wiring grid (dotted line in the figure) for detailed wiring is placed in a wiring area D on the chip.
Is defined, a general grid as shown in FIG. 30B is provided to determine the general wiring route of the net,
It is assumed that the information of the schematic wiring route is obtained as a segment of this grid. The wiring area surrounded by the general grid is called a general grid. In performing the general wiring, first, for each boundary side (Si, j, k in FIG. 30B) of this general lattice, a value (hereinafter, wiring capacity) indicating how many detailed wiring grids can pass through the boundary side Call). The general wiring problem is a problem of “determining wiring routes of all nets on a general grid without exceeding this wiring capacity”.

Next, a hierarchical wiring process based on the two-partitioning process will be described. FIGS. 31A to 31E are diagrams showing a state in which the wiring region is divided hierarchically.

In the processing in the first hierarchy, the wiring area D0,1 is divided into two by a vertical cut line (FIG. 31B), and the cut position is assigned to a cut net crossing this cut line. The considerations at this time are (1) that the wiring is not allocated without exceeding the wiring capacity of each boundary side Si, j, k on the cut line. (2) The wiring length of the cut net is minimized as much as possible. .

The problem is that the cost Ci, j, k (1) when each cut net is assigned to the boundary side Si, j, k is defined in a form depending on the wiring length, and is applied to all cut nets. On the other hand, it is solved as a problem that minimizes the total cost. This problem,
It can be solved by reducing it to a network flow problem.

As shown in the tree structure diagram of FIG. 32, this processing is sequentially performed recursively on each partial area, and the processing is advanced to the final hierarchy where the partial area has a final size.
This completes the entire wiring.

FIGS. 33 (a) to 33 (d) show how the wiring route is obtained in this manner. As shown in the figure, as the hierarchy deepens from the top down, cut positions (shaded in the figure) are allocated on the cut lines, and the wiring route of the net connecting the same potential terminals T is determined. FIG.
FIG. 34A shows a state in which cut lines are sequentially inserted into the wiring area, and the corresponding hierarchical structure is shown in FIG.
Shown in FIG. 34B is a tree diagram in which information indicating the position and direction corresponding to each cut line is set as a node, and similar information of the cut line set in a partial area divided by the cut line is set as a child node thereof. is there.

Hereinafter, the first problem of the conventional hierarchical schematic wiring will be specifically described. FIG. 35 is a diagram for explaining a problem in performing a straight wiring by a conventional hierarchical wiring method.

Now, let us consider a case where the two terminals T are located at a position where they can be connected by a straight line, and the wiring capacitance at each approximate grid boundary on the straight line from T to T is sufficiently large. At this time,
As the cut line is inserted as shown in the tree diagram of FIG. 35B, a cut position on the cut line is assigned. Among the nodes shown in FIG. 35 (b), the nodes 5a to 5g, which are shaded, are nodes involved in the process of allocating the cut net when obtaining the wiring route (T, T). The cut positions 1a to 1g are allocated by these seven allocation processes.

Each allocation process includes a process for obtaining a cut net, a process for determining a cost matrix, and a process for allocating a cut position on a cut line. Therefore,
A considerable amount of time is required until a linear wiring path as shown in FIG. If this is searched from the terminal T to the terminal T by sequential flat processing, the wiring path is determined by processing much less troublesome than this.

Even when an L-shaped wiring path is determined as a schematic wiring path as shown in FIG. 36 (a), the parentheses between terminals that are in a linear positional relationship when going down several layers from the top layer. A case occurs where a location is assigned. In general, general wiring can be connected by a simple wiring path such as an L-shape in many cases, so that a wiring path having a long straight line portion can be obtained. However, in order to obtain this result, a conventional method is used as described above. It was a complicated process.

Further, even when a wiring path with a small number of bends can be obtained, in the conventional hierarchical wiring method, the allocation processing is repeated independently for each partial area. This cannot be taken into account accurately, and the wiring path may have a large number of bends as shown in FIG.

Next, the second problem of the conventional hierarchical schematic wiring will be described with a specific wiring example. Now, it is assumed that, as shown in FIG. 19, a wiring grid D0,1 is provided with a 4 × 4 schematic lattice. In this wiring region, ● indicates terminals A to F, and the same potential terminals having the same terminal names are wired.

First, as a process of the first hierarchy, as shown in FIG. 20, a vertical cut line L is drawn at the center position of the wiring area D0,1 to divide the wiring area into two. There are four boundary sides of the general lattice on the cut line L, and the respective wiring capacitances C
Is 2. At this time, {B, C, D, E} are obtained as cut nets that cross the cut line L. The allocation cost is set to 0 for the boundary side within the minimum rectangle surrounding each cut net as shown in FIG. 21B, and a value proportional to the distance is given as the distance from the boundary increases.

For example, the boundary side in the minimum rectangle surrounding the cut net E is the uppermost side, and the cost is set to 0 for this side, and the cost of each side is set to 1 as the distance from the side becomes lower. Give a few. It is assumed that, after giving the costs in this way, as a result of solving the cost minimization problem, a wiring route indicated by a dotted line in FIG. 20 is obtained.

Next, the processing hierarchy advances one level, and the partial area D
Move to 1,1. FIG. 22 shows the state of the processing in this wiring area. In this partial area, the cut line set in the partial area D1,1 is determined from the terminal belonging to the inside and the cut position 1 (△ in the figure) on the cut line L set in the upper hierarchy D0,1. There are three cut nets that cross {A, B, D}. On the other hand, it is assumed that there are two boundary sides of the approximate grid on this cut line, and the wiring capacitance C of each is 1. In this case, the number of cut nets becomes larger than the wiring capacity and overflow occurs, so that it is not possible to determine a normal schematic wiring.

This is because the assignment of the cut position in the wiring area D0,1 of the upper hierarchy does not take into account the assignment of the partial area D1,1 of the lower hierarchy. This disadvantage becomes remarkable when ROM, RAM, prohibited wiring area, and the like are distributed in a chip in a complicated manner and wiring capacity is not uniform.

There are two or three methods to address this problem. For example, there is a method in which the setting position of the cut line is set to a position to be optimized without being determined as the center of the wiring area, and the division method of the hierarchical processing is selectively changed. However, there is no perfect index for positioning, and even if there is an index, when the wiring area is large, it takes a lot of processing time to check all the set positions. Further, the above problem cannot be fundamentally solved only by the positioning of the cut line.

Separately from this, a method in which a hierarchical wiring algorithm is used as initial wiring, a wiring capacity is determined after wiring, a portion where a wiring route is determined over the entire chip, and the wiring route is corrected. There is also. However, this method results in the use of most of the processing time in the second half of the rewiring processing, which sacrifices the advantage of the processing time of the hierarchical wiring algorithm, and is not a good method.

The first and second problems of the hierarchical wiring algorithm described above are the same in Burstein's method, which is a top-down hierarchical algorithm that repeats 2 × 2 division. In the method of Burstein, the wiring area is divided into four 2 × 2 partial areas in one hierarchy, and the wiring route in the 2 × 2 partial area is determined in each hierarchy. It is divided into 2 × 2 partial areas. However, this method also uses Laut
As in the case of the her method, a situation may occur in which wiring in the upper hierarchy becomes difficult in the lower hierarchy.

[0029]

As described above,
In the hierarchical wiring algorithm in the conventional automatic wiring method, even if the wiring path can be connected by a straight line, the processing is performed in many hierarchies, so that it takes a long processing time. Alternatively, there is a problem that a wiring result with many bends can be obtained. Further, there is also a problem that the number of cut nets exceeds the wiring capacity and a normal wiring path cannot be determined.

Therefore, the present invention has been made in view of the above circumstances, and has as its object to reduce the processing time and to reduce the total processing time by determining a straight wiring route by flat processing. It is an object of the present invention to provide an automatic wiring method capable of shortening a wiring length and normally determining a wiring path without making the number of cut nets exceed a wiring capacity.

[0031]

In order to achieve the above object, a first aspect of the present invention is to divide a wiring region provided with a plurality of nets connecting the same potential terminals into a plurality of partial regions, Based on the positional relationship between the cut position of the net that crosses the boundary between regions and the terminals connected by this net, it is classified as a net to be processed hierarchically or a net to be processed flat, and the wiring of the classified flat net A route is determined at a lower hierarchy two or more hierarchies lower than the hierarchy divided into the plurality of partial areas, and a flat net for which a wiring route cannot be determined is added to a net classified as a net to be hierarchically processed; The gist is to determine wiring routes of all nets by repeating the same processing hierarchically until the partial area becomes a desired minimum area.

In the second invention, a wiring region provided with a plurality of nets connecting the same potential terminals is divided into a plurality of partial regions, and wiring of a wiring target net which needs to be connected between the divided partial regions is provided. Calculate the degree of difficulty in determining the route, when it is determined to determine the wiring route of the wiring target net based on the calculated difficulty, solve the wiring problem of this wiring target net by a hierarchical algorithm, When it is determined that the wiring route of the wiring target net is not determined based on the degree of difficulty, the processing hierarchy is moved from the hierarchy obtained by dividing the partial region to the higher hierarchy to an upper hierarchy, and the processing is moved to the region before the division, The net which makes the wiring difficult in the area is determined, and the wiring path in the area before the division of the net is determined again so that the wiring in the partial area is facilitated. To determine the wiring route of the net to be routed, and to repeat the same processing hierarchically for the lower hierarchy than the hierarchy divided into the partial regions to determine the wiring route of all nets. And

[0033]

The automatic wiring method according to the first invention divides a wiring area to which a plurality of nets are given by a cut line. Based on the positional relationship between the cut position of the net crossing the cut line and the terminals connected by this net, the net is classified into a net to be processed hierarchically or a net to be processed flat. The wiring route of the flat net is determined in a lower hierarchy two or more hierarchies lower than the hierarchy in which the cut line is provided.

The flat net for which the wiring route could not be determined is added as a net to be processed hierarchically. The same process is repeated hierarchically until the partial area divided by the cut line becomes the minimum area, and the wiring routes of all nets are determined.

According to the second invention, a wiring region to which a plurality of nets are given is divided into a plurality of partial regions. The degree of difficulty in determining the wiring route of the wiring target net that needs to connect the partial areas is calculated. It is determined whether to determine the wiring route of the wiring target net based on the degree of difficulty. When it is determined to be determined, the wiring problem of this wiring target net is solved by a hierarchical algorithm, and when it is determined not to be determined, the processing layer is moved from the layer divided into partial regions to the upper layer, and the region before the division is Transfer processing.

In the upper hierarchy, a net which makes wiring in the divided partial area difficult is obtained. The wiring route of the net before being divided is determined again so that the wiring in the partial region is facilitated. Returning to the hierarchy divided into the partial areas, the wiring route of the wiring target net for which wiring was difficult is determined. The same processing is repeated hierarchically for the lower hierarchy than the hierarchy divided into the partial areas, and the wiring routes of all nets are determined.

[0037]

Embodiments of the present invention will be described below with reference to the drawings. First Invention FIG. 1 is a flowchart showing a procedure of an automatic wiring method according to a first invention. FIG. 7 shows a state of a certain hierarchy (generally, hierarchy level i) when the process is performed recursively.

First, in step S1, a process of allocating a cut position at level i is performed. As a specific procedure, (1) the direction and position of the cut line are set in the current area, and the cut net that cuts the cut line is selected from the non-cut nets.

(2) Based on the distribution state of the terminals connected by the cut nets, a cost value when the cut positions of each net are assigned to each boundary is calculated, and a cost matrix is obtained. (3) Using the assignment algorithm, the cut positions of all cut nets are assigned to each boundary on the cut line. At this time, the total cost is minimized and does not exceed the value of the wiring capacitance at each boundary.

As a method of giving the cost value, the wiring length is reflected, and the cost value is increased with respect to the assignment to the boundary of the cut line where the wiring length increases. Also,
The total cost is defined as the linear sum of the allocation costs of each net.
Standard algorithms for solving hcock-type transport problems can be employed.

Next, upon receiving the assignment result, the processing in step S2 is performed in two partial areas (Di + 1, 1, Di + 1, 2) of the level i wiring area (Di) divided by the cut line.
It applies to each of 2). The cut net set CutNet obtained in step S1 is classified into two types of sets in each partial region.

CutNet = HierachNet (1) + FlatNet (1)
(In partial area Di + 1,1) CutNet = HierachNet (2) + FlatNet (2) (partial area Di +
Here, the net of the flat net FlatNet
HierachN, which is a net processed in 3
The net of et is not processed in step S3, and moves to the lower hierarchy (level i + 1) as it is.

A set of cut nets is defined as HierachNet and FlatNe.
An example of a criterion for classifying into t will be described. For each cut net, a minimum rectangle (including straight lines and points) surrounding all the terminals existing in the partial area is obtained as a reference for classification. Based on the relative positional relationship between the shape and position of the minimum rectangle and the cut position, it is determined whether or not it is a flat net. FIGS. 2 to 6 show specific examples of entering a flat net. In the drawing, reference numeral 1 denotes a cut position of the cut net allocated in step 1, a part of a wiring route where a part indicated by 2 is wired by a flat algorithm, and a part indicated by 3 denotes a net which is wired by hierarchical processing. 4 is the minimum rectangle. L indicates a cut line, and T indicates a terminal.

Hereinafter, some conditions for a flat net will be described. Condition F1 “the width of the minimum rectangle is 0 in the direction orthogonal to the cut line and the minimum rectangle exists near the cut line” Condition F2 “The width of the minimum rectangle is 0 in the direction parallel to the cut line, and The minimum rectangle exists on the same straight line as the cut position. "In the example of the net in FIG. 2, the upper partial regions Di + 1 and Di + 1
(The minimum rectangle is composed of one terminal and both width and height are 0).
Is satisfied, so it is wired as a flat net. However, the lower partial area Di + 1, 1 is regarded as a hierarchical net because the minimum rectangle has a width and height of 0 but does not exist near the cut line L.

In the example shown in FIG. 3, the terminal T in the partial area is 2
Although an example of a net composed of terminals is shown, the condition F1 is satisfied by the upper partial regions Di + 1 and Di + 1. The net in FIG. 4 satisfies the condition F2 in the upper partial regions Di + 1 and Di + 1. Also,
FIG. 5 shows an example in which the terminals T of the partial regions Di + 1 and Di + 1 are composed of two terminals, but this also satisfies the condition F2.

In the above example, the flat net can be connected by a straight line. However, when the flat wiring needs to be searched not only in a straight line but also two-dimensionally, that is, the terminals are locally collected. If the conditions are spread out, the conditions can be determined as follows.

Condition 3 "The area of the minimum rectangle is small, and the cut position and the minimum rectangle are close to each other." FIG. 6 shows this example. In order to take advantage of the advantage that the processing does not depend on the net order, which is a feature of the hierarchical algorithm, this condition is such that a flat net having a small degree of freedom in the search range is selected. That is, when the wiring route has a degree of freedom, the wiring route is determined by a hierarchical process.

Next, step S3 of the processing flow will be described. This process is based on the FlatNet selected in step S2.
Is a process of wiring with a flat algorithm such as a line search method. In the case of the schematic wiring, the wiring capacitance may be 0 due to a wiring prohibited area or the like.
Connections are made while searching for a place where the wiring capacity at each schematic lattice boundary is positive. At this time, in the examples of FIGS. 2 to 5, restrictions are provided such that only a wiring path that can be connected in a straight line when wiring the cut position 1 and the terminal T is provided, so that the high-speed hierarchical processing is not lost. I do. These restrictions make the flat algorithm simple and fast.

In step S4, the data is classified as a flat net under the conditions 1 to 3, but the wiring that cannot be wired as a flat net because the wiring capacity is not positive is applied to the HierachNet.
Go to the set and perform hierarchical processing. Hereinafter, the above-described processes S1 to S4 are recursively repeated every time a cut line is set, and the process is completed when the partial area has the minimum size, thereby determining the wiring routes of all nets.

FIG. 7 is a diagram for explaining hierarchical processing according to the first embodiment of the first invention. As shown in FIG. 7 (a), in order to obtain a wiring path between these two terminals, a process of allocating a cut position 1d to a cut line is required once, and a straight wire 2 of a flat net is required twice. This is shown in FIG.
Compared with No. 5, the number of times the allocation algorithm is called is reduced from seven to one, so that a wiring result can be obtained at high speed.

Next, a second embodiment of the first invention will be described. FIG. 8 is a diagram for explaining the hierarchical processing according to the second embodiment. In this example, when flat wiring is performed in step S3, the search is not performed at the deepest level of the hierarchy (level 5 in the figure), but is performed from the current hierarchy (hierarchy i).
The above is a method of obtaining a flat wiring route at a level lower than the level less than (5-i).

FIG. 7 shows flat processing at level i + 2, which is two layers lower than the current layer (level i). In order to obtain the wiring route shown in FIG.
As shown in the tree diagram of FIG.
f and four times of flat wiring 2 are performed.

In the present embodiment, the case where the general wiring problem is dealt with among the wiring problems has been described. However, the portion corresponding to the wiring capacitance is set to 1 at all boundaries, and the detailed description is given. It can also be applied as wiring.

Second Invention FIG. 9 is a flowchart showing a procedure of an automatic wiring method according to an embodiment of the second invention. The wiring method shown in the figure is Route (O) which is a recursive processing program.
bj_Domain, level). As shown in FIG. 9, the wiring on the entire surface of the chip is subjected to this recursive processing. Wiring target area: Obj_Domain = chip area (step S11) Processing layer: level = top layer 0 (step S1)
2) Obtained by giving

FIG. 10 shows a route (Obj_Doma).
FIG. 7 is a flowchart showing the entire processing procedure (in, level). Hereinafter, details of the processing will be described based on the processing flow of FIG.

In FIG. 10, in the route processing, first, the wiring target area Obj_Domain is divided into N partial areas sub_domain [i] (step S).
21). In general, N = 2, N = 2 × 2 = 4, N = 3 × 3
= 9 and the like are applied. Next, a net straddling each partial area is determined as a target net to be processed in this hierarchy (step S22).

Further, the difficulty Dif_factor of the wiring when the wiring in this wiring area is performed at this level is calculated (step S23). For example, cut line 2
When based on the division processing, Dif_factor = α × (C−Nc) may be set. C is the sum of the wiring capacities at the boundaries of the approximate grid on the current cut line, Nc is the number of cut nets crossing the cut line, and α is a constant. Then, it is determined whether or not to wire the wiring area based on the index (step S24). For example, let α = 1 and wire
The critical value of “No” is set to 0, and wiring is performed if Dif_factor> = 0. Further, by changing the value of α, the critical value of wiring / non-wiring can be determined by foreseeing the wiring margin for performing detailed wiring in advance.

Next, if it is determined that wiring is to be performed, S
The wiring area Obj_Domai is obtained by the ove process.
The wiring problem of n is solved (step S25). In the Slave process, for example, when the division process by the cut line is repeated, the position crossing the cut line for all the target nets is solved as the cost minimizing network flow problem as described in (Prior Art). When this process is completed, the recursive function Route is applied to all partial areas (steps S26 and S27).

On the other hand, based on Dif_factor,
The processing when it is determined that the wiring area is not wired is a characteristic part of the present invention. In this case, first, in order to increase Dif_factor in the wiring of the wiring area, a process of reducing the number Nc of cut nets is performed. Therefore, a net (hereinafter referred to as Bad_Net) crossing the cut line inserted in the parent region of the current region is extracted from the Nc cut nets crossing the cut line of the current region (Obj_Domain) (step). S28).

Next, the processing hierarchy is moved up one level from the current hierarchy, and the processing is shifted to the parent area of the current area (hereinafter referred to as Par_Domain) (step S29). In the case of the previously determined net, a wiring route is determined for Bad_Net so that the wiring in the wiring area Obj_Domain in which the wiring is abandoned is facilitated (step S30). This process is S
olveH. The detailed flow is shown in FIG.

FIG. 11 will be described below. Bad_Ne
SolveH processing for t performs recursive processing. The basic functions of this processing are shown in FIGS.
As shown in (1), the wiring route of the cut net is corrected to reduce the amount of cutting the cut line that has caused an overflow in the lower hierarchy.

First, at the beginning of the processing, it is determined whether or not the target net to which such correction has been made can be corrected (step S31). This is, for example, the current hierarchy level l
A check is performed as follows based on the value of the wiring capacitance on the cut line of level.

Now, as shown in FIGS. 12A and 12B, the cut line L1 at the level level + 1 and the level level
There are 1 cut lines L2, and two portions where L2 is separated by L1 are L2b and L2t. The total wiring capacities at the boundary sides between L2b and L2t before the wiring path correction processing are C2b and C2t, respectively. Bad_Net is classified into a type A net {NetA} shown in FIG. 12A and a type C net {NetC} shown in FIG. 12B, and the numbers are Na and Nc, respectively: Bad_Net = {NetA} +} NetC ## {NetA} = Na, # {NetC} = Nc typeA net is, as shown in FIG. 12A, a cut position 1 (located on L2t) on a cut line L2 at L2b.
And can be modified to the type B wiring path. In addition, as shown in FIG. 12B, the type C net can be moved to the position of L2t from the cut position 1 (located on L2b) on the cut line L2, and can be corrected to the wiring path of type D. typeA net and typeC
The net indicates the cut position on the cut line L2 as L2.
Since t and L2b can be exchanged, it is determined whether or not the wiring route can be modified, for example, when Na ≧ Nc based on whether there is a margin in the L2b or L2t wiring capacity at the time of exchange. , C2b <Na-Nc When Na <Nc, if C2t <Nc-Na, the correction processing is disabled, and in other cases, the correction processing is enabled.

Next, if the wiring route cannot be corrected for the given target net, the process is moved to a layer one level higher than the given layer, and the correction is made in the upper layer. For this purpose, the process is described as SolveH (Par_Do).
main, Bad_Net, level-1) (steps S32, S33). As described above, the processing is shifted to the upper hierarchy until the correction becomes possible.

On the other hand, if it is determined that correction is possible,
At this level (Par_Domain), the wiring path is corrected for Bad_Net (step S34). Specifically, the following two methods (MOD
IF1, MODIF2).

(MODIF1) For all the nets in the set Bad_Net of the problem nets that have become difficult to route in the hierarchy below (MODIF1), the cost value is large for the assignment in which the wiring route to the problematic lower hierarchy occurs. Redefine the cost function form so that The passing wiring route is determined by solving the cost minimization problem again for the corrected cost matrix.

(MODIF2) Overflow value of wiring: O_value at the cut line in question
= The number of cut nets-the wiring route is changed for the net corresponding to the wiring capacity of the cut line. That is, FIGS. 12A and 12B
As shown in the above, the type A net-> type B net type C net-> type D net or type B net-> type A net type D net-> type C net is changed, and the wiring of the problematic cut line is changed. The overflow is set to 0. Here, (MODIF1) is
Since the entire Bad_Net is handled, there is a possibility that the number of cut nets in the opposite region may be increased according to the distribution of the margin (remaining) of the wiring capacity of the current cut line and the degree of increase in the cost value, thereby causing a situation in which wiring becomes difficult. Although there is a disadvantage that there is, there is a process to minimize the overall cost value on the current cut line with the correction of the wiring route, and at the same time, the correction position of the wiring route is determined by looking at the distribution of all the wiring capacitance on the cut line There are advantages to be determined.

On the other hand, (MODIF2) corresponds to FIG.
As shown in (c), when a type A net a and a type C net c are exchanged for one set of nets or one net as shown in (a), the type A net a Is exchanged for the type B net b, or the type C net c is exchanged for the type D net d as shown in FIG. Specific processing is shown in the flowchart of FIG. In the figure, L + and L- indicate the upper half and the lower half, respectively, when the current cut line is vertical.

In this modification processing (MODIF2), it is difficult to select a net that minimizes the total cost value because the net type is modified by selecting one net at a time. There is an advantage that the overflow of the wiring of the cut line can be reduced to 0, and the increase of the cut net in the opposite area can be minimized.

Actually, there is a realization mode in which one of these wiring path correction methods or when the same cut line is processed again, the processing is switched to the other processing.

In the processing described above, the type A net is changed to t
When a procedure such as the correction of the wiring route to the type B net is repeated, the problem of the wiring area on the opposite side which is in the same hierarchy but has a different wiring target area may be difficult. For example, when the wiring route is modified as shown in FIGS. 3A to 3C, the right sides of the two horizontal cut lines may be crowded. This is a problem that causes a loop in the recursive processing. A method for solving the problem will be described.

Now, it is assumed that the wiring area Di, j is divided as shown in FIG. 32 when the two division processing is repeated as shown in FIG. It is assumed that the recursive processing is realized by a depth-first processing procedure as shown in FIG. At this time, the numbers indicated by ○ indicate the order in which the cut lines are inserted. That is, processing is performed from the lower left of the partial area.

At this time, for example, when wiring cannot be performed at the cut line 8, the wiring path of the cut line 7 has already been determined. Therefore, returning to the cut line 6, when converting the type B net into the type A net or the type D net into the type C net as shown in FIGS. If not considered, there is a risk that processing will fall into a loop.

In the present invention, FIG.
If the assignment processing on the opposite side of the problem cut line is performed for the second time or more, the wiring route correction only in the case where the wiring capacity of the cut line on the opposite side for which assignment has already been completed has room (MODIF2) is made. (Steps S41, S42, S43), and if there is no room, the process proceeds to the upper hierarchy.

In the above-described wiring path correction processing, the processing (step S35 in FIG. 11) in the case where the corrected wiring path enters the wiring area to which the assignment has already been completed will be described with a specific example. Now, it is assumed that when the hierarchical processing is advanced in the order as shown in FIG. 15, the wiring of the cut line 8 becomes difficult as shown in FIG. At this time, a net for cutting the cut lines 1 to 8 is already assigned to the cut position as a cut pin.

Now, in order to perform the process of correcting the cut line 8, the process returns to the cut line 6, and the wiring route cannot be corrected at 6;
It is assumed that the correction of Net has been completed (solid arrow in FIG. 18).
At this time, the cut net 2 is
Since new wiring paths are generated in the partial area of the left child and its descendants, additional processing of these wiring paths is performed on the cut lines 3, 4, and 5 (the dashed line in FIG. 3).

On the other hand, in the cut line on the right side of the cut line 2 and its descendants due to the correction of the second wiring path, the wiring path associated with the correction of the second wiring path disappears in the first cut line. The processing of deleting these wiring paths is performed on the cut lines 6 and 7 (dotted lines in the figure). After these processes are completed, the recursive process So of the wiring route correction is performed.
Returning to the cut area 8 where veH (step S30 in FIG. 10) is called, the wiring is completed.

The processing flow described above will be described in detail with a specific wiring example. The first embodiment will be described as an example of a hierarchical processing method in which two divisions are repeated, that is, a hierarchical wiring in which a target area is divided into two partial areas by one cut line and a wiring path is determined from the top down.

Now, it is assumed that the wiring target areas D0 and D1 are given at a certain hierarchical level as shown in FIG. Now, as shown in FIG. 20, D0,
It is assumed that a cut line L perpendicular to 1 is drawn to the center position of the wiring area to divide the wiring area into two (step S2 in FIG. 10).
1). It is assumed that there are four boundary sides of the general lattice on the cut line L, and the wiring capacitance C of each is two. At this time, {B, C, D, E} are obtained as cut nets (step S22). Therefore, Dif_factor =
C−Nc = 8−4> 0, and the process proceeds to the process of wiring in this wiring region (steps S23 and S24).

A process Solve (D0,1, .DELTA.B, C,...) For solving the wiring problem (assignment problem) of the wiring region D0,1.
D, E｝, step S25) is, for example, as follows. For each cut net, as shown in FIG. 21, the allocation cost function is set to 0 for the boundary side within the minimum rectangle surrounding each cut net, as described in the background art, and the distance increases as the distance increases. A proportional value shall be set.

Thus, the wiring length can be made to correspond to the cost. FIG. 21A shows a state where each terminal is projected near the cut line, and FIG. 21B shows a cost function type of each net. Thereafter, it is assumed that the result of FIG. 20 is obtained when the cost minimizing assignment problem is solved.

Next, the processing hierarchy advances one step, and the partial area D
It moves to 1,1 (step S26). That is, processing Ro
ute (D1,1, level + 1). FIG. 22 shows the state of processing in this partial area. In this partial area, the net crossing the cut line of this partial area D1, 1 from the terminal belonging to the inside and the virtual cut positions 1B to 1E (△ in the figure) of the cut line L set in the upper hierarchy is ΔA. , B, D}.

On the other hand, it is assumed that there are two boundary sides of the approximate grid on the cut line, and the boundary capacitance C is 1 for each.
At this time, Dif_factor = C-Nc = 2-3 =
Since -1 <0, overflow occurs, and it is determined that the wiring problem of this level is not solved (step S24).

According to the flow of FIG. 10, first, a set of nets Bad_Net = {B, D} that makes wiring of the partial areas D1, 1 difficult is obtained (step S28).

Next, the hierarchy moves up one level, and moves to the parent areas D0,1 of the partial areas D1,1.
olveH (D1,1, {B, D}, level) (steps S29 and S30). This process proceeds as shown in FIG. When Bad_Net is classified into a type A net and a type C net, NetA = {D}, NetC =
{B}, Na = Nc = 1, C2b = (2-1) + (2-1) = 2, C2t = (2-
1) + (2-1) = 2, and since C2b> Na-Nc, this level lev
The processing shifts to the correction processing of the wiring route of el (steps S31 and S31).
34).

In the case of the route correction method MODIF1, the allocation cost function is corrected and re-allocated to the net {B, D} as follows. For the net B (net type NetC), the cost value of the lower boundary side of the cut line L is reset to δ = a sufficiently large value (for example, 4), while the upper boundary side is unchanged.

Conversely, net D (net type NetA)
, The cost value of the upper boundary side of the cut line L is reset to δ = 4, and the lower boundary side is unchanged. Thus, the cost function type is as shown in FIG. When the cost minimization problem is solved with respect to this cost function, the allocation results of B and D are as shown in FIG. At this time, there is no need to perform the processing of S35 in FIG.

Further, the processing is performed by SolveH (Domai
n, Bad_Net, level)
The process returns to level + 1 (partial area D1, 1), and the process of obtaining the wiring target net is executed again. Then D
If_factor = 2-1.gtoreq.0, and the process proceeds to Solve for solving the wiring problem of the partial area D1, 1 this time (step S25). Thus, the wiring process is completed.

Both sides D1,1, D of wiring area D0,1
After the assignment of the cut lines 1 and 2 is completed, FIG.
The following wiring path is obtained. The route modification method MO
The same applies when DIF2 is used as a wiring route correction process. As described above, according to the conventional technique, even when overflow occurs as shown in FIG. 22 and a normal schematic wiring path cannot be obtained, according to the automatic wiring method according to the second invention,
A complete wiring path can be obtained.

Next, as a second embodiment of the second invention, a wiring example will be described in which the completion of wiring is not completed at the level one level higher, but is completed two levels back.

Now, it is assumed that cut lines A to E shown by dashed lines are sequentially inserted into the wiring regions Di, j as shown in FIG. 26A, the hierarchical processing proceeds, and the wiring path is determined. FIG. 26B illustrates the hierarchical processing in a tree structure. Now, as shown in FIG. 27, when the processing shifts to the processing of the cut line LineE in the partial areas Di + 3 and 2, it is determined that the wiring is impossible (step S2).
4).

At this time, first, the parent area Di of LineE
When an attempt is made to modify the Bad_Net wiring path at +2, 1, there is no room for the wiring capacity above the Line C, and the wiring path: {T-X-Y-Z-T} is changed to the wiring path: {T-P-Y
It is assumed that the correction cannot be performed so that -ZT｝ (see FIG. 28) (steps S28 to S31).
As a result, the wiring route is changed so that the cut position Y of the cut line B is corrected, and the cut point Y is moved to the cut point Q (step S).
32, S33). As a result, the wiring route of this net is realized as the wiring route: {TQZZT}.

When the wiring route of the net T is completed in this way, the process returns to the routine (step S30) which called twice the recursive processing, and the partial area Di + 3, 2
Before the wiring moves to the lower hierarchy, a new net crossing the cut line D is generated due to the movement of the cut position from Y to Q before that. The allocation position W is determined (step S35). In this way, a wiring route: {TWQZZT} as shown in FIG. 28 is obtained.

As described above, in the second invention, the entire wiring can be completed by performing the rewiring processing at a plurality of levels. By performing the rewiring based on such hierarchical processing, it is possible to prevent a disadvantage that the processing time is enormous in the peeling and rewiring processing of the entire chip as in the related art.

The second invention can also be applied to the case where the hierarchical processing is performed by dividing the target area into N = 2 × 2, as in the Burstein method [1983]. This wiring area division processing method is described with reference to FIGS.
FIG. 29C shows the hierarchical structure in FIG. Also in this hierarchical processing, the processing flows shown in FIGS. 9 to 11 can be applied. However, the Solve process (step S25) in FIG. 10 is to solve the wiring route of the 2 × 2 wiring region by reducing it to an integer programming problem.

[0096]

As described above, according to the first aspect of the present invention, it is possible to obtain a wiring result with less bending since priority is given to the linear route at each level of the hierarchy. Means that the number of nets handled in hierarchical processing is small. Further, according to the second invention, the wiring route is corrected retroactively from the hierarchy where the problem occurred when the wiring processing was advanced to the upper hierarchy. Thus, it is possible to provide a high-quality automatic wiring route without losing the characteristics of the hierarchical wiring method for high-speed processing.

[Brief description of the drawings]

FIG. 1 is a flowchart showing a processing procedure of an automatic wiring method according to a first invention.

FIG. 2 is a diagram illustrating an example of a flat net and its wiring when the minimum rectangle is one terminal;

FIG. 3 is a diagram illustrating an example of a flat net and its wiring when the minimum rectangle is a straight line.

FIG. 4 is a diagram illustrating an example of a flat net and its wiring when the minimum rectangle is one terminal;

FIG. 5 is a diagram illustrating an example of a flat net and its wiring when the minimum rectangle is a straight line.

FIG. 6 is a diagram illustrating an example of a flat net and its wiring when the area of the minimum rectangle is small.

FIG. 7 is a diagram showing a state of hierarchical processing according to the first embodiment of the first invention.

FIG. 8 is a diagram showing a state of a second embodiment in the first invention.

FIG. 9 is a flowchart showing the entire processing procedure of the automatic wiring method according to the second invention.

FIG. 10 is a flowchart showing details of a Route process shown in FIG. 9;

FIG. 11 is a flowchart illustrating details of a SolveH process illustrated in FIG. 10;

FIG. 12 is a diagram for explaining a type of a net whose route is corrected.

FIG. 13 is a diagram illustrating an example of a route correction method.

FIG. 14 is a flowchart illustrating an example of a route correction method.

FIG. 15 is a tree structure diagram illustrating an example of a hierarchical processing order.

FIG. 16 is a flowchart illustrating a part of a process performed in the route correction process illustrated in FIG. 11;

FIG. 17 is a tree structure diagram showing the order of hierarchical processing until wiring becomes difficult.

FIG. 18 is a diagram for explaining an order in which routes are corrected.

FIG. 19 is a plan view of a wiring target area for explaining a wiring example according to the first embodiment of the second invention.

FIG. 20 is a diagram showing a state where a cut net of the wiring target area shown in FIG. 19 is obtained.

FIG. 21 is a cost function graph showing the cost value of each cut net obtained in FIG.

22 is a diagram showing a state where the processing hierarchy has moved to a partial region of the wiring target region shown in FIG. 20;

FIG. 23 is a cost function graph showing the cost value of the net shown in FIG. 22 after the route is corrected.

FIG. 24 is a diagram showing a result of assigning a net whose route has been corrected.

FIG. 25 is a diagram showing a wiring path finally obtained in the first embodiment of the second invention.

FIG. 26 is a plan view of a wiring region for explaining a second embodiment of the second invention.

FIG. 27 is a diagram showing a state of wiring processing in a partial region of the wiring region shown in FIG. 26;

FIG. 28 is a diagram showing a wiring path finally obtained in the second embodiment of the second invention.

FIG. 29 is a diagram for explaining another area dividing method according to the second invention.

FIG. 30 is a diagram showing a state where a wiring area is divided by a grid.

FIG. 31 is a diagram showing a conventional state of performing hierarchical processing while dividing a wiring region into two parts.

32 is a tree structure diagram illustrating a hierarchical process of the wiring region illustrated in FIG. 31.

FIG. 33 is a diagram showing a state in which a wiring path is obtained by a conventional two-division process.

FIG. 34 is a tree structure diagram of insertion of a cut line into a chip area and corresponding hierarchical processing.

FIG. 35 is a diagram for explaining a conventional method for obtaining a straight wiring route.

FIG. 36 is a view for explaining a conventional method of obtaining an L-shaped wiring route.

FIG. 37 is a diagram showing a state in which a wiring path having many bends is obtained by a conventional method.

[Explanation of symbols]

1,1a-1g, 1B-1E, X, Y, Z, W, P, Q
Cut position 2 Part of wiring route wired as flat net 3 Partial net wired as hierarchical net 4 Minimum rectangle 5a-5g Tree node A, B, C, D, E, T terminals L, L1, L2 L2b, L2t, LineA ~ Lin
eE cut line D, Di, j Wiring area a, b, c, d net Si, j Boundary side of approximate grid

──────────────────────────────────────────────────続 き Continued on front page (58) Field surveyed (Int.Cl. ⁷ , DB name) G06F 17/50 H01L 21/82

Claims (2)

(57) [Claims] A wiring region provided with a plurality of nets connecting the same potential terminals is divided into a plurality of partial regions, a cut position of a net crossing a boundary between the divided partial regions, and a terminal connected by the net Is classified into a net to be processed hierarchically or a net to be processed flatly, and the wiring route of the classified flat net is lowered by two or more layers from the layer divided into the plurality of partial regions. A flat net determined in the lower hierarchy and for which a wiring route could not be determined is added to a net classified as a net to be processed hierarchically, and similar processing is performed hierarchically until the partial area becomes a desired minimum area. An automatic wiring method characterized by determining wiring routes of all nets by repeating. 2. A method for dividing a wiring area provided with a plurality of nets connecting the same potential terminals into a plurality of partial areas and determining a wiring route of a wiring target net which needs to connect the divided partial areas. When calculating the difficulty level, and determining to determine the wiring route of the wiring target net based on the calculated difficulty level, the wiring problem of the wiring target net is solved by a hierarchical algorithm, and based on the difficulty level, When it is determined that the wiring route of the wiring target net is not determined, the processing hierarchy is shifted from the hierarchy divided into the partial areas to the upper hierarchy, and the processing is shifted to the area before the division, so that the wiring in the partial area becomes difficult. Is determined, and the wiring route of this net before it is divided is
Redetermining so that the wiring in the partial area is facilitated, returning to the processing of the partial area, determining the wiring path of the wiring target net, and performing the same processing for the lower hierarchy than the hierarchy divided into the partial area Automatically determine the wiring route of all nets by repeating the above hierarchically.