JPH04113473A - Method and device for wiring between elements - 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 [Field of Industrial Application] The present invention relates to an inter-element wiring method and device for wiring between terminals of a plurality of circuit modules or circuit elements having a correlation in an LSI or a printed circuit board.

[Conventional technology]

The most powerful conventional wiring method between elements is the one written by Riichi [Path Connection Algorithm and Its Applications J (C,
Y, Lee:, An Algorithm for P
ath Connection and Its App
lications, IRE Trans, vol.
EC-10, pp.

356-365 (1961), called the maze method. This method is a forward search that searches and marks a route from the starting point to the ending point for each element.
It consists of four processes in three stages: backward search for backtracing from the end point to the start point, and mark clearing. The feature of this method is that it can always be found if there is a wiring route between the target elements. However, since the early versions of this maze method were designed for sequential processing, they took a lot of calculation time and required too much memory to solve large-scale problems, making them difficult to apply. In order to overcome these problems, we proposed (1) a method to search for routes at the start and end points simultaneously, (2) parallelization by exposing wiring areas, (3) parallelization by grouping pin pairs, and (4) a method for forward search. Attempts have been made to parallelize the route searches for wave flons 1 to 2. As a method belonging to (1), J, 5ouk
up.

“GLOBAL ROUTER” (J, of Di
gj, tal Systems, IV, 1°pp, 59
-69.1980. and Tetsuo Asano, ``Parallel global
Router” (Information Processing Theory, 23, 4.pp, 443-4
50.1982-07). (2)
As a method belonging to this category, there is the method shown in the above-mentioned paper by J. 5oukup.

As for the method belonging to (3), Tatsuya Shindo et al.
-2. ), Hiroko Midoriyo and 2 others, ``Image Processing System TI
"Wiring Processing in TIP-3" (1980, IEICE Information and Systems Division, Zenten), and Hiroko Midoriyo and two others, "Parallel Wiring in TIP-3" (1988, Maejo-dokoro Maeda University, 3Ll-6) , ).The methods belonging to (4) include Masayoshi Tachibana and four others, "Prototype Research on Parallel Routing Processors" (Information Processing Theory, 27, 6+pp.

639-647.1986-06), 5uzuki
,et al,,”A HardwareMaze
Router with Appl] catj, o
n to Interactj, veRip-Up
and Reroute” (IEEE Trans,
Compute, -Aj, dedDes, Integra
ted Cj, rcuits & 5yst, CAD
-5,4,pp.

466-476.1986-10) + and JP-A-63
There is one shown in No.-15367. Among these, the one with the highest degree of parallelism is the parallel wiring method using area division (2).

In addition, in order to perform large-scale wiring processing using multiple processors, a method has been proposed in which the wiring area is divided, a processor is assigned to each divided area, and each area is independently routed. Japanese Patent Publication No. 61-12504
No. 2, JP-A-62-23130, JP-A-62-115
There is one shown in No. 574.

[Problem to be solved by the invention]

The conventional technology related to the area-divided wiring method described above has the following problems. (1) When dividing a region and wiring each region in parallel, it may not be possible to find a wiring route that spans each region. (2) Wiring routes are formed by setting a grid on the surface to be wired (the width of the wiring is smaller than the side) and sequentially connecting adjacent grids, but in conventional technology, each grid is processed. Since it is a unit, there may be a memory shortage when applying it to large-scale problems.

An object of the present invention is to provide an inter-element wiring method that can always find wiring paths between elements if they exist even if the wiring area is divided, and that can save memory even in large-scale problems. An object of the present invention is to provide an inter-element wiring device using the above.

[Means to solve the problem]

