JPH10105530A - Computer connection device - Google Patents

Abstract

(57) [Summary] In a large-scale parallel computer connection device, a network in which a race condition is unlikely to occur when transmission destination addresses are different is configured with a small physical quantity. A computer connecting device that connects n1.times.n2.times.n3.times.n4.times..times.nN processors by an N-dimensional crossbar network to form a parallel computer. It is characterized in that it is realized hierarchically by providing ports that detour to dimensions and input ports for those that detour from other dimensions. FIG. 1 shows a two-dimensional state.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a large-scale parallel computer connection device, and more particularly to a computer connection device in which a network in which a race condition does not occur when transmission destination addresses are different is formed with a small physical quantity.

[0002]

2. Description of the Related Art As shown in FIG. 8A, a number of processors PE0 to PEN-1 are connected to a one-dimensional crossbar network X.
B so that the communication with different destinations does not conflict with each other, this crossbar network XB is
As shown in (B), the input side line is composed of N lines, the output side line is composed of N lines, and a switching element (not shown) is provided at the intersection of each input side line and output side line. is required.

For this reason, it is necessary to construct this crossbar network with a network quantity proportional to the square of the number of processors.
A large-capacity network according to the power is required. Therefore, the number of connectable processors is limited, and there is a problem as a switching network for a large-scale parallel computer.

In order to improve this, as shown in FIG.
A dimensional crossbar network is configured. this is,
For example, when configuring a network between 256 processors, the network is composed of, for example, PE000 to PE063 and PE100 to PE64 configured with 64 processors per group.
PE163, PE200-PE263, PE300-P
The processors PE000 to PE063 are divided into four groups E363 and each processor has three input / output terminals, and the processors PE000 to PE063 are crossbar switches XXB.
0, and the processors PE100 to PE163 are connected to the crossbar switch XXB1.
To PE263 are connected to the crossbar switch XXB2, and the processors PE300 to PE363 are connected to the crossbar switch X.
Connect to XB3.

The processors PE000, PE10
0, PE200, PE300 crossbar switch YXB
0, and the processors PE110, PE101, PE
201 and PE301 are connected to the crossbar switch YXB1, and the processors PE063, PE163, and PE2 are similarly connected.
63 and the PE 363 are connected to the crossbar switch XB63.

Thus, four crossbar switches XXB0, XXB1, XXB having 64 input / output ports are provided.
A network that connects 256 processors in parallel can be configured by 64 crossbar switches YXB0, YXB1,..., YXB63 having 2, XXB3 and 4 input / output ports.

[0007]

The two-dimensional crossbar network shown in FIG. 9 can greatly reduce the amount of hardware of the network as compared with the one-dimensional crossbar network shown in FIG. Communication waiting is likely to occur depending on the combination of the data transfer destinations.

In FIG. 9, when operating with an algorithm for transferring data from the Y direction, the processor PE000
→ Communication of PE201 and processor PE200 → PE2
The 63 communications compete. That is, the processor PE000 →
In the case of communication of the PE 201, communication is performed through the following route.

[0009] PE000 (SW) → YXB0 → PE20
0 (SW) → XXB2 → PE201 (SW) In the case of communication of the processor PE200 → PE263,
Communication is performed by the following route.

[0010] Therefore, in these cases, a conflict occurs on the crossbar switch XXB2.

In order to avoid conflict, there is a method of dynamically selecting which of the X direction and the Y direction should be transferred first. However, a plurality of parallel programs run simultaneously in the system. In such cases, there are difficult problems such as avoiding deadlock. Therefore, in general, the order of transfer directions is fixed, and a conflict occurs as described above.

When the address of the processor is represented by two-dimensional coordinates of X and Y, the following processors PE0 and P0
The communication between E1 and the communication between processors PE2 and PE3 are: Y ₀ = Y ₂ , X ₀で あ れ ば If X ₂ = X ₁ = X ₃ , X ₁ ≠
Even X ₃ to compete.

SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to provide an inter-processor connection device which enables communication between processors with a small amount of hardware and with low contention.

[0014]

In order to achieve the above object, according to the present invention, as shown in FIG.
0, XXB1, XXB2, XXB3, and row crossbar YX
B0, YXB1... YXB63 are provided. The conventional two-dimensional cross bus 29 has 64 lines in the row crossbar XXB0.
In contrast to the input 64 outputs, a crossbar switch X0 of 128 inputs and 64 outputs is provided. Of the 128 input terminals of the crossbar switch X0, 64 terminals are connected to the processors PE00-PE connected to the crossbar switch X0.
63 outputs an input buffer circuit I according to its destination.
The output from the column crossbars YXB0, YXB1,... YXB63 is input to the other 64 terminals.

