JPH04676A - Method and system for determining shortest route - Google Patents

Abstract

PURPOSE:To attain determining the shortest wiring route at high speed and with the small number of wiring layers by using a method for searching segment extended able to search the route with using wiring directions more than three directions and giving a means able to control the redundant by-pass of the wiring route high accurately moreover. CONSTITUTION:The generation processing of a temporary segment in respective wiring layers from a starting point A is executed based on a by-pass quantity per unit grid to respective searching directions in a range not over the total by-pass quantity upper limit value of a route as the one-dimensional searching of a level 1 first for route searching. The total by-pass quantity from the starting point A to a grid point is calculated from on the arbirary grid point arrived by the level 1 searching and the one-dimensional searching of a level 2 is executed after the total change searching in the range in which the total by-pass quantity is not over the apper limit value. The shortest route can be obtained at required accuracy by repeating processing and making the total by-pass quantity upper limit value of the route defined in advance small. Thus, the determination of the wiring route is attained at high speed and with the small number of the wiring layers.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to a method for determining wiring patterns for printed circuit boards, integrated circuits, etc., and a system for determining wiring patterns, and particularly relates to wiring that takes signal delay into consideration. The present invention relates to a shortest route determining method and a shortest route determining system suitable for use in automatically determining patterns using a computer.

[Conventional technology]

In recent years, with the increasing performance of computers, consideration of signal delay due to wiring patterns has become an important issue in the mounting design of printed circuit boards, integrated circuits, etc. Wiring design with the shortest possible wiring has become essential.

Among wiring design automation techniques for printed circuit boards, etc., a prior art method for determining the shortest route using wiring patterns diagonally at 45° is the 1986 I.E.
E.E. International Conference on Computer Needs Design Proceedings, pp. 250-253 (Proceed
ings 1986IEEE International
Al Conference on Computer
-Aided Design (I CCAD-86
), p p , 250=253).

