JPH0743737B2 - Wiring route determination method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION <Industrial field of application> The present invention relates to a wiring route determination method effective in automatically determining an optimum wiring route using CAD or the like.

<Prior Art> In the circuit design of a high-density integrated circuit, a printed wiring board, or the like, in order to increase the integration density, it is required to shorten the wiring distance connecting multiple points as much as possible.

Maze method, line segment search method, and the like are known as conventional wiring route determination methods. For example, in the maze method, the wirable area is divided into a grid shape, and each grid is given a certain weight to determine the optimum wiring path having the minimum weight value.

<Problems to be Solved by the Invention> However, the conventional determination method has the following problems. For example, in FIG. 7, the wiring prohibited areas shown by the symbols W, X, Y, and Z are preset, and the symbols CC 'and BB' are set.
It is assumed that the wiring route connecting the points indicated by is already determined as shown by the solid line. In this state, next, in order to connect both points indicated by the reference sign AA ′, it is unavoidable to connect them by the route shown by the broken line in the figure. That is, in the conventional algorithm, the wirable area is divided vertically and horizontally with a constant unit width, and is sandwiched between the wire prohibited areas (between W and X in this example).
When a plurality of wiring paths pass through, the wiring paths are sequentially arranged by shifting by one unit width. Therefore, CC ', BB'
It is impossible to obtain a solution by interrupting the AA ′ wiring route while the wiring route of A exists. Therefore, the detour shown by the broken line is inevitable. for that reason,
In the conventional method of determining the wiring route between multiple points, there is a limit in shortening the overall wiring length.

The present invention has been made in view of the above circumstances, and has more flexibility in determining a wiring route than in the past, so as to reduce the wiring distance as a whole in multipoint wiring. The purpose is to be able to make decisions.

<Means for Solving the Problems> The present invention adopts the following configurations in order to achieve the above object.

That is, in the wiring route determination method of the present invention, first, the wirable area existing between the wiring prohibited areas is regarded as a boundary line of the wiring prohibited area, and a coordinate system including the wiring prohibited area and the boundary line is formed. .

Next, from the start point to the end point to be connected, connectable branch points are sequentially selected as candidate points from the branch points existing on the boundary line, and the distance from the start point to each selected candidate point is determined. In the case of integrating and checking the intersection with the existing wiring route and intersecting with the existing line, a route that gives the minimum value of the weighted integrated value while adding the preset weight of the intersection to the integrated value is added. Search for. Then, the route that gives the minimum integrated value at the time when the end point is reached is determined as the wiring route.

<Operation> According to the above configuration, instead of dividing the wirable area in advance by a predetermined unit width as in the conventional case to determine the wiring route,
The wireable area existing between the wire prohibited areas is regarded as the boundary line of the wire prohibited area, and a coordinate system composed of only the wire prohibited area and the boundary line is formed, and the wiring route is determined on this coordinate system. Even when a plurality of wiring paths pass through the space between them, a new wiring path can be obtained as a solution by interrupting while existing wiring paths exist.

Moreover, a candidate point is selected from among the branch points on the boundary line, the intersection from the starting point to the candidate point is integrated, and the intersection with the existing wiring route is checked. Since the weights of the wiring are added, the weighting value of the crossing is appropriately adjusted according to the tolerance of the circuit design to select whether to bypass the crossing of the wiring route or use the through hole. Can be done freely.

Therefore, it is possible to always determine the optimum wiring route for connecting the multiple points.

<Embodiment> FIG. 1 is a plan view showing a relationship between a wiring prohibited area provided on a substrate and a wiring path connected between each connection point. In the description of the wiring route determination method of the present invention, in this embodiment, the wiring prohibited areas shown by the symbols W, X, Y, and Z are preset, and the wirings connecting the points shown by the symbols CC 'and BB' are connected. It is assumed that the route has already been determined as indicated by the solid line.

