JP2576752B2 - Rewiring method for line length violation wiring - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an automatic wiring method used for designing wiring of an LSI or the like, and more particularly to a technique for rewiring a wiring violating a line length restriction.

[0002]

2. Description of the Related Art A maze method or the like is employed as a route search method used when an automatic wiring processing apparatus determines a wiring route between two points to be connected in wiring design of an LSI or the like. Has a characteristic of adopting a route that is as short as possible (for example, "CAD for Logic Device", March 20, 1981, published by Information Processing Society of Japan, pages 43 to 50, 3.3 .3 “Wiring”). Therefore, when the wiring length is limited, a route having a wiring length shorter than the lower limit may be determined.

For example, when the two terminals 52 and 53 located at positions as shown in FIG.
A route as shown in FIG. 4 is searched. Here, assuming that the interval between the lines drawn vertically and horizontally in the drawing is 1, the line length of the path 54 is 5, which is equal to the Manhattan length. At this time, the length of the path connecting the terminals 52 and 53 is matched with the amount of delay of another wiring path.
If there is a line length limit of 17 as the lower limit and 21 as the upper limit, the route 54 in FIG. 3 falls below the lower limit of the line length limit,
Violation of line length restriction.

In such a case, conventionally, among the wirings after the automatic wiring, a wiring route that is below the lower limit of the line length limit has been manually corrected.

[0005]

As described above, conventionally, wiring that violates the line length restriction has been manually corrected, so that much time is required for the correction work, which is a major factor that delays wiring design. I was

[0006] Accordingly, an object of the invention is to interconnect path is below the lower limit value of the line length limitation, by providing a redistribution how the line length violation wiring attempting rewiring to satisfy the line length limit automatically Another object of the present invention is to reduce the work time required for wiring design.

[0007]

SUMMARY OF THE INVENTION In order to achieve the above object, the present invention rewires a line length violation wiring as follows.

[0008] From the layout information indicating the wiring state to be re-routed, a route connecting between terminals of a line length violation net that is below the lower limit of the line length limit is deleted.

Next, a search area having a size corresponding to the upper limit value of the line length restriction of the line length violation net is set, and a detour area having a size corresponding to the lower limit value of the line length limit is set in the search area. And the position cost in a rectangular area having two vertices of two terminals to be connected to the line length violation net is the highest,
Next , the position cost in the detour area outside the rectangular area is the next highest.
Ku, the position cost of the search region outside the detour region most
As a matter of course, the position cost is set at each position in the search area so that the position cost is lower outside the detour area outside the rectangular area.

[0010]

[0011]

Next, in the set search area, a path with the minimum cost connecting between the two terminals of the line length violation net is searched in consideration of the set position cost. Then, a path that satisfies the line length restriction obtained by this search is output as layout information.

[0013]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described in detail with reference to the drawings.

Referring to FIG. 1, an example of an automatic wiring processing apparatus for carrying out the method of rewiring a line length violation wiring according to the present invention includes a processing apparatus 1, a storage device 2, a violation information file 3, and a layout information file 4. It is configured.

The violation information file 3 is a file for storing violation information including identification information of a violation wiring net and line length restriction information. For example, when the net A is below the lower limit of the line length limit, data such as a lower limit line length error: net A: lower limit 20: upper limit 100 is stored.

The layout information file 4 is a file for holding layout information relating to the already-wired state to be re-wired. The layout information includes arrangement information of logic blocks (terminals), route information for connecting terminals of wiring nets, line width information, rule information such as a minimum interval between lines, and the like.

The processing device 1 is a device for executing processing relating to rewiring, and includes violation information input means 11, layout information input means 12, wiring peeling means 13, area setting means 14, route search means 15, layout information Output means 1
6 and control means 17.

The violation information input means 11 stores the violation information in the violation information file 3 as line length violation information 21 in the storage device 2.
Means to load.

The layout information input means 12 is means for loading the layout information in the layout information file 4 into the storage device 2 as the layout information 22.

The wiring peeling means 13 is means for deleting path information corresponding to the line length violation net indicated by the line length violation information 21 from the layout information 22.

