JP3229235B2 - Wiring shaping method and apparatus, prohibited area radius determining method and apparatus - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for connecting a phase wiring between terminals on a board, which is a connection path in which only a topological positional relationship with respect to a terminal or an obstacle on a printed circuit board or the like is determined. Regarding the method of shaping the physical wiring, which is the wiring whose target position has been determined, more specifically, the method of expanding the wiring width and equalizing the wiring interval when performing the physical wiring (referred to as equal allocation) Related. Phase wiring is not specified up to the physical position of the path on the board as described above, and all wiring that can be changed and matched without crossing terminals or obstacles is the same phase wiring is there.

[0002]

2. Description of the Related Art A free-angle wiring, which is a wiring composed of an arc and a line segment having a measure of the Euclidean distance, is a conventional 90-degree or 4-degree wiring.
This is a wiring method in which the wiring area can be more effectively used than the fifth wiring. In particular, considering the current situation in which chips and the like are mounted on a printed circuit board at high density, it is very useful if free-angle wiring is performed at high speed and automatically. But,
Shaodi Gao, Mark Jerru
m, Michael Kaufman, Kurt Mehlhorn, Wolfgang Ruelin
g, and Christoph Storb, "On continuous homotopic o
ne layer routing, "In Proceedings of the 4th annua
l ACM Symposiumon Computational Geometry, pages 39
2-402, ACM, 1988, etc.
No practical product exists.

[0003] In addition, techniques for equal allocation and wiring width enlargement include PGA (Pin Grid Array), B
GA (Ball Grid Array), MCM (Multi-Chip Modul
It is important to improve the yield and stabilize the electrical properties with very fine wiring such as e). A method for automatically realizing equal allocation and wiring width expansion for PGA has been reported (Changsheng Ying and Jun Gu, "Automated
pin grid array package routing on multilayer cera
mic substarates, "IEEE Transaction on Very Large S
cale Integration (VLSI) SYSTEMS, 1 (4): pages 571-5
75, 1993) Although it is a free-angle wiring, the wiring is composed of only line segments, and uses wiring that runs radially from the center of PGA and a grid-like arrangement of pins, and lacks expandability. . As a matter of course, there is no product in which the general free-angle wiring is equally allocated and the wiring width is increased.

[0004]

SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to provide a method of enlarging a wiring interval and a wiring width in a marginal portion while employing a free-angle wiring which can effectively use a wiring area. Aim.

Another object of the present invention is to improve the yield and electrical characteristics of a printed circuit board or the like formed as a result of wiring.

[0006]

In the present invention, it is assumed that the phase wiring has already been determined. The shaping from the phase wiring to the physical wiring at a free angle is basically (1) selecting wiring to be shaped, and (2) arc-shaped prohibition from obstacles including wiring prohibition areas other than terminals and terminals. Generate a region, (3)
This is realized by finding the shortest route for the selected wiring so as not to pass through the generated prohibited area. By expanding the radius of the arc of the generated prohibited area, equal allocation and wiring width expansion are realized.

That is, when shaping a phase wiring between terminals on a substrate into a physical wiring, first, a wiring to be shaped is selected from the phase wirings. Then, an obstacle that sees through the wiring to be shaped is specified, and the inside of a circular arc having a radius that is a predetermined multiple of the minimum spacing between the wiring to be shaped and the specified obstacle is prohibited. Set to an obstacle identified as an area. Here, the minimum spacing is determined by the wiring existing between the wiring to be shaped and the specified obstacle and the distance between the wirings. When expanding the prohibited area, at least make sure that the left and right opposite prohibited areas do not overlap,
It is necessary to prevent the prohibited area from overlapping the starting point or the ending point of the wiring. Further, the predetermined multiple is determined by an empty space existing on the substrate. Lastly, the shortest path that does not pass through the prohibited area is detected, and the physical wiring of the wiring to be shaped is determined using the shortest path. Here, when increasing the wiring width, both the left and right boundaries of the wiring to be shaped are separately determined as the shortest paths.

The process of setting an arc-shaped forbidden area when enlarging the wiring width includes a wiring specifying step of specifying a wiring existing between the wiring to be shaped and the specified obstacle.
It is conceivable that the step of enlarging the wiring width of the wiring specified by the wiring specifying step and the step of adding the expanded wiring width are performed based on the wiring width expansion rate set for the specified obstacle. .

The process of setting an arc-shaped forbidden area when performing equal allocation includes a wiring specifying step for specifying a wiring existing between the wiring to be shaped and the specified obstacle, It is conceivable that the process is performed by a step of enlarging the wiring interval between the wirings specified in the wiring specifying step and a step of adding the expanded wiring interval based on the wiring interval enlarging rate set for the object.