The output of the crossbar switch X0 is input to the processors PE00 to PE63. Row crossbar X
The output of XB0 is input to processors PE00 to PE63. Outputs from the processors PE00 to PE63 are input to the column crossbars YXB0 to YXB63 via the input buffer circuits I0 to I63 according to the destination.

The row crossbar XXB1 is also provided with a crossbar switch X1 configured similarly to the crossbar switch X0. Outputs from the processors PE100 to PE163 are input to 64 input terminals of the crossbar switch X1 according to the destination. The signals are input via buffer circuits I100 to I163, and the other 64 input terminals are connected to a column crossbar YXB.
0, YXB1,..., YXB63. The output of the crossbar switch X1 is the processor P
These are input to E100 to PE163.

The output of the row crossbar XXB1 is input to the processors PE100 to PE163. Outputs from the processors PE100 to PE163 are input to the crossbars YXB0 to YXB63 via input buffer circuits I100 to I163 according to the destination.

Row crossbar XXB2, row crossbar XXB3
Are configured similarly to the row crossbar XXB0, and the processors PE200 to PE263, PE300 to PE300, respectively.
PE 363 is connected.

The column crossbar YXB00 is composed of a four-input four-output crossbar switch.
The data output from the XXB3 is sent to the row crossbars XXB0 to XXB3 according to the destination. The column crossbars YXB1 to YXB63 are the column crossbars YXB00.
And a crossbar switch with 4 inputs and 4 outputs.
The data output from the row crossbars XXB0 to XXB3 is transmitted to the row crossbars XXB0 to XXB3 according to the destination.

Now, as in FIG. 9, the processor PE0
A case where data is transferred from 0 to the processor PE201 and data is transferred from the processor PE200 to the processor PE263 will be described.

From processor PE00 to processor PE2
The data sent to 01 is sent to the column crossbar YXB0 after its destination is determined by the input buffer circuit I0 in the row crossbar XXB0. And the row crossbar YXB0
The destination is determined and sent to the row crossbar XXB2. The row crossbar XXB2 outputs this to the processor PE201 by the crossbar X2.

The data sent from the processor PE200 to the processor PE263 is sent to the crossbar X2 after its destination is determined by the input buffer circuit I200, and is sent to the processor PE263 by the crossbar X2.

In this manner, in the present invention, even if data transfer is delayed due to contention in FIG. 9, the present invention can be configured so as not to cause contention, so that data transfer can be performed promptly.

[0024]

FIG. 2 shows a first embodiment of the present invention.
6 will be described with reference to FIG. 2 shows a configuration of a processor, a description of a data transfer processing unit constituting the processor, and an example of an interface between processor networks. FIG. 3 shows a configuration diagram of a row crossbar, and FIG. 4 shows a configuration diagram of an input buffer circuit of the row crossbar. FIG. 5 shows a configuration diagram of a row crossbar switch circuit, and FIG. 6 shows a configuration diagram of a column crossbar.

In the figure, 1 is an instruction processing unit, 2 is a transfer processing unit, 3
Is a main storage device, 4-0 and 4-1 are transmission buffers, and 5-
0, 5-1 are reception buffers, 6 is a transmission control unit, 7 is a reception control unit, 8 is a main memory access control unit, and 10-0 to 10-
63 and 11-0 to 11-63 are input buffer circuits,
0-0 to 20-255 are switch circuits of 32 inputs and 1 output; 21-0 to 21-63 are switch circuits of 4 inputs and 1 output; 22-0 to 22-63 are output buffers; 40 is an input register; Transfer buffer, 42 is a buffer read register, 43 is a control circuit, 44 is a destination selection circuit,
45-1 to 45-64 are output registers, 50 is a selector, 51 is a priority control circuit, 52-1 to 52-32 are input request flag holding units, 53 is a selection control circuit, 54-1 to 5-5
4-32 is an input transfer flag holding unit.

As shown in FIG. 2A, the processor PE
Comprises an instruction processing unit 1, a transfer processing unit 2, and a main storage device 3. The instruction processing unit 1 reads an instruction word (program) stored in the main storage device 3 and performs processing according to the instruction. Then, it instructs the transfer processing unit 2 to transfer data according to a program command. This instruction includes the destination processor number, the transfer source main storage address of the transfer data, the data length, the transfer destination main storage address on the destination processor, and the like.

