JP2674054B2 - Event-driven wiring processing method - Google Patents

Description

DETAILED DESCRIPTION [Overview] A method of determining a wiring route of a printed circuit board or a large-scale integrated circuit, for the purpose of shortening the processing time, a route with a minimum cost is searched for one net whose flag is on. Then, after turning off the flag of the net itself, when a new route is searched, the route searching means that turns on the flag of the registered related net and the new route searched by the route searching means are searched. Associated net detection means for detecting other nets that need to be redone, and registration means for registering the related net of the one net as a net to be searched again when the net detected by the related net detection means is changed. , The flag of all nets is turned on, and the processes by the route searching means, the related net detecting means, and the registering means are performed until there are no nets whose flags are on. The repeated, configured to determine the routing.

[Industrial applications]

The present invention relates to a method for determining a wiring path of a printed board or a large-scale integrated circuit by CAD (computer-aided design).

The number of wires to be processed is very large in a large-scale integrated circuit or a high-density printed board, and a huge amount of processing time is required for the automatic wiring route determination processing. Shortening is required.

[Conventional technology]

As shown in FIG. 8, the method generally used at present for determining the wiring paths of n nets is to set some order to the nets (conductor lines between two points to be wired) and The wiring is sequentially performed from the first to the n-th line, and the process ends. In the middle of the process, the nets that have already been wired are obstructed and the nets that cannot be connected are left. The remaining unconnected nets are processed by manually changing the route or by a special method, which requires a large processing man-hour.

As a method for increasing the automation wiring rate, by repeating the processing shown in FIG. 8 many times as shown in FIG. 9, the dependency on the wiring order is reduced, and unconnected nets are This will increase the possibility of wiring. That is, when an unconnected net remains in the first processing, the evaluation function is different from the evaluation function used in the first processing (for example, the first evaluation function minimizes the number of bends). In the second time, the number of vias is minimized, etc.). Here, this method will be referred to as a "repetitive improvement wiring method".

The applicant further proposed, as a method of pushing forward this "repetitive improvement wiring method", a method of advancing the repeated improvement wiring processing by allowing intersections with already-routed nets, and calling it "automatic wiring method allowing intersections". We have applied for a patent. (Japanese Patent Application No. 62-296477).

This does not obstruct the existing wiring, does not completely prohibit crossing, even though it has a very heavy "cost",
If there is no other way, or if another way becomes a very detour and it adversely affects other nets, it allows crossing. Since the iterative process is performed, in the next round, the intersected net becomes very "costly" due to the intersection, and this is avoided to search for another route.

In the wiring route search, the wiring area is usually divided into a grid shape, and a label that is incremented by 1 is added to each cell that advances from the starting point (unit area divided into a grid shape) toward the target point cell,
Although it depends on the maze method to search for the shortest route, in contrast to this, considering conditions other than the route length, as shown in Fig. 10, a different "cost" is set for movement between cells at each location, and the starting point is set. A method of searching a path with the minimum total cost from the cell to the target point cell is called a "minimum cost path search method". The above "automatic wiring method that allows crossing" allows a crossing with a very heavy "cost" to enter a cell occupied by already wired nets, and searches the wiring route by "minimum cost route search method" It is a thing. In FIG. 10, the cell numbers, ... Show the cells occupied by the already routed nets, indicating that it is very expensive to enter.

[Problems to be solved by the invention]

The conventional iterative improvement wiring method, particularly the automatic wiring method that allows crossing, has a problem that the processing time becomes very long because the wiring processing is re-executed many times for all the nets.

The problem to be solved by the present invention is to provide a wiring processing method that solves such conventional problems.

[Means for solving the problem]

FIG. 1 shows a block diagram of the principle of the event driven wiring system of the present invention.

In the figure, reference numeral 1 is a route search means, and when a route with the lowest cost is searched for one net whose flag is on and a new route is searched for, the net (own net) targeted for the route search Turn off the flag and turn on the flag of the registered related net.

Reference numeral 2 is a related net detecting means for detecting a net which needs to be searched again by the new route searched by the route searching means 1.

Reference numeral 3 is a registration means, which registers the one net as a net to be searched again when the net detected by the related net detection means 2 is changed.

(Operation)

In the present invention, in order to reduce the processing time in the iterative improvement wiring method, the process of searching a route is stopped for all the nets for each iteration, and the nets that may obviously reduce the cost are obtained. Only for that, the method of performing the route search again is adopted, thereby avoiding useless route search processing. For example, in the wiring area as shown in FIG.
It is assumed that when the route search of the net A is redone, a route having a smaller cost than the current route is obtained and the route is changed. At this time, since the net B intersects with the new route A, another route with a minimum cost (broken line) may be found by conducting a route search again. But for Net C, Net A
Since the change of does not have any effect, if the cost function is not changed, even if the route is searched again, the same route as before can be obtained. It is desirable to avoid the processing of the net, which is obviously useless to re-search the route like C.

That is, it is necessary to perform an event-driven process of re-searching only nets that may be improved by re-searching.

For that purpose, it is necessary to detect a net which has to be re-routed according to the change when the route search of a certain net results in a route different from the previous route.

There are the following two types of nets that should be re-routed.

(1) A route that intersects or overlaps with a newly determined route. (For example, Net B in FIG. 2).

(2) A route with a lower cost may be obtained by deleting the old route. (For example, the third
Net B).

The associated net detecting means 2 in FIG. 1 detects the nets corresponding to the above (1) and (2) for the new route of the net X searched by the route searching means 1.