The above purpose is to divide the wiring area, and for each divided area,
Extract the routable boundary lattices on the boundary with other divided areas other than those already used for wiring or those for which wiring is prohibited, divide them into groups of routable boundary lattices based on adjacency relationships, and further A process of adding a routable lattice in the divided region adjacent to the routable boundary lattice group, and then adding an adjacent routable lattice to each resulting lattice group is performed for each lattice groove. By repeating the process simultaneously, the divided area is divided into small areas, each of these small areas is then set as a node, and if there is an adjacency relationship between the small areas, a graph with branches between the points corresponding to the small areas is created. . Then, it is determined in which of the divided small regions the two elements to be connected (each represented by one grid) is included, and the path between these small regions is searched from the connection relationship in the graph above and summarized. This is achieved by creating a wiring route and finally performing detailed wiring in parallel in each small area on this general wiring route.

[For production]

First, the inter-element wiring device inputs wiring status information such as the outline of the wiring area, prohibited areas, and possible wiring areas, and connection request information indicating which elements are to be connected to each other from the design data input section. , input as connection-related information. Next, if the wiring area is divided into a predetermined number of divisions and parallel processing is performed for each divided area, the memory of the processor that performs each process may be small, and the speed can be increased by parallelization. Then, for each divided area, the processor in charge uses the input to divide the boundary lattice into a group of routable boundary lattices, and then assigns a processor to each group of lattices to divide the routable lattice into small areas; Furthermore, since the adjacency relationship for each small region can be determined through the division process, the above-mentioned graph can be created using this information. If a rough wiring route is found using the graph created in this way, it is a route search that uses small areas as units, and the number of small areas is usually much smaller than the number of grids, so the route search is faster. Can be executed using small memory capacity. The route determination for each grid within each small area of the thus obtained general wiring route can be performed using conventional techniques, and if this is executed in parallel in each small area, this process can also be executed at high speed with a small capacity memory. Moreover, according to this method, if a path exists between elements to be connected, a rough path is always found, and therefore a wiring path is always found.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings. 1st
The figure is a block diagram showing an embodiment of the functional configuration of an inter-element wiring device according to the present invention, and FIG. 2 is a block diagram showing the hardware configuration of the device. In Figure 2, the CPU
21 is a processing unit that controls the entire operation, a processor (P
E) 22a to 22d and 23a to 23h are processing devices that perform parallel processing at each processing stage, and these are connected hierarchically.
Each shared memory 20.24a-24d, 25 is connected.

Hereinafter, each processing section 10.12 to 16 will be sequentially explained with reference to FIG. First, from the design data input unit 10 shown in FIG. 1, wiring status information such as already wired areas, prohibited areas, and possible wiring areas in the wiring area, and connection request information indicating which elements are to be connected are sent to the device 11. and set it in the shared memory 25 as a wiring status table and a wiring table. Here, as shown in FIG. 3, the wiring area is managed by dividing it into a large number of grids (small squares), and the grids that are already wired or where wiring is prohibited are marked with diagonal lines. The above wiring status table corresponding to this is
As shown in FIG. 4(a), each grid in FIG. 3 is numbered, and a status flag is associated with each number. The status flag indicates whether the grid in question is already used for wiring, is prohibited (hatched grid in FIG. 3), or is a grid in which other wiring is possible. The wiring request table, as shown in FIG. 4(b), represents the wiring to be connected as a signal and associates the grid numbers at both ends of the wiring (where elements are placed). Note that these tables are updated from the time of initial setting to a state where the used grid is changed to already used and the relevant wiring request is completed (or deleted) every time wiring is determined.

When the input to each of the above tables is completed, the wiring area dividing section 12 of the device 11 is started, and as shown in FIG.
~31d. In this case, the divided regions are considered to be a common boundary region 32 of one grid width, and this boundary region is included in the divided regions on both sides of the boundary. Therefore, divided area 3
1a to 31d have a common boundary area with adjacent areas as shown in FIG.

When this division is completed, each divided area 31a to 31d has a second
The processors 22a to 22d shown in the figure are allocated, and the contents of the wiring status table and wiring request table for the grid points included in each divided area are stored in the shared memory 24a, respectively.
Load to ~24d. Here, the number of divided areas and CPU2
Although the number of processors under 1 is equal to 4, if the number of processors is small, time-sharing processing may be performed to logically achieve the configuration shown in FIG. 2.