The transfer processing unit 2 has a transmitting unit for transmitting data to the network and a receiving unit for receiving data from the network. The transmitting unit transmits data to the network according to the instruction of the instruction processing unit 1. The data to be transmitted to the network or the like includes control information including a destination processor number, an address where data is to be stored in the destination processor, a data length, and the like. And a body part which is a data body read from the main storage device 3. The receiving unit stores the packet received from the network at the address in the main memory specified in the header of the packet.

The main memory 3 stores programs to be executed by the instruction processing unit 1 in the processor PE, data used for arithmetic processing, and the like. The transfer processing unit 2
Has a block configuration as shown in FIG. That is, it includes a pair of transmission buffers 4-0 and 4-1, a pair of reception buffers 5-0 and 5-1, a transmission control unit 6, a reception control unit 7, a main memory access control unit 8, and the like. .

The transmission buffers 4-0 and 4-1 store data of packets to be transmitted alternately. Transmission buffer 4-
0 while the data stored in the transmission buffer 4-1 is stored in the transmission buffer 4-1 while the data stored in the transmission buffer 4-1 is being transmitted. Stores data to be transmitted. Control information is created and transmitted as header portions in data transmitted to the network. Thereafter, the data fetched from the main storage device 3 is temporarily stored in the transmission buffers 4-0 and 4-1 alternately until the data fetched from the main storage device 3 is transmitted to the network according to the instruction of the instruction processing unit 1.

The receiving buffers 5-0 and 5-1 store data received from the network alternately. When the data stored in the reception buffer 5-0 is sent to the main storage device 3, the reception data is stored in the reception buffer 5-1.
The data stored in the reception buffer 5-1 is stored in the main storage device 3.
, The received data is stored in the reception buffer 5-0. From the header received from the network, address information for storing the data body (body part) is extracted. Then, based on this, body data received from the network is stored in a temporary reception buffer and then stored at a predetermined address in the main storage device.

The transmission control unit 6 controls the transmission of data to the network, and includes a signal (buffer full signal) indicating the state of the reception buffer on the network device side transmitted from the network and a main memory access control unit. A signal indicating that data has been stored in the buffer sent from 8 manages how many unsent data are currently in the buffer, and if these can be sent to the network, an instruction to send to the buffer unit is sent. I do.

The reception control section 7 controls data reception from the network, and sends a signal indicating the buffer status to the network when the reception buffer is full. It also manages how many untransmitted data are present in the buffer and processes them so that they are sequentially transmitted to the main storage.

The main memory access control unit 8 controls reading of data to be transmitted to the network from the main memory and control of writing of data received from the network to the main memory. A main memory address to be accessed is sequentially generated from a head address and a data length of a data body (body part) specified in a header of a packet in a packet received from the network or a transmission instruction from the instruction processing unit 1. It issues an access request to the access control unit 8. Based on a memory control signal such as an address of the main memory access control unit 8, data is sent to the transmission buffers 4-0 and 4-1 or the reception buffer 5
Data is stored from −0, 5-1.

The interface between the processor and the network will be described with reference to FIG. FIG. 2 (C)
In the above, Data is a data body to be transmitted, and is composed of a group of signal lines of a plurality of bits. It may include a parity bit for data error checking. Data-Va
The lid indicates that the transmission data is valid when this signal is on. Data-End is turned on when the last data of the packet is transmitted. B
The signal “offer-Full” is a signal for requesting a stop of data transmission because the reception buffer is full. It is also possible to use a Data-Req signal instead of this signal.

Next, the row crossbar XXB shown in FIG. 1 will be described with reference to FIG. The row crossbar XXB is shown in FIG.
As shown in (A) of the row crossbar XXB0, a crossbar switch X0 having 128 inputs and 64 outputs, input buffer circuits 10-0 to 10-63, and input buffer circuits 11-0 to 11-63 are provided.

The input buffer circuits 10-0 to 10-63 have one input and 65 outputs, and the input buffer circuits 11-0 to 11-1-1.
1-63 is one input and 64 outputs. This input buffer circuit will be described later with reference to FIG.

The crossbar switch X0 is a 32-input / 1-output first switch circuit 20-0-20 shown in FIG.
-255, 4-input / 1-output second switch circuit 21-
0-21-63 and output buffers 22-0-22-63
Having.

