JPS60144867A - Parallel data processor - Google Patents

Abstract

PURPOSE:To shorten the time needed for processing data on the wiring design, etc. by performing the data processing with hardware after providing cells in an array and with total or partial asynchronization with a clock. CONSTITUTION:Cells 401 forming an array part 303 are connected to the cells in four directions adjacent to each other via bidirectional data transfer lines 402 excluding the cells at both ends of vertical and horizontal directions respectively. A control part 302 receives the data needed for wiring processing from a host computer and sends it to the part 303 together with a control signal, etc. Then the part 302 receives the data again after the necessary processing is over. In other words, the signals are transmitted in wave forms to four directions from a cell at the starting point by the control signal sent from the part 302 in a cell action mode or a clock asynchronous mode. Thus the data transfer direction is decided. Then a route is decided via a data transfer line decided previously from a terminal point. Thus the signal is transmitted asynchronously between cells by the hardware. This accelerates the transmission of signals and shortens the time for wiring design, etc.

Description

[Detailed Description of the Invention] (Field to which the invention pertains) The present invention can be used by connecting to a simple control device.
The present invention relates to a parallel data processing device that can perform data processing, particularly processing such as wiring route determination, in an extremely short time.

(Prior Art) In the field of wiring design, there is a method that uses correspondence between a wiring grid and an arrangement, particularly as a method for determining wiring routes on a printed circuit board or an LSI chip.

Figure 1 is an explanatory diagram showing the correspondence between conventional wiring grids and arrays.
Each intersection of the wiring grid 101 is made to correspond to each element of the array 102, and from one point to be connected (starting point S), the intersections in the middle of the connection are sequentially checked for vacancies and occlusions. Code L1°L2. L3...
Check whether there is a route that can reach the other point (end point T) to be connected while attaching ..., and if there is a route, go backwards from the end point T to the start point S and connect to the intersection. The code L4. L3. A method is used to find the shortest route between the starting point and the ending point by sequentially following . In the figure, (B) is a prohibited area.

The above-mentioned wiring method rt1 has a high degree of freedom in wiring, and has the characteristic that if a route exists, it always finds the endmost route, and is a very effective means for wiring design. When trying to realize this on a general-purpose computer,
On the computer, all the planes corresponding to the wiring grid must be memorized, and processing can only be performed on one wiring grid at the same time.As the scale of the wiring grid increases, the processing time becomes enormous, and eventually Application of such methods will be prohibited.

Furthermore, in order to speed up the above method, it has been considered that each wiring grid corresponds to a unit of hardware, and many parts of the wiring installation are implemented in hardware. However, in all devices of this type, processing is performed in synchronization with a clock, and if the code is added in a waveform from the starting point, the part corresponding to the wavefront can be processed in parallel, but conversely, if the code is followed from the end point, In the route determination phase, as with the 7-kenyar processing, effective processing is only performed on one wiring grid at the same time in synchronization with the clock, which leads to a dramatic reduction in processing time. There wasn't.

Another method for determining a wiring route using a conventional general-purpose 49 machine is to search for a route using line segments from points to be connected.

Figure 2 is an explanatory diagram of the conventional route search method using line segments, where solid lines are obstacles (no-passing areas), dotted lines are wiring grids, and points A and B are two points that should be connected, that is, the starting point. and the end point.

The method for searching for a route will be explained. Two line segments t from the starting point without cutting. and make tl. Since these do not meet the end point B, the bending point C closest to the starting point A is registered. Next, two line segments t2. from the end point B. Make t3. These also do not meet the starting point A, so the bending point closest to B is registered. Next, create a line segment t4 from point C. t4 meets the line segment t3 from the end point B at the point. From the above, route A-C-
D-8 is obtained. The above method memorizes line segments passing through grid points and searches for a route linearly, so it is
When this method is executed on a T39 aircraft, it requires less storage capacity and can be executed at high speed in a simple case as shown in FIG. However, this method is a heuristic method, and there is no guarantee that an optimal solution will be obtained.As the route becomes more complex, the number of trials will increase significantly, and the number of line segments and points to be memorized will increase. However, there was a drawback that the route could not be discovered due to the limited processing power of the i'lW machine.

(Objective of the Invention) The present invention replaces data processing that was conventionally performed by software with hardware by arranging cells in an array, and in which processing was performed step by step in synchronization with a clock. It is characterized in that some and all processes are performed asynchronously with the clock, and its purpose is to significantly reduce the processing time of data such as wiring wiring. More 1! , embodiments of the present invention will be described in detail with reference to the drawings.