When the processing of the region dividing unit 12 in FIG. 1 is completed in this way, the processors 22a to 22
d operate in parallel to perform the processing of the on-boundary lattice control section 13. FIG. 7(a) shows the boundary lattice part of the divided region 31a in detail, and the lattice without diagonal lines is the boundary lattice where wiring is possible. The process of the control unit 13 divides these wireable boundary grids into grid groups S1 to S3 and R1 to R4 as shown in FIG. 7(b) according to the adjacency relationship. Here, the adjacency relationship means that two lattices that are directly adjacent to each other, or that there are several lattices in between and can be reached by following the adjacent ones in sequence, are in an adjacent relationship, This is generally the same for flat surfaces. In this case, the routable boundary grids are arranged directly above each other, and if there is a prohibited grid between them, the adjacency relationship disappears and they become a separate grid group.

When the division into lattice groups on the boundary is completed, a processor is installed in each lattice group, for example, lattice group SL in FIG. 7(b).

The processors 23a, . . . are assigned to each of the processors 23a, . In this case as well, for example, the available processors 23 for the seven grid groups S1 to R4 in FIG.
When there is a shortage of a to 23h, time division is used.

At the same time, each processor 23a, . . . assigns grating group numbers 81 to R4 to each grating in the divided area in the same manner as the method of generating waves in the maze method.

The process is stopped when the waves generated from each lattice group collide and can no longer travel, and this process is continued until all waves can no longer travel. FIG. 8 shows an example of this process, and the wiring prohibited area in the divided area 31a is shown in the figure (
The shaded area in a), the wiring possible area, is the area without the shaded area. At this time, waves are generated from the vacant grid groups S1 to R4 on the boundary in the same manner as in the maze method, and the wiring area of the divided area 31a is divided into small areas, as shown in FIG. 8(b). The result of this division into small regions is stored by writing the number of the small region to which the grid belongs in the flag of each wireable grid in the wiring status table of FIG. 4(a). Here, each subregion has the same number S as the grid group on the boundary that is its origin.
]~R4 shall be attached. In this processing, the processors 22a to 22d check which wave collided with which wave during the division processing into small regions by the processors 23a to 23h, and notify the CPU 21 of the collision.
1 writes information on a planar graph created using information on which wave of each lattice group collides with a wave of each lattice group into a lattice group connection relationship table provided on the memory 20. As shown in Figure 9, this is a planar graph with each grid group (therefore, a small region) as a node, and the number of the branch between the colliding grid groups, and the region number (small region) indicating the nodes on both sides. This is a table in which the numbers SL, S2, etc.) and the number of grids in the connection part between two small areas corresponding to the branch (number of connected grids) are recorded for each school. . Specific examples of this graph up to now are shown in FIGS. 10 and 11.

Each divided area 81. ..., their connection relationship becomes a planar graph as shown in FIG. 11.

In the next process of the wiring route determination unit 15, the following process is repeated until it is determined in process 15a that there is no element to be wired.

