JPS59188772A - Route retrieval and processing system - Google Patents

Abstract

PURPOSE:To decrease the processing time by dividing a board into plural regions, allocating one processor to a wiring in each region and retrieving simultaneously and in parallel a route in each region. CONSTITUTION:A region control section 3 divides a grating map 10 of the entire wiring region into, e.g., 9 regions 9a-9i, provides a region number to each region respectively and stores the number together with a coordinate of each grating of the region. A section data is inputted sequentially from a section data storage section 1 to decide whether or not the gratings at both ends of the section data are included in any one region divided and when included, the region number is given to the section data corresponding to a section data storage section 1 and written in the section data storage section 1. A wiring control section 5 reads the section data provided with different region number one by one among the section data stored in the section data storage section 1, allocates each section data to the 9 processors 6a-6i one by one and inputs the section data and the region number respectively to each processor. The processor performs route retrieval based on the said information.

Description

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

BACKGROUND OF THE INVENTION Conventionally, this type of route search is carried out by running a track search program on a general-purpose computer having a large capacity memory. This method generally involves dividing the wiring area of printed circuit boards, LSIs, etc. into grids using orthogonal coordinates, and sequentially searching for routes for each pair of grids (there are multiple pairs) at both ends to be connected. Processing time is required. Even in route searching for a pair of grids, for example, starting from one grid, checking the presence or absence of tracks 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 (
C.Y., LEE, “An Algorithm
for PathConnections an
d Its Applications
RE Trans, Volume EC-10S
eptember.

(see 1961). However, it takes a considerable amount of time to sequentially search for routes for all of the plurality of grid pairs.

OBJECTS OF THE INVENTION An object of the present invention is to solve the above-mentioned conventional drawbacks, divide a board into a plurality of regions, allocate one processor to the wiring in each region, and The object of the present invention is to provide a route search processing system that can greatly reduce processing time when route searches are performed simultaneously and in parallel.

Composition of the Invention The search system of the present invention comprises: a section data storage section which divides a wiring board such as a printed board or an LSI into grids in orthogonal coordinates and stores grid pairs at both ends of each route to be connected as section data; 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 divided into the divided regions. an area control unit that assigns a corresponding area number to each area data belonging to any one area and performs area division management; and an area control unit that inputs the area data belonging to each of the divided areas and connects between grid pairs. a plurality of processors that search for a route;
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 each corresponding processor, and controls execution of each processor; and 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, a section data storage unit 1 divides a wiring area of a printed circuit board, an LSI, etc. into a lattice shape using orthogonal coordinates, and stores lattice pairs (generally there are multiple pairs) at both ends of a route to be connected as section data; A lattice map storage unit 2 for storing the usage status of each lattice above and a lattice map of the wiring area divided into multiple areas and corresponding to section data having lattices at both ends within each divided area. an area control unit 3 that assigns numbers to areas to be routed and manages division of the wiring switching area; and a plurality of processors 6a to 6 for each of the divided areas (by the area control unit 3);
a wiring control unit 5 which allocates one section data of 1 at a time and supplies section data whose both ends are in the same divided area read from the section data storage section to the corresponding processor and controls the operation of each processor; A wiring processing unit 7 including a plurality of processors 6a to 61 that searches for routes between the grids at both ends of the data, and route data searched by each processor of the wiring processing unit 7, update the contents of the grid map storage unit 2. and a route data output unit 8 that notifies the section data storage unit 1 that wiring has been completed or incomplete, and a route data storage unit 4 that stores route data output from the route data output unit 8.
It is composed of.

For example, as shown in FIG. 2, the area control unit 3 divides the grid map 10 of the entire wiring area into nine areas 9a to 91, assigns each area a region number (for example, 9a to 9i), and Save along with the coordinates of each grid in that region. 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 each of the nine processors 6a to 61. Allocate one to one, and input section data and its area number to each processor.

Each processor inputs a lattice map within the assigned area from the lattice map storage unit 2, searches for a route between the υ endpoint grids using a certain algorithm from the lattice map and the above-mentioned section data, and obtains route information for the optimal route. is passed to the route data output unit 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 a route is not found, a mark indicating that the route is not wired is written to 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 61, the time required for the search is significantly shortened.

Among the section data stored in the section 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, and the wiring routes are processed in parallel. The lattice map storage unit 2 is updated for each found item and stored in the route data storage unit 4. Also, a wiring completed mark is stored in the section data storage unit 1. The above operation determines the routes for those that can be routed within each area. ○ Both end points exist within the same area, but those that were not connected depending on the route within the area (marked as unwired) In order to search for a route for section data that spans between regions (as shown in the figure), the region control unit 3 redivides the lattice map into regions that are larger than before. For example, as shown in FIG.
To divide. Then, the section marked with the unwired mark is provided. The wiring control unit 5 allocates, for example, processors 6a to 6d to each of the four divided areas, 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 stored in the route data storage unit 4 via the route data output unit 8 in the same manner as described above, and the lattice map storage unit 2 is updated and the route completion mark is written in the section data storage unit 1. It will be done. For section data for which no route has been found, a mark indicating unwired is written in the section data storage section 1.

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

As described above, in the present invention, the wiring area is divided into a plurality of areas, and each of the plurality of divided areas has a
Since the configuration is such that the multiple processors are assigned and the route search is performed simultaneously and in parallel using section data that has both endpoints in each region, the processing time is significantly reduced compared to the conventional method. It has the effect of shortening the time. For those for which routes cannot be found within the divided regions and for wirings spanning between the divided regions, route searches can be performed by sequentially enlarging the divided regions. Overall, the computer time required for route searching can be significantly reduced compared to the conventional method. ,

[Brief explanation of drawings]

FIG. 1 is a block diagram showing the second actual flow side 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. FIG. In the figure, 1... Section data storage unit, 2... Grid map storage unit, 3... Area control unit, 4... Route data storage unit, Death... Wiring control unit, 6a to 61... Processor, 7... Wiring processing unit, 8... Route data output unit, 9a to 91... Area of grid map divided into 9, 1
0... Lattice map, 11a-lid... Region of the grid map divided into four. Agent Patent Attorney Sumi 1) Toshi So 1st cause 436- Figure 2 Figure 3 0

Claims (1)

[Claims] A section data storage unit that divides a wiring board such as a printed circuit board or LSI into a grid on orthogonal coordinates and stores the grid pairs at both ends of each route to be connected as section data, and stores the usage status of the grid on the entire board. The lattice map storage unit and the lattice of the entire board are divided into several areas, and among the interval data stored in the interval data storage unit, the lattice at both ends of the route belongs to one of the divided areas. an area control unit that assigns corresponding area numbers to each area and manages the division of the area, and a plurality of processors that input section data belonging to each of the divided areas and search for connection paths between the grid 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 each corresponding processor, and controls execution of each processor; A route search processing system comprising: a route data storage unit that stores route information searched by a plurality of processors.