JPH0642256B2 - Automatic wiring method - Google Patents

Description

DETAILED DESCRIPTION [Overview] Regarding an automatic wiring method for determining a route of a wiring section, after performing wiring processing by recognizing an intersection of wiring patterns, repeated wiring processing is performed so as to eliminate this intersection. For the purpose of minimizing the wiring cost and improving the automatic wiring rate, calculate the wiring cost including the intersection of the paths corresponding to the specified load factor, and search the path with the smaller wiring cost. The load is provided with a search unit, a crossing message transmission unit for notifying that a net crossing the route searched by this route search unit is to be crossed, and a load factor changing unit for changing the initially designated load factor. According to the load coefficient changed by the coefficient changing unit, the route searching unit repeatedly searches for a route that reduces the wiring cost and determines the route.

[Industrial application field]

The present invention relates to an automatic wiring system for automatically designing a wiring process on a printed circuit board or an LSI using an electronic computer.

[Conventional technology]

Printed circuit boards and LSIs have terminal pairs that should have the same potential.
It is necessary to wire each other without crossing a terminal pair having a different potential.

There is a maze method as a typical conventional wiring method. In this maze method, as shown in FIG. 5, the substrate 11 is divided into meshes, and labeling is sequentially performed for each mesh from each point constituting the terminal pair, for example, the point "A" to the other point "A". ,
It determines the path when the two labeling is done at the same point. Specifically, as shown in FIG. 5, first, "1" is vertically and horizontally centered on the point "A".
Secondly, "2" is attached to the top and bottom and left and right to avoid obstacles around the attached "1" point. Thirdly, when attaching a "3" while avoiding obstacles vertically and horizontally centering on the attached "2", two points from "A" are, for example, points shown in (a) in the figure. Overlapping each other. The path passing through this point (a) becomes the desired wiring. The once obtained mesh on the path is prohibited (obstacle) for other terminal pairs. In this way, in the method of sequentially determining the path for each terminal pair, it is difficult to avoid the occurrence of a non-wiring section in the end because the existing pattern becomes an obstacle for the subsequent wiring. There was a problem that it would end up.
Further, in the conventional maze method and the like, when determining the path of each terminal pair, the path with the shortest wiring and the number of vias (the conductive holes connecting the layers of the board) is reduced to find the path of the minimum cost. However, since the existing wiring pattern is handled as an obstacle, there is a problem that the cost of the wiring as a whole is not always minimized. Further, in the past, since the existing wiring pattern was treated as an obstacle, the phenomenon of detouring due to the influence of the existing wiring pattern is often seen in terminal pairs to be wired later, and the wiring order greatly depends on the wiring cost. There was a problem that it would end up.

An object of the present invention is to recognize the intersection of wiring patterns, perform the wiring processing, and then repeatedly perform the wiring processing so as to eliminate the intersection, thereby minimizing the total wiring cost and improving the automatic wiring rate. I am trying.

[Means for solving problems]

Means for solving the problem will be described with reference to FIG.

In FIG. 1, an initialization unit 1 sets initialization information (for example, an initial value of a load coefficient).

The path search unit 2 searches for a path with the minimum wiring cost under the specified load coefficient.

The crossing message transmitting unit 3 notifies the net (wiring) of the other party to the crossing when the paths cross each other.

The load coefficient changing unit 4 sequentially sets the value of the load coefficient to be large and notifies the route searching unit 2 to gradually reduce the number of intersections.

[Action]

According to the present invention, as shown in FIG. 1, the initialization unit 1 sets an initial load coefficient to a predetermined initial value, and the path search unit 2 uses the set load coefficient to reduce the wiring cost. Is searched for and found, and at this time, if the paths cross each other, the crossing message transmission unit 3 notifies the net of the other party to the crossing. Next, the load factor changing unit 4 sets the load factor so that the wiring cost includes the intersection, and the path searching unit 2 again finds the path with the smaller wiring cost. The transmission unit 3 notifies the other party's net to intersect. The above operation is repeated to find the path when the number of intersections is the minimum.

Therefore, by first finding a path that reduces the wiring cost in a mode that allows the intersection, and then sequentially setting a larger load coefficient so that the intersection includes the wiring cost and repeatedly searching for a path that reduces the wiring cost, Wiring (net)
It is possible to obtain a path in which the wiring cost is reduced in consideration of the whole, and it is possible to increase the automatic wiring rate.

〔Example〕

