JPH0754532B2 - Multi-layer simultaneous wiring method - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a method for automatically determining wiring information of a wiring pattern of a multilayer printed circuit board, a multilayer integrated circuit, etc., and particularly to a pattern and wiring that require the shortest wiring. The present invention relates to a multilayer automatic wiring method suitable for use in determining a pattern having severe length restrictions.

[Conventional technology]

Conventionally, in general, multilayer printed circuit boards, multilayer integrated circuits, etc.
By forming a pair of wiring layers whose patterns run in two directions of the axis and the Y-axis, forming a wiring pattern by this pair, and then laminating an insulating layer between a plurality of pair layers. It was manufactured.

Hereinafter, this type of conventional technique will be described with reference to the drawings.

FIG. 18 is a diagram showing an example of the structure of a wiring layer of a printed circuit board according to the prior art, and FIG. 19 is a diagram showing an example of its wiring pattern. In FIGS. 18 and 19, 1 is an x-axis direction layer, 2 is a y-axis direction layer, 3 is an insulating layer, 4 is an obstacle on the substrate, 5 is a pattern starting point, and 6 is a pattern target point.

The printed circuit board according to the prior art is as shown in FIG.
Two wiring layers of x-axis direction layer 1 and y-axis direction layer 2 are paired,
After performing required wiring on the layer of this pair, a plurality of pair layers are laminated via the insulating layer 3.

The basic idea of an algorithm that is generally used when automatic wiring is performed on a substrate configured in this way is to search the wiring pattern on a plane using two directions of the X axis and the Y axis. It is to do. The pattern example shown in FIG. 19 is an obstacle 4 in which wiring cannot be passed on the substrate.
In this case, the wiring pattern is created by extending the wiring pattern from the pattern start point 5 and the pattern destination point 6 until the generated wiring pattern contacts.
In this case, if there is an obstacle 4 on the substrate as shown in FIG.
By changing the wiring layer of the wiring pattern and changing the traveling direction of the pattern, the pattern is continuously generated.

On the other hand, the printed circuit boards, integrated circuits, etc. have become larger and more densely mounted year by year, and the multi-layered structure is being used. Further, with the increase in scale, consideration of the wiring delay has become an important issue, and it is indispensable to deal with the shortest wiring using diagonal wiring patterns.

As a conventional technique for generating a wiring pattern by a pair layer using such a diagonal wiring pattern layer, for example, Japanese Patent Laid-Open No.
The technology described in Japanese Patent No. 56500 is known.

FIG. 20 is a diagram for explaining layer selection according to this conventional technique, and FIG.
The figure is a diagram for explaining the selection of relay points, and FIGS. 22 and 23 are diagrams showing the wiring pattern examples. 21 to 23, 7 is a relay point candidate, 8 is a wiring pattern, and other reference numerals are the same as those in FIG.

In this conventional technique, first, one layer or two layers by combination are determined according to the angle formed by the line segment connecting the wiring target sections with the x-axis. For example, if it is possible to use the x-axis direction, the y-axis direction, and the Δx-axis direction and the Δy-axis direction that are inclined 45 ° clockwise from the x-axis and the y-axis, respectively, as wiring directions, the wiring layers in these directions Are selected as a pair. 20th-22nd
In the example of the figure, the Δy axis direction and the x axis direction are selected.

Next, depending on the shape of the wiring target section, a plurality of relay point candidates 7
Is selected.

Finally, the shortest feasible pattern is determined from among the plurality of types of wiring patterns set using the selected relay point candidate 7.

Since the above-described wiring method according to the conventional technique limits the wiring direction of the wiring layer in advance before the wiring pattern search, for example, as shown in FIG. 22, wiring between the start point 5 and the destination point 6 is performed. If there is an obstacle 4 in the vicinity of the section, a pattern in a predetermined wiring direction must be used, and on the contrary, a detour of the wiring pattern 8 may occur and the wiring length may become long. In the case of this example, for example, if the pattern in the y-axis direction can also be used, the wiring pattern 8 can be determined as shown in FIG. 23, and the detour of the wiring pattern can be avoided. With the technology, it is impossible to avoid such a bypass of the wiring pattern.

[Problems to be Solved by the Invention]

