JPH02190977A - Processing method for searching route - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Summary] Regarding processing of the maze method for automatically searching wiring routes using a computer, the present invention aims to provide a route search processing method that is improved so as to improve the wiring rate of route search using the maze method. In the process of equally dividing the wiring surface into predetermined cells and searching for a path consisting of the cells dedicated to connecting the required cells by labeling using the maze method, regarding the newly set path,
Starting from one cell and reaching the other cell, the label value is increased by 1 each time the cell is not on the other existing route, and the label value is increased by 1 each time the cell on the existing route is passed through. If the newly set route crosses the existing route, a predetermined first premium value is added to the label value, and if the new route does not cross the existing route, a predetermined second premium value is used. was added.

The label value is set as the new route, and the route with the smallest label value when reaching the other cell is set as the newly set route, and the process of determining the route for all required connections is performed to become a predetermined route setting state. The configuration is such that the first and second premium values are sequentially increased and repeated until .

[Industrial application field]

The present invention relates to a route search processing method that is an improved version of the maze method for automatically searching wiring routes using a computer.

Automatic wiring route searching is known for determining the route for printed wiring that connects the terminals of components mounted on printed circuit boards, etc., but as the density of packaging increases, the automatic wiring rate has decreased. Therefore, it is desired to improve the automatic wiring rate.

[Prior art and problems to be solved by the invention] FIG. 5 is a diagram illustrating labeling in route searching using the maze method. The figure shows the wiring surface, and each square of equal size separated by a broken line is a cell. In order to make a connection between cells of two terminals (hereinafter referred to as a net), a path consisting of cells lined up between them is created. For example, starting from cell S at one end, label value "l" is attached to adjacent cells (label values are indicated by ■, etc. in the figure), and then label values are assigned to cells adjacent to ■. is incremented by 1 to become ■, and labeling is proceeded as shown in the figure to determine the route that reaches the target cell with the minimum label value. In this case, which of the plurality of possible routes to take is determined, for example, by how the top, bottom, left, and right priorities are determined in the direction of travel of the search.

In the above labeling, cells on other already selected routes (hereinafter referred to as wired cells) and terminal cells are excluded from labeling as obstacles that cannot be used as wiring routes. By avoiding cells,
Try to get a route around them if possible.

As a result, each terminal a arranged as shown in FIG. 4(a), for example.
If you use the maze method to search for routes connecting -a', b-b', and c-c', the results will vary depending on the processing order of the terminal pairs, but for example, if you search for a route connecting c-c', If this is determined in advance, wiring between a and a' and between b and b'' becomes impossible, and in any case, the wiring for all three terminal pairs cannot be completed using the above method. For this reason, the maze method has a problem in that as the wiring becomes more complex, the automatic wiring rate decreases significantly, and the ratio of dependence on manual wiring design increases.

The object of the present invention is to provide an improved route search processing method that improves the wiring rate of route search using the maze method.

[Means to solve the problem]

FIG. 1 is a process flowchart showing the configuration of the present invention. FIG. 0 shows the process flow in wiring route search, and 1 to 7 are processing steps.

[For production]

In processing step 1, the wiring surface is equally divided into predetermined cells, and a route consisting of the cells dedicated to connect the required cells is searched by labeling using the maze method. Once the initial settings have been made, one net is extracted in processing step 2.

In order to set a new route for that net, in processing step 3, each time the route starts from a cell at one terminal and reaches a cell at the other terminal, each time the net passes through a cell that is not on any other existing route. Increment the label value by 1.

In addition, when passing through a cell on an existing route, if the newly set route crosses the existing route, the label value is the label value plus a predetermined first premium value, and if it does not cross the existing route, A predetermined second premium value is added to the label value, and the route that reaches the cell of the other terminal with the minimum label value is processed as the newly set route.

Each time the route search for one net in processing step 3 is executed for all the nets identified in processing step 5, the first and second premium values are increased by a predetermined value in processing step 7, and the above processing is performed. Repeat and process step 4
The process is terminated by detecting that the wiring of all nets is completed in step 6 or by detecting a predetermined termination condition in step 6.

With the above processing method, by repeating the process of setting a route with a high cost using a premium value even when it contacts or intersects with an already wired cell, the nets will mutually influence each other during the repeated process, and the cost will increase with each other. Since the route is changed to take a small detour, it becomes possible to find an actually possible route and improve the wiring rate.

〔Example〕

FIG. 2 is a diagram showing the flow of processing in an embodiment of the present invention.

In processing step 10, data such as a net list specifying the wiring plane and cells to be connected is input, and the first and second
A predetermined initial value is given to the premium values (hereinafter referred to as premium values a and b).

In processing step 11, one of the nets is picked up and a route search process is started, the cell at one terminal of the net is set as the first parent cell, one cell adjacent to the parent cell is determined in processing step 12, and in processing step 13, the cell adjacent to the parent cell is determined. Identify whether it is the target cell at the other terminal of the net.