Conventionally, in wiring design for printed circuit boards, etc.,
A pair of two wiring layers with horizontal and vertical wiring directions (
This method has mainly been targeted at substrates with a layer structure in which multiple layers (hereinafter referred to as "pair layers") are laminated, but as shown in Figure 2, in the above method, the wiring is possible in the horizontal direction, Expand in four directions: vertical direction, diagonal ±45' direction, assign any two of these directions including the diagonal direction to each pair layer, and use the diagonal 45 degree direction in any of those pair layers. The target can be a board that can realize connection by a route. In the wiring route determination process using the above method, for such a printed circuit board, etc., first, the optimal pair layer is determined based on the angle formed by the line segment connecting the starting point and the ending point of the wiring target section with the horizontal direction, and then The basic method is to search for the shortest route in a diagonal 45° direction from the start point to the end point in a pair layer using the line segment search method, maze method, etc. as a two-layer wiring method (hereinafter, this method will be referred to as the "two-layer wiring method"). ).

However, in the method for determining the shortest route using the two-layer wiring method described above, the wiring direction for the wiring target section is limited to two directions, which poses an obstacle to route searching for wiring layer patterns, etc. on the desired shortest route. If an object exists, using two determined wiring directions may actually cause a detour in the wiring pattern. Furthermore, with respect to the angle that the line segment connecting the starting point and ending point of the wiring target section makes with the horizontal direction,
All pair layers including diagonal wiring layers are required, and compared to the conventional pair layer configuration with only horizontal and vertical wiring layers,
There is a problem in that a huge number of wiring layers are required.

On the other hand, in contrast to the above-mentioned two-layer wiring method, as shown in FIG. We investigated how to determine wiring routes for layers (hereinafter referred to as "layer groups"). This method searches for a route from the start point to the end point of a wiring target section using at least three or more layers in any of the stacked layer groups, and searches for a route in at least three or more directions. The purpose of this method is to obtain the shortest route by using the method (hereinafter, this method will be referred to as the "multilayer wiring method using the maze method"). According to this, it is possible to always find the path with the shortest route length among multiple routes that can be routed, so by setting the wiring direction to three or more directions, it is possible to avoid problems that may occur due to the two-layer wiring method described above. This has the advantage that unnecessary detours of wiring patterns are eliminated. Furthermore, compared to the two-layer wiring method described above, a large number of wiring sections can be processed at once in a specific layer group, regardless of the angle between the line segment connecting the start point and end point of the wiring target section and the horizontal direction. It is possible to determine the shortest route using a diagonal direction depending on the number of wiring layers.

[Problem to be solved by the invention]

However, although the multilayer wiring method using the maze method solves the problems of the two-layer wiring method described above, it does not take into account large-scale printed circuit boards, integrated circuits, etc., and allows high-speed wiring for a large number of wiring sections. There was a problem that route determination could not be performed.

The purpose of the present invention is to solve the problems of the prior art described above,
It is an object of the present invention to provide a method and system capable of determining the shortest wiring route for large-scale printed circuit boards, integrated circuits, etc. at high speed and with a small number of wiring layers.

[Means to solve the problem]

The above purpose is to:
Instead of using the maze method to search for a route from the starting point to the ending point,
This is achieved by using an extended line segment search method that allows route searching using more wiring directions than the above directions, and by providing means that can control redundant detours of wiring routes with high precision.

The above explanation will be supplemented below using examples shown in FIGS. 4 and 1. FIGS. 4 and 1 show a process for determining the shortest wiring route using at least three wiring directions according to the present invention in a wiring pattern determination system that uses at least three or more wiring layers at the same time. As an example, a wiring route determination process using four wiring layers and four wiring directions shown in FIG. 3 is shown.

In this example, first, a region where wiring is possible is determined for a plurality of wiring layers of at least three layers to be wired.

Each wiring layer is created as line segment data along the wiring direction defined as a unique direction (Fig. 4 (A1)), and the area in which layer changes can be searched for the wiring layer adjacent to each wiring layer is created as grid data. (Figure 4 (A2)).

The search for the wiring route from the starting point A to the ending point B involves repeating the generation of temporary line segments through a one-dimensional search using the above line segment data, and the layer change search using the above grid data from grid points on the temporary line segments. It can be executed by Figure 4 (B
z) and (Bx) show this situation. First, a temporary line segment of level 1 is generated for each wiring layer from the starting point A using the line segment data along each wiring layer. , After performing a layer change search using the grid data, a temporary relay hole is generated. A level 2 temporary line segment is generated from the hindlimb relay hole to each wiring layer using the above line segment data. Thereafter, similar processing is repeated until the temporary line segment reaches the end point B. As described above, the present invention can be implemented as a line segment search method using at least three wiring directions, and can be processed much faster than a route search using the maze method.

However, according to the processing of the line segment search method, although a route with the minimum number of layer changes, that is, a route with the minimum number of route bends is found, there is a possibility that a route with a shorter wiring length using diagonal wiring may be overlooked. Therefore, in the present invention, in order to find a shorter wiring route, in a one-dimensional search from a plurality of grid points reached from a starting point A to an end point B, a route is searched in a detour direction. Limit the search range. FIG. 1 (Ax) and (Ax) show an example of preprocessing for this purpose. That is, first, a partial region Rx is obtained by dividing the region to be wired by four straight lines passing through the end point B,
Rz, . . . R8 should be created (Fig. 1 (Ax)).

For each partial region, a detour amount per unit grid is defined in the search direction of one-dimensional search from arbitrary grid points in the four wiring layers. Basically, the amount of detour becomes smaller as the end point B gets closer, and becomes larger as the end point B gets further away. Figure 1 (
A2) shows an example of the detour amount per unit grid for each search direction in the partial regions R1 and R2. 1st
Figure (Bl).

(Bz) and (Ba) show wiring processing examples in which the range of one-dimensional search in the search direction defined in each wiring layer is limited based on the detour amount for each search direction created by the above preprocessing. . In the route search, first, as a level 1 one-dimensional search, the process of generating a temporary line segment in each wiring layer from the starting point A is performed based on the detour amount per unit grid for each search direction above, and a predefined route is created. This is done within a range that does not exceed the upper limit of the total detour amount (Fig. 1 (B1)). Then, from an arbitrary grid point reached by the level 1 search, calculate the total amount of detours from the starting point A to the grid point, and similarly, within the range where the total amount of detours does not exceed the above upper limit, the level after layer change search is calculated. 2
A one-dimensional search for is similarly performed (FIG. 1 (B2)). By repeating the same process, in this example, a route in which detours of the wiring route are suppressed at a certain upper limit can be discovered by searching up to level 3 (FIG. 1 (B8)). In this case, the shortest route can be obtained with desired accuracy by reducing the upper limit of the total detour amount of the predefined route.

[Effect]

In the shortest route determination method using the above means, at least 3
Since the present invention provides route searching means using an expanded line segment search method using more than three wiring layers and at least three wiring directions, wiring routes can be determined at high speed and with a small number of wiring layers.

Furthermore, in the shortest route determination method using the above means.

This provides a means to place a certain limit on the generation range of temporary line segments by one-dimensional search toward the end point in the line segment search method.
The shortest route can be determined with high accuracy.

〔Example〕

(1) First Embodiment One embodiment of the present invention will be described below with reference to the drawings from FIG. 5 to FIG. 9.

FIG. 5 is a block diagram showing the configuration of the wiring pattern determination system according to the present invention, FIG. 6 is a flowchart showing the processing procedure of the shortest route determination processing control section 505 provided in the wiring pattern determination system, and FIG. , FIG. 8 shows the descriptions of the wiring possible area data storage table 512 and the layer change searchable area data storage table 513 that are referenced and updated in the route search unit 510 using the line segment search method provided in the wiring pattern determination system, and the above-mentioned contents. FIG. 9 is a diagram showing the contents of reference updates to 512 and 513 performed in the processing section 510, and FIG. 9 is a diagram showing the description contents of the temporary line segment data storage table 515 created in the processing section 510.

In FIG. 5, a computer 501 includes a board information file 502 that defines the configuration of wiring layers of printed circuit boards, integrated circuits, etc., wiring directions in each wiring layer, etc., and a net information file 503 that stores wiring target sections. Shortest route determination processing that reads information from the pattern information file 504 that stores pattern information before wiring, performs wiring route determination processing based on the information, and outputs the obtained wiring pattern to the pattern information file 504 again. Has a program. Further, in FIG. 5, the computer 501
The shortest route determination processing control unit 505 in the shortest route determination processing program includes the board information file 502. Net information file 503゜ An input processing unit 506 that reads information from the pattern information file 504, and a routable area creation unit that creates information in a routable area data storage table 512 in which the routable area in each wiring layer is defined as line segment data. 507, a layer change searchable area creation unit 508 that creates information in a layer change searchable area data storage table 513 defined as grid data;
At) * (Az) D Detour control information for creating a detour control data storage table 514 that stores the detour amount per unit grid for each search direction in the partial region and the upper limit of the total detour amount of the route for the wiring target section, as shown in FIG. The creation unit 509 and the data storage tables 512, 513,
514, a route search unit 510 using a line segment search method searches for the shortest route using a line segment search method and creates information in a temporary line segment data storage table 515 based on the temporary line segment data storage table 515. The output processing unit 511 is activated to output the shortest route discovered in the pattern information file 504 as a wiring pattern.