The above-mentioned conventional technique using the wiring layers only in the x-axis direction and the y-axis direction does not consider the wiring delay due to the increase in the scale of the circuit, and it is difficult to reduce the wiring delay by the shortest wiring. Have a point.

Further, the prior art described in the above publication can use a diagonal wiring direction layer and can reduce the wiring delay, but since the direction of the wiring layer is determined in advance, obstacles, etc. In this case, there is a problem in that the pattern may be detoured and the wiring delay may be increased. Further, in this conventional technique, in order to select the optimum pair layer for the wiring target section when the wiring layer is determined, it is necessary to select from all kinds of combinations depending on the traveling direction of the pattern, and the type of the pattern traveling direction is With the diversification, there is a problem that the total number of required wiring layers becomes huge and selection becomes difficult.
Moreover, since the inclination of the wiring target section in the pattern direction varies, the congestion degree of the wiring patterns of each pair layer becomes uneven, which is inefficient, and the connection rate cannot be increased to a certain degree or more. I have a problem.

An object of the present invention is to solve the above-mentioned problems of the prior art, and to diversify the wiring pattern shapes that can be created by a wiring process using a plurality of wiring layers, thereby enabling a high connection rate and the shortest wiring, It is possible to improve the wiring length accuracy of the wiring section where the wiring length is determined, and at the time of determining the wiring pattern,
An object of the present invention is to provide a multi-layer simultaneous wiring method capable of averaging the congestion degree of each layer by considering the congestion degree of each wiring layer.

[Means for Solving the Problems]

According to the present invention, the object is to make the wiring layers three or more wiring layers having different pattern running directions, and execute the following processes (1) to (4) in this order for each wiring target section. It is achieved by determining the wiring pattern.

(1) Calculation of Congestion Degree for Each Layer For each layer, (a) an existing wiring pattern is extracted from the already determined wiring information file, and the pattern length thereof is calculated. (B) The size of the usable wiring area, the maximum number of usable channels (the number of patterns that can be formed between wiring grids) and the traveling direction of the pattern are extracted from the board information file, and the length of the pattern that can be formed is calculated. (C) The degree of congestion for each layer is calculated from the length of the existing wiring pattern and the length of the pattern that can be created.

(2) Score calculation for each layer From the design information file, the angle of the line segment that connects the start point and the destination point of the wiring target section is calculated, and the constraint conditions regarding the wiring length of the wiring target section are extracted and used based on these. The priority of each possible pattern running direction is determined, and the use score is calculated for each of the usable wiring layers based on the priority, the degree of congestion by layer, and the pattern direction of each wiring layer.

(3) Wiring pattern generation A wiring pattern is created on the grid points (pattern creation points) where wiring patterns can be created in all directions from the start point of the wiring target section, and the tip thereof is made the trial end point. next,
The wiring pattern from this trial end point to the next trial end point is created in the same manner as described above, and repeated until the trial end point reaches the target point. As a result, a plurality of candidate wiring pattern candidates are generated. The running direction of the generated wiring pattern candidates is the plane direction 9 including the x-axis direction, the y-axis direction, the Δx-axis direction, and the Δy-axis direction as shown in FIG. 16, and the wiring layers for these plane-direction patterns. Vertical direction 10 is used to connect the two. As a result, it is possible to generate a wiring pattern candidate having a plurality of wiring layers.

(4) Wiring pattern determination When the wiring pattern candidates are generated as described above, the wiring length of each wiring pattern candidate, the traveling direction of each wiring pattern candidate with respect to the wiring target section, and VH (ViaHole: when the wiring pattern changes layers) The trial score at each trial end point is calculated based on the necessity of a through hole created for connecting the layers of (1) and the use score for each layer obtained as described above. Next, for each wiring pattern candidate, the trial scores at all trial end points are summed up to obtain the score of each wiring pattern candidate, and the optimum wiring pattern is determined according to the size of the score. However, for a wiring target section having a designated wiring pattern length, a wiring pattern candidate having a length closest to the designated length is determined as an optimum wiring pattern.

FIG. 17 is a diagram showing an example of the wiring pattern candidates thus determined, and 11 is VH.

