JPH0648488B2 - Automatic wiring method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION <Industrial field of application> The present invention relates to performance improvement of an automatic wiring method for automatically obtaining wiring of a printed circuit board or the like.

<Prior Art> Various automatic wiring algorithms for a printed circuit board have been developed so far, but they are roughly classified into a maze method and a line segment search method.

In the route method, the wiring region is divided into a grid shape, and the route is obtained by extending the search points from the start points of two points existing on the grid along the grid to the end points. In addition, the line segment search method generates line segments including the start point and line segments including the end point, and generates these line segments in the order of vertical and horizontal line segments, and then vertical and horizontal line segments. Then, the route between the two points is continuously calculated until these line segments intersect.

Generally, there are many sets of two points for obtaining a route, but all of these automatic wiring methods are for processing the two sets of points for searching a route in order. That is, a plurality of routes connecting two points are obtained, the best route among these routes is left and the others are deleted, and the next two-point set is searched.

<Problems to be Solved by the Invention> However, in such an automatic wiring method, when the wiring process progresses and it becomes difficult to search for a new route, a method of reworking an already wired portion is often used. However, since the wiring other than the best wiring is deleted when the wiring between two points is obtained, there is a problem that the flexibility is poor because there is no alternative route when the wiring is modified, and the wiring is severely distorted. It was

In order to avoid this problem, a method has been proposed in which the suboptimal route is retained at the stage of finding the route between two points.
When the wiring becomes congested, there is no room to hold a plurality of wirings, and there is a problem that the substantial effect is not sufficient.

<Object of the Invention> An object of the present invention is to provide an automatic wiring method which can be easily modified by holding a plurality of paths.

<Means for Solving the Problems> In order to solve the above problems, the present invention relates to an automatic wiring method for automatically finding a wiring path of a printed circuit board, in which a wiring region is divided in units of a grid, which is the minimum pitch of wiring. , 2 points for obtaining a route are set as nets, a plurality of routes are obtained for each of a plurality of nets, the initial value of the probability density of each route is set to 0, and the following steps to are repeated in order for each net, This is an automatic wiring method characterized in that a unique route is obtained.

A step of obtaining the cost of the route x obtained for a net from the following equation.

Cost of route x = Σ {(sum of probability densities of other nets in the lattice) + (use fee for one lattice)} However, Σ is performed for all lattices belonging to the route x.
Further, the sum of the probability densities of other nets in the lattice is a value obtained by adding the probability densities of routes which pass through the lattice forming the route x and whose start point or end point is different from the route x.

A step of obtaining the probability density of the route x from the following equation.

Probability density of route x = (cost of route x) ^-k / {Σ (cost of route) ^-k } However, Σ is performed for all routes belonging to the target net. Further, k represents the steepness of the probability distribution, and the initial value is 1.
Gradually increase.

The step of obtaining the probability density in the target grid from the following equation.

Probability Density in Target Grid = Max (Probability Density of Paths That Pass through that Grid and Belong to Target Net) However, Max represents the maximum value.

<Embodiment> FIG. 1 is a flowchart showing an embodiment of the automatic wiring method according to the present invention. In this automatic wiring method, two points for obtaining a route are called a net, and for a plurality of nets, a plurality of routes belonging to one net, that is, routes connecting two points are obtained, and their probability densities are obtained. The density is gradually made steep, and finally one route belonging to one net is determined. In FIG.
Initialize first. This initialization includes an operation that makes all probability distributions zero. Next, the route of the point (net) to be wired is obtained using an existing search method such as the maze method.
This route is not only the best route, but several types including the next best route. Next, the probability distribution of each route is calculated. This probability distribution is determined by the number of grids used, the states of other paths, and the like. Next, the probability distribution is made steep by one step to obtain its value, and it is determined from the obtained probability distribution that the route converges, that is, whether or not the route is uniquely determined. If it is uniquely determined, the wiring is determined to have been obtained, and the process is ended. If it does not converge, the route is further searched and the same operation is repeated.

FIG. 2 shows the configuration of an automatic wiring device that realizes this automatic wiring method. In FIG. 2, reference numeral 10 is a control unit, which controls the entire processing. A route search unit 11 obtains a route between nets by a maze method, for example. A probability distribution calculator 12 calculates the probability density of the obtained route by the method described later. A data area 13 is composed of a plurality of partial areas. The printed circuit board is decomposed into a grid having the minimum wiring pitch, and the partial areas of the data area 13 correspond to this grid one to one. FIG. 3 shows the structure of the partial area. In FIG. 3, 14 is the name of the net,
Alternatively, an identifier indicating whether the grid is an empty area, that is, an area where wiring is possible or an area where an obstacle is present is stored. 15 stores the probability density of each net in the lattice. The number of regions 15 increases or decreases according to the number of routes belonging to the net. The route search unit 11 and the probability distribution calculation unit 12 refer to the data area 13 as necessary and write data in this area.

Next, a method of calculating the probability density will be described. The calculation of the probability density is performed for each net based on the mutually complementary definitions shown below.

(1) Cost of route x = Σ {(sum of probability densities of other nets in the lattice) + (use fee for one lattice)} Σ is performed for all lattices belonging to the route x.

The sum of the probability densities of other nets in the lattice is the path x
Is a value obtained by adding the probability densities of routes whose starting point or end point is different from the route x, passing through the grid forming the. That is,
In FIG. 4 (A), the routes 17 to 1 passing through the grid 16 belonging to the route x and having a different starting point or end point from the route x.
It is a value obtained by adding the probability density of 9.