Below, using FIG. 6, the shortest route determination processing control unit 50
The processing procedure of step 5 will be explained. In FIG. 6, input processing is first performed by activating the input processing unit 506 (60
1), Next, initial creation of routeable area data and layer change searchable area data is performed based on the input information 602, 603)
Then, based on the input information, detour control data is initially created prior to route searching (604). After that, in step 605, for the unwired section to be routed, the routeable area data storage table 5122 layer change searchable area data storage table 513. While referring to the detour control data storage table 514, temporary line segments are generated using the line segment search method. The temporary line segments obtained here are sequentially created in the temporary line segment data storage table 515. After the above processing,
Based on the results created in the data storage table 515 for the wiring section, a wiring route is edited and output as a wiring pattern to a pattern information file (606).

After that, it is determined whether there is still an unrouted wiring section (607), and if so, the wiring area data and the layer change searchable area data are updated according to the wiring pattern (602, 603), and the unrouted area is Similarly, steps 604, 605 and 606 are performed. After repeating this operation, when the route search is completed for all wiring sections, the entire process is ended.

In the route search (605) using the line segment search method, as described above, the data storage table 515 is created without referring to the data storage tables 512, 513, 514, but at the same time, the data storage table 515 is created without referring to the data storage tables 512, 513, and 514. Processing is performed after updating the information regarding the completed wiring area. Next, the description contents of data in 512 and 513 and the reference update contents for 512 and 513 in the process of 605 will be explained using FIGS. 7 and 8. In FIGS. 7 and 8, (Ax) and (Az) respectively show examples of the wiring state before wiring and at the end of level 2 route search.