When the edge of the arc of the set prohibited area protrudes from the other prohibited area existing on one side of the wiring to be shaped, the shortest path may detour more than necessary. In addition to the above processing,
It is necessary to reduce the radius of the arc of the protruding prohibition area so that the edge does not protrude.

The process of setting the prohibited area when the wiring width of the wiring to be shaped is enlarged includes the steps of setting a prohibited area for determining the boundary on the one side of the wiring to be shaped and the other steps of setting the prohibited area. Setting a prohibited area for determining a side boundary. In this way, the boundaries on both sides of the shaping target wiring can be determined by the shortest paths for each of the two prohibited areas.

The wiring width enlargement rate set for the obstacle is determined by considering the wiring crossing the critical cut between the specified obstacle and the other one obstacle, and considering the wiring width expansion for the other one obstacle. Determining the upper limit of the rate, and storing the lowest of the upper limits of the wiring width expansion rate for the obstacle where the critical cut exists from the specified obstacle as the wiring width expansion rate of the specified obstacle May be determined by executing the following.

The wiring interval enlargement factor set for an obstacle is determined by taking into account the wiring that crosses the critical cut between the specified obstacle and another one obstacle, and taking the wiring interval for the other one obstacle into consideration. Determining the upper limit of the enlargement ratio, and storing the lowest of the upper limit of the wiring interval expansion ratio for the obstacle having the critical cut from the specified obstacle as the wiring interval expansion ratio of the specified obstacle. It is also conceivable to make the determination by executing the steps.

According to the present invention, there is provided a method for determining an enlarged radius of an arc-shaped forbidden area set as an obstacle for a certain wiring in order to uniformly allocate wiring between terminals on a substrate and to increase the wiring width. There exist other aspects. In this method, first, a ratio of allocating a surplus space of a substrate to an increase in wiring width and a ratio of allocating to an increase in wiring interval are specified, and a critical cut between one obstacle and another one obstacle is specified. In consideration of the wiring crossing and the wiring interval, the upper limit of the wiring width expansion ratio for the other one obstacle and the ratio allocated to the expansion of the wiring interval are allowed within a range allowed by the ratio allocated to the expansion of the wiring width. Within the range, the upper limit of the wiring interval enlargement ratio for the other obstacle is determined. Then, the lowest one of the upper limits of the wiring width expansion ratios for obstacles having a critical cut from one obstacle is defined as the wiring width expansion ratio of one obstacle, and the lowest one of the upper limits of the wiring interval expansion ratios. Is stored as the wiring interval enlargement ratio of one obstacle. Further, a wiring existing between a certain wiring and one obstacle is specified, and the width of the specified wiring is expanded by a wiring width expansion rate set for the one obstacle. further,
The interval between the wirings specified in the wiring specifying step is expanded by the wiring space expansion rate set for the one obstacle.
Finally, for the specified wiring, the enlarged wiring width and the enlarged wiring interval are added to determine the radius of the prohibited area of one obstacle. When enlarging the wiring width, for the last addition, a first step of adding a wiring interval adjacent to the shaping target wiring from the selected obstacle and a wiring width of the specified wiring, and By performing the second step of adding the enlarged wiring width of the wiring to be shaped to the result, it is easy to obtain the boundaries on both sides of the wiring to be shaped.

Creating an apparatus for performing the above-described processing and a program for causing a computer to execute the above-described processing can be easily performed by those skilled in the art who have understood the following description. Also, it is obvious to those skilled in the art that a program for causing a computer to execute the above processing is stored in a recording medium.

[0016]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS A basic processing flow will be described with reference to FIG. It is assumed that the phase wiring has already been determined as described above. References describing how to determine this phase wiring include W. Dai, T. Dayan, D. Staepelelaere, "Topologi
cal Raiting in SURF: Generating aRuber-Band Skect
h, "28th DAC 1991, pp39-44, etc. An example of the phase wiring is shown in FIG. 2. First, one wiring to be shaped from the phase wiring to the physical wiring is selected (step 12). Identify obstacles that see through the target wiring (Step 1
4). This “see through” means that the wiring to be shaped is directly visible from the obstacle without being shielded by other terminals, etc.
It is detected by a method such as plane scanning. Depending on the obstacle, the shaping target wiring can be seen not only in one direction but also in two or more directions. In such a case, the wiring existing between the shaping target wiring and the obstacle may be different depending on the viewing direction. Therefore, the different viewing directions are treated as different obstacles. Note that the obstacle includes a terminal on the board and a region where wiring other than the terminal is prohibited. One of the obstacles specified in step 14 is selected, and processing is performed from this obstacle (step 16).