The area setting means 14 enables the path search means 15 to search for a new path satisfying the line length restriction for the line length violation net from which the path information has been deleted by the wiring peeling means 13. This is a means for setting a detour area and setting a search area indicating a search range.

The bypass area is set in consideration of the lower limit of the line length limit. Although several specific setting methods are conceivable, in this embodiment, the coordinates of the two terminals to be connected to the violation net are (Xt, Yt), (Xs, Ys) (where Xt ≦ X
s, Yt ≧ Ys), the following detour area is set such that the shortest path along the outer edge of the detour area is equal to the lower limit.

A detour area; a rectangular area having two vertices, coordinates (Xt-A, Ys-A) and coordinates (Xs + A, Yt + A), where A = {(lower limit value-Manhattan length) / 4} -1 ... (1)

On the other hand, the search area is set to a range including at least the detour area. However, if a search area having an excessively large size is set, the divergence of the route search becomes large, and the search area greatly exceeds the upper limit of the line length limit. Since it is useless to search up to, it is set in consideration of the upper limit of the line length limit. Although several specific setting methods are conceivable, in the present embodiment, the following search areas are set so that the shortest route along the outermost circumference of the search area is equal to the upper limit.

A search area; a rectangular area having two vertices, coordinates (Xt-B, Ys-B) and coordinates (Xs + B, Yt + B), where B = (upper limit value-Manhattan length) / 4 (2)

The area setting means 14 sets a position cost for a route search for each position in the search area.

The position cost of each position in the search area is set so that the cost of the outer route search is always low in order to actively promote the route search outside the detour area. In this embodiment, the position coordinates (X
(p, Yp).

If the position coordinates (Xp, Yp) are not in the detour area, the position cost is set to zero.

The position coordinates (Xp, Yp) are two terminals to be connected (the coordinates are (Xt, Yt), (Xs, Y
s), if not in a rectangle having two vertices Xt ≦ Xs and Yt ≧ Ys) but in a detour area, α = min (min (| Xp− (Xt−B) |, | (Xs + B) ) −Xp |), min (| Yp− (Ys−B) |, | (Xt + B) −Yp |)) From α obtained by (3), a value obtained by the following equation is set as a position cost. Location cost = 1 + 2 × (α−1) (4)

When the position coordinates (Xp, Yp) are within a rectangle having two vertices with two terminals to be connected, a predetermined positive value is added to the maximum position cost determined by Or the position cost obtained by multiplication. In this embodiment, 6 is added to the maximum position cost.

The route search means 15 sets a minimum cost in consideration of the position cost and the diffusion cost in the search area set by the area setting means 14 as a path between two terminals to be connected to the net whose line length has been violated. This is a means for searching for a route to be. Here, the diffusion cost is a cost when one is moved from a position of a certain position coordinate to an adjacent position, and is set to 1 regardless of the diffusion direction in this embodiment. If the diffusion cost is the same regardless of the diffusion direction, the diffusion cost may be omitted.

The layout information output means 16 outputs the wiring route obtained by the route search means 15 to the layout information 22.

The control means 17 includes the violation information input means 11,
Layout information input means 12, wiring peeling means 1
3, means for controlling the entire rewiring process by the area setting means 14, the route search means 15, and the layout information output means 16, and an example of the control flow is shown in FIG.

Hereinafter, the operation of the present embodiment configured as described above will be described.

When the start of rewiring is instructed from a keyboard or the like (not shown), the control means 17 of the processing apparatus 1 starts control according to the control flow shown in FIG.

First, the control means 17 transmits the violation information input means 1
1 is started (S1 in FIG. 2).

The violation information input means 11 inputs the violation information stored in the violation information file 3 and stores it in the storage device 2 as the line length violation information 21.

Next, the control means 17 activates the layout information input means 12 (S2).

The layout information input means 12 inputs the layout information stored in the layout information file 4 and stores it as the layout information 22 in the storage device 2.

Next, the control means 17 checks whether or not unprocessed violation information remains in the line length violation information 21 (S).
3). If not, the rewiring process ends. If it remains, process S4 for one of the violation information
To S7.