In this state, in order to newly connect the two points indicated by the reference sign AA ′, first, as shown in FIG. 2, the wirable area V existing between the wiring prohibited areas W to Z is set to the wiring prohibited areas W to Z. The boundary line L is regarded as the boundary line L, and a coordinate system including only the wiring prohibited areas W to Z and the boundary line L is configured. Therefore, on the boundary line L, there are branch points from to due to the existence of the wiring prohibited areas W to Z.

Next, a search procedure for connecting the two connection points AA 'with the shortest distance using this coordinate system will be described with reference to the flowchart shown in FIG. In the following explanation,
The “data file” means the coordinates of candidate points that are sequentially selected as connectable from the branch points existing on the boundary line in the course of searching the wiring route from the start point A in all directions and the start point to the candidate point. It means that the data including the integrated value of the distance has been registered.

First, regarding the point A as the start point and the point A ′ as the end point, both points A,
Register the coordinates of A'in the data file (step s1),
Further, "0" is given as an integrated value of the distance of the starting point A to make these initial values (step s2). Next, the route having the smallest integrated value of the distances from the starting point A is taken out from the data file (step s3), and the tip coordinates of this route (which initially coincides with the starting point A) coincide with the coordinates of the end point A '. It is determined whether or not (step s4). Since they do not match at first, a branching point (and in this example) that can be connected from the starting point A is subsequently selected as a candidate point, and the number of candidate points n (= 2).
And register it in the data file (step s5). Then, the integrated value from the starting point A to one candidate point (for example, the integrated value between A- is "4") is obtained (step s8). In addition, in this step 8, the intersection with the existing wiring route is checked, and when intersecting with the existing line, a preset weight of the intersection is added to the above integrated value. In this example, since there is no intersection with the existing line, after registering the integrated value "4" in the data file, the candidate score n is decremented by one (step s9), and the process returns to step s6. If the number of candidate points n is not 0, there are still candidate points remaining, so the integrated value from the starting point A to other candidate points (in this example, the integrated value between A- is "2") is calculated (step s8), after registering the integrated value "2" in the file, the candidate score n is decremented by one (step s9), and the process returns to step s6. In this state, each data of the route and integrated value registered in the data file is
As shown in FIG.