Next, a prohibited area is set within a circular arc having a radius that is a predetermined multiple of the minimum interval between the wiring to be shaped and the selected obstacle as a forbidden area. It is set (step 18). The minimum spacing required is determined by the wiring between the wiring to be shaped and the selected obstacle. That is, it is determined by adding all the widths (wiring widths) of the wirings between the shaping target wirings and the selected obstacle, and the intervals between the wirings (wiring intervals). Then, as an embodiment of the present invention, a wiring width expansion rate, a wiring interval expansion rate, or both are set for each obstacle for which a prohibited area is set. If only the wiring width is enlarged, only the wiring width enlargement ratio may be set. If only the wiring interval expansion ratio is enlarged, only the wiring interval enlargement ratio may be set. Generally, set both. If only the wiring interval enlargement ratio is set, all the wiring intervals between obstacles selected from the shaping target wiring are enlarged by the wiring interval enlargement ratio, and the enlarged wiring intervals are added. Next, the wiring widths of all the wirings between obstacles selected from the shaping target wirings determined by the design rule are added, and half of the wiring widths of the shaping target wirings are further added. The sum obtained by adding the expanded wiring interval and the added wiring width is a predetermined multiple of the interval in step 18. Note that the half of the wiring width of the shaping target wiring is added because the shortest distance route obtained in a later step is added.
Is set as the center line of the wiring to be shaped. On the other hand, in order to increase the wiring width, it is necessary to calculate the radii of two types of prohibited areas. This is to determine boundaries on both sides of the wiring. Hereinafter, processing required in the case of increasing the wiring width and the wiring interval will be described. When only the wiring width is increased, the wiring interval need not be increased (the wiring interval expansion rate is set to 1).

First, as shown in FIG. 3, a wiring existing between the wiring to be shaped and the selected obstacle is specified (step 32), and the wiring width expansion rate set for the selected obstacle is determined. The wiring interval enlargement ratio is inspected (step 34). The method of specifying the wiring existing between the shaping target wiring and the selected obstacle can be performed by the above-described method such as the plane scanning. Then, the wiring width of the specified wiring is enlarged according to the wiring width enlargement ratio (step 36). Further, the wiring interval of the specified wiring is enlarged according to the wiring interval enlargement ratio (step 38). Here, the wiring interval includes a wiring interval adjacent to the shaping target wiring. Steps 36 and 38 can be interchanged. Then, first, the wiring widths of all the enlarged wirings and the enlarged wiring intervals are added (step 40). This is defined as radius 1. This includes a distance from a predetermined point inside the selected obstacle (a point serving as a start point or an end point of the critical cut: the center of a circle if the obstacle is circular) to the boundary with the outside of the obstacle. In this step, the wiring widths may be added together, and the wiring intervals may be added together, and then added, or they may be arranged between the selected obstacle and the shaping target wiring. In the order of the wiring, the addition may be performed as in the following: interval, wiring width, interval, wiring width, interval. Then, the wiring width of the wiring to be shaped is added to the radius 1 (step 42). The wiring width of the wiring to be shaped is also the wiring width enlarged by the wiring width enlargement rate inspected earlier. This is radius 2. Then, the radius 1 and the radius 2 are used as the radius of the arc-shaped forbidden area (step 44). Radius 1
Represents the boundary of the wiring to be shaped near the selected obstacle, and the radius 2 represents the boundary on the opposite side.

By performing the above-described processing, the enlarged prohibited area can be set as an obstacle that can see through the shaping target wiring. However, unless the wiring width expansion rate and the wiring interval expansion rate are appropriate, the wiring itself may become impossible or the wiring may be unnecessarily bypassed. That is, FIG.
As shown in (a), if the right and left prohibited areas of the shaping target wiring overlap each other, wiring cannot be performed. Similarly,
As shown in FIG. 4B, even if the prohibited area overlaps the start point and the end point of the wiring, the wiring cannot be performed. Also, as shown in FIG. 4C, when the edge of the arc of the set prohibited area protrudes from another prohibited area existing on one side of the shaping target wiring, it is determined in a later step. The shortest distance between terminals may detour more than necessary. The wiring width enlargement ratio and the wiring interval enlargement ratio should be set so that such a problem does not occur. An example of the method of determining the wiring width expansion rate and the wiring interval expansion rate will be described in detail below.

