JPH0477949B2 - - Google Patents

Description

[Detailed description of the invention]

[Table of Contents] [Overview] [Industrial Application Fields] [Prior Art and Problems to be Solved by the Invention] [Means for Solving the Problems] [Operations] [Example] [Effects of the Invention] [Effects of the Invention] Overview] In a method of wiring a wiring section with a specified line length L using a computer system, the Manhattan length between the starting point S1 and the ending point E1 of the wiring section taken out from the wiring section storage unit 21 is expressed as l1. In this case, the specified line length L is always longer than the Manhattan length l1. (Minimum L = l1. If L is shorter than l1, wiring is impossible.) Therefore, the specified line length L is L if the length that must be detoured is dl. It must be =l1+dl. That is, the length dl that must be detoured is dl=L-l1. The length dl that must be detoured is automatically determined because the designated line length L and the Manhattan length l1 between the starting point S1 and the ending point E1 are given. The present invention provides a point (detour point) where the rectangular distance (Manhattan length) from the two points is constant so that the locus of the point where the diagonal straight distance from the two points is constant becomes an ellipse.
This method focuses on the fact that the trajectory of Di) is octagonal (diamond). Furthermore, there is not just one type of octagon (diamond), but there are as many as the number of points that can be reached from the starting point S1 or the ending point E1. A new start point Si (i = positive integer from 1 to n) or end point Ei (i = 1 to n (a positive integer of
= positive integer from 1 to n), that is, li = l1 + Δli (Δl1 = 0) From the new starting point Si or ending point Ei, or from the starting point Si and ending point Ei, both the X direction and the Y direction are positive/negative. Detour only in one direction, and the sum of the detour length in the X direction and the detour length in the Y direction is constant L-li The points Di on each side of the octagon (diamond) formed by the set of integers) are stored in the detour point storage unit 22, and from the detour point storage unit 22, Take out one usable detour point Di that exists above,
In the wiring mechanism 12, the detour point Di and the starting point Si,
Then, wire is wired between the detour point Di and the end point Ei with a Manhattan length, and further, wire is wired with a Manhattan length between the start point S1 and the new start point Si, or between the end point E1 and the new end point Ei. This is what I did. [Industrial Application Field] The present invention relates to a specified length automatic wiring method for wiring a wiring section of a highly integrated (LSI) circuit, a multilayer printed board, etc. to a specified length. Advanced functionality for recent computer systems,
With the increase in processing power, the wiring density of highly integrated (LSI) circuits or printed circuit boards on which such circuits are mounted is becoming increasingly large. Depending on the size of the signal propagation delay caused by the wiring length, phenomena such as delay over/racing may occur, making it impossible to obtain the initial processing capacity. It's starting to come. For this reason, there has been a need for a specified automatic wiring method that can perform high-quality wiring that satisfies the above-mentioned line length restrictions with a high wiring rate in a large number of wiring sections. [Prior art and problems to be solved by the invention] FIG. 6 is a diagram illustrating an example of a conventional automatic wiring method when there is no line length specification. The automatic wiring method shown in FIG. 6 above is the so-called "line search method", and for example,
When there is an existing congested wiring area indicated by diagonal lines, if you try to automatically route between the starting point S1 and the ending point E1 using the line search method, the wiring will be detoured as shown, and there will be restrictions on the wiring length. There was a problem that it was not possible to create wiring that satisfied the following. Therefore, in the past, wiring sections (wires) with specified wire lengths were either directly wired using discrete wiring, which was easy to manage the wire length (increasing manufacturing costs), or
Alternatively, the current method is to manually embed the wiring into an empty wiring route (increasing the number of design steps). In view of the above-mentioned conventional drawbacks, the present invention automatically performs wiring for a large number of wiring sections (wires) at a high wiring rate and satisfying a specified wiring length, thereby reducing manufacturing costs and design man-hours. The purpose is to provide a method for achieving this goal. [Means for Solving the Problems] Figure 1 is a principle block diagram of the specified length automatic wiring method of the present invention. The present invention includes the following means. (1) In a method of wiring a wiring section with a specified line length L using a computer system, the Manhattan length between the starting point S1 and the ending point E1 of the wiring section taken out from the wiring section storage section 21 is l1. Then, a new starting point Si (i=positive integer from 1 to n) or ending point Ei (i=positive integer from 1 to n) is obtained by moving the starting point S1 or the ending point E1 by an arbitrary distance Δli within the detourable range. integer), and the above starting point S1, or ending point E1, or starting point S1
And when the sum of the Manhattan length Δli from the end point E1 to the above arbitrary new start point Si or end point Ei and the above l1 is li (i=positive integer from 1 to n),
That is, li = l1 + Δli (Δl1 = 0) From the new starting point SI, the ending point Ei, or the starting point Si and the ending point Ei, take a detour in either the positive or negative direction in both the X direction and the Y direction, and then An octagon (diamond) formed by the i-th (i = positive integer from 1 to n) set of points where the sum of the detour length in the direction and the detour length in the Y direction is constant L-li. The points Di on each side are stored in the detour point storage unit 22, and one usable detour point Di existing on the side of the i-th octagon (diamond) is retrieved from the detour point storage unit 22. , In the wiring mechanism 12, wiring is made between the detour point Di and the starting point Si and between the detour point Di and the ending point Ei with a Manhattan length, and furthermore, between the starting point S1 and a new starting point Si, or between the ending point E1 and the new The configuration is such that the wiring is connected to the end point Ei with a length of Manhattan. (2) Set the detour point Di on the side of the i-th (i=positive integer from 1 to n) octagon (diamond) above to 1
When extracting one, the shortest distance is searched in all directions from the starting point Si or the ending point Ei, and the point that intersects the edge of the i-th set of points (diamond) is set as the detour point Di. (3) When extracting the detour point Di on the side of the i-th (i=positive integer from 1 to n) octagon (diamond) above, find the shortest point Di in all directions from each of the starting point Si and ending point Ei. The distance is searched, and among the points that intersect with the side of the i-th octagon (diamond), the point where the intersections from the starting point Si and the ending point Ei are the same is determined as the detour point. Let it be Di. [Operation] That is, according to the present invention, if a path with the specified line length L as described below theoretically exists, it can be found without fail, and since the degree of freedom of the path is large, the wiring There is an effect of having high ability. In a method of wiring a wiring section with a specified line length L using a computer system, the Manhattan length between the starting point S1 and the ending point E1 of the wiring section taken out from the wiring section storage unit 21 is taken as l1, and the corresponding A new starting point Si (i = positive integer from 1 to n) or ending point Ei (i
= positive integer from 1 to n), and the sum of the Manhattan length Δli from the above starting point S1 or ending point E1, or starting point S1 and ending point E1 to the above arbitrary new starting point Si or ending point Ei and the above l1.
When li (i = positive integer from 1 to n), that is, li = l1 + Δli (Δl1 = 0) Both the X direction and Y direction from the new starting point SI, or the ending point Ei, or the starting point Si and the ending point Ei Detour only in one direction, either positive or negative, and the i-th point (i=1 to n The points Di on each side of the octagon (diamond) formed by the set of positive integers) are stored in the detour point storage unit 22, and from the detour point storage unit 22, Pick out one usable detour point Di that exists on the edge of
In the wiring mechanism 12, the detour point Di and the starting point Si,
Then, wire is wired between the detour point Di and the end point Ei with a Manhattan length, and further, wire is wired with a Manhattan length between the start point S1 and the new start point Si, or between the end point E1 and the new end point Ei. If wiring cannot be completed even after selecting all available detour points Di, set i=i+1 and repeat the same wiring as above. Therefore, as described above, if a path with the specified line length L logically exists, it can be found without fail, and since the degree of freedom of the path is large, the wiring ability is high. . [Examples] Examples of the present invention will be described in detail below with reference to the drawings. For convenience of explanation, the first single diamond, which is an octagon with the largest area and largest circumference, will be taken up, and then the second diamond, the third diamond, and so on will be referred to in this order. That is, i=1 i=i+1. Note that the maximum number of types of diamonds, i.e.
As mentioned earlier, there are as many maximum values imax as there are points that can be reached from the starting point S1 or the ending point E1. FIG. 2 is a diagram schematically showing the diamond wiring method according to the present invention, FIG. 3 is a flowchart showing the operation of the diamond wiring method according to the present invention, and FIG. 4 is a diagram showing the diamond wiring method according to the present invention. FIG. 5 is a diagram schematically showing one embodiment, and FIG. 5 is a diagram showing the relationship between each starting point candidate and trial order of the multi-diamond wiring method. The wiring route storage section 22, the wiring route storage section 23, and related mechanisms are the means necessary to implement the present invention. still,
The same reference numerals indicate the same objects throughout the figures. First, Fig. 2a is a diagram schematically showing the wiring method for a single diamond, which is an octagon with the first maximum circumference and maximum area.
The single diamond wiring method will be explained with reference to the figure and FIGS. 3a and 4 while referring to this figure. In Figure 2a, the Manhattan length (the shortest length along the X-axis and Y-axis) of the starting point S1 and the ending point E1 is l
1. Assuming that the specified line length is L, and the detour is made in either the positive or negative direction in both the X and Y directions, the sum of the detour length in the X direction and the detour length in the Y direction is L-l1 A set of points with a constant value constitutes the sides of the octagon shown in this figure. The applicant calls this octagon “diamond”.
It is called. That is, as shown in this figure, if a detour point D1 is set on the side of the diamond and a long distance wire is drawn between the D1 point and the starting point S1, and between the D1 point and the ending point E1, the total line length is It becomes L. To explain this fact in more detail, the diamond formed based on the present invention has a starting point S1,
Considering straight lines in the X and Y directions that pass through the end point E1,
For each straight line, the starting point S1 and the ending point E1
Let the line connecting points a and b whose distance from An octagon, the diamond described above, is formed. In this case, the actual route connecting the starting point S1 and the ending point E1 is clearly equal to the line length of the dotted line route,
The dotted line path is expressed by equation (1). That is, l1+2*(lx+ly)...(1) Now, lx+ly(L-l1)/2, so substituting this into equation (1) above yields l1+2*(L-l1)/2=L, It can be seen that it is equal to the specified length L above. Next, the wiring method for this single diamond will be explained using the flowchart of FIG. 3a and FIG. 4. First, the central processing unit (CPU) 1 executes a specific program 20 rotated in the main storage device (MS) 2 to perform the following operations. Steps 50 and 51: Select one of the wiring sections (hereinafter referred to as a wire) from the wiring section storage section 21 in the main memory (MS) 2, and select the starting point S of the wire.
1, or detour only in either the positive or negative direction (in this example, the positive direction) in both the X direction and the Y direction from the end point E1, and use the usable points on each side of the diamond as the detour point. Select as D1. If there is no usable detour point on the diamond, the wiring will be unsuccessful, but if the detour point D1 exists, the process moves to the next step. Step 52: A wiring process is performed in Manhattan length between the starting point S1 of the wire and the detour point D1 on the side of the diamond by a program executed by the central processing unit (CPU) 1. Step 53: If the detour point D1 does not allow wiring of Manhattan length, return to step 50, select another usable point on each side of the same diamond as the detour point D1, and repeat the same wiring process. If the shortest wiring is completed, the process moves to the next step 54. Step 54: Processing is performed to wire the wire between the detour point D1 and the end point E1 of the wire in a Manhattan length. Step 55: If the wiring is successful, it means that the wire has been wired with the specified length L, so after storing the wiring route in the wiring route storage section 23 on the main storage device (MS) 2. , selects the next wire from the wiring section storage section 21 described above and returns to the starting point (start) of the main wiring process, but if it fails, the starting point S1 and the detour point D1
Return to step 50 to enter the same process as if wiring could not be established between the two. When this single diamond wiring method is used, it is possible to create a specified length wiring with an unlimited number of relay vias (VIAs) and a considerably high route search ability. Next, a multi-diamond wiring method will be explained with reference to FIGS. 2b and 3b.
This multi-diamond wiring method is a method for discovering a wiring route, if it exists, in the case where the single diamond wiring method described above has failed. Step 60: Set wiring level j=1. Step 61: As described above, select one wire from the wiring section storage section 21, and set the starting point to S1 and the ending point to E1. Step 62: Start point S1 and end point E1 of the wire
The above-mentioned single diamond wiring process explained in FIGS. 3a and 4a is performed between the two. Step 63: If wiring is possible using the single diamond wiring method, the process jumps to step 70 and stores the wiring route in the wiring route storage unit 23, but if wiring is not possible, the process goes to the next step. Move. Step 64: Check whether all Sj's have been searched, and if there is any other Sj for which single diamond wiring has not been performed yet, jump to step 69 to attempt the same single diamond wiring using that Sj as the starting point. If the above level j=1, there is only one S1, so the process moves to the next step 65. Step 65: Check wiring level j < limit value. Here, the limit value jmax is theoretically allowed up to a value corresponding to the number of usable relay vias in the diamond with the first maximum circumference and maximum area, but the processing time will be enormous. , a realistic value such as jmax=10 is set. If the above-mentioned wiring level j exceeds the above-mentioned limit value, the single diamond wiring method can no longer be executed, and therefore the wiring is recognized as unsuccessful for the wire, but if it does not exceed the above-mentioned limit value If so, move on to the next step. Step 66: Perform the calculation of wiring level j=j+1. Steps 67 and 68: From the starting point Si-1 to the X direction and Y
A search line is drawn in the direction until an unusable point or edge of the diamond is reached. One of the points on the search line is, for example, S2, and with S2 as the new starting point, between the new starting point S2 and the ending point E1, {specified length L-S2 and distance Δl2 between the starting point} If we create a diamond formed by a set of points with -l1 constant, we will get the second diamond shown by the dotted line A in Figure 2b. A usable detour point D2 is taken on the non-overlapping side of this second diamond and the first diamond shown by the solid line, and between this D2 and S2 and D2 and the end point E1, as shown in Figure A. If you can wire it with Manhattan length, you will be able to discover new routes that could not be discovered with the first diamond. Even with this second diamond, all S2
If a route cannot be found by searching for the
A search line is drawn in the direction and the Y direction, and one of the points on the search line is designated as S3.
Using this S3 as a new starting point, a new diamond (third diamond) is created in the same manner between the new starting point candidate S3 and the ending point E1, and wiring is attempted. In the example shown in Figures 2b and 2, the new starting point S3 is set from the starting point candidate S2 of the second diamond, and the single diamond wiring is connected between S3 and the ending point E1 in the third diamond. Shows when it is done. Step 69: Select the starting point candidate Sj that has not yet been subjected to single diamond wiring, and jump to Step 62. A wiring method that increases the level of diamond by repeating the above process is called the multi-diamond wiring method. Figure 3b shows that, as shown in Figure 5a, if a wiring route cannot be found after trying all the starting point candidates Sj for each level of the diamond, the level of the diamond is increased. This shows the flow of operation of the wiring method. In addition, as shown in FIG. 5b, a method can be used in which the level is raised first, the game is tried, the game returns to the original level, and then the game continues to try by moving to the next starting point. In addition, in this figure, there is one starting point S1, S
In this example, there are 3 S3s and 6 S3s, which indicates that they are tried in the order of . Raise the level of the diamond to jmax,
If all reachable points from the starting point S1 are taken as the starting point candidates Sj, then if a path with the specified line length L theoretically exists using the multi-diamond wiring method of the present invention, then The route can be discovered. (Claim 1) In the above diamond wiring method, the detour point D1 is selected on the side of the diamond by simply sequentially selecting available points on the side of the diamond. However, as a modification method, there is the following method. () Search for the Manhattan length in all directions from the starting point Si or ending point Ei. In this process, only the points that intersect with the diamond at that time are set as detour point candidates Di. The detour point candidate Di and the end point E1 or the start point S1
I will try to see if I can run a wiring between the two and the length of Manhattan. (Claim 2) () Search for the shortest distance in all directions from the starting point Si. In this process, only the points that intersect with the diamond at that time are set as detour point candidates Di for the starting point Si. Search for the shortest distance in all directions from the end point Ei. In this process, only the point that intersects with the diamond at that time is set as a detour point candidate Di′ for the end point Ei. The detour point candidate Di for the starting point Si and the detour point candidate Di′ for the end point Ei are searched at the same point. If the same point is found in the process, the route connecting the detour point, the starting point, Si, and the ending point Ei with the Manhattan length is set as the wiring route. (Claim 3) When the above modified method is used, when the wiring is congested, the number of detour points Di to be selected is reduced compared to trying to search for a wiring route for all detour points.
This has the effect of shortening processing time. In this way, the present invention provides the starting point S1 of the wiring section.
, the Manhattan length with the end point E1 is l1, and the specified line length is L, then detour from the start point S1 or the end point E1 in only one direction, either positive or negative, in both the X direction and the Y direction. Then, the set of points where the sum of the detour length in the X direction and the detour length in the Y direction is constant L-l1 is an octagon (diamond).
Focusing on the formation of The feature is that the experiment is conducted on diamonds with wiring levels j (i=1 to m). [Effects of the Invention] As described in detail above, the automatic specified length wiring method of the present invention is a method for wiring a wiring section with a specified length using a computer system. Starting point S1 of wiring section
, and the Manhattan length with the end point E1 is l1, and the specified line length is L, detour only in one direction, either positive or negative, from the starting point S1 or the ending point E1 in the X direction and Y direction. Then, the points on each side of the octagon (diamond) formed by the set of points where the sum of the detour length in the X direction and the detour length in the Y direction at that time is constant L-l1 are stored in the detour point storage unit. memorize it,
One of the usable detour points D1 on the side of the octagon (diamond) is taken out from the detour point storage section, and the detour point D1 and the starting point S are extracted in the wiring mechanism.
1, and connect the wiring with the Manhattan length between the detour point D1 and the end point E1, or connect all available detour points D.
If wiring cannot be completed even if 1 is selected, a new starting point Si (i = 1 to n
positive integer) or end point Ei (i = positive integer from 1 to n)
Then, the sum of the Manhattan length Δli from the above starting point S1 or ending point E1, or starting point S1 and ending point E1 to the above arbitrary new starting point Si or ending point Ei and the above l1 is
When li (i = positive integer from 1 to n), that is, li = l1 + Δli Either positive or negative in both the X direction and Y direction from the new starting point SI, or the ending point Ei, or the starting point Si and the ending point Ei. The i-th point (i = positive integer from 1 to n) where the sum of the detour length in the X direction and the detour length in the Y direction is constant at L-li when detouring in only one direction. The points Di on each side of the octagon (diamond) formed by the set of are stored in the detour point storage unit 22, and from the detour point storage unit 22, on the i-th octagon (diamond), Since the same wiring is repeated repeatedly, if a route with the specified line length L theoretically exists, it can be found without fail, and since the degree of freedom of the route is large, This has the effect of high wiring ability.