(+14 structure and operation of the invention) FIG. 3 shows the (114 structure) of the first embodiment of the invention.
It is used to determine wiring routes for printed circuit boards, LSIs, etc. by connecting it to an appropriate control device, and 301 is the I/T Ace part that connects with the Hoss I/Yu 39 machine, and 302 is the control part. , 303 is an array section.

The control unit 302 receives data necessary for wiring processing sent from the host computer, sends it to the array unit 303, and also sends clock signals and various control signals to the array unit 303.
After the processing is completed, data is received from the play unit 303.

FIG. 114 shows an example of the configuration of the array section 303. A cell 401 is connected to adjacent cells in four directions by a bidirectional data transfer path 402, except for the cells at the top, bottom, left, and right ends. 40: The line is connected to all cells 401 by the control line from the control unit 302. 404 is a signal terminal for outputting the result, 405 and α 406 C are human power IN1 in the X and y directions, respectively.407 and 408 are X and y decoding circuits, respectively, and
09 and 410 are decoded and sent to cell 40.
Make selection 1.

FIG. 5 shows an example of the configuration of the cell 401.
11. 502 and 503 are registers indicating the state of the cell, 501 indicates the starting point, 502 indicates the ending point, and 503 indicates whether or not it is a prohibited area. Cells that are not in any of these states indicate empty cells through which wiring can pass, and these registers can be set to any state by signals from the control section. Reference numeral 504 is a register for storing the result after route discovery, and each of the registers 501 to 504 may have a storage capacity of 1 bit. 505 to 509 are all OR gate circuits, and 510. 511 AND
Gate circuit, 512, input gate circuit, 513. 51
4 is a selector circuit, and 515 is an arbiter, which has the function of outputting only No. 15 that reached the arbiter 515 the fastest among the signals that have passed through the input gate circuit 512, and operates asynchronously with the clock. do. 516! '
Which f^1 child the output of the f arbiter 515 appears in V (a processor/coder that generates an appropriate code accordingly, 517
・:L register 518 is a programmable data transfer circuit, and the data transfer direction can be selected according to the output l'i'i information, and 519 to 522( Me, L so Jl zo Jt upper F], - the person who receives the lVJ'j from the adjacent cell on the right if the bell 117.52.U~52 (ilI:t sowazo 717l-
Muni's right 1 buttocks 1 and the output terminal that transmits faith to the cell -J',
527 and 5281 are X.

ycheetah7-ta409. 410 input y: f, child, 529 to 536 are control signal input terminals from the control device, 537 to 5391d output terminals to the control device, 540 is a nft register, 541 is xr? decoder 4
This is a cell selection circuit that selects a specific cell based on signals from 07 and 408, and the above is the configuration of the cell.

Cell operation mode i4, a) Clock operation mode, b
) There are two types of clock asynchronous motes. Each operation mode will be explained below.

a) Status registers 501 to 503v are controlled by signals from the clock synchronization mode control unit.
c. Register whether the cell is the starting point, the ending point, or a wiring prohibited area, and after finding the route, register 504 with the route as an obstacle to the next net.
or register 501vc as the starting point for the next terminal connection. Moreover, these operations are performed in synchronization with the clock supplied from the 1llll.

b) A control signal from the clock asynchronous mote controller causes the signal to be propagated in a waveform in four directions from the starting point cell, the arbiter 515 determines the data transfer direction, and the signal is stored in the register 517 via the processor/coder 516. After, programmable data transfer circuit 5
It is set to 18. This time, on the contrary, the signal propagates from the end point through the already determined data transfer path, and the route is established. The above operations are performed asynchronously, regardless of the clock. Asynchronous data transfer is different from transfer by l steps using a clock, in other words, the signal transmission distance depends on the number of clocks. The distance depends only on the gate delay of the data transfer path. Therefore, a much faster (+4.,;,L) transmission than the clock cycle is possible.

FIG. 6 shows an example of the propagation of the starting point S and the bow in the array MIi 303 after a unit time has elapsed.