Returning to FIG. 1, when the process proceeds to step 20, it is determined whether all the obstacles specified in step 14 have been processed. In this case, all obstacles may be processed, but in order to speed up the processing, if a certain distance is left from the wiring to be shaped, the obstacle is ignored and the obstacle to be processed is ignored. Step 18 may be performed only for obstacles to be sorted and processed. Sorting can also be performed in step 14. If the processing has not been completed, the process returns to step S16. If the processing has been completed, the process proceeds to step 22, and the physical wiring of the wiring to be shaped is determined using the shortest path that does not pass through the prohibited area. That is, the shortest path is the center line of the physical wiring when only the wiring interval is increased, and the shortest path for radius 1 and the shortest path for radius 2 obtained in FIG. Thus, the physical wiring of the wiring to be shaped is determined. For example, when a prohibited area as shown in FIG. 5 is set (FIG. 5 includes an obstacle with the prohibited area described in this paragraph), the wiring a shown in FIG. 2 is shaped into a physical wiring. In this case, the terminals may be connected by the shortest route as shown in FIG.

Then, it is determined whether or not all the wires have been processed (step 24). If there are wires to be processed, the process returns to step 12. If there is no wiring to be processed, the process ends (step 26). In this way, when the phase wiring is determined, the phase wiring can be shaped into the physical wiring. When the phase wiring as shown in FIG. 2 is shaped, it becomes as shown in FIG. FIG. 8 shows a case where the shortest route is connected before the prohibited area is enlarged. 8 and FIG. 7, it can be seen that the equal allocation is performed (the wiring width is not originally expanded).

In the following, a method of setting the wiring width expansion rate and the wiring interval expansion rate for each obstacle will be described. In this embodiment, each obstacle is set by performing the following processing before step 12 in FIG. Here, a case is shown in which the uniform allocation and the wiring width enlargement are performed simultaneously. However, when only the wiring width enlargement or the uniform allocation is performed, this can be performed by appropriately setting parameters described later. First, the wiring interval enlargement ratio is α, and the wiring width enlargement ratio is β. Each of αβ is given a subscript by the number of the obstacle. Variables indicating how to allocate an extra space on the substrate to the wiring interval and the wiring width are D _c and D _w (where D _c + D _w ≦ 1).

Then, a process as shown in FIG. 9 is performed. First, the variables described above are determined (step 52). That is, the user is made to input D _c and D _w so as to satisfy D _c + D _w ≦ 1. The user, in the case of only an enlarged wire spacing sets the D _w 0 may be set D _c to less than one digit. Also, the D _c in the case of expanding only the wire width is set to 0, may be set D _w to less than one digit. 1
This is because it is not necessary to allocate all the extra space on the substrate to the wiring width and the wiring interval, the wiring interval, or the wiring width. Next, an obstacle i for setting each enlargement factor is selected (step 54). Then, an obstacle j having a critical cut between the obstacle j and the obstacle i is selected (step 56). The critical cut is a line segment connecting the two objects at the shortest distance. In this process, if a plane scan is performed from the obstacle i, the obstacle j of the other party can be found. Then, α _i and β _i that are the upper limits in relation to the obstacle j are calculated (step 58). This α _i ,
The calculation of β _i is described in detail below.

When a critical cut is determined, a wiring passing through the critical cut can be specified. The processing for specifying the wiring can be performed by the same method as the processing for specifying the wiring between the obstacle and the wiring to be shaped. When the wiring is specified in this manner, the total of the wiring width and the total of the wiring intervals are derived, and are respectively referred to as Wij and Cij.
If the obstacle is a terminal, the respective radii are Ri, Rj.
(A length from a predetermined point in the obstacle (a start point or an end point of the critical cut) to a point where the boundary outside the obstacle and the critical cut intersect), and a critical cut between the obstacle i and the obstacle j Length of CCij is length (CCij)
Then, the extra length (interval) SSij related to the critical cut is as follows. SSij = length (CCij) -Ri- Rj-Wij-Cij D c set this SSij earlier, when distributed to the wiring width and the wiring interval in a ratio of D _w, alpha _i, the upper limit of the beta _i are as follows Become. α _i = (D _c * SS ij + _C ij) / _C ij β _i = (D _w * SS ij + _W ij) / W ij

