JPS648875B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Technical Field The present invention relates to a route search processing method used to determine wiring routes when designing wiring for printed circuit boards, LSIs, etc.

Prior Art Conventionally, this type of route search is performed by running a track search program on a general-purpose computer having a large capacity memory. This method generally divides the wiring area of printed circuit boards, LSIs, etc. into grids using orthogonal coordinates, and searches for routes sequentially for each pair of grids at both ends (of which there are multiple pairs) to be connected, which requires a large amount of processing time. It takes time. Even when searching for a route for a pair of grids, for example, starting from one grid, checking the presence or absence of lines in four adjacent grids, and sequentially extending the route, it takes a large amount of computer time. Furthermore, in order to find the shortest route from among the plurality of routes found, it is necessary to perform a so-called "exhaustive" route search. Algorithms have also been developed that take advantage of the flexibility of software to approximately find the shortest path with a small number of searches (CY
LEE, “An Algorithm for Path Connections
and Its Applications”, IRE Trans.Volume
(See EC-10 September, 1961). However, it still takes a considerable amount of time to sequentially search for routes for all of the plurality of grid pairs.

OBJECT OF THE INVENTION The object of the invention is to solve the above-mentioned conventional drawbacks and
Processing time can be shortened by dividing the board into multiple regions, assigning one processor to the wiring in each region, and performing route searches within each region in parallel. The object of the present invention is to provide a route search processing method.

Structure of the Invention The route search processing method of the present invention includes a printed board,
Divide the wiring area of LSI etc. into a grid using orthogonal coordinates,
In a route search processing method that searches the grid pairs at both ends of each route to be connected to find a wiring route, the wiring area to be searched is divided into multiple areas and each divided area is used to connect each of the divided areas within that area. The present invention is characterized in that the route is searched by being assigned to a processor that searches for a route, and the route is searched by sequentially enlarging divided areas of the wiring area to be searched.

The processing device used in the route search processing method of the present invention divides a wiring board, such as a printed board or LSI, into a lattice shape using orthogonal coordinates, and stores the lattice pairs at both ends of each route to be connected as interval data. a storage section, a lattice map storage section that stores the usage status of the lattice of the entire board, and a lattice map storage section that divides the lattice of the entire board into a plurality of regions, and of the section data stored in the section data storage section, the grids at both ends of the route are as described above. an area control unit that assigns corresponding area numbers to section data belonging to any one of the divided areas and performs area division management; a plurality of processors that search for connection paths between pairs;
a wiring control unit that allocates the plurality of processors to each of the divided regions, inputs grid data read from the section data storage unit to the corresponding processors, and controls execution of each processor; The present invention is characterized by comprising a route data storage section that stores route information searched by each of the processors.

Embodiments of the Invention Next, the present invention will be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention. That is, the section data storage unit 1 divides the wiring area of a printed circuit board, LSI, etc. into grids according to orthogonal coordinates, and stores grid pairs (generally there are multiple pairs) at both ends of the route to be connected as section data.
, a lattice map storage unit 2 for storing the usage status of each lattice on the wiring area, and section data that divides the lattice map of the wiring area into a plurality of areas and has grids at both ends in each divided area. an area control unit 3 that performs area division management by assigning corresponding area numbers to the areas; and a plurality of processors 6a for each of the plurality of areas divided by the area control unit 3.
-6i, one by one, supplying section data whose both ends are in the same divided area read from the section data storage section to the corresponding processor, and controlling the operation of each processor; a wiring processing unit 7 including a plurality of processors 6a to 6i that search for routes between the grids at both ends of the section data;
a route data output unit 8 that updates the contents of the lattice map storage unit 2 with the route data searched by each processor of the wiring processing unit 7 and notifies the section data storage unit 1 that wiring has been completed or incomplete; The route data storage section 4 stores route data based on the output data of the section 8.

For example, as shown in FIG. 2, the area control unit 3
The grid map 10 of the entire wiring area is divided into nine areas 9a.
9i, assign a region number (for example, 9a to 9i) to each region, and save the region along with the coordinates of each grid. Then, section data is sequentially inputted from the section data storage unit 1, and it is determined whether or not the grids at both ends of the section data are included in any one of the divided regions, and if so, the region number is added to the corresponding section data in the section data storage section 1 and written into the section data storage section 1.

The wiring control section 5 reads section data assigned different area numbers one by one from among the section data stored in the section data storage section 1, and sends each section data to nine processors 6a to 6.
i on a one-to-one basis, and input section data and its area number to each processor.

Each processor has a grid map storage section 2.
A lattice map within the allocated area is inputted from , a route search between both end point lattices is performed using the lattice map and the section data using a certain algorithm, and route information of the optimal route is passed to the route data output section 8 . The route search algorithm can be the same as the conventional method, but since the area is small, it is easy to select the optimal route. The route data output unit 8 is
When a route is found, the lattice map storage section 2 is updated with the route data, and a mark indicating that wiring has been completed is written in the corresponding section data in the section data storage section 1. Note that the route data storage unit 4 stores the searched route.
If the route is not found, a mark indicating that the route is not wired is written in the corresponding section data in the section data storage section 1. Since the route search within each of the above-mentioned areas is performed simultaneously and in parallel by a plurality of processors 6a to 6i, the time required for the search is greatly reduced.

Among the interval data stored in the interval data storage unit 1, those with area numbers (those with both end points in the same area) are processed in parallel by multiple processors in the same way. For each wiring route found, the grid map storage section 2 is updated and stored in the route data storage section 4. Also, a wiring completed mark is stored in the section data storage unit 1. Through the above-described operations, routes for those that can be wired within each area are determined.

To search for routes where both endpoints exist in the same area but are not connected by routes within the area (marked as unwired) and for section data that spans between areas. , the area control unit 3 re-divides the grid map into areas that are larger than before. For example, as shown in Figure 3,
The grid map 10 is divided into four regions 11a to 11d. Then, the new area number is assigned to the section data marked as unwired and the section data having both end points within the newly divided area. For example, the wiring control unit 5 controls a processor 6a for each of the four divided areas.
6d and give corresponding interval data to each processor. Each processor inputs the lattice map of the corresponding area from the lattice map storage section 2, and searches for a route between both end points of the section data. The found route is sent to the route data output section 8 in the same manner as described above.
The data is stored in the route data storage section 4 via the lattice map storage section 2, and the wiring completed mark is written in the section data storage section 1. For section data for which a route cannot be found, a mark indicating unwired is written in the section data storage section 1.

Next, the area control section 3 divides the lattice map into further enlarged areas and performs similar processing, and finally performs similar processing for all wiring areas, thereby completing the route search for all section data.

As described above, in the present invention, a wiring area is divided into a plurality of areas, one processor is assigned to each of the plurality of divided areas, and the processing for section data having both endpoints in each area is performed. Since the route search is performed simultaneously and in parallel by the plurality of processors, the processing time can be significantly reduced compared to the conventional method. For wiring for which no route has been found within the divided areas and for wiring spanning between the divided areas, it is possible to search for routes by sequentially enlarging the divided areas. Overall, the computer time for route searching can be significantly reduced compared to the conventional method.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an embodiment of the present invention, FIG. 2 is a diagram showing a lattice map divided into nine parts in the above embodiment, and FIG. 3 is a diagram showing a lattice map divided into four parts in the above embodiment. It is a diagram. In the figure, 1... section data storage section, 2...
Lattice map storage unit, 3... Area control unit, 4... Route data storage unit, 5... Wiring control unit, 6a to 6i
...Processor, 7...Wiring processing section, 8...Route data output section, 9a-9i...9-divided lattice map area, 10...Lattice map, 11a-1
1d...A region of the grid map divided into four.

Claims (1)

[Claims] 1. A route search process in which the wiring area of a printed circuit board, LSI, etc. is divided into grids based on orthogonal coordinates, and a processor searches for grid pairs at both ends of each route to be connected to find a wiring route. The method includes: a section data storage section that stores grid pairs at both ends of each divided route to be connected together with a region number as section data; and a grid map storage section that stores usage state information of each grid on the wiring region. , an area control unit that divides the entire grid into multiple areas, assigns area numbers to the divided areas, and assigns each of the multiple processors to search for connection paths within the area; a wiring control unit that inputs the section data and area number read from the section data storage section to the assigned processor for each area; and a wiring processing unit that includes a plurality of processors that searches for connection routes between pairs of grids based on section data to which the grids belong and usage status information of the grids stored in the grid map storage unit; a route data storage unit that stores route information; The results searched by the wiring control section are output, and based on the results, the lattice usage status information in the lattice map storage section is changed, and information as to whether wiring has been completed is stored in the section data storage section. , a route data output unit that stores the searched route in the route data storage unit, and the area control unit includes means for sequentially enlarging and redividing the divided areas to be searched, and the redivided area. 1. A route search processing method comprising: means for assigning an area number to section data within the route; and means for newly allocating each area to which the new area number has been assigned to a processor.