JP3569433B2 - Automatic wiring device - Google Patents

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to an automatic wiring device that determines wiring using a computer.
[0002]
For the wiring design of a printed circuit board or the like, a computer is used by a computer program such as CAD to automatically determine a wiring route. It is necessary that the wiring route satisfies wiring restriction conditions (interval between wires, interval between wires and vias, interval between vias, etc.). As the mounting density increases, there is a need for an automatic wiring device that efficiently obtains appropriate wiring.
[0003]
[Prior art]
FIG. 9 is an explanatory diagram of a conventional technique.
9 (a) and 9 (b),
111 is a via A.
[0004]
Reference numeral 112 denotes a via B.
Reference numeral 113 denotes a line segment, which is a wiring.
Reference numeral 114 denotes a back wiring, which is a line connecting the via A (111) and the via B (112).
[0005]
The distance between the via A (111) and the line segment 113 is L1.
The distance between the via B (112) and the line segment 113 is L2.
The distance between the via A (111) and the via B (112) is L3.
[0006]
It is assumed that the distances L1 and L2 between the via and the line segment satisfy the constraint on the distance between the via and the line segment. There are further restrictions on vias, and there is a requirement that the distance between vias must be larger than that obtained by doubling the distance between line segments and vias. That is, in FIG. 9A, L3> 2 × L1 and L3> 2 × L2 must be satisfied. FIG. 9A does not satisfy this condition because L3 = 2 × L1 and L3 = 2 × L2.
[0007]
FIG. 9B satisfies this condition because L3> 2 × L1 and L3> 2 × L2.
FIG. 9C shows an example of vias arranged in a staggered pattern on a square lattice.
[0008]
115 is a line segment of the wiring.
In order to satisfy the above constraint on the interval between vias, in the conventional automatic wiring device, the positions of the vias generated in the route search are generated in a staggered pattern on a square lattice as shown in FIG. 9 (c). Like that. The via position obtained for the via at such a position automatically satisfies the constraint on the interval between vias.
[0009]
[Problems to be solved by the invention]
FIG. 10 is an explanatory diagram of a problem to be solved by the invention.
FIG. 10A shows a case where the via arrangement does not satisfy the condition of the via arrangement interval.
[0010]
Reference numeral 111 denotes a via A, which is arranged on a square lattice.
Numeral 112 denotes a via B, which is arranged on a square lattice.
113 is a line segment.
[0011]
The distance between the via A (111) and the line segment 113 and the distance between the via A (111) and the via B (112) with respect to the distance between the via B (112) and the line segment 113 do not satisfy the above-described constraint.
[0012]
FIG. 10B shows a staggered via including the via A.
In FIG. 10, vias C, D, and E are vias in a staggered pattern including the via A. Reference numeral 116 denotes a region where the surface is a wiring prohibited region and vias cannot be arranged.
[0013]
In FIG. 10B, the via having the best condition (the shortest path via) with respect to the via A is the via E, but the via E cannot be arranged due to the wiring prohibited area 116 on the surface. Therefore, the optimum wiring route cannot be obtained.
[0014]
FIG. 10C shows a state where wiring is performed by a via that is not at the position of the staggered pattern including the via A.
In FIG. 10C, a via F is a via located at a position outside the via group of the staggered pattern including the via A. It is assumed that an optimal route is provided by the via A and the via F. The distance between the via A and the via F satisfies the constraint of the distance between the via A and the via F with respect to the distance between each via (via A, via F) and the line segment 113.
[0015]
As described above, in the conventional automatic wiring, vias can be arranged only in one kind of via group of the staggered pattern. Therefore, as shown in FIG. However, even when the optimum route can be obtained by the above, the wiring route cannot be actually obtained.
[0016]
SUMMARY OF THE INVENTION An object of the present invention is to provide an automatic wiring device that can automatically wire vias at any positions on a square lattice.
[0017]
[Means for Solving the Problems]
According to the present invention, there is provided an automatic wiring apparatus for automatically obtaining a wiring by a computer, wherein a path searching means for searching a wiring path from a start point to an end point in accordance with wiring information, and a wiring path obtained by searching for each point on a square grid. A square grid via setting means for setting a via at a grid point requiring a via; and a grid point on a square grid, where A is an arbitrary point on the square grid, and a point which includes the grid point A and forms a staggered pattern. Group 1 as a group 1, a via group 1 setting means for setting a via to a grid point requiring a via in the search of the group 1, and a point adjacent to a point included in the group 1 on a square grid, A group 2 setting means for setting a via to a grid point requiring a via in the search for the group 2 in a search for the group 2 with a point which becomes a staggered pattern in which the grid points are shifted, a gap between the via and a line segment, Constraint condition determination means for determining whether or not the relationship between the intervals between the two vias satisfies the constraint condition, wherein the path search means includes a via arranged on a wiring route obtained by searching for a square lattice point. However, when the constraint condition is not satisfied, a route search is performed for a grid point of Group 1 including a grid point where a via that does not satisfy the constraint condition is arranged, and a via is set at a grid point that is an optimum wiring route. If the via set from group 1 satisfies the above constraint, the obtained optimum wiring route is output. If no via satisfying the constraint is found in the search for the grid point of group 1, the grid point of group 2 is output. A route is searched for, a via is set at a grid point to be the optimum wiring route, and if the via set from the group 2 satisfies the above-mentioned constraint condition, the obtained optimum wiring route is output. One.
[0018]
FIG. 1 is a diagram showing a basic configuration of the present invention.
FIG. 1A shows the device configuration.
In FIG. 1 (a),
1 is an automatic wiring device.
[0019]
Reference numeral 2 denotes a route search means for performing a route search for finding an optimal route from the start point to the end point.
Numeral 3 denotes a square lattice via setting means for generating a via at an arbitrary position on the square lattice.
[0020]
Reference numeral 4 denotes via group 1 setting means for generating vias in via group 1 on a square lattice. For example, a via is generated in a staggered pattern 1 on a square lattice.
[0021]
Reference numeral 5 denotes via group 2 setting means for setting a via to a via group 2 different from the via group 1 on the square lattice. The via group 2 is, for example, a staggered pattern, and is a staggered pattern 2 in which one lattice point is shifted on the square lattice with respect to the staggered pattern 1.
[0022]
Numeral 6 denotes a constraint condition judging means for judging whether the interval between the vias satisfies the constraint condition or not.
FIG. 1 (b) is a flowchart of the operation of the configuration of FIG. 1 (a).
[0023]
Before explaining FIG. 1B, the basic configuration of the present invention will be conceptually described with reference to FIGS.
FIG. 2 is an example of a via group of the present invention, showing an example of a staggered pattern.
[0024]
In FIG. 2, a circle represents a via arranged on a square lattice. The via of number 1 is the via group 1 of the staggered pattern 1. The via of No. 2 is the via group 2 of the staggered pattern 2.
[0025]
Hereinafter, the present invention will be described by taking as an example the case where the via group 1 is the staggered pattern 1 and the via group 2 is the staggered pattern 2.
FIG. 3 illustrates the operation of the basic configuration of the present invention.
[0026]
In FIG. 3A, reference numeral 21 denotes a via A. 22 is a via B. 23 is a line segment connected to the via A. Reference numeral 24 denotes a line segment which is wired between the via A and the via B. A line segment 25 is connected to the via B. FIG. 3A shows that the vias A and B do not satisfy the via interval constraint.
[0027]
FIG. 3B shows the via arrangement of the via group 1 (staggered pattern 1).
In FIG. 3B, a via A (21), a via C, a via D, and a via E are vias in a staggered pattern 1. Reference numeral 30 denotes an area whose surface is a wiring prohibited area.
[0028]
The via E is a via that provides an optimum path, but the via E cannot be arranged because the surface is the wiring prohibited area 30. Therefore, the staggered pattern 1 indicates that the optimum route cannot be obtained.
[0029]
FIG. 3C shows a case in which a via is obtained by a via group 2 (staggered pattern 2) different from the via group 1.
Via F (28), via G, via H, and via I are the via groups of the staggered pattern 2. The via F provides an optimum route. Reference numeral 29 denotes a back wiring, which connects the via A (21) and the via F (28) on the back.
[0030]
Since the via of the optimum route was not found in the staggered pattern 1, the via is found in the staggered pattern 2. As a result, the optimum route can be obtained from the via F (28).
[0031]
In the conventional automatic wiring device, only vias on the staggered pattern 1 could be obtained. Therefore, when the via E could not be obtained, a wiring route could not be obtained. Even in such a case, according to the present invention, the optimum route can be obtained by using the staggered pattern 2 via.
[0032]
The operation of the basic configuration of the present invention shown in FIG. 1A will be described with reference to FIG.
S1 A route search is performed at a via position on an arbitrary square lattice (for example, via B is obtained for via A in FIG. 3).
[0033]
S2, S3 The constraint condition of the interval between the vias is determined. If the constraint condition is satisfied, the process ends. If not, the process of S4 is performed.
S4 Since the via obtained in S1 does not satisfy the constraint of the interval between the vias, the route search is performed in the via group 1.
[0034]
S5, S6 It is determined whether the optimal route has been determined. If found, the process ends. If not found, the process of S7 is performed.
S7 Since the optimal route was not found for the via of the via group 1, the route search is performed for the via group 2.
[0035]
According to the present invention, a wiring can be obtained by a via at an arbitrary position on a square lattice. Then, only when the vias on the square lattice do not satisfy the constraint condition, the optimum route can be obtained in the via group 1. Further, when the optimum route is not found in the via group 1, the route search can be performed in the via group 2, so that the degree of freedom in wiring is increased and the optimum wiring can be found efficiently.
[0036]
BEST MODE FOR CARRYING OUT THE INVENTION
FIG. 4 shows an embodiment of the device configuration of the present invention.
In FIG.
Reference numeral 41 denotes a square lattice via setting unit, which generates a via on the square lattice.
[0037]
Reference numeral 42 denotes via group 1 setting means for generating vias in a staggered pattern 1 on a square lattice.
Reference numeral 43 denotes via group 2 setting means for generating vias in a staggered pattern 2 on a square lattice.
[0038]
Reference numeral 44 denotes a route search unit for finding a wiring route (start point and end point) according to the wiring information.
Reference numeral 45 denotes a constraint condition determination unit which determines whether or not an interval between vias, an interval between line segments, and the like satisfy a predetermined constraint condition with respect to the obtained wiring route.
[0039]
Reference numeral 46 denotes a route information holding unit which holds wiring information (a start point, an end point, and the like of a route search) for wiring.
Reference numeral 51 denotes a wiring data holding device which holds data such as the shape and size of a component, and data such as the type and width of a line segment.
[0040]
Reference numeral 53 denotes a component data holding unit that holds data such as the shape and size of the component.
A line segment data holding unit 54 holds data such as the width and type of a line segment.
[0041]
Reference numeral 89 denotes an output device.
90 is an input device.
The operation of the configuration of FIG. 4 will be described.
[0042]
The wiring information is provided by the input device 90 and held in the route information holding unit 46. The route search unit 44 determines a wiring route according to the component data, the wiring data, and the wiring information. At this time, if a via is required, the via is set at a required position by the square lattice via setting unit 41. Then, the route search unit 44 performs a route search to obtain an optimum route. The constraint condition determination unit 45 determines whether the via of the obtained optimum route satisfies the constraint condition or does not satisfy the constraint condition. If the constraint condition is satisfied, the obtained optimum route is output. If the vias taken on the square lattice do not satisfy the constraint of the interval between the vias, the via group 1 setting means 42 arranges the vias in the staggered pattern 1 and obtains the wiring route. Then, the route search unit 44 obtains an optimum route from the via of the staggered pattern 1. Then, when the optimum route is obtained, the optimum route is output. When the optimum route is not obtained in the staggered pattern 1, the via group 2 setting means 43 arranges a via in the staggered pattern 2. Then, the route search unit 44 obtains an optimum wiring route using the staggered pattern 2 via. If the optimum route is obtained, the wiring is output. If the optimum route is not found in the staggered pattern 2, the process of finding the target route ends. Then, a route search for the next wiring is performed.
[0043]
FIG. 5 shows an embodiment of the system configuration of the present invention.
In FIG.
61 is a computer.
[0044]
62 is a CPU.
63 is a memory.
Reference numeral 64 denotes an automatic wiring program loaded in the memory.
[0045]
Reference numeral 65 denotes component data loaded in the memory.
66 represents line segment data loaded in the memory.
Reference numeral 67 denotes wiring information, which represents wiring information loaded into the memory.
[0046]
A storage medium 80 stores an automatic wiring program, and is a magnetic storage medium such as a floppy disk, an optical storage medium such as a CDROM, or a storage medium capable of storing other test programs.
[0047]
81 is an automatic wiring program.
Reference numeral 82 denotes a square lattice setting program.
83 is a via group 1 setting program.
[0048]
84 is a via group 2 setting program.
85 is a route search program.
Reference numeral 86 denotes a constraint condition program, which is a program for determining a constraint condition.
[0049]
A storage medium drive device 87 loads a test program stored in the storage medium 80 into the computer 61.
An input device 90 is an external storage device such as a keyboard and a mouse for inputting wiring information and the like or a magnetic disk device for storing wiring information.
[0050]
Reference numeral 91 denotes a display for displaying and outputting wirings and the like.
Reference numeral 92 denotes a printer which prints out wiring and the like.
Reference numeral 94 denotes an external storage device, such as a magnetic disk device, which holds the obtained wiring.
[0051]
FIG. 6 is a flowchart of an embodiment of the device configuration of the present invention.
S1 A via is set on a square lattice.
S2 Perform wiring.
[0052]
S3, S4 It is determined whether the space between the vias satisfies the constraint condition. If it is satisfied, the obtained wiring is output, and the process is terminated. If it is not satisfied, the process of S5 is performed.
[0053]
S5: Set a via for the staggered group 1.
S6 Wiring is performed using the staggered group 1 via.
S7 It is determined whether a route has been obtained. If found, the wiring is output and the process is terminated. If not found, the process of S8 is performed.
[0054]
S8 A via is set to the via group 2 (staggered pattern 2).
S9 Wire. If the route is obtained, the wiring is output and the process is terminated. If not found, the process ends.
[0055]
An embodiment of the wiring obtained by the present invention will be described with reference to FIGS.
In FIG.
21 is a via A.
[0056]
22 is a via B.
23 is a line segment.
Reference numeral 29 denotes a back wiring connecting the via A and the via B.
[0057]
FIG. 7 (a) shows a case where a wiring is obtained with vias obtained on a square lattice, and the interval between the vias A and B satisfies the regulation.
FIG. 7 (b) shows a case where a wiring is obtained with a via obtained on a square lattice, but the interval between the via A and the via B does not satisfy the constraint condition. In such a case, a route search is performed next with the staggered pattern 1 via (see FIG. 7C).
[0058]
FIG. 7C shows an example in which a route is obtained by a via of the group 1 setting unit (staggered pattern 1).
FIG. 8 shows an example in which a route has been obtained in the via group 1 (staggered pattern 1) and the via group 2 (staggered pattern 2).
[0059]
In FIG.
Reference numeral 21 denotes a via A, which is a staggered pattern 1 via.
Reference numeral 22 denotes a via B, which is a staggered pattern 2 via.
[0060]
23 is a line segment.
Reference numeral 29 denotes a back wiring connecting the via A and the via B.
Reference numeral 221 denotes a via C, which is a via of the via group 2.
[0061]
Reference numeral 222 denotes a via D, which is a via of the via group 2.
223 is a line segment.
Reference numeral 229 denotes a back wiring, which is a line segment connecting the via C and the via D.
[0062]
FIG. 8 shows a via of the staggered pattern 1 and a part of wiring is obtained by the via A and the via B. However, since there was a wiring that could not be obtained with the staggered pattern 1 via, a route search was further performed with the staggered pattern 2 via, and a wiring route was obtained with the vias C and D.
[0063]
【The invention's effect】
According to the present invention, a route search can be performed by arranging an arbitrary position via on a square lattice, and a route search can be performed also in the via group 1 and the via group 2, so that the degree of freedom in wiring is increased and the optimum wiring is efficiently obtained. be able to.
[Brief description of the drawings]
FIG. 1 is a diagram showing a basic configuration of the present invention.
FIG. 2 is a diagram illustrating an example of a via group according to the present invention.
FIG. 3 is an operation explanatory diagram of a basic configuration of the present invention.
FIG. 4 is a diagram showing an embodiment of an apparatus configuration of the present invention.
FIG. 5 is a diagram showing an embodiment of a system configuration of the present invention.
FIG. 6 is a diagram showing a flowchart of the embodiment of the present invention.
FIG. 7 is a diagram showing an embodiment of the present invention.
FIG. 8 is a diagram showing an embodiment of the present invention.
FIG. 9 is an explanatory diagram of a conventional technique.
FIG. 10 is an explanatory diagram of a problem to be solved by the invention.
[Explanation of symbols]
1: Automatic wiring device 2: Route search means 3: Square lattice via setting means 4: Via group 1 setting means 5: Via group 2 setting means 6: Constraint condition judging means