The input buffer circuit 11-0 determines whether the data transmitted from the processor PE00 is to be sent to any of the processors connected to the crossbar switch X0 or to the row crossbar XXB0. Since it is output in response, it has 65 outputs.

The output of the first switch circuit 20-0 is the second switch circuit 2 which sends an output to the processor PE0.
1-0. This first switch circuit 20-0
To the processor PE0 from the input buffer circuits 10-1 to 10-31.

The output of the first switch circuit 20-1 is the second switch circuit 2 which sends an output to the processor PE1.
1-1 is input. This first switch circuit 20-1
To the processor PE1 from the input buffer circuits 10-0 to 10-31.

First switch circuit 20-2 (not shown)
Is input to a second switch circuit 21-2 that sends an output to the processor PE2. The first switch circuit 20-2 includes input buffer circuits 10-0 to 10-3.
1 to the processor PE2.

The first switch circuit 20-3 to the first switch circuit 20-63 are similarly configured, and each output is a second switch circuit 21-3 for sending an output to the processors PE3 to PE63. To 21-63. The first switch circuits 20-3 to 20-3
Input buffer circuits 10-0 to 10-31 are provided in 20-63.
Is transmitted to the processors PE3 to PE63.

As described above, the first switch circuits 20-0 to 20-0
20-63 includes input buffer circuits 10-0 to 10-3.
1 to 3 for processors PE0 to PE63, respectively
2 are applied and output to the second switch circuits 21-0 to 21-63, respectively.

The output of the first switch circuit 20-64 is input to a second switch circuit 21-0 which sends an output to the processor PE0. This first switch circuit 2
Input buffer circuits 10-31 (not shown) are provided for 0-64.
Data from the processor PE0 to the processor PE0 is input.

The output of the first switch circuit 20-65 is input to a second switch circuit 21-1 which sends an output to the processor PE1. This first switch circuit 20-
Data to the processor PE1 from the input buffer circuits 10-31 to 10-63 is input to 65.

The output of the first switch circuit 20-66 is input to a second switch circuit 21-2 which sends an output to the processor PE2. This first switch circuit 20-
Data to the processor PE2 from the input buffers 10-31 to 10-63 is input to 66.

The output of the first switch circuit 20-127 is input to a second switch circuit 21-63 which sends an output to the processor PE63. The first switch circuits 20-127 have input buffers 10-31 to 10-.
Data from processor 63 to processor PE63 is input.

As described above, the first switch circuit 20-6
4 to 20-127, the input buffer circuit 10-32
(Not shown) Processors P from 10 to 63 respectively
32 inputs to E0 to PE63 are applied, and the second switch circuits 21-0 to 21-
63 is output.

The output of the first switch circuit 20-128 is input to a second switch circuit 21-0 which sends an output to the processor PE0. This first switch circuit 20
−128 has input buffer circuits 11-0 to 11-31.
(Not shown) to the processor PE0.

The output of the first switch circuit 20-129 (not shown) is the second output for sending the output to the processor PE1.
Is input to the switch circuit 21-1. This first switch circuit 20-129 has an input buffer circuit 11-0.
To 11-31 to processor PE1.

As described above, the first switch circuit 20-1
28 to 20-191 (not shown) include processors PE from input buffer circuits 11-0 to 11-31, respectively.
The second switch circuits 21-0 to 21-6 are configured so that 32 inputs to 0 to PE 63 are applied.
3 is output.

The output of the first switch circuit 20-192 is input to the second switch circuit 21-0 which sends the output to the processor PE0. This first switch circuit 20
Data to the processor PE0 from the input buffer circuits 11-32 (not shown) to 11-63 is input to -192.

The output of the first switch circuit 20-193 (not shown) is the second output for sending the output to the processor PE1.
Is input to the switch circuit 21-1. The first switch circuit 193 includes input buffer circuits 11-32 to 1
A signal from 1-63 to processor PE1 is input.

As described above, the first switch circuit 20-1
92 to 20-255, input buffer circuits 11-32
Processors PE0 to PE6 from 11 to 63 respectively
It is configured such that 32 inputs to three are applied, and are output to the second switch circuits 21-0 to 21-63, respectively.

The second switch circuit 21-0 has first switch circuits 20-0, 20-64, 20-128, 20
Four data from -192 are input. The second switch circuit 21-1 has the first switch circuit 20-
1, 20-65, 20-129 (not shown), 20-1
The four data from 93 (not shown) are input. Similarly, four data are input to the second switch circuits 21-2 to 21-63.