In FIG. 17, a _{1 to} a ₆ are trial scores at each trial end point, and the scores of the wiring pattern candidates in this example are: Becomes

[Action]

The determination of the wiring pattern according to the present invention, for each wiring target section, to calculate the degree of congestion by layer based on the existing wiring pattern length,
Since the wiring pattern is determined in consideration of this, the usage rate of each layer can be controlled in detail. In addition, in order to create a wiring pattern for multiple layers at the same time when creating a wiring pattern, it is possible to generate various wiring pattern candidates by considering all patterns in the traveling direction that can be used at the start point and each trial end point. Therefore, it is possible to improve the connection rate. Furthermore, when determining the wiring pattern, the optimum wiring pattern can be selected from various wiring pattern candidates according to the length and detour of the existing wiring pattern in the wiring target section, and the shortest wiring or the designated wiring length can be selected. With the wiring by, a highly accurate result can be obtained.

〔Example〕

An embodiment of the multi-layer simultaneous wiring method according to the present invention will be described below in detail with reference to the drawings.

FIG. 1 is a flow chart for explaining processing in one embodiment of the present invention, FIG. 2 is a hardware configuration diagram of one embodiment of the present invention, and FIG. 3 is a configuration of a wiring layer of one embodiment of the present invention. FIG. 4, FIG. 4 is a diagram for explaining the length of the existing wiring pattern, FIG. 5 is a diagram for explaining the score calculation of each layer according to the congestion degree, and FIG. 6 is a wiring pattern example for explaining the score calculation. Figure,
7 (a) and 7 (b) are perspective views showing examples of wiring pattern candidates, FIG. 8 is a plan view showing examples of wiring pattern candidates, and FIGS. 9 to 11 show examples of wiring patterns by designating the wiring length. Figure,
12 and 13 are diagrams showing examples of wiring patterns for explaining the wiring pattern score calculation method, FIG. 14 is a diagram for explaining the relationship between parameters used for score calculation and scores, and FIG. 15 is a wiring pattern. It is a figure which shows the example of a score of a candidate. 2 to 4
In FIGS. 6 and 13, 21 is a computer, 22 is a design information file, 23 is a basic information file, 24 is a wiring information file, and 25 to 28 are wiring layers for each direction. This is the same as in the case of FIGS.

One embodiment of the present invention is, as shown in FIG. 2, a computer 21 for performing automatic wiring processing, a design information file having coordinates of a wiring target section, constraint conditions at the time of wiring of the wiring section, and the like.
22, a board information file 23 having information about a board on which a wiring pattern is printed, and a wiring information file 24 holding wiring pattern information determined by automatic wiring processing.

An embodiment of the present invention configured in this way is such that the wiring target section extraction S1 and the congestion degree calculation S for each layer as shown in FIG.
2. The wiring pattern is determined by sequentially executing the six processing steps of the score calculation S3 for each layer, the wiring pattern candidate generation S4, the wiring pattern determination S5, and the wiring pattern storage S6.

Hereinafter, regarding the processing at each stage, the wiring processing between the normal wiring section and the shortest wiring section will be described. In the embodiments of the present invention described below, the optimum wiring pattern is a pattern having the smallest score. Further, as shown in FIG. 3, the layer constitution of one embodiment of the present invention is as follows.
Layer), y layer direction layer (B layer), 45 ° direction layer (C layer) and 135 ° direction layer (D layer) with respect to the x-axis. VH11 penetrating layers
Are freely provided, and the wiring patterns on each wiring layer can be connected to each other.

Stage I: Wiring target section extraction (step S1) From the design information file 22, each coordinate of the start point and the destination point of the wiring pattern that constitutes the wiring target section, and the constraint conditions for wiring the section (wiring pattern length, wiring The pattern shape, etc.) is read out and input to the computer 21.

Stage II: Calculation of congestion degree for each layer (step S2) The computer 21 calculates the congestion degree for each layer by the following calculation formula.

However, l _x = the number of grids in the x direction of the existing wiring pattern l _y = the number of grids in the y direction of the existing wiring pattern.

That is, the length of the existing wiring pattern is, as shown in FIG.
Based on the position of the starting point 5 and the position of the destination point 6 of the pattern, a linear distance between both positions can be obtained with the grid point distance as a unit.