The break propagates Iha in four directions from the starting point S, and the unit (1
? It shows the outer periphery of the cell where the signal from the starting point S arrived after f time has elapsed. In other words, the use of arbiter 515 (assuming that the gate delays are the same for all cells, it is possible to detect the direction in which the signal arrived at the cell most quickly. In other words, if the gate delays are equal, the distance calculation and multiple It is possible to find the shortest path without coding the pits.

Next, an example of the operation of the parallel data processing apparatus of the present invention will be described in detail with reference to FIGS. 4 and 5.

The operation of the entire device can be roughly divided into 1) reset phase; 2)
) state set 7 aids, 3) bus search phase, 4)
The process is divided into a trace back phase, 5) a state reset phase, and 6) a clear phase, and each of the seven phases will be explained in order below. In addition, in this example, the wiring 1gQ
Although the single-layer wiring is limited to the vertical and horizontal directions, it is easy to expand to enable multi-layer wiring and diagonal wiring, so a description thereof will be omitted.

l) Reset phase This phase is executed only once at the beginning of device operation.

That is, the status registers 501 to 503 and registers 504 and 517 are cleared by the signal from the control i1 device.

2) State set phase The state of the cell, that is, the start point, end point, and prohibited area,
The x, y decoder 407.4 receives a signal from the control device.
08 to iiT+L, and select the cell from the cell selection circuit 54.
1, and select the state register 5 of the corresponding cell in the array section.
Set to 01-503. Phases 1) and 2) of ``2'' are performed in synchronization with the clock from the control device 11, and during this period, the input gate circuit 512 is closed by the control signal from the control signal input terminal 532.

After this phase ends, the control device issues a control signal to enter the next clock asynchronous mode.

3) The OR gate circuit 508 is opened by a signal from the bus search phase control input terminal 533, and the register 517 can be read by a signal from the control signal input terminal 535.

In 2) above, cell I/state register 501~
Depending on the contents of 503, each cell in the array section has a different function. If the contents of the status register 50, 3 are at the logic level Jl+, that is, if the cell is in a prohibited area, the human cover gate circuit 512 kI IX4,
No signal is transmitted to the corresponding cell. When the contents of the status register 501 are at the logic level n1n, that is, when the cell is the starting point, the selector circuit 5 is activated by the output of the OR gate circuit 507 and the signal from the control signal terminal 534 indicating that it is the bus search phase. ]4 selects the output of the OR gate') circuit 507 and outputs a logic level 111'. Further, the programmable data transfer circuit 518 receives a control signal from the control signal input terminal 5 indicating that the bus search phase is in progress.
The output of the selector circuit 514, that is, the logic level Jn, is outputted to the output terminals 523 to 526 for data transfer to adjacent cells in response to the signal from the selector circuit 36. status register 50
2 is at logic level “1”, that is, the cell is the end point, or the status register 501
, 502 and 503 are all at logic level l1
When it is on, that is, when the cell in question is an empty cell, in these cases, the selector circuit 514 receives the signal from the output of the input gate circuit 512 via the OR gate circuit 509;
Then, the programmable data transfer circuit 518 outputs the input signal to all output terminals 523 to 526 according to the signal from the control signal input terminal 536.

It is impossible for the state logic "xzso□" and the logic level "n1n1", that is, the cell in question, to be both the starting point and the ending point.

As described above, the logic level 1111 is propagated only from the cell serving as the starting point between vacant cells asynchronously with the clock. At this time, the arbiter 515 selects only the signal that arrived at the input signal terminals 519 to 522 of the vacant cells the fastest, and the direction in which the signal arrived the fastest is passed through the encoder 516 to the register 517.
The content is stored in the clear phase and does not change by the signal from the control signal input terminal 535 until the clear phase. In this way, the empty cells memorize the direction in which the signal arrived fastest from the starting point one after another, and when the signal reaches the ending point, the corresponding cell memorizes the direction in which the signal arrived fastest, just like the empty cell. In addition, the logical product of the outputs of the status register 502 and the OR gate circuit 508, that is, the AND gate circuit 5
The output of 11 becomes logic level n111 and this phase ends. From this point on, the signal propagates between empty cells in a waveform from the starting point, and at the same time, the direction of the first arriving signal is stored asynchronously. Furthermore, if the route does not exist or is unnecessarily long, that is, if the signal from the starting point does not reach the ending point even after a certain period of time has passed, this phase is forcibly terminated by a signal from the control device. In this case, next
Head to the clear phase. As is clear from the above description, the starting point cell does not have to be singular, and may be plural. That is, wiring for a multi-terminal net is also possible.