The output of the second switch circuit 21-0 is sent to the processor PE0 via the output buffer 22-0.
The output of the second switch circuit 21-1 is sent to the processor PE1 via the output buffer 22-1. Outputs of the second switches 21-2 to 21-63 are similarly sent to the processors PE2 to PE63 via the output buffers 22-2 to 22-63.

In the input buffer circuit 10-0, the destination of the input data is the row crossbar Y except for the processors PE0 to PE63 connected to the column crossbar XXB0.
An output terminal for transmitting to XB00 is provided. Similarly, in the input buffer circuits 10-1 to 10-63, the destination of the input data is the data other than the processors PE0 to PE63 connected to the column crossbar XXB0.
An output terminal for transmitting to B1 to YXB63 is provided.

Next, the configuration of the input buffer circuit will be described with reference to FIG. Since each input buffer circuit has substantially the same configuration, the input buffer circuit 10-0 will be representatively described. FIG. 4A is a configuration diagram of the input buffer circuit 10-0, and FIG. 4B is a configuration diagram of the control circuit.

The input buffer circuit 10-0 has the structure shown in FIG.
, An input register 40, a transfer buffer 41,
Buffer read register 42, control circuit 43, destination selection circuit 44, output registers 45-1, 45-2, 45-
3, 45-4... 45-64.

The input register 40 receives the transfer data from the transfer processing unit 2 of the processor. The transfer buffer 41 stores the transfer data received from the processor by the input register 40.

The buffer read register 42 reads data from the transfer buffer 41 and sends it to the control circuit 43 and the destination selection circuit 44. The control circuit 43 reads the destination information included in the head of the packet to be transferred, and according to the destination information, the destination selection circuit 4
4 includes a destination decoder 43-0 and a destination register 43-1. Destination decoder 43-0
Then, the destination information included at the head of the packet to be transferred is read and held in the destination register 43-1. Then, the destination selection circuit 44 is controlled so as to transmit the transfer packet to the output register 45 corresponding to the destination. That is, a path in the destination selection circuit 44 from the buffer read register 42 to the output register 45, that is, a switch SW (FIG. 3) to be opened is selected from the buffer read register 42, the selected path is made valid, and the transfer is performed. Enable the request signal (included in the data transfer signal line to SW). When a transmission permission signal (included in the data transfer signal line to the SW) is received from the switch SW, the data is sequentially read from the transfer buffer and the buffer read register 4
2. Control the data to be sent to the switch SW via the destination selection circuit 44, and selectively perform data transfer to the output register 45 connected to the switch.

For example, the processor PE
If it is determined that the data should be sent to 0, the destination selection circuit 4
4 to the output register 45-0 and the processor PE
Output register 4 when it is determined that
Sent to 5-1. When it is determined that the data should be sent to the column crossbar YXB, the data is sent to the output registers 45-64.

The input buffer circuits 11-0 to 11-63 shown in FIG. 3B are configured in substantially the same manner as the input buffer circuits shown in FIG. 4, but the output of the destination selection circuit 44 is applied to the column scrobar YXB. No output. That is, the output of the destination selection circuit 44 is output to the output registers 45-0 to 45-4 to which the data addressed to the processors PE0 to PE63 are respectively input.
5-63 and is not output to the column crossbar YXB.

Next, the switch circuit of the row crossbar will be described with reference to FIG. This switch circuit is a switch circuit of 32 inputs and 1 output and has the same configuration.
A representative description will be given using the switch circuit 20-0. FIG.
As shown in (A), the switch circuit 20-0 is connected to the selector 5
0 and a priority control circuit 51. Selector 5
0 is the input buffer circuit 10-0, 10-1 ... 10
-31 (not shown) is input,
Based on a path selection signal transmitted from the priority control circuit 51, a path between any one input and output is enabled,
As a result, one of them is selected, and the subsequent switch circuit 2 is selected.
Send to 1-0.

The priority control circuit 51 includes, as shown in FIG. 5B, input request flags 52-1, 52-2,.
, A selection control circuit 53 for selectively outputting a plurality of data according to, for example, round robin logic, and transfer flags 54-1, 5 set according to the selection result.
4-2... 54-32.

Therefore, when a plurality of inputs are transmitted to the selector 50, the input request flags 52-1 to 52-2 are correspondingly transmitted.
Since a part of −32 is selectively turned on, the selection control circuit 53 selects one of them based on, for example, a round robin method and turns on one of the transfer flags 54-1 to 54-32 accordingly. Thus, a selector selection signal, that is, a path selection signal is generated and output to the selector 50. The selector 50 sends the input data selected in response to this to the switch circuit 21 at the subsequent stage.

