JP2931683B2 - Labeling method in automatic wiring processing - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a labeling method in automatic wiring processing, and more particularly, to a wiring plane of a printed circuit board, LSI, or the like, which is an object of automatic wiring, is formed of an m.times.n (m, n is an integer) grid. The window is divided into a plurality of windows, and each grid is given a weight for being used as a wiring portion, and the labeling for the adjacent grids taking into account the weight is performed in the unit of the window in order from the window at the starting point. The present invention relates to a labeling method for determining the wiring route between the terminals at the start point and the destination point based on the result of the labeling.

[0002] Such automatic wiring processing is performed using a computer, but recently, due to the high density of printed circuit boards, LSIs, and the like, the processing time required to determine the wiring path has been reduced. It is more necessary to plan.
The present invention relates to a labeling method for responding to such a demand for shortening the required processing time.

[Prior art]

A conventional maze method, which is a method of obtaining a wiring route between terminals based on a result of labeling, is shown in FIGS.
This will be described with reference to FIG. In FIG. 6, A 'and B' are terminal pairs subject to automatic wiring processing, A 'is a starting point, and B' is a destination point. The plane to be automatically wired such as a printed circuit board or an LSI is divided into a lattice so that these two points are placed on the lattice, and the hatched portion is a prohibited area where the wiring pattern cannot be drawn. is there.

FIG. 6 (a) is an explanatory diagram showing the weight of using each grid of the plane to be automatically routed as a wiring portion. The smaller the numerical value is, the more preferentially the wiring pattern is used. This indicates that the grid is made. This weight depends on the positional relationship with the existing wiring pattern,
It is determined in advance based on the difficulty in performing the subsequent wiring.

[0005] Here, the active grid having the ability to label adjacent grids is only the point A 'at first, and A'
From the point, four grids adjacent to the east, west, north and south of this grid are labeled, that is, the value obtained by adding the weight of each of the grids to the label value (weight) of point A itself is assigned to the grid.

Then, in the next second step, FIG.
, The grids labeled in the first step (the numbers in circles) become active grids, and labeling is performed in the direction of the arrows from these active grids.
Label values are newly assigned to five adjacent grids.

When labeling from a plurality of adjacent grids is possible, such as labeling on grids E and F at this time, the smaller label value is assigned. For example, in the case of the grid E, the label value from the grid on the north side is "7" and the label value from the grid on the east side is "8", and the former label value is added.

Hereinafter, labeling is performed in the same procedure.
The label state at the time when the labeling at the sixth step is completed is as shown in FIG. Note that the part of the number surrounded by a circle is the active grid for the next step. For example, the grid G with the label value of “17” in the labeling of the fifth step is the grid G in the next seventh step. West active grid H
Is updated to the label value of "16" by the labeling from.

FIG. 6D shows a state in which the labeling at the ninth step has been completed. At this time, the label value "22" is added to the destination point B 'for the first time. Here, in the active grid (the part of the number surrounded by a circle), the label value of each of the grids I and J in the upper right part is smaller than the label value “22” of the destination point B, and a new label from these grids Since the label value of the target point B 'may be updated to a value smaller than "22" by the labeling, labeling from the grids I and J is continued thereafter.

The labeling is completed in the state shown in FIG. 6E where the label value of the destination point B is no longer updated to a smaller value. , The wiring route between A 'and B' is determined by sequentially following the adjacent grid with the smaller label value.

In such a maze method, 70 to 80% of the total processing time is required for labeling, and even after the label value is assigned to the target point B 'as shown in FIG. Since it may be necessary to continue the subsequent labeling, it has been proposed to use dedicated hardware to speed up the automatic wiring process.

Hereinafter, an automatic wiring process using the dedicated hardware will be described with reference to FIGS.
FIG. 7A shows a wiring plane divided into a plurality of windows each having a grid of m × n (m and n are integers), FIG. 7B shows the weight of each grid in this wiring plane, and FIG. FIG. 9 shows an outline of hardware dedicated to automatic wiring processing for performing labeling on the wiring plane, and FIG. 9 shows data contents of a plurality of PEs (processor elements) which are a part of the hardware. Figure 10 shows this hardware
(a) shows how to label the wiring plane. The configuration of the PE (processor element) is disclosed in Japanese Patent Application Laid-Open No. 2-81258.