[0027] α _i ,
β _i is an enlargement factor that does not cause the situation shown in FIG. 4A in relation to the obstacle j. Also, obstacle j
Is a terminal, and a wiring (with a wiring width of wj) comes out from the terminal, the following calculation is required to obtain an enlargement factor that does not cause the situation as shown in FIG. 4B. That is, the extra interval SS'ij is as follows: SS'ij = length (CCij) -Ri-wj / 2-Wij-Cij, and the upper limits of α _i and β _i are as follows. α _i =
_{(D c * SS'ij + Cij)} / Cij β i = (D w * SS'ij + Wij + wj / 2) / (Wij + w
j / 2)

In the case of FIG. 4B, wj /
If the forbidden area is small by two, one wire can be drawn from the obstacle j, so that SS′ij is as described above. That is, it is sufficient to secure a width that allows one wire to be drawn from the obstacle j as the minimum necessary interval.

By dividing the cases as described above, the upper limits of α _i and β _i of the obstacle i with respect to the obstacle j are calculated. Then, alpha _i of the obstacle i, the calculation result is previously calculated this, smaller than beta _i, holds the calculation result, otherwise, it continues to hold the value currently held (Step 6
0). Although α _i and β _i for all obstacles j may be held and the minimum value may be used later, updating the calculation every time the calculation is performed requires a smaller storage capacity. The reason why the minimum value is used is that if a value higher than the minimum value is used, a state as shown in FIG. 4A or 4B may occur somewhere.

After the above processing is completed, it is determined whether all the critical cuts from the obstacle i have been processed (step 62). If not, the process returns to step 56. If it has been processed, the stored α _i and β _i are _replaced with the obstacle i
(Step 64). Then, the above processing is performed for all obstacles i (steps 66 and 68).

In the above-described processing, the wiring space expansion ratio and the wiring width expansion ratio are set for each obstacle. From the above equation, when only the wiring width is enlarged, the wiring interval enlargement ratio is 1, and when only the equal allocation is performed, the wiring width expansion ratio is 1.

When the processing of FIG. 9 is performed, it is possible to cope with the cases (a) and (b) where inconvenience occurs in enlarging the prohibited area shown in FIG. However, the case of (c) cannot be handled by the processing of FIG. Therefore,
Before performing step 20 in FIG. 1, it is checked whether the edge of the arc of the prohibited area does not protrude from the other prohibited area on each side of the wiring to be shaped. Then, for the protruding prohibited area, the radius of the prohibited area is reduced in accordance with the arc of another prohibited area. Then, FIG.
The situation as shown in (c) does not occur.

As a method of this inspection, an edge of a circular arc protruding from another prohibited area is searched for from one terminal side to another terminal of the two terminals to be wired. If you reach the terminal side,
A method of similarly searching from one terminal side to one terminal side can be considered. Explaining with reference to FIG. 4C, when searching from the lower left side to the upper side of the shaping target wiring, the right edge (when viewed from the center of the arc) of the arc of the shaded prohibited area is protruding. I understand. Then, the search is performed from the upper side to the lower side, and the edge of the protruding arc is inspected. In this case, since the edge of the arc of the shaded prohibited area protrudes only on one side, the protruding arc edge cannot be found in the search from the upper side to the lower side. Next, a search is performed from the lower right side of the shaping target wiring to the upper side and from the upper side to the lower side.
In this case nothing is found.

Although one embodiment of the present invention has been described above, the present invention is not limited to this. For example, in the above description, the wiring interval expansion ratio and the wiring width expansion ratio are set for all the obstacles, and the equal allocation and the wiring width expansion are performed for all the wirings. It is also possible to set a prohibited area enlarged only for obstacles. Further, the processing in FIG. 9 is to be performed before step 12 in FIG. 1, but the same applies to the processing before step 18.

The present invention can be realized by an apparatus that executes the above-described processing and a program that causes a computer to execute the above-described steps. For example, the computer shown in FIG. 10 can be used. Bus 94
A main memory 80, a central processing unit CPU 82, an input device 84 including a mouse and a keyboard, a communication device 86 including a modem, a hard disk drive HDD 88,
Display device 90 including CRT and liquid crystal display device, printer 9
2 etc. are connected. An auxiliary storage device such as a magneto-optical disk (MO) or a floppy disk drive FDD may be connected. A program for executing each of the above-described steps by such a computer is stored in the HDD 88, and the same applies to information on the board such as a terminal position and a phase wiring path. The program and the information on the board are loaded into the main memory 80 and executed by the CPU 82. D _c, parameters such as D _w is designated by the input device 84. The result of the execution is displayed on the display device 90 or output to the printer 92. The execution result is also stored in the HDD 88 so that it can be retrieved later when necessary.
The communication device 86 is used for inputting information on the board and the program itself from a remote location to the computer shown in FIG. 10 and outputting an execution result to a remote location where execution has been ordered. The above configuration is an example, and especially the communication device 86 is optional.
There is no problem even if such a device does not exist. Although not shown because the premise of the present invention is that the phase wiring has been determined, a program that determines the phase wiring from information such as terminal positions on the board and which terminals are to be connected is described. May be stored in the HDD 88, the program may be executed by the CPU 82, and the execution result may be stored in the HDD 88.

FIG. 11 shows an example of an apparatus for executing the above-described processing. The board information storage device 100 that stores information on the board such as the position and size of an obstacle such as a terminal, the path of a phase wiring, and the like, calculates a wiring width expansion rate and a wiring interval expansion rate set for each obstacle. It is connected to a setting processor 110 and a prohibited area setting processor 120 that sets a prohibited area area based on the set enlargement ratio. The prohibited area setting processor 120 is connected to the shortest path determining device 130. The enlargement ratio setting processor 110 calculates the wiring width enlargement ratio and the wiring interval enlargement ratio to be set for each obstacle using the board information stored in the board information storage device 100 in advance, and stores the calculation result in the board information storage device 100. To be stored. Then, the prohibited area setting processor 120 selects a wiring to be processed by the wiring selector 122 and detects an obstacle that sees through the wiring to be processed by the obstacle detector 124. Thereafter, the prohibited area setting device 126
Sets an arc-shaped forbidden area having a radius that is a predetermined number of times a minimum distance between the obstacle and the wiring. This process is performed using the wiring interval expansion rate and the wiring width expansion rate set for each obstacle by the expansion rate setting processor. Further, the processing described in paragraph numbers 0030 and 0031 is also performed. When such a prohibited area is set, the shortest path determining device 130 detects the shortest path that does not pass through the prohibited area, and uses it to determine the physical wiring. The shortest path determination device 130
The processing described above corresponding to FIG. 4C is also performed.

FIG. 11 shows an example in which the present invention is applied to an apparatus, and other configurations are possible. For example, what is illustrated is necessary as a processing element, but the target processing can be executed even if the connection relation, the block division of the processing, and the like are not limited to FIG. Further, since the premise of the present invention is that the phase wiring is determined, the board information storage device 10
Although the information is stored in 0, it is also possible to provide a processing device for determining the phase wiring from information such as the positions of the terminals on the board and which terminals are connected.

[0036]

As described above, it is possible to provide a method of increasing the wiring interval and the wiring width in a portion where there is room while using the free-angle wiring which can effectively use the wiring area.

Further, the yield and electric characteristics of a printed circuit board or the like formed as a result of wiring can be improved.

[Brief description of the drawings]

FIG. 1 is a diagram showing a processing flow of the present invention.

FIG. 2 is a diagram illustrating an example of a phase wiring.

FIG. 3 is a diagram showing a detailed processing flow of step 18 in FIG. 1;

FIG. 4 is a diagram illustrating an example in which a problem occurs when a prohibited area is enlarged.

FIG. 5 is a diagram showing a case where a prohibited area is set in the case of FIG. 2;

6 is a diagram illustrating a case where one physical wiring is implemented according to a prohibited area in FIG. 5;

FIG. 7 is a diagram after all wirings of FIG. 2 have been shaped into physical wirings.

FIG. 8 is a diagram after all wirings of FIG. 2 have been shaped into physical wirings without enlarging a prohibited area.

FIG. 9 is a diagram illustrating an example of calculation of a wiring width enlargement ratio and a wiring interval enlargement ratio.

FIG. 10 is a diagram illustrating an example of a configuration of a computer.

FIG. 11 is a diagram illustrating an example of an apparatus that executes the present invention.

[Explanation of symbols]

REFERENCE SIGNS LIST 100 board information storage device 110 enlargement ratio setting processor 120 prohibited area setting processor 122 wiring selector 124 obstacle detector 126 prohibited area setting unit 130 shortest path determination device

Continuation of front page (72) Inventor Hiroaki Eto 1623-14 Shimotsuruma, Yamato-shi, Kanagawa Prefecture IBM Japan, Ltd. Tokyo Research Laboratory (56) References JP-A-10-198722 (JP, A) JP-A-10-63697 (JP, A) JP-A-9-153083 (JP, A) JP-A-5-40808 (JP, A) JP-A-61-94395 (JP, A) (58) Int.Cl. ⁷ , DB name) H01L 21/82 G06F 17/50 658