In (A2), sl is a vertical wiring layer, B2°B5
indicates a temporary line segment generated in a wiring layer diagonally at 45°. In Figure 7, (Bz) and (B2) are respectively (
Ar) shows the state of the wiring possible area data corresponding to (A2). Moreover, (C1) and (C2) are the description items of this wiring possible area data and (Bl).

(Bz) shows the description content corresponding to (Bz). In the route search, all description items are referred to for these line segment data, namely, the starting point side Xs'/coordinates, the ending point side Within the search range defined by the data storage table 514, a temporary line segment is generated using all or part of the appropriate line segment data. When part of the hindlimb line segment data is used as a temporary line segment, the line segment data is divided into a plurality of line segment data. Further, the searched flag for line segment data corresponding to the temporary line segment is updated from an unsearched state to a searched state. In the example shown in the figure, line segment data Q1. before wiring. After confirming that Qz is in an unsearched state, a temporary line segment 82,515 is generated. In this case, for a temporary line segment s5 generated using a part of line segment data Q1, Then, line segment Q1 is converted into line segment L1. Law L
It is divided into +. Also, line segment Q2 and divided line segment L
The searched flag for No. 8 is updated from an unsearched state (0) to a searched state (1). As described above, in the route search, a one-dimensional search is performed by referring to the routable area data, and processing is performed by updating the routable area data using temporary line segments generated by the one-dimensional search. Also the 8th
In the figure, (B 1).

(B2) shows the state of layer change searchable area data corresponding to (AX) and (AX), respectively. Also (C
1) and (C2) indicate the description items of this layer change searchable area data and the description contents corresponding to (Bz) and (Bz). In route search, the description items (x+y coordinates, searched flag) of these grid data are referred to, and after determining whether layer change search is possible from any grid point position, layer change search is performed, and then The searched flag of the grid data corresponding to the limb grid point position is updated to the searched state. In the example shown in the figure, a layer change search is performed for the grid point position v2 on the temporary line segment that occurred in the level 1 search after confirming that the grid point position is in an unsearched state. It shows. In this case, the grid point position V2 is updated from an unsearched state (0) to a searched state (1). In this way, the route search is performed by referring to the layer change searchable area data, performing a layer change search from an arbitrary grid point position, and updating the layer change searchable area data at the grid point position. .

In the route search using the line segment search method (605), the above-mentioned temporary line segments are sequentially generated, thereby creating the temporary line segment data storage table 515, but in the output processing (606), the temporary line segment data storage table 515 is created based on the table 515. After editing the wiring route, it is output to the pattern information file 504 as a wiring pattern.

Finally, the table 5 that allows editing of this wiring route.
15 will be explained using FIG. 9. FIG. 9(A) shows an example of the state of the temporary line segment at the time when the route search from the starting point A to the ending point B is completed.