Here, each grid of the wiring plane to be automatically routed is set with a weight for use as a wiring portion, and labeling is performed by a plurality of PEs in units of this window. . In other words, the plurality of PEs perform labeling of an adjacent window to be processed next after labeling of a predetermined window ends.

In FIG. 8, 5 is a processor array,
Each consists of processor elements (PE1 to PE9) that are responsible for one grid of each window,
For example, in the case of labeling window 0, PE5 is in charge of grid A (starting point) and PE3 is in charge of grid J. Also,
Reference numeral 3 denotes a controller for controlling these PEs, and reference numeral 11 denotes a PE control memory mounted on the controller.

Here, each PE is connected via a communication path to each of the PEs in charge of the north, south, east and west grids adjacent to the grid in charge, for example, PE1 is PE2, PE4
Are also connected to PE3 and PE7. A communication path is also provided between the controller 3 and the processor array 5, and data such as data distribution for labeling and label values are provided between the PE control memory 11 and each PE. Data collection. The controller 3 controls the data distribution and data collection,
E controls the operation to be executed.

As described above, the controller 3 sets the starting point and the destination point of the labeling in the processor array 5,
In addition, each PE is instructed to specify a window, and the labeling is executed. After it is determined that the label value is no longer updated in the window, a window for executing the next labeling is indicated. The window is switched by setting the base address of the memory in the PE.

In the data of the memory of each PE shown in FIG. 9, "windownumber", "target"
"tLabel" and "nLabel" are work data common to each window, and the others are data for each window.

The number in parentheses indicates a window number. For example, “nWindow (0)” is a window number “3” adjacent to the north side of window 0,
“Cost (2)” in the memory of PE1 is the weight “4” of the lattice L handled by PE1 in window 2.

As for "startFlag", only "startFlag (0)" in the memory of PE5 which is in charge of the starting point A of window 0 becomes "1".
As for “targetFlag”, “targetFl” in the memory of the PE 6 in charge of the target point B of the window 2
“ag (2)” is “1”.

Next, the dedicated hardware shown in FIG.
The state of labeling the wiring plane in (a) will be described with reference to FIG. In the figure, A indicates the starting point, B indicates the destination point, the shaded portion indicates the active grid at that time, and the arrow indicates the direction in which the label giving the minimum label value has been transmitted. The event queue 4 is an area provided in the PE control memory 11 for storing the window number of the next window to be labeled.
In this event queue, the window numbers are stored in ascending order of the window numbers, starting from the right side.

FIG. 10B shows a state in which the labeling of window 0 has been completed, and the next queue to be labeled, that is, the window adjacent to the active grid of window 0, is stored in the event queue. 1 and the window number of window 3 are stored.

FIG. 10 (c) shows a state in which labeling of the windows 1 and 3 has been completed, and the event queue has windows 0, 2 and 4 to be labeled next. Window number is stored. Note that the already labeled window 0 is the target of the next labeling because the active grid with the label value “15” at the lower right in window 3 is located in the window 0 adjacent to its south side. This is because there is a possibility of updating the label value of the grid (there is no north-south arrow between this active grid).

FIG. 10 (d) shows a state in which labeling of window 0, window 2 and window 4 has been completed. In the event queue, window 1 and window 3 to be labeled next are displayed. And the window number of the window 5 are stored. Here, the window 3 and the window 5 are subjected to the next labeling process for the same reason as in the case of FIG. 10C.

At this stage, the label value "3
Although “0” is added, the label value of the active grid of the window 4 is transmitted through the window 5 so that the destination point B
Since the label value of may be updated to a smaller value, the subsequent labeling process is executed. At this time,
In the grids M and N at the upper right and lower right of the window 2, the respective label values “31” are larger than the label value “30” of the destination point B, and are not active grids.

FIG. 10 (e) shows a state in which labeling of windows 1, 3 and 5 has been completed, and the event queue has windows 2 and 4 to be labeled next. Window number is stored.

FIG. 10 (f) shows a state in which all labeling processes have been completed, that is, a state in which the active grid has disappeared and the event queue has become empty. Note that the grids P and Q at both lower corners of the window 2 remain larger than the label value of the target point B even if the respective label values are updated.