Now, as shown in FIG. 3, the layout information 22 includes information of a net 51 composed of a terminal 52, a terminal 53, and a path 54 having a line length of 5 connecting the two terminals. Since the upper limit value of the line length limit of the target is 21 and the lower limit value thereof is 17, the lower limit line length error: violation information of the net 51: the lower limit value 17: the upper limit value 21 is not processed in the line length violation information 21. The processing of S4 to S7 for a violating wiring that is below the lower limit of the line length limit will be described in detail, taking the case where the remaining as an example.

First, the control means 17 activates the wiring peeling means 13 for the above violation information (S4).

The wiring peeling means 13 deletes the path information of the path 54 of the violation net 51 indicated by the violation information from the layout information 22.

Next, the control means 17 activates the area setting means 14 for the above violation information (S5).

The area setting means 14 sets a search area and a detour area for the offending net 51 by the method described above. In this case, the value of A according to the above equation (1) is
2,53 Manhattan length is 5, the lower limit of wire length limit is 1
7, A = {(17-5) / 4} −1 = 2, and a bypass area as indicated by reference numeral 56 in FIG. 4 is set.

Since the upper limit of the value of B according to the above equation (2) is 21, B = (21-5) / 4 = 4, and a search area as indicated by reference numeral 55 in FIG. 4 is set. Reference numeral 57 in FIG. 4 indicates a rectangular area having the terminals 52 and 53 as two vertices.

Further, the position cost of each position in the search area 55 is calculated and set by the above-described method. Thereby, the position cost as shown in FIG. 5 is set at each position in the search area 55. In FIG. 5, the numerical values of 01, 03, and 09 indicate the position cost of the position, and the position of the position cost 0 is indicated by a blank. With such a location cost, assuming that the spreading cost is 1 regardless of the spreading direction, the detour area 56
Although the total cost of the location cost 0 and the diffusion cost 2 is only 2 even if two grids are advanced outside, the location cost 0 in the detour area 56 is sufficient.
If we advance 1 through 2 grids, position cost (1 + 1) and diffusion cost 2
Thus, the total cost becomes 4 when the position cost 03 is advanced by two grids, and the total cost is 8 when the location cost 03 is further advanced by two grids in the area 57. Therefore, the detour area 56
In particular, it is difficult to search for a route inside the rectangular area 57 where the two terminals 52 and 53 can be connected with the shortest length, and the route is actively searched for outside the detour area 57.

When the processing of the area setting means 14 is completed, the control means 17 activates the route searching means 15 for the above-mentioned violation information (S6).

The route search means 15 determines the minimum cost route connecting the terminal 52 and the terminal 53 in the search area 55 in which the position cost is set as shown in FIG. Explore.

FIG. 6 shows a route search result of the route search means 15. In the figure, the route highlighted by shading is a route with the minimum cost obtained as a result of the route search performed by the route search means 15 from the terminal 53, and its line length is 17 and the upper limit of the line length limit is 21, All of the lower limits 17 are satisfied. The value in the circle in the figure is the number of grid passes to the grid, and the value on the right side of the circle indicates the total cost of the position cost and the diffusion cost on the route to that position.

When the processing of the route search means 15 is completed, the control means 17 performs post-processing (S7). In this post-processing, it is determined whether or not the line length of the route obtained by the route searching means 15 satisfies the line length limit. If satisfied, the violation information processed this time in the line length violation information 21 is marked as processed and successful, and then the net 51 is
The layout information output unit 16 is activated.

The layout information output means 16 outputs the wiring route searched by the route search means 15 to the layout information 22 as new route information of the net 51. As a result, information composed of the terminal 52, the terminal 53, and the path 58 connecting the two terminals as shown in FIG. 7 is stored in the layout information 22 as the information of the net 51, and the line length limited net is corrected. It has been done.

On the other hand, if the line length of the new route obtained by the route searching means 15 still does not satisfy the line length limit, the processing at that time is optional, but in the present embodiment, the control means 17 is used.
Restores the wiring path in the layout information 22 peeled off by the wiring peeling means 13 and returns the line length violation information 21
The violation information processed this time is marked as processed and unsuccessful.