FIG. 7 shows an example of the state in each cell 401 of the array section 303 at the end of the path search phase of the device of the present invention. S indicates the starting point, T indicates the ending point, (13) indicates a prohibited area, and the arrow indicates the state of the register 517 in each cell, that is, the direction in which the signal from the starting point S reached the cell most quickly.

4) Traceback phase: The contents of the status register 5°02 of the relevant cell are at logic level 1.
1'', that is, when it is the end point, the selector circuit 514 outputs the output of the OR gate circuit 507, that is, the logic level l11@, and the programmable data transfer circuit 518 outputs a control signal indicating that it is the trace back phase. A signal from the input terminal 536 sets the logic level "11" only in the direction stored in the register 517.
Output. When the contents of the status register 503 of the cell concerned are at logic level 111'', that is, when the passage is prohibited, the input gate circuit 512 is closed as in the passerch frame.When the contents of the status register 501 of the concerned cell are at the logical level nun. In the case of the starting point, when the input signal reaches the corresponding cell, the logical one product of the output of the OR gate circuit 508 and the output of the state register 501, that is, AN
The output of the D gate circuit 510 is at logic level II II II
This notifies the control device that the route has been determined, and ends this phase. At this time, the vacant cell is transferred from the end point to the register 5 by the programmable data transfer port 518.
According to the transfer direction stored in 17, signal transmission is performed asynchronously, and the path is the empty cell where the output of the OR gate circuit 508 becomes the logic level Jl, and the result is stored in the register 504. . Also, at the starting point, the signal from status register 501 causes programmable data transfer port 518 to not transmit signals in either direction.

5) State resetting phase From this phase, processing is again synchronized with the clock from the control device. ``At the end of the traceback phase, whether or not the cell in question is a route is stored in the register 504. If the route to be determined is a two-terminal net, the selector circuit 513 uses a signal from the control unit input terminal 530 to pass the result (route) shift register 540,
It is sent from the output terminal 537 to the control unit jξ. Furthermore, the route is registered as a prohibited area for the next connection to the network. That is, the result is logically summed with the status register 503 and stored in the status register 503 again. After this, if the requested route to Clear AIDS is three or more terminals, the route between two terminals is re-registered as the starting point 7. That is, the output of the selector circuit 513 is sent to the status register 501 by a signal from the control signal input terminal 530.
Store in. After this, the terminal moves to the /x search phase and determines the route to the next terminal. After repeating the above and completing all terminal wiring, the route is output to the control device in the same way as in the case of a two-terminal network. Since the route that has already been taken is registered as the starting point, it is stored in the register 504 by the OR gate circuit 505.
and the status register 501 and outputs the result.

6) Clear phase: Controls the route determination for the next step (No. 8 controls registers 504.517 and status registers 501.502)
Clear. After this, proceed to 2) state setting phase. By repeating the following two phases, it is possible to wire multiple terminals and multiple nets. In the embodiment described above, if a route exists, it can always be found, and if the delay time of each cell is the same, the shortest route can be found.

Next, a second embodiment of the present invention will be described.

This example is used to determine wiring routes for printed circuit boards, LSIs, etc., and is the same as the above description except for the configuration inside the cell. That is, since the overall configuration is as shown in FIG. 3 and the configuration of the array section is as shown in FIG. 4, the explanation thereof will be omitted here.

FIG. 8 shows the structure of another embodiment of the cell used in the present invention. 801.802. '803 is a status register indicating the status of the cell, 801 is the starting point, 802
indicates the end point, and 803 indicates whether or not it is a prohibited area. A cell that is not in any of these states is an empty cell through which a wire can pass. These registers can be set to any state by signals from the control section. 804 is a register that stores the result after route discovery. Here, registers 801 to 804 each have a storage capacity of 1 bit,
Well, 805 to 810 are OR gate circuits, 811.81
2 is an AND gate circuit, 813 is an input gate circuit, 81
4 is a gate circuit, 815 to 817 are selector circuits, 81
8 is an arbiter that detects the signal that reaches the arbiter fastest among the parts that have passed through the input gate circuit 813, and 819 selects an appropriate sign depending on which terminal the output of the arbiter 818 appears on. Generating encoder, 82
0 is a register that stores the output of the encoder 819, 82
1 is a programmable data transfer port, 822.823 is an input terminal that receives output signals from adjacent cells in the upper and lower directions, and 824.825 is an input terminal that receives output signals from adjacent cells in the left and right directions. , 826-829
830 and 831 are signal input terminals from the X+Y decoders 407 and 408, 832 to 841 are control signal terminals from the control device, and 842 to 844 are to the control device, respectively. 845 is a register, and 846 is a cell selection circuit that selects a specific cell based on the signals from the X+Y decoders 407 and 408. The following is the cell configuration.