[0027]

The above-described labeling in units of windows by dedicated hardware also requires 6 labels.
There is a problem that the window switching is performed 11 times for one window, and the processing time is still long.

Therefore, according to the present invention, when a plurality of window numbers are contained in the event queue, labeling is performed only for the window having the smallest label value transmitted to the window of each window number. By doing so, it is possible to reduce the time required for labeling by minimizing the occurrence of relabeling the window once labeled and updating to a smaller label value as much as possible. With the goal.

[0029]

SUMMARY OF THE INVENTION The present invention relates to m × n (m,
n is an integer) into a plurality of windows consisting of a grid, and each of the grids has a weight set for being used as a wiring portion.
In the method of sequentially performing labeling on adjacent grids taking into account the weight in units of the window from the window at the starting point, when there are a plurality of adjacent windows to be labeled next, labeling is performed. The next labeling process is performed only on the adjacent window that has the smallest label value transmitted from the active grid of the processed window, and the label value of the window whose labeling process has been completed is smaller by the labeling process again. This reduces the occurrence of cases such as updating to a value.

FIG. 1 is a diagram illustrating the principle of the present invention. In the figure, reference numeral 1 denotes wiring plane data, which is mxn (m, n
) Is data indicating the adjacent relationship of each window in a wiring plane divided into a plurality of windows formed of a lattice of (integer).

Numeral 2 denotes weight data, which is set in each grid of the wiring plane and includes weights for use as wiring portions.

Reference numeral 3 denotes a controller, which sends wiring plane data 1, weight data 2, and the label value of the active grid used for the next labeling to the processor array 5, and outputs the label value of the labeled active grid to the processor array 5. It receives the window number of the window adjacent to the active lattice from the processor array 5 and controls the operations executed by the processor array 5.

Reference numeral 4 denotes an event queue, which is a window number sent from the processor array 5 and a minimum value among the label values corresponding to the window number (of the active grid transmitting the label value to this window). Are stored as a set.

Reference numeral 5 denotes a processor array, which is composed of m × n processor elements each of which is in charge of one grid, and the processor elements which are in charge of adjacent grids are connected via a communication path. Perform labeling for each grid of the window indicated by 3.

The basic procedure of the labeling process according to the present invention is as follows. That is, the controller 3 sends the window number of the window of the starting point to the processor array 5 to indicate the window to be first labeled.

Each processor element of the processor array 5 sequentially performs labeling on the designated window in the same manner as in the related art on each of adjacent grids through which label values are transmitted.

The processor array 5 sequentially transmits the label value of the active grid capable of transmitting the label value to the adjacent window and the window number to the controller 3. If the label value is equal to or greater than the label value of the target point at that time, the data is not transmitted to the controller 3 or even if it is transmitted, the controller 3 treats the data as invalid data. I have. This is because even if subsequent labeling is performed using this label value, there is no possibility that the label value of the destination point is updated to a smaller value.

The controller 3 confirms that the transmission of new contents from the controller 3 has ceased, and pairs the transmitted window number with the smallest label value corresponding to the window number. Add to event queue.

The controller 3 determines whether or not data of the window number remains in the event queue. If "YES", the labeling is ended, and if "NO", the process proceeds to the next step.

The window number paired with the smallest of the label values in the event queue is retrieved and sent to the processor array 5, indicating the next window to be labeled, and Delete the data from the event queue and return to the step. According to the basic procedure described above, when there are a plurality of windows to be labeled next, labeling is performed only for a specific one of the windows.

It should be noted that, among the data not sent to the processor array 5 in the step, the event queue of the set whose label value is equal to or larger than the label value of the target point (at this time) is also set. May be deleted. This is because even if subsequent labeling is performed based on these label values, there is no possibility that the label value of the destination point is updated to a smaller value.

[0042]

As described above, when there are a plurality of adjacent windows capable of transmitting the label value of the active grid of the window for which labeling has been completed, the labeling is not performed for all the windows as in the related art. Labeling is performed only for one window specified according to a predetermined rule.