[Brief explanation of the drawing]

Fig. 1 is a principle block diagram of the specified length automatic wiring method of the present invention, Fig. 2 is a diagram schematically showing the diamond wiring method according to the present invention, and Fig. 3 is a flowchart showing the operation of the diamond wiring method according to the present invention. The diagram shown,
FIG. 4 is a diagram schematically showing an embodiment of the present invention,
FIG. 5 is a diagram showing the relationship between each starting point candidate and the order of trials in the multi-diamond wiring method, and FIG. 6 is a diagram illustrating an example of a conventional automatic wiring method. In the drawing, 1 is the central processing unit (CPU), 2
is the main memory (MS), 11 is the detour point setting mechanism,
12 is a wiring mechanism, 20 is a program, 21 is a wiring section storage section, 22 is a detour point storage section, 23 is a wiring route storage section, S1, S2, S3...Si... are starting points, E
1,...Ei... is the end point, D1, D2, D3,...Di...
indicates the detour point, L indicates the specified length, l1 indicates the Manhattan length between the start point and the end point, and 50 to 55 and 60 to 70 indicate the operation steps, respectively.

Claims (1)

[Claims] 1. In a method of wiring a wiring section with a specified line length L using a computer system, the method comprises: The Manhattan length is l1, and the point obtained by moving the starting point S1 or the ending point E1 by an arbitrary distance Δli within the detourable range is the new starting point Si (i=positive integer from 1 to n) or the ending point Ei (i = a positive integer from 1 to n), and the sum of the Manhattan length Δli from the above starting point S1 or ending point E1, or starting point S1 and ending point E1 to the above arbitrary new starting point Si or ending point Ei and the above l1.
When li (i = positive integer from 1 to n), that is, li = l1 + Δli Either positive or negative in both the X direction and Y direction from the new starting point Si, or the ending point Ei, or the starting point Si and the ending point Ei. The i-th point (i = positive integer from 1 to n) where the sum of the detour length in the X direction and the detour length in the Y direction is constant L-li ) is stored on each side of the octagon (diamond) formed by the set of Take out one available detour point Di that exists,
In the wiring mechanism 12, the detour point Di and the starting point Si,
and wiring between the detour point Di and the end point Ei with a Manhattan length, and further wire between the starting point S1 and the new starting point Si or between the ending point E1 and the new ending point Ei with a Manhattan length. A specified length automatic wiring method featuring: 2 When extracting one detour point Di on the i-th (i=positive integer from 1 to n) side of the octagon (diamond) above, find the shortest distance from the starting point Si or ending point Ei in all directions. The specified length automatic wiring method according to claim 1, characterized in that a search is performed and a point that intersects with a side of the i-th set of points (diamond) is set as the detour point Di. . 3 When extracting the detour point Di on the i-th (positive integer from 1 to n) octagon (diamond) side, calculate the shortest distance from each of the starting point Si and ending point Ei in all directions. Perform the search, and among the points that intersect with the side of the i-th octagon (diamond), the point where the intersections from each of the starting point Si and ending point Ei are the same point is set as the detour point Di. A designated length automatic wiring method according to claim 1.