Cell operation mode (dl) As mentioned earlier, it can be roughly divided into clock synchronous mode and clock asynchronous mode. Data transmission between cells, detection of the fastest arriving signal by arbiter 818, and transmission to register 820 through encoder 819. ': 1) Reading processing is performed asynchronously with the clock; L1 and others are in a mode synchronized with the clock.

Next, an example of the operation of the apparatus of the present invention will be described in detail with reference to FIGS. 4 and 8. The operation of the entire device can be roughly divided into 1) reset phase, 2) state set phase, and 3
) path search phase, 4) traceback phase,
It is divided into 5) status resetting phase and 6) clearing phase. Each phase will be explained in order below.
3) The path search phase and subsequent steps are the same as those in the first embodiment described above, so detailed explanation will be omitted.

l) Status registers 801 to 801 are controlled by control signals from the reset phase control device.
803 and registers 804.820.

2) State set phase The state of the relevant cell is set to cell 1 in the state registers 801 to 803 in the same manner as in the case of FIG. 801 is the starting point, 80
2 indicates the end point, and 803 indicates whether or not it is a prohibited area.

Cells other than these are considered to be empty cells. During this time, the manual gate circuit 813 is closed by a signal from the control signal terminal 834.

3) Path search phase A signal from the control signal terminal 836 opens the gate of the p-OR gate circuit 807, and a signal from the control signal terminal 838 enables the register 802 to be written.

Additionally, gate circuit 814 is opened.

Depending on the contents of the status registers 801 to 803 set in the status set phase of 2) above.

Each cell in the play section functions differently. When the contents of the status register 803 are at logic level n I I+,
That is, if the cell in question is in the prohibited area, the input gate circuit 813 is closed and no signal is transmitted to the cell in question. 1 when the contents of the status register 801 are at logic level I11''
1, if the cell is the starting point, the selector circuit 816 selects the output of the status register 801 and sets it to 0.
■Kuge I/Circuit 808 and 809 logic level l
+1" is output. The selector circuit 817 first selects the left and right [
Upper F]] direction data transfer path, that is, OR gate circuit 8
09 (808). The programmable data transfer circuit 821 transmits signals only in the left and right (up and down) directions. Therefore, the output terminals 828, 829 (82f
], 827), a logic level n I I+ is output, and a logic level 1lON is output to the output terminals 826, 827 C828, 829]. Next, the status register 802
When the content of the cell is at logic level "11", that is, the cell is the end point, or the status register 801, 80
The contents of 2 and 803 are both at logic level ll011.
When , that is, when the cell in question is an empty cell,
The direction in which the input signal reached the cell most quickly (in this case, either the left or right [up or down] direction) is sent to the encoder 819.
At the same time, the selector circuit 817 selects the signals from the cells in the left and right [up and down] directions, that is, the output of the OR gate circuit 809 (808),
The programmable data transfer circuit 821 transmits signals only in the left and right (up and down) directions. ° i.e. output terminal 828.8
29 (826, 827) at logic level 11'', output terminal 7826.827 (C828, 829) at logic level 11''
ol+ is output and transmitted to the left and right (top and bottom) cells.

Here, the direction once stored in the register 820 does not change until the clear phase. Furthermore, it is impossible for both status registers 801 and 802 to be at logic level I11'', that is, the cell in question is both the starting point and the ending point.From the above, the signal is transmitted from the starting point in the left and right (up and down) directions, and when the signal reaches For each cell, the direction that reached the cell fastest was stored in register 820.

Next, the selector 817 selects the data transfer path in the ``2-down-1-left-right'' direction, that is, the output of the off-gate circuit 808C809). Programmable data transfer circuit 821
transmits signals only in the vertical (left and right) directions.

Therefore, if the output of the OR'y'-to circuits 808 and 809 is 11111, that is, the cell is the starting point, or the signal (ζ1 is already the starting point!) is sent to the cell. Reach register 820 and input Vc state J
' Only from the cell that is connected bc to the cell in the -1-'F' [: left and right] direction #aLQ::Δchild 826
．． 827 C828, 829:] logic level II only
I Ir is output Jz, output: JJ Ir1-r828
, 829 [826, 827] Ic ti logical level 1
1o'1 talent.