If it is not the target cell, in processing step 14, the label value obtained by adding 1 to the label value of the current parent cell (initial value is 0) is set as the temporary label value of the cell.

In processing step 15, the cell is changed to an already wired cell (however,
(except when the parent cell is a wired cell for the same wiring), and if it is a wired cell, process step 16
Then, the cell is divided into the part after crossing the existing wiring and the part before crossing the existing wiring when viewed from the wiring currently being processed, and the temporary label value of the former is set to the above-mentioned tentative bell value 10a, and the temporary label value of the latter is set to the above-mentioned tentative label value. Let's assume the bell value is 10.

In processing step 17, the temporary label value is compared with the label value already stored for that cell (the initial value is set to an appropriately large value), and the smaller label value and its parent direction (of cell a) are compared. direction) as the label of that cell. Note that if the cell is not a wired cell in processing step 15, the process immediately proceeds to processing step 17.

This completes the process of labeling one adjacent cell, so in process step 18 it is determined whether there is an unprocessed adjacent cell in another direction, and if there is an unprocessed adjacent cell, the process returns to process step 12 and the above procedure is performed for another adjacent cell. Process in the same way as .

If all adjacent cells have been processed, in processing step 19 it is determined whether there are any unprocessed cells with respect to the label value of the current parent cell, and if there are any unprocessed cells, the next parent cell is determined and the process returns to processing step 12. The neighbor cell labeling process is performed for the new parent cell as described above.

In this way, after completing the process of making each cell a parent cell for all cells with a certain label value, in processing step 20, the label value to be made the parent cell is set to the next largest value, and other control information is rewritten. After setting, the process returns to step 12 and the process is performed as described above.

Figure 3 shows a=50. This is a diagram showing an example of a label when labeling is performed as described above from one end of the net indicated by S, with b=5, and the label value is shown in the circle of each cell,
An arrow indicates the parent direction.

As a result of proceeding with the processing in this way, - processing step 13
When it is determined that the target cell has been reached, a route has been set for that net, so step 2
1, and it is determined whether the wiring is complete, that is, whether a route without intersecting or contacting other nets has been obtained for all the nets. If the wiring is complete, the route search process is terminated.

If the wiring is not completed, it is determined in processing step 22 whether all nets have been processed, and if there are unprocessed nets, the process returns to processing step 11, picks up the next net to be processed, and starts processing as described above.

In this way, when all the nets have been processed, proceed to processing step 23 and check that, for example, the paths of all the nets will not change at all from the path of the previous processing result even with the current processing. This is detected and the process is terminated using this as a termination condition.

If the termination condition is not met, process step 2
In step 4, the extra values a and b are increased by predetermined values, and the process returns to step 11, where the processing of all nets is restarted using the new values of a and b.

As described above, when processing is started with the initial value of a=b=o, for example, the shortest route for each net is determined, ignoring other nets. FIG. 4(b) is an example of the result set in this manner for the net route shown in FIG. 4(a).

Next, in the state shown in FIG. 4(b), for example, a=50. When a route search is performed with b=5, the route a-a' is selected to avoid the route set b-b', as shown in (C).
C-C" will not intersect with other routes, but a
-a'' and bb'.

Next, for example, if we increase a = 100 and b = lO and perform the process again, a-a'' and b-
The path b' is chosen to avoid contact with c-c', and the wiring is completed at this stage in this example. That is, wiring can be completed even when wiring is impossible using the conventional maze method.

〔Effect of the invention〕

As is clear from the above description, the present invention has a remarkable industrial effect in that the automatic wiring rate is improved in the processing of the maze method for automatically searching wiring routes by a computer.

[BRIEF DESCRIPTION OF THE DRAWINGS] Fig. 1 is a process flow chart showing the configuration of the present invention, Fig. 2 is a process flow chart of an embodiment of the present invention, Fig. 3 is an explanatory diagram of labeling of the present invention, and Fig. 4 is a process flow chart showing the configuration of the present invention. The figure is an explanatory diagram of a wiring example, and Fig. 5 is an explanatory diagram of labeling using the maze method. In the figures, 1 to 7. 10 to 24 are processing steps. Fig. 1 is a process flow diagram showing the structure of the present invention.

Claims (1)

[Scope of Claims] In the process of equally dividing a wiring surface into predetermined cells and labeling and searching routes consisting of the cells dedicated to connect the required cells (1 to 1). 7) For the newly set route, increase the label value by 1 each time the route passes through a cell that is not on the other existing route, starting from one cell and reaching the other cell. and when passing through the cell on the existing route, if the newly set route crosses the existing route, the label value is set as the label value plus a predetermined first premium value; If it does not cross, set the label value to which a predetermined second premium value is added, and set the route with the minimum label value when reaching the other cell as the new route (3), A route search processing method characterized in that the process of determining the route for a connection is repeated by sequentially increasing the first and second premium values until a predetermined route setting state is reached (4 to 7).