First, an example of intersection (cross-shaped cross and overlap) will be described with reference to FIG.

FIG. 2 (a) shows a cross cross. This cross is
It is an intersection where paths cross in the same layer. In order to avoid this intersection, it is necessary to provide a path so as to bypass the terminal of the other party that intersects, which is a type of intersection that is difficult to avoid easily.

FIG. 2 (b) shows the overlap. This overlap is a kind of intersection in which the paths are overlapped in parallel and the intersection can be easily avoided by translating any of the paths in parallel.

Next, the configuration of one embodiment of the present invention will be described with reference to FIG.

In FIG. 1, the initialization unit 1 sets the initial value of the load coefficient for calculating the wiring cost of the path.
Initially, the load factors γ = 0 (for cross cross) and δ = 0 so that the crossing (cross cross and overlap) described with reference to FIG. 2 is not included in the wiring cost.
Set (for overlap). As a result, initially, the path search unit 2 searches for a path that minimizes the wiring cost in a mode in which the intersection is recognized.

The path search unit 2 searches for a path in which the wiring (net) between the designated terminal coordinates has the minimum wiring cost under the set load coefficient. The wiring cost is
It is calculated by the cost function f shown in the following equation (1).

f = α × wiring length + β × number of vias + γ × + number of crosses + δ × number of overlaps (1) where α, β, and δ represent load factors for each element, and the wiring length is the total wiring of the net. The length (total path length) and the number of vias indicate the number of via holes for changing the wiring layer, and the number of cross crosses indicates the number of crossing paths on the cross as shown in FIG. 2 (a). The number of laps represents the number of overlapping paths in parallel as shown in FIG. 2 (b).

When the crossing message transmitting unit 3 searches for a path that minimizes the value f of the equation (1) under the set load coefficient, and finds out the path, when the crossing message sending unit 3 crosses another path. The fact is notified to the other party's net that intersected.

The load coefficient changing unit 4 changes the load coefficient.

Next, according to the procedure shown in the flowchart of FIG.
The operation of the configuration shown in FIG. 1 will be sequentially described in detail with reference to FIGS.

In FIG. 3, the figure shows a state in which pre-processing is performed.
As shown in FIG. 4 (a), this is a message WA for the path connecting the terminals A and _A , a net WB for the path connecting the terminals B and _B , and a net for the path connecting the terminals C and C. W _C , set so that wiring is performed in the order of the nets W _A , W _B , and W _C , and a load coefficient γ = 0 for calculating the wiring cost (meaning that the cross cross is not included in the wiring cost. ), And δ = 0 (which means that the overlap is not included in the wiring cost) as an initial value.

The figure shows a state in which a route search is performed. This means, for example, for the net shown in FIG. 4 (a), the route having the minimum wiring cost is searched and found under the load coefficient set in the figure.

The figure shows a state in which a crossing message is transmitted. This means that when the path found in the figure intersects another path, the partner net is notified of the intersection.

The figure shows a state in which the load coefficient is changed. This is because the value of the load coefficient γ = δ = 0 initially set in the figure is changed so that the wiring cost includes sequential intersections such as load coefficient γ = 1 and δ = 0. It means decreasing.

A flow in which the procedure from the above figures is applied to a specific example according to the present invention in FIG. 4 will be sequentially described in detail below.

First, the load coefficient (γ = δ = 0) set in the figure
Substituting into (1), we obtain the following equation (2), and mean to search and find the path where the value of this expression (2) is the minimum in the figure, for example, the path shown in Fig. 4 (b). There is.

f = α × wiring length + β × via number (2) In the state shown in FIG. 4 (b), three wirings (net)
Are crossed and wired. This means that
The figure crossing message transmitting unit 3 notifies the net of the other party to cross as shown in the table at the right end of FIG. 4 (b).
In (b) of the table in Fig. 4 (b), net W _A is net W _B , W _C
It means that the cross is crossed. (C) is the net W _B
Indicates that it crosses the net W _C. (D)
Indicates that there is no net in which the net W _C crosses (represented by an empty set).

Secondly, the path search in the figure is performed again. In the case of this embodiment, the right edge of the as shown in Table of FIG. 4 by the first step (b), with respect to the net W _A, net W _B, W _C
Since it has been reached, a route with the same wiring length and the same number of vias (that is, the same wiring cost) is searched for by avoiding these crosses, as shown in Fig. 4 (c). Ask for. Similarly, for net W _B , net W _C
Therefore, avoiding this cross-cross, the path with the same wiring length and the same number of vias should be
As shown in Figure (c), it is searched for. Since the fact that a cross is crossing has not arrived at the net W _c , the path shown in FIG. 4 (b) at the previous time is left as it is.