Then, since this rule is to select the window adjacent to the active grid having the smallest label value from the adjacent windows, after performing the labeling on the selected window, the window from other windows is selected. It is unlikely that relabeling with the incoming label value will update the selected window's label value to a smaller value, and the window required to complete the entire labeling process will be low. Can be reduced.

Hereinafter, this labeling will be described with reference to FIGS. Here, A is the starting point, B is the destination point, the shaded portion is the active grid, and the weight of each grid is set to the same content as in FIG. The number to the right of each window number is the smallest of the label values of the active grid adjacent to the window, and these are 1
It constitutes a set of data. And the data of each set is
The numbers on the right side are stored in accordance with the rule of rearranging the numbers in ascending order and the smaller number is placed at the head of the event queue 4, and the next labeling is stored at the head (right side) of the event queue 4. Performed only for the window with the window number.

FIG. 2A shows an initial state. In the event queue 4, a window 0 of a starting point A for performing labeling first and a weight "1" of the starting point A are stored. Is stored.

FIG. 2B shows a state in which labeling of window 0 has been completed.
The data of "1" has been deleted. In the event queue, data in which the window numbers “1” and “3” of the window adjacent to the window 0 and the minimum label values “13” and “2” are set as the rule Are stored with the set of “3-2” of the window 3 at the top.

Here, the window 3 is at the top because the minimum value “2” of the label value of the active grid adjacent to the window 3 is the minimum value “13” of the label value of the active grid adjacent to the window 1. Because it is smaller than ".

Hereinafter, labeling of the first window of the event queue is sequentially performed in the same manner.

FIG. 2C shows a state in which the labeling of the window 3 has been completed.
The data of "2" has been deleted. Then, in the event queue, window 0 adjacent to window 3
And data on window 4 are newly added.
A set of data is stored starting from the set of “4-5” in the window 4.

The reason why the data for window 0 is newly added is that the label value is transmitted to the window 0 from the active grid of the label value "15" at the lower right of the window 3, and the label of this window is This is because it is possible to perform the attachment.

FIG. 2D shows a state where the labeling of the window 4 has been completed.
The data of "5" has been deleted. Then, data for window 1, window 3 and window 5 adjacent to the window 4 is newly added to the event queue.
-8 "at the beginning.

Here, with respect to the window 3, only the grid with the lower label value "18", which is not yet marked with an arrow, between the grid on the left side of the window 4 and the window 3 performs labeling. It is in an active state with the ability,
For window 1, the data of the set of the minimum label value "17" of the adjacent grid on the north side and the data of the set of the minimum label value "13" of the adjacent grid on the west side are stored in the event queue. Will be.

FIG. 2E shows a state in which labeling of the window 5 has been completed.
8 ”has been deleted. And, in the event queue, window 2 adjacent to window 5
And data on window 4 are newly added.
A set of data is stored starting from the set of "2-11" in window 2.

FIG. 2 (f) shows a state where labeling of window 2 has been completed.
At this time, the label value "14" is added to the target point B, and the grids R, R at the lower corners where the value after labeling is larger than this "14" are deleted. S
Is not given a label value.

Although no new data is added to the event queue, five sets of data (two sets of data corresponding to different windows for window 1) remain. , Followed by labeling of these four windows.

FIG. 3A shows a state in which all labeling processes have been completed, that is, the active grid has disappeared, and
This indicates a state where the queue data has been lost. At this time, no label value is assigned to each grid of the window 1 in which the value after labeling is larger than the label value “14” of the destination point B.

Incidentally, in the state of FIG.
If the label value “14” or more is used for subsequent labeling, there is no possibility that the label value of the destination point B is updated to a smaller value, so the labeling for window 0 and window 3 is omitted. May be. In this case, three sets of data, "3-18" of window 3, "1-17" of window 1, and "0-15" of window 0 are event data.
It is removed from the queue and the state of the event queue is
(b).

As described above, the total number of windows to be labeled is nine when ending from the event queue state in FIG. 2 (f), and ends in the event queue state in FIG. 3 (b). In this case, the number is seven, and in each case, the number is smaller than that of the conventional eleven.

[0059]

An embodiment of the present invention will be described below with reference to FIGS. Here, the controller, each processor element (PE), the wiring plane, the weight of each grid, and the like have the same configuration as those in FIGS.