Pattern length L that can be created (example) (1) In the case of x-axis direction layer and y-axis direction layer L = (number of grids in the x-axis direction of the substrate) x (number of grids in the y-axis direction of the substrate) x (created between the lattices (Maximum number of possible patterns)-(Number of grids in the non-wiring area on the board) (2) 45 ° direction layer, 135 ° direction layer Step III: Score calculation for each layer (step S3) (a) Based on the degree of congestion of each layer obtained above, a score that is an index of usability of each layer is determined. For example, when the congestion degree of the wiring in each layer has a value as shown in FIG. 5, a score according to each congestion degree is given. This score is determined so that the sum of the scores of each layer is 100 and the ratio of the congestion degree and the ratio between layers do not change.

(B) Based on the shape of the wiring target section and the constraint condition at the time of wiring, the above-mentioned score of each layer is corrected to calculate the use score for each layer. The use score for each layer will be described with reference to an example of a wiring pattern shown in FIG. The wiring target section of the wiring pattern 8 shown in FIG. 6 is between the start point 5 and the destination point 6, and in this case, the x-axis direction layer (A layer) and the 45 ° direction layer (B layer).
The wiring pattern 8 using two wiring layers (layer) is the shortest. Therefore, the x-axis direction layer (A
In order to make it easier to use the layer) and the 45 ° direction layer (C layer), for example, subtract 5 from the score according to the congestion degree of the corresponding layers A and C in FIG. In this case, use the score by layer. Also, 135 ° direction layer (D layer)
Is in the direction opposite to the wiring target section in FIG. 6, so that the Y-axis direction layer (B layer) is made easier to use than this layer, for example, the congestion degree of the Y-axis direction layer (B layer) in FIG. Subtract 3 from the score obtained by, and use this for B in the case of normal wiring.
The use score for each layer, that is, the Y-axis direction layer, is used. As a result, the congestion level of each layer and the start point 5 and the destination point 6 of the wiring target section
The layer-by-layer use score for the normal wiring section, which takes into account the shortest wiring depending on the angle between and, is determined as shown in FIG. Also, for the shortest wiring designated section, it is necessary to place importance on the shortest route rather than the congestion degree of the layer, so ignore the congestion degree of the layer,
In order to make the x-axis direction layers 25 and 45 ° direction layers easy to use, for example, the usage score is determined as shown in FIG.

Step IV: Generation of Wiring Pattern Candidates (Step S4) Now, it is assumed that a pattern is generated between the starting point 5 and the destination point 6 at the positions shown in FIG. In this case, from the starting point 5 to the destination point 6, the obstacle 4 is avoided and the wiring pattern candidates are generated in all directions. In FIGS. 7 and 8,
R _x , R ₄₅ , R ₁₃₅ , R _y are examples of wiring pattern candidates, and
FIG. 7A is a perspective view in which wiring pattern candidates R _x and R ₄₅ are interconnected, and FIG. 7B is a wiring pattern candidate.
The perspective view of the inter-layer wiring of R ₁₃₅ and R _y is shown.

The wiring pattern candidate R _x is a case where a pattern is generated from the starting point 5 in the x-axis direction. The pattern in the x-axis direction is extended to a position where the obstacle 4 is avoided, VH11 is created, and the pattern is transferred to the B layer and then the y-axis direction In order to make a shortest wire connection to the target point, the pattern is transferred to the D layer via VH11 and is directly connected to the target point 6 by the 135 ° direction pattern.

The wiring pattern candidate R ₄₅ is the shortest pattern, and it is impossible to generate a pattern in the direction of 45 ° directly from the starting point 5 due to the obstacle 4, so the y-axis direction pattern is generated once to avoid the obstacle 4. Is the shortest.

The wiring pattern candidate R ₁₃₅ is the shortest pattern when the pattern is generated in the 135 ° direction from the starting point 5.

The wiring pattern candidate R _y is the shortest pattern when only the x-axis direction layer and the _y- axis direction layer having low layer-by-layer use scores in the normal wiring section are used.

Next, wiring is performed with a pattern length determined by the design information file 2. An example of wiring length designation wiring is shown in FIG.
This will be described with reference to FIG.

FIG. 9 shows an example in which the starting point 5 and the destination point 6 are wired with a designated length of 11 grids on the layer in the x-axis direction and the y-axis direction. However, when the obstacle 4 exists in the vicinity of the destination point 6, the wiring pattern using only the x-axis direction layer and the y-axis direction layer has two grids like the wiring pattern l ₁ as shown in FIG. Detour will occur. In this case, if the diagonal pattern is used, the wiring length can be shortened and the accuracy for the designated pattern length can be improved as in the wiring pattern l ₂ in FIG.

Step V: Wiring pattern determination (step S5) (1) Calculation of wiring pattern score Refer to FIG. 12 for the method of calculating the wiring pattern score during normal wiring of the shortest wiring pattern R ₄₅ explained with reference to FIGS. 7 and 8. And explain.

At the first trial end point α between the start point 5 and the destination point 6, from the start point 5 to the trial end point α, the vector approaching the destination point has a lattice number of 1 and the VH11 is not used. According to the figure, vector score l = 5, VH score V =
It becomes 0. Further, since the used wiring layer is the B layer which is the y-axis direction layer, the layer score L = 10 from FIG. Similarly, in trial end point β, from trial end point α to trial end point β,
It is a vector that approaches the target point, the number of grids is 2, and VH11 is used between the BC layers at the trial end point α, and the wiring layer used is
Since the C layer, which is the 45 ° direction layer, is used, the vector score l = 10, the VH score V = 2, and the L = 32 can be obtained from FIGS. 14 and 5. Similarly, at the trial end point γ reaching the target point 6, VH11 is used between the C-A layers at the trial end point β and the A layer which is the x-axis direction layer is used as the wiring layer used. From Figure 14 and Figure 5, vector score l
= 10, VH score V = 2 × 2 = 4, L = 14 can be obtained. The total of all of these points becomes the wiring pattern score for the normal wiring of the wiring pattern R ₄₅ , and the value is 87.

Similarly, by using FIGS. 14 and 5, the wiring pattern score at the time of the shortest designated wiring of the wiring pattern R ₄₅ can be obtained. In this case, each score at each trial end point is shown in FIG.

As described above, the wiring pattern score for each wiring pattern candidate can be obtained, and the wiring pattern score for each wiring pattern candidate described with reference to FIGS. 7 and 8 is as shown in FIG. .

(2) Wiring pattern determination In one embodiment of the present invention, the one with the smallest wiring pattern score is taken as the optimum solution, so during normal wiring, the wiring pattern candidate R _y is based on the score shown in FIG. At the time of shortest designated wiring, wiring pattern R ₄₅ is selected in the same way,
Determined as a wiring pattern.

As described above, even for the same wiring section, as shown in FIGS.
Based on the figure, a wiring pattern using the x-axis direction layer and the y-axis direction layer, which has a low degree of congestion in the wiring layer, is selected during general wiring, and the congestion degree can be averaged. The shortest wiring pattern is selected regardless of the congestion level of the wiring layer.

Step VI: Wiring pattern storage (step S6) Information (coordinates, wiring layer name, etc.) about the wiring pattern selected in step V is stored in the wiring information file 24.
With the above, the process for one wiring target section is completed.

According to the above-described embodiment of the present invention, in a normal wiring section, various wiring pattern candidates for all layers are automatically generated in consideration of the congestion degree of each wiring layer due to the determined wiring pattern. It is possible to automatically determine the optimum wiring pattern for the wiring target section from among them. Further, in the shortest wiring designated section, it is possible to automatically determine the shortest wiring pattern that can be generated by considering all wiring layers when generating the wiring pattern. Further, according to one embodiment of the present invention, in the section in which the wiring length is designated in advance, all wiring layers are taken into consideration when the wiring pattern is generated, so that it is possible to flexibly cope with the detour of the wiring pattern. It is possible to automatically determine a wiring pattern with high wiring length accuracy.

The above-described embodiment of the present invention relates to the creation of a wiring pattern on a substrate having four wiring layers. However, the present invention is not limited to the number of wiring layers as long as it has a plurality of wiring layers. It is optional and can be applied to the creation of a wiring pattern on a printed circuit board, LSI, or the like.

〔The invention's effect〕

As described above, according to the present invention, it is possible to consider all the wiring layers that make up a printed circuit board, LSI, etc. when creating a wiring pattern. It is possible to select a different wiring pattern, and when the wiring pattern is determined, the usage rate of each wiring layer can be controlled in more detail by considering the congestion degree of each wiring layer due to the existing wiring pattern. As a result, the present invention has a high connection rate, shortest length wiring,
It is possible to improve the accuracy at the time of wiring with the specified wiring length.

[Brief description of drawings]

FIG. 1 is a flow chart for explaining processing in one embodiment of the present invention, FIG. 2 is a hardware configuration diagram of one embodiment of the present invention, and FIG. 3 is a configuration of a wiring layer of one embodiment of the present invention. FIG. 4, FIG. 4 is a diagram for explaining the length of the existing wiring pattern, FIG. 5 is a diagram for explaining the score calculation of each layer according to the congestion degree, and FIG. 6 is a wiring pattern example for explaining the score calculation. Figure,
7 (a) and 7 (b) are perspective views showing examples of wiring pattern candidates, FIG. 8 is a plan view showing examples of wiring pattern candidates, and FIG.
Figures 10, 10 and 11 show examples of wiring patterns by specifying the wiring length, Figures 12 and 13 show examples of wiring patterns for explaining the wiring pattern score calculation method, and Figure 14 shows The figure which explains the relationship between the parameter and the score which are used for score calculation,
FIG. 15 is a diagram showing scoring examples of wiring pattern candidates, FIG. 16 is a diagram explaining pattern running directions, FIG. 17 is a diagram showing wiring pattern candidate examples, and FIG. 18 is a layer structure of a printed circuit board according to a conventional technique. FIG. 19 is a diagram showing an example of the wiring pattern, FIG. 20 is a diagram explaining layer selection according to the prior art, FIG. 21 is a diagram explaining selection of relay points, FIG. 22, FIG. twenty three
The figure is a diagram showing an example of the wiring pattern. 1 ... x-axis direction layer, 2 ... y-axis direction layer, 3 ... insulating layer,
4 ... Obstacle, 5 ... Start point, 6 ... Destination point, 7 ... Relay point candidate, 8 ... Wiring pattern, 9 ... Plane direction, 10 ...
Vertical direction, 11 …… VH, 21 …… Computer, 22 …… Design information file, 23 …… Board information file, 24 …… Wiring information file.

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁶ Identification number Internal reference number FI Technical indication location H05K 3/46 B 6921-4E (72) Inventor Yasuyuki Fujiwara 4026 Kuji Town, Hitachi City, Ibaraki Co., Ltd. Hitachi Research Laboratory, Hiritsu Manufacturing Co., Ltd. (56) Reference JP-A-2-2467 (JP, A)

Claims (2)

[Claims] 1. A wiring for automatically determining a wiring pattern based on a wiring target section consisting of a start point and a destination and a constraint information at the time of wiring of a circuit having a multilayer wiring layer having a plurality of wiring layers with different pattern traveling directions. In the method, each of the wiring layers having a usable pattern running direction in the multilayer wiring layer according to the angle of the line segment connecting the starting point and the destination point of the wiring target section and the constraint condition regarding the wiring length of the wiring target section. Determining the priority of each of the usable wiring layers based on the priority sequence and the pattern running direction, and between the start point and the destination point of the wiring target section on the plane. A plurality of wiring patterns using three or more layers as wiring layers by performing a route search of a wiring pattern to be advanced and a layer change search of an interlayer via hole perpendicular to a plane connecting the plurality of wiring layers. Generating a candidate for each of the wiring pattern candidates, and determining a score for each of the wiring pattern candidates based on the usage score of each wiring layer to be used, the length of the wiring pattern, and the presence / absence of an interlayer through hole. And a step of determining an optimum wiring pattern based on the score of 1. 2. A step of determining a ratio of an existing wiring pattern length to a pattern length that can be created for each wiring layer and calculating a congestion degree of each wiring layer, and determining a use score of the wiring layer. The multi-layer simultaneous wiring method according to claim 1, wherein the use score of the wiring layer is also determined by adding the congestion degree of the wiring layer.