(2) Probability density of route x = (cost of route x) ^-k / {Σ
(Cost of route) ^-k } Σ is performed for all routes belonging to the target net.

k represents the steepness of the probability distribution, and the initial value is set to 1 and gradually increased.

(3) Probability density in the target grid = Max (Probability density of the path through the grid that belongs to the target net) Max represents the maximum value. That is, in FIG. 4 (B), the maximum of the probability densities of the routes 21 to 23 belonging to the same net and passing through the lattice 20 is taken.

That is, first define the probability density of each route,
By repeating the calculation of ~ (3) in order, the final route is obtained.

Next, a method for wiring will be described based on a specific example with reference to FIG. FIG. 5 (A) shows a printed circuit board,
It is composed of 5 × 3 grids. The shaded area is an obstacle that cannot be wired. In this state, the lattice (A) and
When the wiring connecting (A), (B) and (B) is obtained in a form that allows duplication, four routes A1, A2, B1, B2 are obtained as shown in (B).
Is required. Routes having the same letters A and B at the beginning indicate that they belong to the same net. These routes (1) ~
The result of calculating the probability density of each route by applying Eq.
Shown in the figure. In the first iteration, the probability density of each route is set to 0, the above equation (1) is applied to find the cost of each route, and then the equation (2) is applied to find the probability density. That is, since three grids are used in the route A1 and five grids are used in the A2, if the fee for use of one grid is 0.1, the route A is used.
The cost of 1 and A2 is 0.3 and 0.5 from the equation (1),
From equation (2), the probability densities are 0.62 and 0.38. Similarly, the probability densities 0.58 and 0.42 of the routes B1 and B2 are obtained. From these values, the probability density of the target grid is calculated by Eq. (3). Number of iterations 2 using equations (1) and (2)
Then, the same operation is performed to obtain the probability density of the number of repetitions 3. Next, when k = 2 and the same operation is repeated three times, and k = 3 is repeated twice, A2,
The probability density of B1 is 1, the other probability density is 0, and the route A
2, B1 is confirmed. In this example, all routes are first obtained, but an appropriate number of routes may be first obtained for each net, and may be added each time the probability density calculation is repeated. Further, although the probability density is calculated three times for each of k = 1 and k = 2, it may be calculated an appropriate number of times depending on the situation.

In this embodiment, the cost of the route is defined as the ratio of the lattice belonging to the route competing with the routes belonging to other nets, but it may be defined by other amounts. For example, instead of using a grid-like data structure, as shown in FIG. 7, each route is a node having a net name and position information of the route, and the competitive relationship between the routes is represented by an arc graph representation. It is also possible to use the sum of coupling coefficients determined according to the distance between the routes.

<Effects of the Invention> As described specifically above with reference to the embodiments, in the present invention, a plurality of routes are obtained for a plurality of nets, and the probability density of these routes is gradually made steeper. Finally, one route is decided. Therefore, since the suboptimal route is also saved in the wiring process, there is an effect that the automatic wiring which is more flexible than the conventional one can be performed, and as a result, the wiring ability can be improved.

Further, there is an effect that a plurality of routes can be always secured even if the wiring is complicated.

Further, since this automatic wiring method essentially wires all nets at the same time, it is not necessary to consider the wiring order in detail.

Furthermore, it is possible to develop a program that performs parallel processing for each net, and it is possible to speed up the processing.

[Brief description of drawings]

FIG. 1 is a flow chart showing an automatic wiring method according to the present invention, FIG. 2 is a block diagram showing the configuration of an automatic wiring device, FIG. 3 is a diagram showing the structure of a data area, and FIGS. FIG. 7 is a diagram for explaining, and FIG. 7 is a diagram showing another method for obtaining the cost. 10 ... Control unit, 11 ... Route search unit, 12 ... Probability distribution calculation unit, 13 ... Data area, 17-19, 21-2
3 ... Path, 16, 20 ... Lattice.

Claims (1)

[Claims] 1. An automatic wiring method for automatically finding a wiring route of a printed circuit board, wherein a wiring region is divided in units of a lattice having a minimum wiring pitch, and two points for obtaining a route are set as nets, and a plurality of nets are respectively set. An automatic wiring method characterized in that a plurality of routes are obtained one by one, the initial value of the probability density of each route is set to 0, and the following steps (1) to (4) are sequentially repeated for each net to finally obtain a unique route. . A step of obtaining the cost of the route x obtained for a net from the following equation. Cost of route x = Σ {(sum of probability densities of other nets in the lattice) + (use fee for one lattice)} However, Σ is performed for all lattices belonging to the route x.
Further, the sum of the probability densities of other nets in the lattice is a value obtained by adding the probability densities of routes which pass through the lattice forming the route x and whose start point or end point is different from the route x. A step of obtaining the probability density of the route x from the following equation. Probability density of route x = (cost of route x) ^-k / {Σ (cost of route) ^-k } However, Σ is performed for all routes belonging to the target net. Further, k represents the steepness of the probability distribution, and the initial value is 1.
Gradually increase. The step of obtaining the probability density in the target grid from the following equation. Probability Density in Target Grid = Max (Probability Density of Paths That Pass through that Grid and Belong to Target Net) where Max represents the maximum value.