With the above procedure, the wiring cost according to the equation (2) is determined to be the minimum and the number of cross crosses is reduced.

Thirdly, in the figure, the load coefficient is changed, that is, the load coefficient γ is set to a positive value (for example, 1) and δ = 0. And
The load coefficient (γ = positive value, δ = 0) set in the figure
Substituting into (1), the following equation (3) is obtained, and the path where the value of equation (3) is the smallest with respect to FIG. 4 (c) is searched, for example, the path shown in FIG. 4 (d) is searched. And find out. Specifically, Fig. 4 (c)
(E) in the right end of the table as shown with the net W _A
Crosses the net W _B , so the path shown by the net W _A in FIG. 4 (d) is searched and found to avoid this. For the other nets W _B and W _C , since a cross cross has occurred, it is determined to be the same as the previous time. At this time, as shown in (f) in the table on the right end of FIG. 4 (d), the net W _A is notified in the figure of the overlap.

f = α × wiring length + β × via number + γ × cross cross number ...
(3) Fourth, in the figure, the load coefficient is changed, that is, the load coefficient γ is set to a positive value (for example, 1) and δ is set to a positive value (for example, 1). Then, the path shown in FIG. 4 (d) for which the value of the equation (1) becomes the minimum, for example, the path shown in FIG. 4 (e) is searched and found. Specifically, as shown in (f) in the table at the right end of FIG. 4 (d), the net W _B overlaps with the net W _A , so avoid this. As shown by the net W _B in Fig. 4 (e),
Move only the trace. Since no overlap has occurred with respect to the other nets W _A and W _C , it is determined to be the same as the previous one.

By the above operation, the route that minimizes the wiring cost is initially found without including the cross cross and the overlap in the wiring cost, and then the route that minimizes the wiring cost is found by including the cross cross in the wiring cost. In addition, by finding the path that minimizes the wiring cost by including the overlap in the wiring cost, the wiring (net)
It is possible to find the path that minimizes the wiring cost in consideration of the whole.

FIG. 3 shows a state in which termination processing is performed. this is,
By the operation described above, when there is a terminal pair whose intersection cannot be resolved to the end, this means that this terminal pair (net) is deleted as unwired.

〔The invention's effect〕

As described above, according to the present invention, a path that reduces the wiring cost is found in a mode in which the intersection is initially recognized, and the load coefficient is set to be sequentially increased so that the intersection is included in the wiring cost. By adopting a configuration that repeatedly searches for a path that reduces the wiring cost, a path that reduces the wiring cost can be determined in consideration of the entire wiring (net), and the automatic wiring rate can be increased. it can. As a result, it is possible to significantly reduce the design time required for layout setting of the integrated circuit.

[Brief description of drawings]

FIG. 1 is a block diagram of one embodiment of the present invention, FIG. 2 is an intersection example, FIG. 3 is a flowchart for explaining the operation of the present invention, FIG. 4 is an explanatory view of a specific example of the present invention, and FIG. 5 is a conventional maze. The labeling explanatory drawing by the method is shown. In the figure, 1 is an initialization unit, 2 is a route search unit, 3 is a crossing message transmission unit, and 4 is a load coefficient changing unit.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Toshiyuki Shibuya, 1015 Kamiodanaka, Nakahara-ku, Kawasaki City, Kanagawa Prefecture, Fujitsu Limited (72) Hideki Miwato 1015, Kamedotachu, Nakahara-ku, Kawasaki City, Kanagawa Prefecture, Fujitsu Limited (56) References JP-A-62-102361 (JP, A)

Claims (1)

[Claims] 1. An automatic wiring method for determining a path of a wiring section, wherein a wiring cost including a crossing of paths corresponding to a designated load coefficient is calculated, and a path search unit for searching a path with a small wiring cost ( 2), a crossing message transmission unit (3) notifying that a net that intersects the route searched by this route search unit (2) is intersected, and a load coefficient changing unit that changes the initially specified load factor. According to the load coefficient changed by the load coefficient changing unit (4), the path searching unit (2) repeatedly searches for a path that reduces the wiring cost and determines the path. The automatic wiring method is characterized in that