After finishing the above post-processing, the control means 17 returns to the processing S3 in FIG.

As described above, when the control means 17 finishes processing all the violation information in the line length violation information 21, it ends the control.

Although one embodiment of the present invention has been described above, the present invention is not limited to the above embodiment, and various other additions and changes are possible. For example, the following is also possible.

The wiring stripping means 13 deletes all other wiring routes existing in the search area from the layout information, and the area setting means 14 searches the route so as to avoid the existing wiring position as much as possible. After setting the position cost of the position where the wiring is located to the maximum cost, the route search means 15 searches for the minimum cost route. If the wiring route obtained by this search satisfies the line length limit, the layout information output means 16 outputs the wiring route to layout information. At this time, the control unit 17 checks whether or not the wiring route is a route that passes through the position where the wiring has been made. If the wiring route does not pass, the deleted wiring route is returned to the layout information. On the other hand, in the case of a route that passes through the position where the wiring has already been made, the wiring route that did not pass through the wiring route among the deleted other wiring routes is returned to the layout information as it is,
With respect to the already-routed route that has passed, a route that does not pass through another route is newly obtained by the re-routing process, and is returned to the layout information.

As described above, according to the present invention, the wiring path of the line length violation net is deleted from the layout information, and a search area having a size corresponding to the upper limit of the line length restriction of the line length violation net is set, and the search area is set. A detour area having a size corresponding to the lower limit of the line length limit is set in the search area, and a position in a rectangular area having two vertices at two terminals to be connected to the line length violation net is set.
Location cost is highest, out of the rectangular region of the detour region
The search is performed such that the position cost is the next highest and the position cost in the search area outside the detour area is the lowest, but the position cost is lower on the outer side in the detour area outside the rectangular area. A position cost is set at each position in the area, a path with the minimum position cost is searched as a new path between two terminals to be connected to the line length violation net, and a path that satisfies the line length restriction obtained by the search is searched. Output to the layout information, it is possible to correct a wire length violation net that is below the lower limit of the wire length limit without human intervention, and it is possible to design wiring quickly by shortening the work time required for the correction. .

[Brief description of the drawings]

FIG. 1 is a block diagram showing an example of an automatic wiring processing apparatus for implementing a method for rewiring a line length violation wiring according to the present invention.

FIG. 2 is a flowchart illustrating an example of a control flow of a control unit.

FIG. 3 is a diagram illustrating an example of a net that is below a lower limit of a line length limit.

FIG. 4 is a diagram showing a setting example of a search area and a detour area.

FIG. 5 is a diagram showing an example of a position cost set in a search area and a detour area.

FIG. 6 is a diagram illustrating a state of searching for a minimum cost route.

FIG. 7 is a diagram illustrating an example of a net after correction.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Processing apparatus 11 ... Violation information input means 12 ... Layout information input means 13 ... Wiring peeling means 14 ... Area setting means 15 ... Route search means 16 ... Layout information output means 17 ... Control means 2 ... Storage device 21 ... Line length Violation information 22: Layout information 3: Violation information file 4: Layout information file

Claims (1)

(57) [Claims] 1. A route connecting terminals of a wire length violation net below a lower limit of a wire length limit is deleted from layout information indicating a wiring state to be rerouted, and a wire length of the wire length violation net is removed. A search area having a size corresponding to the upper limit value of the limit is set, and a detour area having a size corresponding to the lower limit value of the line length limit is set in the search area, and two terminals to which the line length violation net is to be connected are set. Is the highest in the rectangular area having two vertices, the position cost in the detour area outside the rectangular area is the next highest, and the position cost in the search area outside the detour area is the lowest. Of course, in the detour area outside the rectangular area, the position cost is set at each position in the search area so that the position cost becomes lower toward the outside, and the set cost is set in the set search area. Consider location costs Searching for a path with the minimum cost connecting the two terminals of the line length violation net, and outputting a path satisfying the line length restriction found by the search to the layout information. Rewiring method of violating wiring.