The wiring target element setting section 15b selects the element (
A pair of elements (grids) are extracted from the wiring request table of FIG. 4(b), and then the small area to which these elements (grids) belong is searched from the wiring status table of FIG. 4(a).

As shown in FIG. 8, the general wiring route determination unit 15c determines a general wiring route in units of small areas that connects the small areas to which the two elements found in the wiring target element setting unit 1.5b belong. decide. The processing up to this point by the wiring route determination unit 15 is executed by the CPU 21. In the example of Fig. 10, the element (lattice) to be connected is the small area R2 and T.
1 (the node indicated by the double circle in Figure 11)
, the determination of this rough wiring route is shown in the planar graph in Figure 11,
The problem of finding the shortest distance connecting nodes R2 and T1 can be solved using a well-known method. As a result, in the case of FIG. 11, the nodes R2-R1, -8L-82-T2-Ul-TI
is the approximate wiring route. This route covers the entire wiring area 30
(See FIG. 5) What is shown above is FIG. 12.

This figure shows all the divided regions 31a to 31d in FIG. 10 together, and the elements to be connected in the small regions Tl and R2 are indicated by eS and eE. The approximate route is this element es
, eE is a solid line connecting them. The general wiring route determination unit 15c sets a relay terminal e1 at a position where this route passes through the boundary of the small area.
~e12 is set and the process ends.

In the detailed wiring route determination unit 15d, the processor 2 of FIG.
3a to 23h are assigned each small area on the general wiring route, and the general wiring route determination unit 15 is assigned to each small area on the general wiring route.
Wire between the relay terminals provided in c by parallel operation. The wiring method is the same as the conventional technology, for example, the small area U1 in FIG.
The processor assigned is terminal e2, e2 and 03.
Perform the wiring within the Ul between the two.

In the wiring possible area updating unit 15e, the detailed wiring route determining unit 1
．． The use of the lattice that has already been wired in 5d is prohibited.

This is done by updating the status flag of the lattice used in the wiring status table of FIG. 4(a) and prohibiting wiring in that lattice. Also, since the number of grids lined up at the boundaries between small areas on the rough route is reduced by one due to wiring, an update process is performed to reduce the number of connected grids for the corresponding connection branch number in the connection relationship table in Figure 9 representing the graph by one. . As a result, each small area where new wiring can be done becomes smaller as shown in FIG. 13. Furthermore, if the vertical width of the relay terminal e8 in FIG. 12 is the width of one lattice, the small regions S1 and 82 are no longer adjacent to each other due to the wiring between the elements eS and eE, as shown in FIG. This can be determined from the fact that as a result of the updating process of the connection relationship table shown in FIG. , S in the graph of Figure 11
Remove the branch between L and 82. In this way, the process returns to the setting between the next elements.

〔Effect of the invention〕

According to the present invention, it is possible to perform inter-element route searching in a large wiring area at high speed, and the required memory capacity can be reduced, so that high-quality LSI and printed circuit board layouts can be reliably and efficiently obtained. There is.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an example of the functional configuration of an inter-element wiring device according to the present invention, FIG. 2 is a block diagram showing an example of the hardware configuration of the device, and FIG. 3 is an explanatory diagram of a grid wiring area. , FIG. 4 is an explanatory diagram of the wiring status table and the wiring request table, FIGS. 5 and 6 are explanatory diagrams of the area division method according to the present invention, and FIG. 7 is an explanatory diagram of the method for integrating the wireable grid on the boundary according to the present invention. , FIG. 8 is an explanatory diagram of the method of dividing a wiring possible area in the present invention, FIG. 9 is an explanatory diagram of a wiring possible grid group connection relationship table, FIGS. 10 and 11 are explanatory diagrams of a planar graph, FIG. 12 is an explanatory diagram of a method for determining a general wiring route, and FIG. 13 is an explanatory diagram of a method for updating a wiring possible area and a planar graph. 12... Area division section, 13... Boundary grid control section,
14... Wirable area dividing section, 15... Wiring route determining section, 15c... Schematic wiring route determining section, 15e...
Routable area update unit, 20, 24a to 24c,
25-shared memory, 21-CPU, 22a to 22d,
23a-23h... Processor, 30... Placement line area, 31a-31d... Division area, 40... Boundary area, R1-R4°81-83. TL T2. Ul,
U2: small area, e1 to e12...relay terminal. Representative Patent Attorney Masami Akimoto C...11.5.12. ,...

Claims (5)

[Claims] 1. In an inter-element wiring method in which a wiring path is determined by dividing a wiring surface into grids and connecting two grids designated at the positions of two elements with a series of vertically or horizontally adjacent grids, the above-mentioned grid A first table indicating whether each element is prohibited from being used for wiring in advance or has already been used for wiring and is prohibited from use, and corresponds to two element positions that require wiring. and a second table storing grid pairs, and divides the wiring surface so that each of the wiring planes is divided by boundary regions each consisting of a grid row of one grid width, and the boundary regions are shared by both of the divided regions. In each of the divided areas, a lattice that can be wired and is not prohibited from use in the first table is extracted from the lattice on the boundary area, and the lattice is divided into a plurality of divided areas. In the second process of dividing into lattice groups that can be reached by the relation, and in each of the above divided regions,
A third process of dividing the wireable lattice in the divided area into small areas equal to the number of the lattice groups by sequentially adding the wireable lattice to each of the lattice groups in an adjacent relationship; Small regions generated from the same grid group are combined as the same small region, and then each small region is used as a node, and when two small regions have adjacent grids, a planar graph with branches between the corresponding nodes is generated. a fourth process of
With reference to the second table, a pair of lattices requiring wiring are extracted, and a route connecting nodes corresponding to the small area to which each of the lattices belongs is searched on the planar graph to obtain an approximate wiring route; Further, a fifth process of determining a relay grid in a boundary area between the small areas through which the route passes, and a sixth process of determining detailed wiring between the relay grids in each of the small areas forming the wiring route, Through this processing, the grid used for wiring is prohibited from being used on the first table, the pairs of grid points that are no longer needed due to the wiring are removed from the second table, and the grid points that are adjacent to each other by the wiring are removed from the second table. An inter-element wiring method characterized by performing a seventh process of removing, if there is an edge between small regions in the planar graph that does not have an edge. 2. 2. The inter-element wiring method according to claim 1, wherein the fifth process, the sixth process, and the seventh process are repeatedly executed until there are no lattice pairs requiring wiring in the second table. 3. In an inter-element wiring device that divides a wiring surface into grids and defines a wiring route by connecting two grids designated at the positions of two elements with a series of vertically or horizontally adjacent grids, the grid is A first table indicating whether each element is prohibited from being used for wiring in advance or has already been used for wiring and is prohibited from use, and corresponds to two element positions that require wiring. A second table storing grid pairs, and dividing the wiring surface so that each of the wiring planes is divided by boundary regions each consisting of a grid row of one grid width, and the boundary regions are shared by both of the divided regions. a first processing means for forming a plurality of divided regions, and in each of the divided regions, extracts a wireable grid on the boundary region that is not designated as prohibited in the first table, and sets the grid in an adjacent relationship; a second processing means for dividing the lattice group into reachable lattice groups, and sequentially adding the routable lattice in the lattice group in each of the lattice groups in an adjacent relationship to each of the lattice groups; A third processing means divides the subregions into equal number of subregions, and synthesizes the subregions generated for each of the divided regions as the same subregion if they are generated from the same grid group, and then sets each subregion as a node. a fourth processing means for generating a planar graph having branches between corresponding nodes when two small regions have adjacent lattices, and extracting a pair of lattices requiring wiring by referring to the second table; Searching the planar graph for a route connecting nodes corresponding to the small area to which each of the grids belongs to obtain a rough wiring route, and further determining a relay grid in the boundary area between the small areas through which the route passes. a sixth processing means for determining detailed wiring between the relay grids in each of the small areas forming the wiring route; Pairs of lattice points that are prohibited to be used on the first table and become unnecessary due to the above wiring are removed from the second table, and the branches between adjacent small areas that do not have the above routable lattice due to the above wiring are An inter-element wiring device characterized by comprising: a seventh processing means for removing any part of the planar graph. 4. 4. The inter-element wiring device according to claim 3, wherein the second processing means is configured by assigning one processor to each of the divided regions. 5. 4. The inter-element wiring device according to claim 3, wherein one or both of the third processing means and the sixth processing means are configured by allocating one processor to each of the small areas.