Here, si, sz, Sat number 8 is level 1,
B5°B6 indicates level 2 temporary line segments, and B7 indicates level 3 temporary line segments. Further, FIG. 9(B) shows the description items of the temporary line segment data storage data 515 and the description contents in the state shown in (A) above. In this table, for a temporary line segment at level i, a pointer to the parent temporary line segment indicating the original temporary line segment from which the temporary line segment was derived, and a pointer to the parent temporary line segment from which the temporary line segment was derived. It has the "derivation source lattice point position" that indicates the upper lattice point position as a description item.The "pointer to the parent board line segment" for the level 1 temporary line segment is "null", and the 6 derivation elements The grid point position '' is the starting point A. In this example, the "pointer to the parent board line segment" for the temporary line segments sx, sz, and SRt sa of level 1 is "nu 11" and the "lattice point position of the derivation source" is the starting point A. Temporary line segment 851
The "pointer to the parent board line segment" for 58 is sl, the "derived grid point position" is vl, and the temporary line segment s7 of level 3
The "pointer to the parent board line segment" for is B5, and the "lattice point position of the derivation source" is v2. Editing of the wiring route in output processing is done by starting the temporary line segment that has reached the end point B by referring to the above-mentioned ``grid point position of the derivation source'' and then referring to the above-mentioned pointer to the parent temporary line segment. This can be done without tracing the temporary line segment leading to s7.
, obtain the relay hole v2. Next, 35 is obtained by referring to the "pointer to the main board line segment" for 57, and the line V2 Vl and relay hole v1 are obtained from the temporary line segment s6. Finally B5
By referring to the "pointer to the parent board line segment" for
! , and the line v 1-A can be obtained by the temporary line segment s1.

An embodiment of the shortest route determining method according to the present invention has been described above.According to this embodiment, it is possible to realize a route search means using an extended line segment search method using at least three or more wiring layers. , it is possible to process faster than the maze method, and it is also possible to determine wiring routes with fewer wiring layers than two-layer wiring. Furthermore, since the amount of detour of the route can be accurately controlled in the process of generating temporary line segments from arbitrary lattice points, the wiring route can be realized with high precision within the desired allowable amount of detour.

(2) Second Embodiment In the route search unit (510 in FIG. 5) using the line segment search method in the embodiment described in (1), a plurality of temporary line segments generated from the starting point are searched for. Added a control function that generates next-level temporary line segments from multiple grid points on temporary line segments in order of decreasing total detour amount for multiple temporary routes from the starting point to the multiple grid points. do. This situation is the 10th
As shown in the figure.

According to this embodiment, since the search is performed in order from the grid point with the smallest total amount of detours, it is possible to find the route with the smallest amount of detours among the routes that satisfy the given allowable amount of detours.

(3) Third Embodiment If the route search unit (51o in FIG. 5) using the line segment search method in the embodiment described in (1) cannot find a wiring route from the start point to the end point, A control function is added to continue the route search after increasing the total detour amount upper limit value for the wiring route from the start point to the end point given by the detour control information creation unit (5o9 in FIG. 5). This situation is shown in FIG.

According to this embodiment, the wiring ratio can be improved by gradually relaxing the set value of the total detour amount upper limit value.

〔Effect of the invention〕

According to the present invention, in a system in which a wiring pattern is determined using diagonal wiring direction wiring layers and at least three or more wiring layers, it is possible to quickly determine a wiring pattern with a small number of wiring layers. be. Further, redundant detours of the wiring pattern can be avoided, and the wiring pattern can be determined with high precision within the allowable detour limit length.

[Brief explanation of drawings]