In this state, the candidate score n becomes 0, so that the process returns to step s3 and the path with the smallest weight is taken out from the data file.
Here, since the integrated value of the route A- is the smallest, the data of this route is taken out. Subsequently, it is determined whether or not the coordinates of the tip of the path A- (coordinates of the branch point) match the coordinates of the end point A '(step s4). Since there is a mismatch at this stage, the next candidate point connectable from the branch point (in this example) and the number n (= 2) of the candidate points are subsequently registered in the data file (step s
Five). Next, the integrated value of the distance from the starting point A to one candidate point selected via the branch point (for example, A
The integrated value of the --- route is calculated as "10", this integrated value "10" is registered in the data file, the candidate score n is decremented by one (step s9), and the process returns to step s6. If the number of candidate points n is not 0, there are still candidate points, so the integrated value of the distance from the starting point A to another candidate point via the branch point (the integrated value of the route A --- is " 9 ") is obtained (step s8), the integrated value" 9 "is registered in the file, the candidate score n is decremented by one (step s9), and the process returns to step s6. In this state, the data of the route and the integrated value registered in the data file are as shown in FIG. 4 (b).

In this state, the number of candidate points n is 0, so the process returns to step s3, and the route with the smallest integrated value is taken out from the data file. Here, since the integrated value of the A- route is the minimum, the data of the A- route is extracted. Then, the tip coordinates (coordinates of the branch point) of this A-route are the end points A '.
Discriminates whether or not they match the coordinates of (step s
Four). Since there is a mismatch at this stage, the next candidate point (only in this example) connectable from the branch point and the number n (= 1) of the candidate points are subsequently registered in the data file (step s5). Then, after registering the integrated value of the distance from the starting point A to the candidate point via the branch point (the integrated value of the route of A-- is “20”) in the data file, the candidate point number n is decreased by one (step s9), and returns to step s6.
In this state, each data of the route and the weight registered in the data file is as shown in FIG. 4 (c).

Subsequently, returning to step s3, the path with the smallest weight is extracted from the data file. Here, since the weight of the A− route is the minimum, the data of this A− route is extracted.

In this way, the above steps s3 to s9 are repeated to search for the route that gives the minimum integrated value, and when the coordinates of the tip of the searched route match the end point, the minimum integrated value at that point is reached. The route that gives the value is determined as the wiring route (step s10).

Whether or not there is an intersection with the existing track in step s8 is determined as follows.

Connection information is provided in advance in eight directions for each of the branch points. For example, regarding the branch point, as shown in FIGS. 5 (a) and 5 (b),
Information about other branch points connected centering on is added.
Then, in FIG. 2, the existing wiring path is B--
-B ', and the route to be newly wired is A ---
In the case of A ′, the confluence point and the branch point of the portion where the newly routed line overlaps the existing line are examined. That is, as shown in FIG. 6, the merging point of the lines A to A'with respect to the lines B to B'is and the branch point is. Then, at the confluence, the line is located on the right side when the B-line is viewed from the center. On the other hand, at the branch point, the -A 'line is located on the right side when the -B' line is centered. That is, it can be seen that both lines do not intersect because they are on the same side. By the way, when a part of the new wiring path exists as a line ---- at the branch point, looking around the B'line--
Since the track is located on the left side, the existing side is different at the confluence and branch points, so it can be seen that both tracks intersect.

If you want to avoid the intersection with the existing line, if you set the weight of the intersection to be large in step s8, the integrated value will also be large, so it will be excluded from the wiring route candidates in step s3 and another route that does not intersect will be searched. It will be. Therefore, by appropriately adjusting the weighting value of the intersection in accordance with the tolerance of the circuit design, it is possible to freely select whether to avoid the intersection to bypass the wiring path or to adopt the through hole.

<Effects of the Invention> According to the present invention, the conventional restrictions when determining a wiring route are relaxed, and even if there is an existing wiring route between the wiring prohibited areas, both wiring routes are provided. A new wiring route can be determined by cutting in between. Therefore, the wiring distance as a whole can be shortened as much as possible. Moreover, by appropriately setting the weighting value of the intersection in accordance with the tolerance of the circuit design, it is possible to freely adjust whether to avoid the intersection of the wiring paths and to make the detour or to use the through hole. Therefore, it is possible to always determine the optimum wiring route for connecting multiple points.

[Brief description of drawings]

1 to 6 show respective embodiments of the present invention, and FIG. 1 is a plan view showing the relationship between a wiring prohibited area provided on a substrate and a wiring path connected between each connection point, FIG. 2 is an explanatory diagram of a coordinate system configured when determining a wiring route,
FIG. 3 is a flowchart of a wiring route search procedure, FIG. 4 is an explanatory diagram showing the contents of data on the way of searching the wiring route, FIG. 5 is an explanatory diagram of branch information set at each branch point of the coordinate system, and FIG. The figure is an explanatory diagram of a method of determining whether or not there is an intersection with an existing wiring route. FIG. 7 is a plan view showing the relationship between the wiring prohibited area provided on the substrate and the wiring path connected between the connection points for explaining the conventional wiring path determination method. W-Z ... Wiring prohibited area, V ... Wiring possible area, L ... Boundary line, ...... Branch point, A ... Start point, A '... End point.

Claims (1)

[Claims] 1. A writable area existing between wiring prohibition areas is regarded as a boundary line of the wiring prohibition area, and a coordinate system composed of the wiring prohibition area and the boundary line is constructed. From the to the end point, connectable branch points are sequentially selected from the branch points existing on the boundary line as candidate points, the distances from the start point to each selected candidate point are integrated, and the existing If the intersection with the wiring route is checked and if it intersects with the existing line, the route that gives the minimum weighted integrated value is searched while adding the preset intersection weight to the integrated value, and the end point is reached. A wiring route determining method, characterized in that a route that gives a minimum integrated value at a time point is determined as a wiring route.