Claims (16)

(57) [Claims] 1. A phase wiring between terminals on a board, which is a connection path for which only a topological positional relationship with respect to a terminal or an obstacle is determined, is a wiring whose physical position on the board is determined. A wiring shaping method for shaping into a certain physical wiring, wherein a step of selecting a wiring to be shaped, a step of specifying an obstacle that sees through the wiring to be shaped, and the obstacle specified as the wiring to be shaped A prohibited area setting step of setting the specified obstacle as a prohibited area within an arc having a radius that is a predetermined number of times as long as the minimum distance that must be left between the prohibited area, and not passing through the prohibited area. Detect the shortest path such as
Determining a physical wiring of the wiring to be shaped using the shortest path. 2. The prohibited area setting step includes: a wiring specifying step of specifying a wiring existing between the wiring to be shaped and the specified obstacle; and a wiring set to the specified obstacle. 2. The method according to claim 1, further comprising: a step of enlarging a wiring width of the wiring specified in the wiring specifying step based on a width expansion rate; and a step of adding the expanded wiring width.
The wiring shaping method described. 3. The prohibited area setting step includes: a wiring specifying step of specifying a wiring existing between the wiring to be shaped and the specified obstacle; and a wiring set to the specified obstacle. 2. The wiring shaping method according to claim 1, further comprising: increasing a wiring interval between the wirings specified in the wiring specifying step based on an interval expansion rate; and adding the expanded wiring interval. 3. 4. A step of inspecting whether or not the edge of the arc of the prohibited area set in the prohibited area setting step does not protrude from another prohibited area existing on one side of the wiring to be shaped. 2. The wiring shaping method according to claim 1, further comprising: reducing the radius of the arc of the protruding prohibition region so that the edge does not protrude. 5. When the wiring width of the wiring to be shaped is increased, the prohibited area setting step sets a prohibited area for determining a boundary on one side of the wiring to be shaped; Setting a prohibited area for determining a boundary on the other side of the wiring to be shaped. 6. The wiring width enlarging ratio is determined by taking into account wiring crossing a critical cut between the identified obstacle and another one obstacle, and calculating the wiring width enlarging ratio for the other one obstacle. Determining an upper limit, and storing, as the wiring width expansion rate of the specified obstacle, the lowest one of the upper limits of the wiring width expansion rate for the obstacle having the critical cut from the specified obstacle. 3. The wiring shaping method according to claim 2, wherein the wiring shaping method is determined by executing the following steps. 7. The wiring interval enlarging ratio for the other one obstacle in consideration of wiring crossing a critical cut between the identified obstacle and another one of the obstacles. Determining the upper limit of, and storing, as the wiring interval expansion rate of the specified obstacle, the lowest one of the upper limits of the wiring interval expansion rate for the obstacle having the critical cut from the specified obstacle. 4. The wiring shaping method according to claim 3, wherein the determination is made by performing the following steps. 8. A forbidden area radius determination for determining an enlarged radius of an arc-shaped forbidden area set as an obstacle for a certain wiring in order to equally allocate wiring between terminals on a substrate and to increase wiring width. A method of designating a ratio of allocating a surplus space of the substrate to an increase in wiring width and a ratio of allocating to an increase in wiring interval, the method comprising: specifying a ratio between one obstacle and another obstacle. In consideration of the wiring crossing the critical cut and the wiring interval, the upper limit of the wiring width expansion ratio for the other obstacle and the expansion of the wiring interval are allocated within a range allowed by the ratio allocated to the expansion of the wiring width. Determining an upper limit of the wiring interval enlargement ratio for the other one of the obstacles within a range allowed by the ratio; and determining the upper limit of the obstacle for which a critical cut exists from the one of the obstacles. The lowest one of the upper limits of the line width expansion rate is the wiring width expansion rate of the one obstacle, and the lowest one of the upper limits of the wiring interval expansion rate is the wiring interval expansion rate of the one obstacle. Storing the wiring, a wiring specifying step of specifying a wiring existing between a certain wiring and the one obstacle, and the wiring width expansion rate set to the one obstacle,
Enlarging the width of the wiring specified by the wiring specifying step; and enlarging an interval between the wirings specified by the wiring specifying step by the wiring interval expansion rate set to the one obstacle. The wiring specified in the wiring specifying step,
Adding the expanded wiring width and the expanded wiring interval to determine the radius of the prohibited area of the one obstacle. 9. A phase wiring between terminals on a board, which is a connection path in which only a topological positional relationship with respect to a terminal or an obstacle is determined, is a wiring whose physical position on the board is determined. What is claimed is: 1. A wiring shaping device for shaping into a certain physical wiring, comprising: a selector for selecting a wiring to be shaped; a detector for identifying an obstacle that sees through the wiring to be shaped; and the obstacle identified as the wiring to be shaped. A prohibited area setting processing device for setting the specified obstacle as an prohibited area within an arc having a radius that is a predetermined number of times as long as a predetermined interval of a minimum distance between the object and the prohibited area; Detect the shortest path that does not pass,
And a physical wiring determination device that determines a physical wiring of the wiring to be shaped using the shortest path. 10. A prohibited area setting processing device, comprising: wiring specifying means for specifying wiring existing between the wiring to be shaped and the specified obstacle; and setting the wiring to the specified obstacle. 10. The wiring shaping apparatus according to claim 9, further comprising: means for expanding the wiring width of the wiring specified by the wiring specifying means by a wiring width expansion rate; and means for adding the expanded wiring width. 11. A prohibited area setting processing device, comprising: wiring specifying means for specifying a wiring existing between the wiring to be shaped and the specified obstacle; and setting the wiring to the specified obstacle. 10. The wiring shaping apparatus according to claim 9, further comprising: means for expanding a wiring interval between the wirings specified by the wiring specifying means, and means for adding the expanded wiring interval based on a wiring interval expansion rate. 12. A detector for inspecting whether the edge of the arc of the prohibited area set by the prohibited area setting processing device does not protrude from another prohibited area existing on one side of the wiring to be shaped, The wiring shaping apparatus according to claim 9, further comprising: a processing device that reduces the radius of the arc of the protruding prohibited area so that the edge does not protrude when the protruding area protrudes. 13. The prohibition area setting processing device sets a prohibition area for determining a boundary on one side of the shaping target wiring when expanding the wiring width of the shaping target wiring, and 10. The wiring shaping apparatus according to claim 9, further comprising setting a prohibited area for determining a boundary on the other side of the target wiring. 14. A forbidden area radius determination for determining an enlarged radius of an arc-shaped forbidden area set as an obstacle for a certain wiring in order to uniformly allocate wiring between terminals on a substrate and to increase wiring width. An apparatus, comprising: an input device for specifying a ratio of allocating a surplus space of the board to an increase in a wiring width and a ratio of a surplus space to an increase in a wiring interval, between an obstacle and one other obstacle. In consideration of the wiring crossing the critical cut and the wiring interval, the upper limit of the wiring width expansion ratio for the other obstacle and the expansion of the wiring interval are set within a range allowed by the ratio allocated to the expansion of the wiring width. A first processor that determines an upper limit of the wiring interval enlargement ratio for the other one obstacle within a range allowed by the allocation ratio, and an obstacle for which a critical cut exists from the one obstacle The minimum of the upper limit of the wiring width enlargement ratio is the wiring width expansion ratio of the one obstacle, and the lowest of the upper limit of the wiring interval expansion ratio is the wiring interval expansion ratio of the one obstacle. As a second processor to store, a wiring specifying device for specifying a wiring existing between a certain wiring and the one obstacle, and the wiring width expansion rate set for the one obstacle,
A third processor for expanding the width of the wiring specified by the wiring specifying device; and expanding the distance between the wirings specified by the wiring specifying device by the wiring interval expansion rate set for the first obstacle. A fourth processor, and a wiring specified by the wiring specifying device;
A forbidden area radius determining apparatus, comprising: a fifth processor that adds the enlarged wiring width and the enlarged wiring interval to determine a radius of the forbidden area of the one obstacle. 15. A computer is provided with a phase wiring between terminals on a board, which is a connection path for which only a topological positional relation with respect to a terminal or an obstacle is determined, and a physical position on the board is determined by the computer. A program that causes a computer to select a wiring to be shaped; and a step of causing a computer to specify an obstacle that sees through the wiring to be shaped. The specified obstacle is set as a prohibited area within an arc having a radius that is a predetermined number of times as long as a minimum interval between the wiring to be shaped and the specified obstacle. Prohibiting area setting step, detecting a shortest path that does not pass through the prohibited area, and determining a physical wiring of the wiring to be shaped using the shortest path. Recording medium, characterized in that to perform the steps. 16. A program for causing a computer to determine an enlarged radius of an arc-shaped forbidden area set as an obstacle for a certain wiring in order to evenly allocate wiring between terminals on a substrate and increase the wiring width. Wherein the program causes the computer to specify a ratio of allocating a surplus space of the substrate to an increase in wiring width and a ratio of allocating to an increase in wiring interval. In consideration of the wiring crossing the critical cut between the other obstacle and the other wiring and the wiring interval, the wiring width expansion ratio for the other one obstacle is within a range allowed by the ratio allocated to the wiring width expansion. And determining an upper limit of the wiring interval expansion rate for the other one of the obstacles in a range allowed by a ratio allocated to the expansion of the wiring interval. The minimum of the upper limit of the wiring width expansion rate for all obstacles having a critical cut from the one obstacle is defined as the wiring width expansion rate of the one obstacle and the upper limit of the wiring interval expansion rate. Storing the lowest one as the wiring interval enlargement factor of the one obstacle; a wiring specifying step of specifying a wiring existing between a certain wiring and the one obstacle; According to the wiring width expansion rate set in
Enlarging the width of the wiring specified by the wiring specifying step; and enlarging an interval between the wirings specified by the wiring specifying step based on the wiring interval expansion rate set for the one obstacle. The wiring specified in the wiring specifying step,
Add the expanded wiring width and the expanded wiring interval,
Determining the radius of the forbidden area of the one obstacle.