The registration means 3 registers the net X as a net to be searched again when the detected net is changed, and sets the flag of the net to ON.

The route search means 1 determines the net whose flag is on,
The route is searched, and when it is finished, the flag of its own net is turned off. When a new route with a small cost is searched, the flag of the related net registered as the net to be searched again when this net is changed is turned on.

When a new route is searched for, the related net detection means 2 detects the related net associated therewith, and the registration means 3 registers it.

In this way, when only the nets corresponding to the above (1) and (2) are rerouted one after another, and no net corresponding to (1) and (2) is generated, the minimum solution of the cost function is obtained. If so, the process ends.

〔Example〕

The present invention will be described more specifically with reference to the examples shown in FIGS. 4 to 7.

FIG. 4 is a flowchart showing a process according to one embodiment of the present invention.

The operation will be described below according to each step of the flowchart. (A) of the figure shows the flow of the entire processing, which is as follows.

First, set the flag on for all nets,
Set the maximum value in the computer to "previous cost" (previous cost).

Route search processing is performed on nets whose flags are on.
Details of the route search processing are shown in FIG.

It is judged whether or not there is a net whose flag is on, and if it exists, the process returns to the step, and if it does not exist, the processing ends.

(B) of the figure shows the flow of the route search processing, which is as follows.

The route with the smallest cost is searched, the cost is substituted for the "new cost", and the flag of the own net is reset to off.

The value of "new cost" is compared with the value of "previous cost" of this net to determine whether "new cost" is smaller than "previous cost". If so, the process proceeds to step. If not, the process is terminated assuming that the route cannot be improved.

Set the value of "new cost" to "previous cost" and change to a new route. The flag of the net newly crossed or overlapped by the new route and the flag of the net registered as the net to be searched again is set to ON.

For a new path, it finds nets that might move to a path with a lower cost as it moves.

With respect to the net detected by the step, the net currently being processed is registered as the net to be searched again when the net is changed, and the process is terminated.

FIG. 5 is a diagram showing an example of detection of intersecting and overlapping nets. The new intersection or superposition of the steps in the flowchart of FIG. 4 by the new route can be detected as follows, as shown in FIG.
That is, if the number of the net for which the route is determined is registered in each cell in the wiring area data divided in a grid pattern,
For example, if A has already been registered in the cell that tried to register the net B, it can be immediately detected that A and B intersect or overlap.

FIG. 6 is a diagram showing a search example of a net to be searched again. The net to be re-searched in the step in the flowchart of FIG. 4 can be detected as follows, as shown in FIG. That is, if there is a net A reachable from the terminals (B, B) at both ends at a cost lower than the cost of connecting the start point cell-end point cell (between BB) when searching for a certain route B, this is To detect. This is because the movement of the net A may allow the net B to take a route with a smaller cost. In the figure, the concentric circles are schematic representations of equal-cost wavefronts starting from terminals B and B, but in practice they are carried between cells divided in a grid pattern, and in this embodiment, The numbers of other nets hit at the stage of the route search are recorded, and when this becomes a new route, these nets are recorded as nets to be searched again in step.

FIG. 7 is a diagram showing an example of registration of nets to be searched. In the present embodiment, the net to be searched again for the step in the flowchart of FIG. 4 is registered in the data structure as shown in FIG. That is, when there are two nets B and C to be searched again when the net A is changed, the nets B and C are connected with a pointer. The hatched line in the net C indicates that there is nothing following. The registration example of FIG. 7 corresponds to the contents of FIG.

〔The invention's effect〕

As described above, according to the present invention, the "repetitive improvement wiring method that allows crossing" to obtain a high wiring rate in the automatic wiring process.
It is possible to eliminate the wasteful processing in step (1) and significantly reduce the processing time, and the effect of improving the processing efficiency of the automatic wiring is extremely large.

[Brief description of the drawings]

FIG. 1 is a block diagram of the principle of the present invention, FIG. 2 is a diagram showing the influence of another net by changing the route of one net, and FIG. 3 is a diagram showing an example in which a small cost is obtained by deleting an old route. FIG. 4 is a flow chart showing a process according to an embodiment of the present invention, FIG. 5 is a diagram showing an example of detection of intersection and superposition, FIG. 6 is a diagram showing an example of detection of a net to be searched again, and FIG. 7 is a search. FIG. 8 is a diagram showing a registration example of a net to be redone, FIG. 8 is a diagram showing a normal wiring method, FIG. 9 is a diagram showing a repeated improvement wiring method, and FIG. 10 is a wiring model in which a cost is set for movement between cells. FIG. In the drawing, 1 is a route search means, 2 is a related net detection means, and 3 is a registration means.

Claims (1)

(57) [Claims] 1. A cost for moving to an adjacent cell is set for each unit cell in which a wiring area is divided in a grid pattern, and a minimum cost is set for each net from a cell determined as a start point to a cell determined as an end point. In a system that searches for a route, a route with the lowest cost is searched for one net whose flag is on, and the flag of the net itself is turned off. A route searching means (1) for turning on the flag of 1), a related net detecting means (2) for detecting another net which needs to be searched again by the new route searched by the route searching means (1), and The net detecting means (2) is provided with a registration means (3) for registering a related net of one net in the previous period as a net to be searched again when the net detected is changed. The configuration is such that the wiring route is determined by repeating the processing by the route searching means (1), the related net detecting means (2), and the registering means (3) until there is no net for which the flag is turned on until there is no net whose flag is on. The event-driven wiring processing method characterized by the above.