The switch circuit 21 has the same configuration as the switch circuit 20 shown in FIG. 5, but differs only in that it has four inputs and one output, and a detailed description is omitted. The selector receives data from the preceding switch circuit and outputs the data to the output buffer circuit. In the switch circuit 21, the request flag is set by a transfer request from the preceding switch circuit.

The switch circuit of the column crossbar will be described with reference to FIG. The switch circuits of the column crossbar include input buffer circuits 60-0 to 60-3 and switch circuits 61-0 to 61-0.
61-3 and output buffers 62-0 to 62-3.

The input buffer circuit 60-0 has the same configuration as the input buffer circuit 10, but differs in that there are four outputs. The data transmitted from the row crossbar XXB0 is input to the input buffer circuit 60-0, and is selectively output to the switch circuits 61-0 to 61-3 according to the destination of the data. The input buffer circuit 60-1 is connected to the row crossbar X
The data transmitted from XB1 is input and selectively output to switch circuits 61-0 to 61-3 according to the destination of the data. The input buffer circuits 60-2 and 60-3 have the same configuration, receive data sent from the row crossbars XXB2 and XXB3, and select and output the data to the switch circuits 61-0 to 61-3 according to the destination of the data. You.

The switch circuit 61-0 includes the switch circuit 2
1-0, the input buffer circuit is constituted by a four-input one-output switch circuit. The data transmitted from the input buffer circuits 60-0 to 60-3 is output to the output buffer 62 in a round-robin manner, for example, according to the destination. −0 and sent to the row crossbar XXB0.

Each of the switch circuits 61-1 to 61-3 is also constituted by a four-input one-output switch circuit, and transfers the data transmitted from the input buffer circuits 60-0 to 60-3 to their destinations. , And outputs the data to the output buffers 62-1 to 62-3, for example, in a round-robin manner, and sends them to the row crossbars XXB1 to XXB3.

The operation of the present invention will be described for the case where the case of transmitting data from the processor PP00 to the processor PE201 and transmitting data to the processor PE200 to the processor PE263 in FIG. 1 are performed simultaneously.

When transmitting data from the processor PE00 to the PE201, the processor PE00 first outputs data addressed to the PE201 to the row crossbar XXB0. The data from the processor PE00 is shown in FIG.
4B, the address is decoded by the control circuit 43 shown in FIG. 4A and sent to the output register 45-64 from the destination selection circuit 44, and is sent to the column crossbar YXB0. Sent out. In the column crossbar YXB0, the input buffer circuit 60-0 receives this, determines that it should be transmitted from its destination to the row crossbar XXB2, and transmits the received data to the switch circuit 61-2. The switch circuit 61-2 sends this to the row crossbar XXB2 via the output buffer 62-2.

In the row crossbar XXB2, the column crossbar YX
When this data is received from B0, the input buffer circuit (corresponding to 11-0 in FIG. 3) receives this data, decodes its destination, and determines that it should be sent to the processor PE201. The data is sent to a switch circuit 20-129 (not shown) for sending data to the processor PE201. The switch circuit 20-129 outputs this to an output buffer (FIG. 3) for sending data to the processor PE201.
Of the switch circuit (21-2-1) corresponding to
1), and the data is sent to the processor PE201. In this way, data is transmitted from the processor PE00 to the processor PE201.

When sending data from the processor PE200 to the PE263, the processor PE200 first outputs data addressed to the PE263 to the row crossbar XXB2. The data addressed to the processor PE 263 is shown in FIG.
Of the buffer circuit (corresponding to 10-0) is decoded, it is determined that the data is to be transmitted to the processor PE 263, and a switch circuit (20-63 not shown) for transmitting data to the processor PE 263 is determined. ). Then, data is sent from this switch circuit to the switch circuit (corresponding to 21-63), and is sent to the processor P via an output buffer (corresponding to 22-63).
The data is transmitted to E263. When data is sent from the processor PE200 to the PE 263 in this manner, the row crossbar XX to which the processor PE200 is connected is connected.
Data is transmitted only by B2.

Therefore, in these cases, since no conflict occurs, the apparatus does not enter the waiting state as shown in FIG. Next, a description will be given based on an example in which a large number of processors are connected and arranged by a three-dimensional crossbar with reference to FIG. FIG. 7 shows a case where 256 processors of one group are connected to 1024 processors in four groups.