Claims (1)

In an automatic wiring device that requires wiring automatically by a computer,
Route search means for searching for a wiring route from the start point to the end point according to the wiring information;
A square grid via setting means for setting a via at a grid point requiring a via in a wiring route obtained by searching for each point on the square grid;
Let A be an arbitrary point on the square lattice, a lattice point on the square lattice, and a point that includes the lattice point A and form a zigzag pattern are group 1 and search for group 1 Via group 1 setting means for setting a via;
A point which is adjacent to a point included in the group 1 on a square lattice and has a staggered pattern shifted by one lattice point is set as a group 2, and a search is performed for the group 2 to find a via point at a lattice point requiring a via. Via group 2 setting means for setting
Constraint condition determining means for determining whether or not the relationship between the via and the line segment interval and the interval between the two vias satisfies the constraint condition;
When the vias arranged on the wiring route obtained by the search for the square lattice points do not satisfy the constraint conditions, the route search means includes a group 1 including the lattice points at which the vias that do not satisfy the constraint conditions are arranged. A route is searched for a grid point of the group 1, a via is set at a grid point that is an optimum wiring path, and if the via set from the group 1 satisfies the constraint condition, the obtained optimum wiring path is output. If no via that satisfies the constraint condition is found in the search for a grid point, a route is searched for the grid point of group 2 and a via is set at a grid point that is an optimal wiring route. An automatic wiring device, which outputs a determined optimum wiring route if a condition is satisfied.

Images