FIG. 1 is a diagram illustrating a wiring route detour control method in a route search using a line segment search method according to the shortest route determining method of the present invention, and FIG. Figure 3 is a diagram explaining the route determination method.
FIG. 4 is a diagram illustrating a method for determining the shortest route using a multilayer wiring method using a maze method. FIG. , FIG. 5 is a block diagram showing the configuration of the wiring pattern determination system according to the first embodiment of the present invention, and FIG. 6 is a block diagram showing the configuration of the wiring pattern determination system according to the first embodiment of the present invention, and FIG.
Flowchart showing the processing procedure of 05, FIG.
8 is a diagram explaining the layer change searchable area data storage table 513 shown in FIG. 5, and FIG.
FIG. 10 is a diagram explaining the temporary line segment data storage table 515 shown in the figure, and FIG.
The figure is a diagram showing a third embodiment of the present invention. A...Start point of the wiring target section, B...End point of the wiring target section, 81, 82. −・S@−=−temporary line segment, Vlt V
Z* v3゜■4...Lattice point, P...Pin (through hole), Figure (A1) Level 3 exploration Figure Layer structure> Wiring direction> Wiring butter paste diagram A+) A picture of a child (A2) (C+) A (A+) (A2) (B+) (B2) (C1) (C1) Fig. 10 ■～■: Search Sequence chart (A) (B) Fig. 11 Detour amount suppression upper limit value: Small detour amount suppression upper limit value 2 large

Claims (1)

[Claims] 1. A method for determining the shortest route of a wiring pattern, in which a wiring pattern for connecting target wiring sections of a printed circuit board, an integrated circuit, etc. is determined using at least three or more wiring layers simultaneously: ( a) For each wiring layer, at least three wiring directions are defined as unique directions, and the wiring possible area in each wiring layer is defined as line segment data developed in the unique direction. (b) Create a searchable region for layer change to an adjacent wiring layer in each wiring layer as grid data; (c) Search for a wiring route from the start point to the end point of the wiring target section. is performed by a line segment search method that repeatedly performs a one-dimensional search from an arbitrary lattice point using the above-mentioned wiring possible area and a layer change search from the arbitrary lattice point using the above-mentioned layer changeable area, (d) Divide each wiring target area into a plurality of partial areas by all the straight lines in the specific direction of each wiring layer passing through the end point, and apply the above linear line from any grid point in each wiring layer to each partial area. Give a detour amount per unit grid in the search direction of the original search, (e) Give an upper limit to the total detour amount of the route from the starting point to the end point, and in the one-dimensional search from the arbitrary grid point to the end point. , limiting the search range according to the upper limit value of the total amount of detours and the amount of detours per unit grid. 2. In the method for determining the shortest route as set forth in claim 1, (f) for a plurality of grid points reached by route searching from the starting point, calculate the total detour amount of the route from the starting point to the plurality of grid points; A method for determining the shortest route, comprising: giving priority to the search order from the plurality of lattice points to the end point according to the magnitude of the total amount of detours. 3. In the method for determining the shortest route according to claim 1, (g) gradually increasing the upper limit given to the total detour amount of the route from the starting point to the ending point, and performing the one-dimensional search from any grid point. A shortest route determining method characterized by gradually expanding the range of. 4. In a wiring pattern shortest route determination system that determines a wiring pattern for connecting wiring target sections in a printed circuit board, integrated circuit, etc. by simultaneously using at least three or more wiring layers, (a) each of the wiring layers described above; Means for defining at least three or more wiring directions as unique directions, and creating a wiring possible area in each wiring layer as line segment data expanded in the unique direction, for each wiring layer; (b) means for creating a layer change searchable area for adjacent wiring layers in each wiring layer as grid data; (c) means for searching for a wiring route from the start point to the end point of the wiring target section; means for performing a one-dimensional search from an arbitrary grid point using a possible region and a layer change search from the arbitrary grid point using the layer changeable region repeatedly using a line segment search method; (d) Each wiring target area is divided into a plurality of partial areas by all the straight lines in the directions specific to each wiring layer passing through the end point, and the above one-dimensional search is performed for each partial area from an arbitrary grid point in each wiring layer. (e) means for giving a detour amount per unit grid in the search direction; A shortest route determining system comprising: means for limiting a search range according to an upper limit value of the total amount of detours and the amount of detours per unit grid.