The first group 100 includes the processor PE0
-63 is connected to the first crossbar XXB0, and the first crossbar XXB1 is connected to the processors PE64 to 127.
, A first crossbar XXB2 to which the processors PE128 to 191 are connected, a first crossbar XXB3 to which the processors PE192 to 255 are connected, and a second crossbar 200
To 263.

The first crossbar XXB0 has the same configuration as the crossbar XXB0 shown in FIG. 1 and includes a 128-input / 64-output crossbar switch, an input buffer circuit and the like. The first crossbars XXB1 to XXB3 are similarly configured.

The second crossbar 200 is the first crossbar XX
8 inputs and 4 outputs crossbar switch 30 for input from B0
An input buffer circuit 200-0 having a destination control function for selecting whether to transmit the data to 0-0 or to a crossbar ZXB0 constituting a third crossbar 400 described later;
Whether the input from the crossbar XXB1 is sent to the 8-input 4-output crossbar switch 300-0 or the third crossbar 400
And an input buffer circuit 200-1 for selecting whether or not to transmit the signal to the crossbar ZXB1 forming the first crossbar XXB2.
Input from an 8-input 4-output crossbar switch 300-
An input buffer circuit 200-2 for selecting whether to transmit the signal to 0 or a crossbar ZXB2 (not shown) constituting the third crossbar 400, and an 8-input 4-output crossbar switch 300- for input from the first crossbar XXB3. 0 or the crossbar Z forming the third crossbar 400
An XB3 (not shown) includes an input buffer circuit 200-3 for selecting whether to transmit the signal to an XB3, and an eight-input four-output crossbar switch 300-0.

The 8-input 4-output crossbar switch 300
−0 is the first crossbar XXB0, XXB1, XXB
2. In addition to the data input from XXB3,
XB0, ZXB1, ZXB2 (not shown), ZXB3
Data (not shown) are input, and are selectively output to the first crossbars XXB0 to XXB3. The second crossbars 200-1 to 200-63 are also the second crossbars.
The configuration is the same as that of the crossbar 200-0.

The second group 101 includes the first group 10
0 and the processor PE2
It has four 128-input, 64-output first crossbars 56 to 511 connected to each other, and 64 second crossbars having 8-input, 4-output crossbar switches and input buffer circuits.

The third group 102 is similarly configured in the same manner as the first group 100. The third group 102 includes 64 processors PE512 to 767 each connected to 64 processors.
64 including four first crossbars having 28 inputs and 64 outputs, a crossbar switch having 8 inputs and 4 outputs, and an input buffer circuit.
Second crossbars.

The fourth group 103 is also configured in the same manner as the first group 100, and includes four 128-input / 64-output first crossbars to which 64 processors PE 768 to 1023 are connected, respectively. 8 inputs 4
6 having an output crossbar switch and an input buffer circuit
It has four second crossbars.

The third crossbar 400 has four inputs and four inputs.
256 crossbars Z with output crossbar switches
XB0 to ZXB255. These crossbars ZXB0 to ZXB255 are connected to the second
Connected to crossbar.

That is, the four output lines output from the second crossbar 200 are respectively crossbars ZXB0 (ZX is omitted in the display of the output lines in FIG. 7 and displayed as B0).
Output to ZXB1, ZXB2, ZXB3. Also the second
The four output lines output from the crossbar 201 are output to the crossbars B4, B5, B6, and B7, respectively. The four output lines output from the second crossbar 201 are respectively a crossbar ZXB4 (ZX is omitted in the display of the output lines in FIG. 7 and is indicated as B4), ZXB5, ZXB6,
Output to ZXB7. Other second crossbars 202 to 26
The same applies to 2 (not shown). And the second crossbar 26
Each of the four output lines output from 3 is a crossbar ZX
B252-255.

The input lines for inputting data to the second crossbar 200 are input from the crossbars ZXB0 (also indicated as B0 in FIG. 7), ZXB1, ZXB2, and ZXB3. Input lines for inputting data to the second crossbar 201 are input from the crossbars ZXB4 to ZXB7. An input line for inputting data to the second crossbar 263 is input from the crossbars ZXB252 to 255.

The second groups 101, 102 and 103 also have crossbars ZXB 0, ZX
B1 to ZXB255. In FIG. 7, for example, the processors PE0 to PE102
When data is transmitted to the third crossbar 200, the data output from the processor PE0 is input to the first crossbar XXB0, where the destination is determined and transmitted to the second crossbar 200.