FIG. 4 is a flowchart showing the operation procedure of the controller 3. That is, in the event queue 4,
The window number “1” of the starting point and the weight “1” of the starting point are added, and the process proceeds to the next step.

'Take out the head data of the event queue 4 and send it to the processor array 5, instruct each processor element a window for performing labeling, and proceed to the next step.

'Confirm that the label value of each grid sent from the processor array 5 has not been updated to a new value, and proceed to the next step.

'The label values sent from each PE are grouped for each corresponding window number, and data in which the minimum label value and the window number in each group are paired are created. Proceed to step.

'Data including the (minimum) label value and the window number is added to the event queue 4, and the process proceeds to the next step.

'The data remaining in the event queue 4 and the newly added data are sorted using the label value as a key, and the process proceeds to the next step. By this sorting, each data in which the label value and the window number are grouped is arranged from the head in ascending order of the label value.

'The sorted label values are compared with the label value "targetLabel" of the target point at that time, and a set of data having a relationship of "the former ≧ the latter" is deleted from the event queue 4. In addition, "target
The initial value of “Label” is set to infinity.

It is determined whether or not the data in the event queue 4 has been exhausted. If "YES", the control for the processor array 5 is ended, and if "NO", the process returns to step "." By such a procedure, the operation of each PE is controlled. In the above procedure, the order of step 'and step' may be reversed.

On the other hand, the procedure of label calculation in each PE is shown in FIG.
It is like. The label calculation in each PE is as follows:
The process is repeated for each grid in a single window as indicated by the controller.

That is, (1) The controller sets a window number for performing labeling, and initially sets a window number “0” of the starting point A.

(2) Initial value setting for labeling the memory of each PE is performed. That is, the label value of the destination point B is set to infinity, and each P
There is no label input from the adjacent grid to the grid that E is in charge of, and the label values of these grids themselves are infinite. .

(3) It is determined whether or not to proceed to the subsequent label calculation. For example, in window 0, in the case of labeling from the starting point A to its north adjacent lattice T, which is handled by PE2, label (0) and target
Label value is infinity, nLabel value is starting point A
Since the label value of “1” and the value of cost (0) are “1”, this determination condition is satisfied and the process proceeds to the subsequent label calculation, and the value of label (0) of PE2 changes from infinity to “2”.
However, in the case of labeling from grid U to its north adjacent grid V, which is handled by PE3, label
Since the value of (0) is “14”, the value of nLabel is the label value of the grid U “13”, and the value of cost (0) is “12”,
Since the first inequality of the determination condition is no longer satisfied, the label calculation does not proceed, and the value of label (0) of PE3 is not updated (see FIGS. 2A and 2B and FIG. 8).

Also, for example, in window 2, P
In the case of labeling from grid W to its west adjacent grid R, which is handled by E7, the value of targetLabel is "14", the value of nLabel is the label value of grid W "14",
Since the value of cost (2) is "4", the second inequality of the determination condition is not satisfied, and the process does not proceed to the subsequent label calculation (see FIG. 2 (f) and FIG. 8).

(4) Update the label value of the assigned grid with a value obtained by adding its own weight to the label value transmitted from the adjacent grid. For example, the label value of the previous grid T is changed from infinity to “2”.
Update to

(5) Add azimuth data indicating from which direction the label value is transmitted to the assigned grid. For example,
When a label is input from the adjacent grid A on the south side as in the case of labeling the grid T, the dir of the memory of PE2 is input.
The value of S (0) is set to “1”.

(6) The current label value of the assigned grid is transmitted to the adjacent grid in which the azimuth data remains "0", that is, the adjacent grid excluding the grid of the label input source, via the communication channel. .

(7) When the targetFlag of the assigned grid is “1”, the value of the targetLabel is updated with the label value of the assigned grid. When the targetFlag is “0”, the value of the targetLabel is not updated and the next Proceed to step.

(8) When the assigned grid is adjacent to another window, the window number and the label value of the assigned grid are transmitted to the controller. Otherwise, the label value of the assigned grid is transmitted to the controller. Return to step (2) without telling. Each PE repeatedly executes such parallel processing in units of windows.