From the starting point or (d) from the starting point, from the cell where the irises have reached, fi-i "j"
is transmitted, and in each cell where the new signal reaches, the signal reaches the cell most quickly and is stored in the force direction register 820. ]・Similarly, Ir right [”21・], soil 1・[
The signal is transmitted alternately in the left and right directions, and the status register 80
This process is repeated until the signal from the starting point is transmitted to the cell where logic level 1111 is 2, that is, the ending point. Note that data transfer starts from the left and right directions here, but - as shown in [].
11: The same applies from the direction.

When the signal from the starting point reaches the ending point, the OR gate circuit 8
08,' OR gate circuit 80 via the output of 809
7 rises to logic level Jll, status register 80
2, that is, AND gate circuit 812
The output becomes logic level II-III, and this phase ends. In addition, if the route does not exist or has many unnecessary twists and turns, this phase will be forcibly terminated with (No. 6) from the control device. If it is not possible, this phase is ended and the process proceeds to Clear Noise.Also, as in the case of the first embodiment, the starting point cell may be single or plural.

FIG. 9 shows an example of the state in the cell 401 of the array section 303 after the pass search steps are completed among the seven steps for route determination in another embodiment of the cell of the device of the present invention, where S is the starting point and T is the starting point. indicates the end point, and ω) indicates the prohibited area. Further, the arrow indicates the state of the register 820 in each cell, that is, the direction in which the signal from the starting point reached the cell most quickly.

4) “Trace the signal from the grasshopper phase control signal terminal 837” to the ligating circuit 81
The gate No. 4 is closed, and the selector circuit 816 selects the output of the status register 802 based on the control signal χ1.1 signal 835. When the contents of the state register 802 of the cell are at the logic level -+1, that is, when the cell is at the end point, the outputs of the OR gate circuits 809 and 810 are both at the logic level 1lIII. Selector circuit 8] 7 R
, the logic level "1" which is the eleventh logic of the OR gate circuits 808 and 809, that is, the output of the OR gate circuit 810.
Select 111. Programmable data transfer path 821
is stored in the register 820 (F
Transfer number j. Status register 801.80 of the cell
If the contents of 2°803 are all at logic level I+011, that is, if jJJ is an empty cell, the selector circuit 817 selects the logic level I+011. The output of the OR gate circuit 810 is selected, and the programmable data transfer circuit 821 transmits the signal only in the direction stored in the register 820. Since the cell that reached the monk is a route, it is stored in the register 804 through the OR gate circuit 807. This phase is performed asynchronously to the clock and continues at the trench where the signal from the end point reaches the start point. Status register 801
Cell 7', whose contents are at logic level J+, that is, the starting point, is programmed by the signal 801, and the programmatic data transfer circuit 821 does not transmit a signal in either direction.

When the signal from the end point reaches the corresponding cell, it passes through the OII r-to circuits 808 and 809 and performs a logical product (AND) of the output of the OR gate circuit 807 and the output of the status register 801.
The output of the gate circuit 811 becomes logic level II 11, and this phase ends.

This means that the route has been determined. Further, when the content of the status register 803 of the cell is at logic level "1", that is, when the cell is in a prohibited passage area, the gate of the input gate circuit 813 is closed and the input signal is not transmitted in any direction.

5) Status resetting phase From this phase onwards, the processing is synchronized with the clock again. This phase is similar to the first embodiment, and when the path to be sought is a two-terminal net, the selector circuit 815 outputs the connection ff1 (route) from the control signal terminal 833 (i) via the shift register 845. The information is sent from the terminal 844 to the control device, and the route is registered as a prohibited area for the next network to be connected.

That is, the logical sum of the result and the status register 80 is stored in the status register 803 again. If the route that can be requested after this to proceed to the clear phase is a three-terminal net or more, the route between the first two terminals is re-registered as the starting point. That is, the output of the selector circuit 815 is transferred to the status register 801 by transmission from the control signal terminal 833.
Store in. After this, the process returns to the bus search phase and determines the route to the next terminal. This is repeated until all terminal wiring is completed, and the route is output to the control device in the same way as in the case of the 2-terminal connection. Since the route already in progress is registered as the starting point, the register 80 is registered by the OR gate circuit 805.
4 and the status register 801 and outputs the result.