In the second crossbar 200, the input buffer circuit 200-0 receives this signal and sends the third crossbar 4 from its destination.
This is sent to the crossbar ZXB0 constituting 00. The crossbar ZXB0 determines that the data should be transmitted from the destination to the second group 103 and determines that it should be transmitted to the second crossbar ZXB0 of the second group 103 (see FIG. 7).
200 equivalent). As a result, the 8-input / 4-output crossbar switch existing in the second crossbar of the second group 103 determines its destination, and
Is transmitted to the connected crossbar (corresponding to XXB3 in FIG. 7), whereby the processor PE1023 receives the data from the processor PE0.

FIG. 1 describes a two-dimensional crossbar network, and FIG. 7 describes a three-dimensional crossbar network. However, the present invention is not limited to these, and a multidimensional one may be constructed. be able to.

Further, in the present invention, in a two-dimensional crossbar network, the number of processors connected to the row crossbar and the capacity of the crossbar switch constituting the row crossbar are not limited to these embodiments. Of course, the capacity of the crossbar switch constituting the column crossbar is not limited to this.

Furthermore, the present invention is not limited to this embodiment also in a three-dimensional crossbar network. As is apparent from the above description, in the present invention, when data is transmitted to processors having different destinations by forming the crossbar in a hierarchical structure, occurrence of communication waiting can be extremely reduced. In the present invention, when n is the number of lower crossbars or processors connected to the crossbar, the configuration of the crossbar excluding the highest hierarchy is 2 × n inputs and n outputs. Thus, when the address of the processor is represented by coordinates, two communication PEs (X0, Y0, Z0, W0...) → PE (X1,
Y1, Z1, W1...) PE (X2, Y2, Z2, W2...) → PE (X3,
Y3, Z3, W3...) Is Z1 = Z3, Z1 ≠ Z3, Z1 、 Z3,
If Y1 ≠ Y3, there is no competition.

According to the embodiment of the present invention, since a large number of processors are connected by a two-dimensional crossbar network, the occurrence of a combination of transfer destinations which has conventionally been waiting for communication can be largely eliminated. .

According to the embodiment of the present invention, since a large number of processors are connected by the crossbar network having a three-dimensional configuration, a communication wait occurs even in a network to which a great number of processors are connected as compared with the case shown in FIG. Can be greatly improved.

According to the embodiment of the present invention, by providing this switch means, a crossbar network having a configuration of three or more dimensions can be formed. Can be greatly improved.

[0095]

According to the first aspect of the present invention,
Since a port that detours to another dimension and an input port that detours from another dimension are provided for each input of the crossbar network of each dimension, the occurrence of competition can be reduced by the crossbar network having a small physical quantity.

According to the second aspect of the present invention, the crossbar switch of dimension k (k = 1...
Since the configuration is made up of k inputs and nk outputs, the occurrence of contention can be reduced by a crossbar network having a small physical quantity.

[Brief description of the drawings]

FIG. 1 is a diagram showing an embodiment of the present invention.

FIG. 2 is a configuration example of a processor, a data transfer processing unit, and an interface between processor networks.

FIG. 3 is a configuration diagram of a row crossbar XXB.

FIG. 4 is a configuration diagram of an input buffer circuit of a row crossbar.

FIG. 5 is a configuration diagram of a switch circuit of a row crossbar.

FIG. 6 is a configuration diagram of a column crossbar YXB.

FIG. 7 is a diagram of a second embodiment of the present invention.

FIG. 8 is an explanatory view (part 1) of a conventional example.

FIG. 9 is an explanatory view (part 2) of a conventional example.

[Explanation of symbols]

 Reference Signs List 1 instruction processing unit 2 transfer processing unit 3 main storage device 4-0, 4-1 transmission buffer 5-0, 5-1 reception buffer 6 transmission control unit 7 reception control unit 8 main storage access control unit PE processor XXB row crossbar YXB Row crossbar

Claims (2)

[Claims] 1. A computer connection device comprising n1.times.n2.times.n3.times.n4.times..times.nN processors connected by an N-dimensional crossbar network to form a parallel computer. A computer connection device, which is realized in a hierarchical manner by providing a port detouring to another dimension and an input port for a detouring port from another dimension. 2. The computer connection device according to claim 1, wherein the crossbar switch of dimension k (k = 1... N-1) is composed of 2 × nk inputs and nk outputs.