As described above, in the labeling of a certain window instructed by the controller, each PE in the active state where the assigned grid can transmit the label value to the adjacent window has the label value of the assigned grid, The adjacent window number is sent to the controller.

Then, at the point when the update of these data does not occur, the controller sends the window number having the smallest label value to each PE, and the PE side receiving this transfers the labeling of this window. Further, each label value of the active grid of the adjacent window transmitted to this window is also sent to the PE side and used for labeling the next adjacent window.

In the above description, the number of windows is six,
Although the number of grids in each window is set to nine, in the actual automatic wiring processing, for example, a wiring plane in which each window has 16384 (128 × 128) grids in 80 (10 × 8) windows is used. ing.

[0081]

According to the present invention, the wiring plane to be subjected to the automatic wiring processing is divided into m × n windows (m and n are integers), and the weight of each grid from the starting point is taken into account. When labeling is performed in this window unit, the window in which the minimum label value at that time is transmitted among multiple adjacent windows that can transmit the label value of the active grid of the window for which labeling has been completed Only perform the next labeling, and reduce the rate at which label values are assigned and then relabeled and updated to smaller label values. , The total number of windows can be reduced, and the required processing time of the entire automatic wiring can be shortened.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating the principle of the present invention.

FIG. 2 is an explanatory diagram (No. 1) showing a state of labeling according to the present invention.

FIG. 3 is an explanatory view (No. 2) showing a state of labeling according to the present invention;

FIG. 4 is a flowchart illustrating an operation procedure of a controller according to the present invention.

FIG. 5 is a flowchart showing an operation procedure of each processor element (PE) of the present invention.

FIG. 6 is an explanatory diagram showing a state of labeling by a conventional maze method (part 1) in which weight is added.

FIG. 7 is an explanatory diagram showing a wiring plane divided into a plurality of windows composed of m × n (m and n are integers) grids and weights of the grids;

FIG. 8 is an explanatory diagram showing an outline of hardware dedicated to automatic wiring processing for performing labeling in window units in FIG. 7;

FIG. 9 is an explanatory diagram showing data contents of each of a plurality of PEs (processor elements).

10 is an explanatory diagram showing a state of labeling by the conventional maze method (part 2) in which weights are added in the wiring plane of FIG. 7;

[Explanation of symbols]

 1 Wiring plane data 2 Weight data 3 Controller (PE controller) 4 Event queue 5 Processor array

Continuation of the front page (56) References JP-A-60-144867 (JP, A) JP-A-62-80757 (JP, A) JP-A-63-15367 (JP, A) JP-A-2-17576 (JP) , A) (58) Field surveyed (Int.Cl. ⁶ , DB name) G06F 17/50 G06F 15/16 H01L 21/82

Claims (2)

(57) [Claims] 1. A wiring plane which is divided into a plurality of windows each having a grid of m × n (m and n are integers), each of which has a weight set for use as a wiring portion. , A controller with an event queue, and each has a one-to-one grid of the window
And a processor array having m × n processor elements connected to each other by a communication path, and the weight assigned to the window specified by the controller. Is automatically added from the window of the starting point by the processor array, and the wiring route between the starting point and the destination point is determined based on the result of the labeling. In the labeling method in the processing, the processor array to which the wiring plane data indicating the adjacency relation of each window and the weight data of each grid are given, while repeatedly executing the labeling for each grid of the designated window. , That of an active grid that can convey label values to adjacent windows The controller sends the label value and the window number of the adjacent window to the controller, and at a predetermined time, the controller determines the transmitted window number and the minimum value of the label values corresponding to the window number. Adding the paired data to the event queue, and then sending to the processor the window number paired with the lowest of the label values in the event queue. While indicating that only the window specified by the window number is the target of the next labeling, the process of deleting the data of this window number pair from the event queue is repeated, and the label value of the destination point is further increased. Labeling is performed until it is no longer updated with a small value. Labeling method. 2. The controller according to claim 1, wherein the controller sets the event queue for a pair of the label value and the window number in the event queue, the label value being equal to or larger than the label value of the destination point. 2. A labeling method in an automatic wiring process according to claim 1, wherein the labeling method is performed by deleting the labeling method.