6) Clear Phase Clear registers 804.820 and status registers 801.802 by control signals for next net routing. After this, proceed to the state setting phase (2).

Second, by repeating each phase, wiring with multiple terminals and multiple nets is possible.

In this embodiment, if a route between two points exists, it is always found, and the route with the least number of bends is found.

(Effects) As explained in Section 2, the present invention performs data transfer between cells arranged in an array asynchronously with the tarokk, and furthermore, determines the data transfer direction of each cell in a process synchronized with the clock. Since decisions are made asynchronously without performing any process, processing can be performed much faster than the synchronous type, so it can be used, for example, in wiring design for printed circuit boards and LSIs to perform complex processing. Wiring routes can be determined in an extremely short time without having to do so. Moreover, since the /...-ware structure is simple, it has advantages such as being suitable for high speed and large-scale implementation by LSI.

[Brief explanation of the drawing]

Fig. 1 is an explanatory diagram showing the correspondence between a conventional wiring grid and an arrangement, Fig. 2 is an explanatory diagram of a conventional route searching method using line segments, and Fig. 3 is an explanatory diagram showing the configuration of the first embodiment of the present invention. Figure shown, 4th
5 is a diagram showing an example of the structure of the array section, FIG. 5 is a diagram showing an example of the structure of the cell, FIG. 6 is a diagram showing an example of signal propagation from the starting point after a unit time has elapsed in the play section, 7 is a diagram showing an example of the state of each cell in the array section at the end of the bus search phase of the device of the present invention, FIG. 8 is a diagram showing the configuration of another embodiment of the cell used in the present invention, and FIG. 9 7 is a diagram showing an example of the state of each cell after the path search phase is completed in each phase of route determination in another embodiment of the cell of the device of the present invention. FIG. 101... Wiring grid, 102...
・Array, 301...Interface section with host computer, 3゛02... Control m+Irτl
i, 303...F'shii)
τ15/101...Cell, 402...
...Data transfer path, 403...
Control line, 404...Signal terminal, 405-
......X direction input line, 406...
・Y direction input line, 407...X decoding circuit, 408...Pa°°y decoding circuit, 409
．． /110 Input terminal, 501 to 50
3...Status register,'504,51
7°°゛・・・Register, 505-509...
...OR gate circuit, 510, 511...
...AND gate circuit, 512...
・Input gate circuit, 513, 514...
Selector circuit, 515...Arbiter,
516 ...... Enco 1', 518°°°
°゛°Purflocramable data transfer circuit, 519-52
2... Input signal terminal, 523-526.
...Output terminal, 527, 528...
・Signal input terminal from X+Y decoder, 529 to 53
6... Control signal input terminal, 537-539
・・・・・・・・・Output terminal, 540・・・・・・・・・
・Shift register, 57Il...Cell selection circuit, 801-803...Status register, 804, 820...Register, 805-
810・・・・・・OR gate circuit, 811.8
12......AND gate circuit, 813...
-...Manual gate circuit, 814...
...Gate circuit, 815-817 ...Selector circuit, 818...7-Hitter, 8
1.9... Encoder, 821...
...Programmable data transfer ports, 822-825
......Input terminal, 826-829...
...Output terminal, 830.831...
Signal input terminals, 832-841...°゛゛°°control signal terminals, 842-844...Output terminals to control device, 845...Shift register 1 ．． -846...Cell selection circuit, A, S ・
・・・・・・・・・Start point, B, T ・・・・・・・・・
End point, (B)... No-passing area, C, D.
・・・・・・Fold points, L1 to L4・・・・・・・
・Multiple bit code, to-t4... Line segment. Patent applicant Nippon Telegraph and Telephone Public Corporation Figure 1 02 Figure 2 [ Figure 3 Figure 4 Figure 5 Continued from page 1 [Phase] Inventor Hitoshi Kitazawa 183 Ono, Atsugi City
Nippon Telegraph and Telephone Public Corporation Atsugi Telecommunications Research within Hata Estate

Claims (1)

[Claims] In a data processing device including a plurality of cells having the same hardware configuration and having adjacent connections to each other, the cell is configured to determine from which adjacent cell the first input signal from the adjacent cell came. a circuit for identifying whether there is an asynchronous VC;
Next using that identification result. 1. A parallel data processing device comprising a circuit for controlling whether to selectively receive some of input signals from adjacent cells or selectively output to some of adjacent cells.