JP2954220B2 - Data transfer network for parallel computers - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a data transfer network for transferring packet data.

[Conventional technology]

In recent years, advances in LSI technology have made it possible to realize a high-performance parallel computer system by connecting a large number of high-speed and large-capacity processors and performing parallel processing.
In such a system, it is necessary to exchange a large amount of data between processors, between a processor and a memory, and a data transfer network for connecting processors as shown in FIG. 2A is required. The conventional method of configuring a data transfer network is described in detail in, for example, Kurokawa et al., Information Processing Vol. 27, (1986), No. 9, Special Issue on “Parallel Processing Technology” 3.1, Coupling Method, pp. 1005-1021. Have been.

As a data transfer network, those using a crossbar switch and those using a multi-stage switch are known. In this case, a packet in which data to be transferred is added with a transfer destination address is sent to the data transfer network, Paths are sequentially generated in the network for the packets.

[Problems to be solved by the invention]

When the data transfer network is configured by a crossbar switch, the hardware becomes enormous, which is difficult to realize. Therefore, it is practical to use a multi-stage switch system. In the above-mentioned packet, the data length is usually several tens of bits or more, and the transfer destination address is required to be ten or more bits when using several thousand or more processors. It goes without saying that it is desirable to transfer all bits of the packet in parallel for high-speed packet transfer, but if all bits of the packet can be sent in parallel, the number of signal lines and switches becomes enormous. , The bit width d of the data transfer path must be relatively small (at most about 10 bits or less). Therefore, from a practical point of view, as shown in FIG. 2B, each packet is divided into a plurality of subpackets each having a plurality of bits d, all bits in each subpacket are transferred in parallel, and different subpackets are A method of sequentially transferring is required. In this case, not only the data but also the transfer destination address needs to be divided into at least two or more partial addresses.

Each switch of the multistage switch constituting the data transfer network determines the destination of the input packet from the destination address in the packet, performs appropriate switching, and outputs the packet to an appropriate output terminal. Even when the data and the transfer destination address are divided as described above, this switching can be performed by each switch by waiting for the arrival of all the partial addresses. Once the switching is performed, the data subpackets sequentially transmitted after the transfer destination address can be transmitted to the next-stage switch in a pipeline manner. However, if the switching of each switch is performed after all the partial addresses arrive, there is a problem that the switching start time is greatly delayed as compared with the case where all bits of the transfer destination address are transferred in parallel.

SUMMARY OF THE INVENTION An object of the present invention is to provide a data transfer network in which the switching start time of each switch is not delayed so much even when the transfer destination address is divided into a plurality of partial addresses.

[Means for solving the problem]

For this reason, in the present invention, the partial address required to determine the next switch to which a switch should send a packet is the first of a plurality of sub-buckets each including the partial address supplied to the switch. If so, the switch is configured to start switching when the first packet arrives. As a further desirable mode, when the partial address necessary for the next-stage switch to perform switching is not included in the first subpacket, the preceding switch switches the partial address so that the partial address is included in the first subpacket. Was changed between subpackets.

[Action]

According to the present invention, by adopting the above-described configuration, it is possible to reduce the waiting time required for the switches constituting the data transfer network to start switching, thereby realizing a high-speed data transfer network.

〔Example〕

Prior to the description of the embodiment of the present invention, an example of a data transfer network that uses a divided address but does not attempt to speed up switching according to the present invention will be described with reference to FIG. .

FIG. 3 shows a data transfer network (hereinafter, also simply referred to as a network) having a multistage switch configuration.
Suppose we have 6 outputs.

In FIG. 3, S00-S37 are 2-input / 2-output switches constituting a network, and the numbers in [] added above each switch indicate the numbers.

0 'to 15' are network input ports, 0 "to 15"
Is the output port of the network. Output port 0 "~
15 ″ is the address in binary notation (0000) to (1111)
Is expressed as FIG. 4 shows an example of the configuration of a switch used in the network of FIG. 3 for dividing and transferring a transfer destination address in the multistage switch. In FIG. 4, reference numerals 11 and 12 denote input ports of the switch, O1, O2 output port, E1 is the output port selection circuit, Q _1, Q ₂ is input queue, Q
₃ , Q ₄ are output queues, L 1, L 2, L 3, L 4 are registers for storing the partial addresses included in the above subpacket, S
Reference numerals 1 and 2 denote selectors, MS1 is a memory storing information and procedures necessary for switch operation, and P1 is a switch controller for controlling switch operation.

Here, for simplicity, it is assumed that a packet given to the network has a transfer destination address of 4 bits, data of 4 bits, and a bit width of a data transfer path of 2 bits, and transfers the packet as shown in FIG. 2B. Destination address is partial address
It is assumed that the data is divided into A ₁ and A ₂ and divided into data D ₁ and D ₂ . Also, as shown by the bold line in FIG.
Consider a case where the data is transferred from the input port 1 'to the output port 11 ". Since the address of 11" is (1011), A ₁ , A
₂ represents a bit string of 10, 11 respectively. The operation of the data transfer network of FIGS. 3 and 4 at this time will be described with reference to FIG. As shown in FIG. 5, [00] in FIG.
The partial address A ₁ ,
It is assumed that A ₂ and partial data D ₁ and D ₂ are sequentially input. At this time, in the switch S00, the first and second partial addresses A ₁ and A ₂
Are stored in registers L3 and L4, respectively, and the partial addresses A ₁ and A _{2 and the} partial data D ₁ and D ₂ are sequentially stored in the input queue.
Output C3, C4 of registers L3, L4 (partial address in this case
A ₁ , A ₂ ) are switch controller P1 respectively
The switch controller P1 responds to the contents of the in-switch memory MS1 and the outputs C3 and C4 of the registers L3 and L4 when the partial addresses A ₁ and A ₂ are set in the registers L1 and L2, respectively. Selector S in output port selection circuit E1
1, control information M1 and M2 for S2 are created and given to them. More specifically, in this case, the switch controller P1
Determination bit position information J1 indicating that the first bit of the first subpacket is a determination bit as indicated by * in FIG. 5 is provided from the memory MS1 and consists of outputs C3 (= A1) and C4 (= A2). The above-mentioned judgment bit is taken out of the bit address.
In this case, since this value is 1, based on this, E1
For the middle selector S2, input port I2 to output port O2
Control information M2 for generating a path leading to. Thus, the sub-packets are sequentially transmitted from the output port O2 to the next-stage switch S14 via the output queue Q3.

In FIG. 3, the output port O2 is selected in the switch S00.
As shown in the figure, determination bit position information J1 that the determination bit position is the second bit of the first subpacket is given from the memory MS1 in the switch, and the determination bit (0 in this case) is input to the switch S14. Port I1 to output port O
A path to 1 is generated, and the packet is sent to the switch S24. Hereinafter, the determination bit (1 in this case) in the switch S24
In the switch S35, the second bit (1 in this case) of the second subpacket, and the packet is transferred to the output port 11 ″ of the network by the same processing.

FIG. 6 shows a timing chart of the above operation. In FIG. 6, it is assumed that each of the above sub-packets is sequentially supplied to the input port at every time T. It is also assumed that the switch controller P1, selectors S1, S2, etc. in each switch operate at a sufficiently high speed. As can be seen from FIG. 6, in the data transfer networks of FIGS. 3 and 4, each switch starts switching upon arrival of two divided addresses. Therefore, in addition to the transfer time 4T for four subpackets, the time 2T for waiting for the arrival of two divided addresses at each switch.
× 4 = 8T is added, so the network transfer time is
12T is required.

 Next, examples of the present invention will be described.

FIG. 7 shows a data transfer network comprising a multi-stage switch according to the present invention, which differs from FIG. 3 in that switches S00 'to S37' wait for arrival of all sub-buckets including a transfer destination address. However, after the first sub-packet arrives, switching is performed, the output port connected to the next-stage switch to which the packet is to be transmitted is determined, and the transmission of the sub-packet is started. 'To S17' are such that, for a plurality of subpackets including the divided transfer destination address, the above-mentioned divided addresses are exchanged between the first subpacket and the second subpacket. In the example of Network described with reference to FIGS. 3 and 4, the switches S00 to S0 in the first stage are used.
7 and the second-stage switches S10 to S17, the partial addresses necessary to determine the next-stage switch to which each switch should send a packet have a partial address in the first sub-packet of the input packet. One partial address A1, but in the switches S20 to S37 of the third and fourth stages,
It is the second partial address A2 in the second subpacket. However, as shown in FIG. 7, the second stage switch S10 '
When the sub-packet string input to ～S17 'is outputted, the second partial address A2 to the first sub-packet, partial address A ₁ as the first partial address A ₁ is included in the second sub-packet, A _By replacing ₂ with the second-stage switches S10 'to S17', the next-stage switch causes the partial address required for switching to be included in the first subpacket.

FIG. 1A is an example of the configuration of the switches S10 'to S17' in the second stage of FIG. 7. The difference from FIG. 4 in the configuration is that the input ports I1 or I2 are provided with registers L1, L2 or L1.
A selector S3 for selecting the outputs C1 and C2 of the registers L1 and L2, and an output C3 and L3 for the registers L3 and L4 so as to first select the one to be transmitted first among the partial addresses stored in L4. The selector S4 or S6 that selects the partial address string output from the selector S5 that selects C4 and the partial address string output from the selector S3 or S5 prior to the partial data stored in the input queue Q1 or Q2 and gives it to the output port selection circuit E1 And the switching controller P2 synchronizes with the arrival of the first subpacket of the packet at the input port I1 or I2, and outputs a packet start signal PSTR provided in parallel with this packet.
1 or PSTR2, the operation is started, and the operation is ended in response to the packet end signal PEND1 or PEND2 given in synchronization with the end of the packet arriving at the input port I1 or I2. Is always pointed to any bit of the partial address in the first subpacket.

As shown in FIG. 1B, the first-stage switches S00 'to S07' and the third and fourth-stage switches S20 'to S37'
In FIG. 1A, registers L1 and L3 for storing subpackets and selectors S3 to S6 are omitted. That is, these switches are different from the second-stage switches S10 'to S17' mainly in that they do not exchange subpackets, but they are the same in that they respond to the packet start signals PSTR1, PSTR2 and the packet end signal PEND2. is there. As in the case of FIG. 3, the bit width of the data transfer path is 2 bits and the transfer destination address is two partial addresses A ₁ , A for explanation of the operation of FIG.
_The data consisting of two pieces of data consists of two pieces of partial data D ₁ and D ₂ , each of which is included in a subpacket having a length of 2 bits.
As shown by the bold line in FIG. 7, input port 1 'to output port
Consider the case of forwarding to 11 '. The operation of the data transfer network of FIG. 7 at this time will be described with reference to FIG. As shown in FIG. 8, the same partial addresses A ₁ and A ₂ and partial data D as in FIGS. 3 to 5 are applied to the input port I2 of the switch S00 'at the coordinates [00] in FIG. ₁ and D ₂ are sequentially input. Switches S00 ', S24', S3 in FIG.
The operation of 5 'is almost the same as the operation of the switches S00, S24 and S35 in FIG. 7, except that each switch starts operation when the first partial address arrives. That is, in the case of FIG. 7, the determination bit positions for determining the destination switch of the packet from each switch are all within the partial address of the first sub-packet as indicated by * in FIG. The difference is that the transmission destination is determined and transmission is started without waiting for the arrival of the subpacket.

Next, an example of the operation of the switch S14 'in FIG.
This will be described with reference to the time chart in FIG. Switch S1
The partial addresses A ₁ and A ₂ and the partial data D ₁ and D ₂ are sequentially sent to the input port I1 from the switch S00 ′ to 4 ′. At this time, a packet start signal PSRT1 is given to the switch controller P2 in synchronization with the arrival of the leading partial address and in parallel with the packet transfer, and the switch controller P2 performs a control operation so that the switch S00 'performs the following operation. To start. At the switch S14 ', the first timing
Storing partial address A ₁ in the register L2, and moves the first partial address A ₁ in the register L1 at a second timing that follows, and stores the second partial address A ₂ in the register L2.
At the third and fourth timings, the partial data
D ₁ and D ₂ are sequentially stored in the input queue Q ₁ . Here, the content C2 of the register L2 is given to the switch controller P2. In the present case, this partial address A ₁ is applied to the switch controller P2 as C1 when the first partial address A ₁ arrives in register L2. The switch controller P2 creates control information M1 and M2 for the selectors S1 and S2 in the output port selection circuit E1 in response to the bit at the position indicated by the determination bit position information J2 given from the memory MS2 out of the output C2. To generate a path from the input port I1 to the output port O1. Furthermore, the switch controller P2 is
Of the first partial address A ₁ stored in the register L ₁ and the second partial address A ₂ stored in the register L ₂ ,
In the timing, the A _2, also in the fourth timing
Given such control signal M3 selects A ₁ to the selector S3, thereby interchanging the order of the partial address A ₁ and A _2. Furthermore, the switch controller P2 is the partial address A ₂ output from the selector S3 in the third timing, selecting a partial address A ₁ output from the selector S3 respectively in the fourth timing, The fifth At the sixth timing, the partial data D ₁ and D ₂ stored in the input queue Q1 are respectively selected, and a control signal M4 to be supplied to the output port selection circuit E1 is supplied to the selector S4. The output of the selection circuit E1 is given to the output queue Q3, and A ₂ , A ₁ , D ₁ , and D ₂ are input and stored in the output queue Q3 at the third, fourth, fifth, and sixth timings, respectively. You. As a result, the transfer destination address generated by replacing the partial addresses A ₁ and A ₂ as described above can be selectively given to the output port selection circuit E1 prior to the data stored in the input queue Q1.

FIG. 9A shows that the time required for the address arrival at the switches S00 ', S24' and S35 'in FIG. 7 is half the time T in the case of FIG.
Only needs to be done. Therefore, the transfer time of the network is 9T, which is 25% faster than 12T in the case of FIG. 3 (FIG. 6).

Note that the switch controller P2 can perform the same processing on the packet supplied from the input port I2, and can determine the priority of the input data of the input ports I1 and I2 as in the case of FIG. it can. The switch controller P2 has an output enable signal for each of the output ports O1 and O2.
When OE1 and OE2 are given and OE1 is in the output permission state, the output control signal OC1 is given from the switch controller P2 to the output queue Q3, and from the output queue Q3, the partial addresses A ₁ , A ₂ , The data D ₁ and D ₂ are sequentially sent to the output port O1. Similarly, when the signal OE2 is in the output permission state, the output control signal OC2 is provided from the switch controller P2 to the output queue Q4. When the output queues Q3 and Q4 are filled with data and cannot store new data, status signals SQ1 and SQ2 connected to the switch controller P2 are given to the switch controller P2. From there, the input enable signal IA of the normal input terminals I1 and I2
1, IA2 is output, but the above status signals SQ1, SQ2
As a result, the input enable signals IA1 and IA2 are set to the input disabled state,
Prohibits new packets from being input. In the case of the configuration shown in FIG. 7, the input enable signal IA1 (or I
By inputting A2) to the preceding switch as the output permission signal OE1 (OE2), it is possible to prevent packets from being lost due to overflow of the queue in the middle of the transfer path. In FIG. 1A, the control of the timing of setting the data in the registers L1, L2 and the output queues Q1, Q3 is controlled by signals T11, T12, T13, T14.
The timing of setting data in the registers L3 and L4 and the output queues Q2 and Q4 is controlled by signals T21, T22, T23 and T24, and these signals are given from the switch controller P2. FIG. 10 is a schematic configuration diagram of the switch controller P2 of FIG. 1A. In the figure, a timing supply circuit 10
A and 10B are packet star start signals PSTR1 or PSTR2
Activate the address decoder 16A or 16B in response to, and provide a timing clock to the counter 12A or 12B,
The end of the packet is given in synchronization with the timing given to the input port I1 or I2 (FIG. 1A). The counter 12A or 12B and the timing decoder 14A or 14B are reset in response to the packet end signal PEND1.
Address decoder 16A or 16B outputs register L2 or L4
Of C2 or C4, the bit indicated by the determination bit position information J2 provided from the memory MS2 is cut out and the input packet is sent to the conflict control 22 as a signal indicating which of the output ports O1 and O2 should be sent. The timing decoders 14A and 14B output control signals T11 to T13, M3 and M4 and activate the output queue control 18A or 18B and the selector control 24 'in response to the count values of the counters 12A and 12B, respectively. The conflict control 22 checks whether there is a conflict between the outputs of the address decoders 16A and 16B. Therefore, selector control signals M1 and M2 are generated. In the conflict control, if there is a conflict between the two outputs, only one of them is sent to the selector control 24 in response. At the same time, it sends an input control 20A or 20B signal provided corresponding to the other of the address decoders 16A and 16B. The input / controls 20A and 20B generate a signal IA1 or IA2 for inhibiting transmission of a new packet and send it to the preceding switch.

The output queue controls 18A and 18B generate signals T14 and OC for controlling the output queue Q3 or Q4, and also generate a packet start signal PSTR1 or PSTR2 and a packet end signal PEND1 or PEND.
2 is generated in synchronization with the start of packet transmission and the end of packet transmission by the output queue Q3 or Q4, and sends these signals to the next-stage switch.

FIG. 9B shows a time chart in the case where timing control different from that in FIG. 9 is performed using the circuits in FIGS. 6, 7A and 7B. In this case, as in the case of FIG. 9A, the partial address A ₁ , A ₂ and the partial data D ₁ , D ₂ are sequentially sent to the switch S14 ′ of the circuit of FIG. 6 from the switch S00 ′ to the input port I1. In the switch S14 ', the first timing
Portion stores the address A ₁ in the register L2, then determines an output port to be sent the data. The second that follows
In the timing, the first partial address to move to the register L1, and sends the second partial address A ₂ to the output queue Q3 by through the register L2. In the embodiment of FIG. 9B, S1
The partial address A ₁ require processing (interpretation) to determine the forwarding destination of the packet 4 'included in the first sub-packet, partial address A ₂ in the second sub-packet S1 is
No processing (interpretation) is required at 4 '. Therefore, it is possible to pass through the register at the second timing as described above. The control of the switch controller P2 and the selectors S1, S2, S3, S4 at this time can be realized by a method similar to the case of FIG. 9A. Next, the partial data D ₁ and D ₂ are sequentially stored in the input queue Q1 at the third and fourth timings, respectively, and A ₁ at the third timing, D ₁ at the fourth timing, and D 5 at the fifth timing. Send D ₂ to output queue Q3. As a result, in FIG. 9B, the one in S14 ′ required in FIG.
Reduce waiting time for T minutes. In FIG. 9B, the transfer time required for 9T in FIG. 9A is reduced to 8T, and a pipeline operation without waiting time can be realized.

In the above description, for the sake of simplicity, the partial addresses A ₁ and A ₂ and the partial data D ₁ and D ₂ are temporarily stored in the output queue Q3, but the output enable signal OE1 is output enabled from the beginning. In this state, it is obvious that the output queue Q3 may be bypassed or passed through and sent immediately to the output port O1 at the third, fourth, fifth, and sixth timings. It is also apparent that the output queues Q3 and Q4 for storing the partial address sequence and the partial data sequence may be provided after the input port, not before the output port, or may be provided on both of them. The input queues Q1 and Q2 and the output queues Q3 and Q4 may be FIFO memories, or may be configured by RAMs or register files. In Figure 1B, register L3
L4 and the registers L1 and L2 are connected in series, but the first sub-packet is connected to the register L1 (or
L3), the second subpacket may be stored in the register L2 (or L4). In this case, the register
In L1 to L4, the RAM (having a sufficient data word length) may be constituted by using a part of the register file.

As is clear from the above description, the effect of the present invention is large in a network, and the effect increases as the number of switches increases. In the above description, the data width of the data transfer path is set to 2
Although the bit, the transfer destination address is 4 bits, and the data is 4 bits, the present invention is effective for any value if the number of bits of the transfer destination address is larger than the data width of the data transfer path. it is obvious. The switch is 2
Although the description has been made using the input / output configuration, it is apparent that the present invention is effective regardless of the switch configuration and the network configuration.

FIG.11A is a view showing another embodiment of the present invention,
PE44 are processors, and the data transfer network connecting each processor is formed by switches EX11 to EX44 and X
It is composed of partial networks NX1 to NX4 and a Y partial network. The packets transferred in the data transfer network are the same as those shown in FIG. 2B. However, the transfer destination partial addresses A ₁ and A ₂ are determined to be equal to the subscript i in the X direction of the processor PE _ij and the subscript j in the Y direction. That is, the address of the processor PEij is represented by a set of an X address i and a Y address j.

In FIG. 11A, i is the same processor PEij (j =
1-4, i = 1, 2, 3, 4) and j is the same processor PEij
(I = 1 to 4, j = 1, 2, 3, 4) belong to one cluster.

The X partial network NXi (i = 1, 2, 3, 4) is a processor PEij of a cluster (called an X cluster) sharing i.
(J = 1 to 4) are connected to each other, and the Y subnetwork NY
j (j = 1, 2, 3, 4) is mutually connected to the processors PEij (i = 1 to 4) belonging to a cluster sharing j (called a Y cluster). These partial networks NXi, NYj
This is a network composed of multi-stage switches as shown in FIG. As will be described later, each of the multistage switches used therein does not need to exchange the partial addresses, and therefore can be constituted by the switches shown in FIG. 1B. The switches EXij (j = 1 to 4, i = 1 to 4) are connected to the X partial network NXi, the Y partial network NYj and the processor.
This is a three-input / 3-output port switch that mutually connects PEij.

For example, the partial network NX1 has processors PE11,
PE12, PE13, PE14 are switches EX11, EX12, EX13, E, respectively.
Connected via X14, NY1 has processors PE11, PE21,
PE31 and PE41 are connected via switches EX11, EX21, EX31 and EX41, respectively.

The switch EXij is connected to the processor PEij as shown in FIG. 11B.
Has an input port IPij, an output port OPij, an input port IXij with the partial network NXi, an output port OXij, an input port IYij with the partial network NYj, and an output port OYij.

Since the switches EXij need to exchange the partial addresses A ₁ and A ₂ as described later, for example, the first
The switch shown in Fig. 12 in which the switch shown in Fig. A is changed to 3 inputs / 3 outputs is used. Each part and each signal in FIG. 12 are the same as the parts and signals in FIG. 1A having a sign starting with the same English letter or English character string.

In this embodiment, the processor PEij and the processor PEkl
The data transfer between (1 ≦ i, j, k, l ≦ 4) is performed as described later in detail. PEij → EXij → NXi → EXil → NYl → EXkl → PEkl or PEij → EXij → NYi → EXkj → This can be performed via one of two paths, NXk → NXkl → PEkl.

Hereinafter, the operation of the network in FIG. 11A will be described with reference to FIGS. 13A to 13C.

Switch EXij is input port IP from a processor PEij
It is assumed that a packet addressed to the processor PEkl has been received via ij (step 130).

First and second partial addresses at the beginning of this packet
A ₁ and A ₂ are now equal to the X-direction address k and the Y-direction address 1 of the destination processor PEkl.

(1) Now, step EXij, as shown in FIG. 13A,
It is determined whether this packet satisfies the first condition A ₁ (= k) = its own X-direction address (i) (step 132), and if this condition is satisfied (ie, the destination processor PEkl)
And the source processor PEij belong to the same X cluster), it is determined whether or not this packet satisfies the second condition A ₂ = its own X-direction address (j) (step 134). (Ie the source processor PE
ij and destination processor PEkl are the same), switch EX
ij sends this packet to processor PEij via its output port OPij (step 163). On the other hand, as a result of the determination of the second condition in step 134, the second condition was not satisfied. In this case (that is, when the destination processor PEkl is another processor belonging to the same X cluster as the processor PEij), the partial addresses A ₁ and A ₂ are replaced (step 13).
8), through the output end OXij, to the X partial network NXi,
This packet is transmitted (step 140). By this address exchange, the Y-direction address 1 of the destination processor PEkl is located at the head of this packet. As a result, X
Each switch of the partial network NXi (= NXk), the first subpacket arrives soon in this packet, it starts switching in response to the partial partial address A ₂ in the head portion. The subnetwork NXk sends this packet to the switch EXkl via its input port IXkl.
Upon receiving this packet (step), the switch EXkl, as shown in FIG. 13B, receives a partial address (A ₂ (=
1)) is equal to the address 1 in the Y direction of the switch EXkl (= EXij) (step 164). In this case, the condition that they are equal is satisfied, so the switch
EXkl sends this packet to processor PEkl via its output port OPkl (step 166).

Thus, packet transmission is performed between processors in the same X cluster.

(2) If the result of the determination of the first condition in step 132 in FIG. 13A shows that the first condition is not satisfied (that is, the destination processor PEkl and the source processor PEij do not belong to the same X cluster) Case), the second condition A ₂ (= 1)
= It is determined whether or not its own Y-direction address (j) is present (step 142). As a result of this determination, if this condition is satisfied (that is, if the processors PEkl and PEij do not belong to the same X cluster but belong to the same Y cluster, step EX
ij sends this packet to the Y partial network NYj via the output port OYij (step 144).

The partial network NYj sends this pocket to the switch (Ekj) having the X address equal to the partial address A ₁ (= k) at the head of this packet. That switch (Ek
In j), as shown in Fig. 13C, this packet is
When the packet is received from IYkj (step 152), it is determined whether this packet is equal to the second partial address A ₂ = the own Y-direction address (step 154). In this case, since this condition is satisfied, the switch Ekj sends the packet to the processor (PEkj) connected thereto via the output port OPkj. Thus, packet transfer between the two processors belonging to the same Y cluster can be performed.

(3) When the result of the determination in step 142 of FIG. 13A is negative, that is, when the destination processor PEkl and the source processor PEij do not belong to the same X cluster and do not belong to the same Y cluster. , There are two paths connecting these two processors. That is, the first route is a route for first transferring a packet to the first partial network X. Specifically, PEij → EXij → NXi → EXil → NYl → EXkl →
PEkl. In this route, since the Y address is determined first, this route is hereinafter referred to as a Y priority route. The second route is a route for first transferring a packet to the Y partial network, and specifically, PEij → EXij → NYj → EXkj → NXk →
EXkl → PEkl. In this route, since the X address is determined first, this is hereinafter referred to as a priority route.

In step 146, one of these two routes is selected.

This selection may be determined in advance for each switch EXij. In this case, step 146 is omitted.
Alternatively, the amount (load) of packets passing through each partial network of the network may be measured, and the above selection may be dynamically changed so that the load becomes as uniform as possible.

When the X priority route is selected in step 146, the switch EXij sends the packet to the partial network NYj via the output port OYij (switch 144). In response to this packet, the partial network NYj sends out the packet via the input port IYkj of the switch Ekj having the X address equal to the partial address A ₁ (= k) at the head of the packet. When the switch receives the packet (step 152), as shown in FIG. 13C, it determines whether the second partial address A ₂ (= 1) = Y address (= j) of the switch is satisfied, as shown in FIG. 13C. Is determined (step 154). In this case, j
Since ≠ l is assumed, the result of this determination is negative. In this step Ekj, the partial addresses A ₁ ,
Swapping the A _2, transfer the partial address A ₂ at the beginning (step
158). After that, the packet is sent to the X partial network NXk.
Send out via output port OXkj.

Each switch in this partial network NXk is partial address A ₂ at the beginning of this packet to respond to it on arrival. The sub-network then sends this packet to the switch Ekl with the Y-direction address equal to the sub-address A ₂ (= 1).

The switch Ekl via the input port IXkl receives this packet (step 162, FIG. 13B) and the first partial address A ₁ own X address of this packet (= k)
Is determined to be equal to In this case, since this determination result is affirmative, the switch Ekl sends this packet to the processor PEkl. In this way, packet transfer between two processors that do not belong to the same cluster is performed by the X priority route.

If the Y priority route is selected in step 146 (FIG. 13A), the switch EXij replaces the partial addresses A ₁ and A ₂ in the packet and moves A ₂ to the top (step 138). Thereafter, the packet is transmitted to the X partial network NXi (step 140). The partial network NXi sends the packet to the switch EXil having a Y address equal to the partial address A ₂ (= 1).

In FIG. 13B, after receiving this packet (step 162), the switch EXil determines whether A ₁ (= k) is equal to its own X-direction address (= i) (step 164). In this case, the result of this determination is negative, the switch replaces the partial addresses A ₂ and A ₁ , moves A ₁ to the beginning of the packet (step 168), and forwards the packet again to the Y partial network NYl ( Step 170).
This partial network Nyl, the packet forwards the packet to the first partial address A ₁ (= k) to have the same X-direction address switch Ekl of this packet. In this switch Ekl, steps 152, 154, 15 in FIG.
The processor PEk connected to this packet by 6
send to l. Thus, a packet is routed between two processors that do not belong to the same cluster by the Y priority route.

An advantage of the network as in the present embodiment is that the scale of each partial network is reduced, thereby facilitating the implementation. The processor as described above because it is clustered, in among the partial network NYj only the first partial address A ₁ of the transfer destination address, only the second partial address A ₂ becomes necessary in NXi. In this embodiment, since the means for replacing A ₁ and A ₂ is provided in step EXij, the necessary partial addresses in each of the partial networks NXi and NXj are always in the first subpacket. It is not necessary to wait for all partial addresses to arrive, and high-speed data transfer becomes possible.

In the operation of the network of FIG. 11A, the speed can be further increased by changing as follows.

That is, in FIG. 13B, the determination 164 when each switch (EXmn) receives a packet from the X partial network NXm, where m and n are integers, is determined by the network NXm
It is necessary to wait for the arrival of the partial address A ₁ from. However, as already mentioned, the network NXN, packets carry partial address A ₂ at the head. Therefore, the above determination 164 becomes possible only when the second subpacket from the partial network NXm arrives at the switch EXmn. The same problem occurs for decision 154 in FIG. 13C. These problems can be improved by changing the partial networks NXm, NYn, etc. as follows.

That is, as shown in FIGS.14A and 180B of the partial network NXm or NYn, respectively, as steps 180A and 180B in FIG. 14B, when outputting a packet from each to a certain switch EXmn, a switch in a partial network closest to the switch is output. , So that the partial addresses A ₁ and A ₂ in the packet are interchanged. This can be achieved in a manner similar to the method described in FIG. 9B.

As a result, the operation of the switch EXmn received from the X partial network in the NXm packet is as shown in FIG. 14C. In the figure, the same reference numerals as those in FIG. 13B denote the same processes. This improved operation as can be seen from this figure, switch EXmn is performed the determination process 144 for partial address A ₁ is the same as in FIG. 13B, X partial network improvements already mentioned since the beginning of the packet sent from NXm contain this partial address a _1, the determination processing 144 can be initiated as soon as the arrival of the partial address a _1. Further, as a result of the X-subnetwork NXm changing the address at the time of packet output, the address change required in FIG. 13B is not required in FIG. 14C.

Similarly, the operation of the switch EXmn when receiving a packet from the Y partial network NYm is as shown in FIG. 14D. In the figures, the same reference numerals in FIG. 13C denote the same parts. Also in this case, the comparison between FIG. 14C and FIG. 13B is directly applicable.

Although A ₁ and A ₂ are 2 bits and d is 2 bits in the above description, the effect of the present invention does not change even if this is an arbitrary number of bits. Also, the transfer destination address is divided into three, a partial network is provided in the Z direction in addition to the X and Y directions, and EXij is made into 4 input ports / 4 output ports like EXijk. It is also clear that the number of divisions of can be increased.

FIG. 15 shows an embodiment of such a data transfer network. In the figure, EX ₁₁ , NX ₁₂ , NX ₁₄ , N ₄₄ etc. represent the partial transfer network 7.1 in the X direction, NY ₁₁ , NY ₁₂ , N
Y _14, NY ₄₄ etc. represents the Y direction partial transfer network, these are partial network NZ ₁₁ in this embodiment is the same as the first 11A Figure Z _{direction, NZ 21, NZ 41, NZ} 14 ... NZ
_{There are 44} etc.

Switch EX at the intersection of these three partial networks
₁₁₁ , E ₁₄₁ , EX ₄₁₁ , EX ₄₄₄ etc. and processor PE ₁₁₁ , PE
₁₄₁ , PE ₄₁₁ , and PE ₄₄₄ are provided.

In the figure, each partial network is represented by a straight line for simplification, and only a part of switches and processors are represented.

The switch EX ₁₁₁ is connected to the X direction partial network NX ₁₁ , Y
Direction partial network NY ₁₁ , Z direction partial network NZ
₁₁ and the processor PE1 ₁₁ are connected to each other through an input port and an output port.

 The same applies to other processors.

When transferring a packet from one processor to another, constitute a destination address in the packet from the portion of _{A 1, A 2, A 3} . Assuming that the packet destination processor is Pijk, the respective X, Y, Z direction coordinates i, j, k
be equivalent to.

Now, for example, when transmitting a packet from the processor PE ₁₁₁ to the PE _444, there are several packet transfer routes.

For example, PE ₁₁₁ → EX ₁₁₁ → NX ₁₁ → EX ₄₁₁ → NY ₁₄ → EX ₄₄₁ → NZ ₄₄ → EX
₄₄₄ → PE ₄₄₄ is one of them.

The operation when transferring a packet according to this route is as follows.

Switch EX ₁₁₁ passes this packet to partial network NX.
If sent to _11, the switch EX ₁₁₁ as in the case of FIG. 13A, without replacing the partial address _{A 1, A 2, A 3} , and transfers. Partial network NX ₁₁ is the packet and sends it to the switch EX ₄₁₁ with the X coordinate equal to the address A _1. The switch EX ₄₁₁ sets the partial address A ₂ ,
Because A ₂ of the A _3, A ₁ is different from the self-Y coordinates, and sends the Y direction subnetwork NY _14. At that time, the addresses in the packet are changed in the order of A ₂ , A ₃ , and A ₁ . The network sends to the switch EX ₄₄₁ with equal Y coordinate a packet to the address A _2.

In the switch EX _441, the partial address A ₃ in this so different from the self-Z coordinates, and sends the packet to the Z-direction partial network NZ _44. At this time, the addresses are A ₃ , A ₁ , A ₂
Change to the order. The network sends the packet to the EX ₄₄ with equal Z coordinate address A _3. Upon receiving this, the switch EX ₄₄₄ passes this packet to the processor PE.
_Send to ₄₄₄ .

Thus, in this embodiment, when there are more processors than in the case of FIG. 11A, data transfer between them can be performed. In addition, since each switch EX performs the above-described switching of addresses, the switches can be switched in response to the leading partial address of the packet that has arrived at the partial network.

In addition, as shown in FIGS.
Instead of replacing the addresses in the ₄₁₁ and EX ₄₄₁ , the partial network NX ₁₁ , NY ₁₄ and NZ ₄₄ can perform a higher-speed operation by replacing three addresses when outputting a packet.

FIG. 16A shows another embodiment of the present invention. PE is a processor, EX is a switch, and as shown in the figure, the processor PE
For each of a plurality of processors similar to 100, one switch similar to the switch EX100 is provided, and each switch EX has an input port connected to four switches close to each other,
They are connected by output ports to form a net-like data transfer network. Also, as shown in FIG. 16B,
The switch EX100 has an input / output port IP100 / OP100 with the processor PE100 and an input / output port with the 4-neighbor switch.
Output port, IN100 / ON100, IW100 / OW100, IS100 / OS10
0, IE100 / OE100. Also in this embodiment, as described above, the packet transferred between the processors is:
As shown in FIG. 18, the packet is transmitted and received as a packet including an example of a subpacket divided for each bit width d of the data transfer path. This embodiment is different from the other embodiments in that the transfer destination address in the packet is divided into two so that the number of bits is d-1 bits or less, and the upper part of the divided transfer destination address is globally divided. The address A _G , the lower part is used as the local address A _L , and A _G , A _L are stored in the upper sub-packet, and the first sub-packet contains the division stored therein. Address is A _G or A _L
This is the point that a flag bit L indicating whether or not the above is provided. For simplicity, d = 4, and A _G and A _L each have 3 bits. As shown in FIG. 17, 64 processors represented by a total of 6 bits of A _G and A _L are connected by a switch as shown in FIG. 16A, and the processors are arranged as shown in FIG. Eight clusters having the same global address are clustered. In this embodiment, each switch is, for example, a 7A
The configuration shown in FIG. 20 in which a switch similar to that shown in FIG. 12 and FIG. 12 has a configuration of 5 input ports / output ports can be used. The operation of each part in FIG. 20 and the meaning of the reference numerals are the same as those in FIG. 7A having the reference signs starting with the same alphabetic character (string). The configuration of FIG. 20 differs from the configuration of FIG. 7A in that the divided address storage registers L12 and L22 and the selector S31
That is, the setting circuit X21 for setting the flag bit L is provided. X21 is the set signal XC from the switch controller P21
21 sets the flag bit L. The operation of the switch will be described below. In FIG. 20, the portions indicated by R22 to R25 have the same configuration as the portion indicated by R21, and are omitted for simplicity. In each processor, when data is transmitted for the first time, _AG is put in the first subpacket, and the L bit is set to 0. FIG. 19 shows the processing procedure in each switch. In this embodiment, since the L bits are provided, each switch does not need to refer to the local address A _L while a L = 0, therefore, everything including the divided transfer destination address as above Without waiting for the sub-packet to arrive, the next-stage switch to which the packet should be sent can be determined. When packets are successively transferred and enter a switch in the cluster having the same global address as the target processor, the switch waits for the arrival of a subpacket containing the local address A _L , as in FIG. 7A. _A.sub.L and _A.sub.G are exchanged so that the local address is included in the first subpacket, and is transmitted to the next stage as L = 1. Subsequent switches can determine the next switch to which the packet should be sent without waiting for the arrival of the second subpacket including the global address.

In FIG. 17, when each processor has an address as shown in the figure, the processor NS of A _G = 000, A _L = 110, A _G = 110, A _L
Consider a case where a packet is sent to a processor NR of = 110.
Here, each switch stores the local address of an adjacent processor and the global address of an adjacent cluster together with its own address, and compares the global address _AG with its own global address while L = 0. If different, the transfer direction and output port are determined by comparing _AG with the global address of the adjacent cluster. In the simplest case, the transmission may be performed in a direction in which the difference between the global addresses is minimized. According to this algorithm, the packet follows the path as shown in FIG. 17 and reaches the switch at the position indicated by NX (A _G = 110, A _L = 000). Where N
The switches for X are A _L and A _G as in the case of the switch in FIG. 7A.
Are exchanged, and L = 1 is sent to the next stage. After that, the local address is compared with the local address of the adjacent processor, and the transfer direction,
The output port can be determined. In this embodiment, among the switches at each stage, only the XN switch needs to wait for the arrival of two subpackets including A _G and A _L , and the other switches wait for the arrival of the transfer destination address. Is only half the time when the present invention is not used, and the effect is very large especially when the number of processors is large.

In the above description, A _G and A _L each have 3 bits, but the effect of the present invention does not change even if the number of bits is arbitrary.

Although the transfer destination address is divided into two, the effect of the present invention does not change even if the number of divisions is increased and the L bit is changed to a plurality of bits accordingly. Furthermore, although the switches of the data transfer network are connected to the vicinity of four, the effect of the present invention does not change even if the switches are connected to an arbitrary number.

In the description of the embodiments above, the preceding of the data packet has been indicated by the transfer destination address included in the first two or more subpackets, but the equivalent is as follows.
Obviously, the tag information for indicating the transfer destination address may be used. Such tag information includes, for example, the Excl. Of the address of the transmitting processor and the transfer destination address.
Usive Or can be used.

As described above, according to the present invention, it is not necessary to wait for the arrival of all of a plurality of subpackets including a transfer destination address at each stage of a plurality of switches configured in a multistage in a data transfer network. Will be possible.

[Brief description of the drawings]

FIG. 1A shows a second stage switch (S14 ') of the apparatus of FIG.
FIG. 1B is a schematic diagram of the first, third or fourth stage switches (S00 ', S24' or S35 ') of the apparatus of FIG. 6, and FIG. 2A is the present invention. FIG. 2B is a diagram showing a structure of a packet of the present invention, FIG. 2B is a diagram showing a structure of a packet of the present invention, and FIG. 3 is a diagram of a low-speed data transfer network for comparison with the present invention. FIG. 4 is a schematic configuration diagram of a switch (Sij) of the network of FIG. 2, FIG. 5 is a diagram for explaining the operation of the switch of the network of FIG. 2, and FIG. FIG. 7 is a schematic diagram of the data transfer network according to the present invention, FIG. 8 is a diagram for explaining the operation of the switch of the device of FIG. 6, FIG. 9A. FIG. 9B is a time chart of an example of the operation of the apparatus shown in FIG. 6, and FIG. 6 is a time chart of another example of the operation of the device of FIG. 6, FIG. 10 is a schematic configuration diagram of a switch controller (P2) used for the switch of FIG. 7, and FIG. Another embodiment of the data transfer network, FIG. 12 is a schematic configuration diagram of a switch (EXij) used in the apparatus of FIG. 11, and FIG. 13A is a switch (EXij) of FIG. 13B is a flowchart of the operation when the switch (EXij) used in the device of FIG. 12 receives a packet from the partial network NY, and FIG. 13C is used for the device of FIG. FIG. 14A is a flowchart of the operation when the switch (EXij) receives a packet from the partial network NX. FIG.
Xj) Improved operation flow chart, FIG. 14B shows the Y-direction sub-network (N
FIG. 14C is a flowchart of the improved operation when the switch (EXij) of the apparatus of FIG. 12 receives a packet from the Y-direction partial network (NYi); FIG. 14D 12 is a flowchart of an improved operation when the switch (EXij) of the apparatus of FIG. 12 receives a packet from the X-direction partial network (NXj). FIG. 15 is a three-dimensional data transfer using the partial network. 16A is another embodiment of the present invention using a lattice-coupled network. FIG. 16B is a diagram showing input / output ports of the switch (EX100) in FIG. 16A. 16A is a diagram showing a data transfer route in the device of FIG. 16A. FIG. 18 is a diagram showing a packet used in the device of FIG. 16A. FIG. 19 is a flowchart of the operation of the switch (EX) of the device of FIG. 16A. , FIG. 20, FIG. 16B is a schematic configuration diagram of a switch (EX) of the device in FIG. 16A.

Continuing from the front page (72) Inventor Teruo Tanaka 1-280 Higashi Koikekubo, Kokubunji-shi, Tokyo Inside the Central Research Laboratory, Hitachi, Ltd. (72) Inventor Shigeo Nagashima 1-280 Higashi Koigakubo, Kokubunji-shi, Tokyo Inside the Central Research Laboratory, Hitachi, Ltd. (56) References JP-A-60-232743 (JP, A) JP-A-61-289746 (JP, A) Special table sho 59-501038 (JP, A)

Claims (7)

(57) [Claims] In a data transfer network for connecting a plurality of processors and transferring data between them, a plurality of switches are connected in multiple stages, and a switch in each stage is connected to a plurality of switches in a preceding stage and a switch in a subsequent stage. Each connected to a plurality of switches, each switch having means for receiving a packet from a preceding switch, the packet including an address of a destination processor and data to be delivered, wherein the address of the destination processor is a plurality of bits. And the data has a plurality of partial data composed of a plurality of bits, and the receiving means sets each of the partial addresses of the plurality of partial addresses to have all the bits. Receive in parallel, the individual partial data of the plurality of partial data receive all its bits in parallel, or Receiving a plurality of partial addresses and a plurality of partial data sequentially, and further comprising: each switch has a path selecting means connected between the receiving means and a plurality of switches at the next stage. The means may include that each individual partial address of the received plurality of partial addresses transfers all of its bits in parallel, and that each individual partial data of the plurality of partial data transfers all of its bits in parallel; A partial address and a plurality of partial data are sequentially transferred to a selected one of a plurality of switches at the next stage, and each switch has a control unit connected to the reception unit and the path selection unit. The control means controls the path selection means in response to one or more bits of a predetermined one of the plurality of received partial addresses, and the plurality of processors Clustered by the number of bits of each of the plurality of partial addresses constituting the address, the data transfer network interconnects the clustered processors in a cluster, and comprises The control means included in at least a part of switches of the partial network includes at least one or more remaining switches in response to the arrival of the first partial address of the packet. Before the partial address arrives, decodes one or more predetermined bits in the first partial address to control the path selecting means connected to the control means, and Any one of the processors may have the same number of partial nets as the number of the partial addresses constituting the address. Connected to the network via another of the above switches not included in any of the partial networks, the switch having an input port of the number of partial addresses +1 and an output port of the number of partial addresses +1; One of the input ports is connected to the one processor, the other of the input ports is connected to each of the plurality of sub-networks, one of the output ports is connected to the one processor, and the output port is The other is connected to each of the plurality of partial networks and transfers packets between each input port and each output port, and is connected to the plurality of partial networks and included in any of the partial networks. The switch that does not have a means for changing the transfer order of the received partial addresses, and When transferred from the work to another partial network, the transfer order changing means of the switch replaces the partial addresses necessary for the control means of the next-stage switch to control the path selecting means with all the received partial addresses. A data transfer network characterized by the first transfer among them. 2. In a data transfer network for connecting a plurality of processors and transferring data between them, a plurality of switches are connected in multiple stages, and a switch in each stage is connected to a plurality of switches in a preceding stage and a switch in a subsequent stage. Each connected to a plurality of switches, each switch having means for receiving a packet from a preceding switch, the packet including an address of a destination processor and data to be delivered, wherein the address of the destination processor is a plurality of switches. A plurality of partial addresses composed of bits, the data has a plurality of partial data composed of a plurality of bits, and the receiving means includes: Are received in parallel, and each partial data of the plurality of partial data receives all its bits in parallel, And a plurality of partial addresses and a plurality of partial data are sequentially received. Further, each switch has a path selecting means connected between the receiving means and a plurality of switches at the next stage. The means may include that each individual partial address of the received plurality of partial addresses transfers all of its bits in parallel, and that each individual partial data of the plurality of partial data transfers all of its bits in parallel; A partial address and a plurality of partial data are selectively transferred to a selected one of a plurality of switches at the next stage, and each switch has a control unit connected to the reception unit and the path selection unit. The control means controls the path selection means in response to one or more bits of one of the plurality of received partial addresses, and controls the plurality of processors. Are clustered by a number that can be specified by the number of bits of each of the plurality of partial addresses constituting the address, and the data transfer network interconnects the clustered processors in a cluster, And an arbitrary one of the plurality of processors is connected to a plurality of partial networks having the same number as the number of the plurality of partial addresses constituting the address. , Connected through another of the above switches not included in any of the upper sub-networks not included in any of the sub-networks, the switch comprising an input port of the number of the partial addresses + 1 and the number of the input of the partial addresses + 1 One of the input ports is connected to the one processor, and the other of the input ports is One of the output ports is connected to each of the plurality of sub-networks, one of the output ports is connected to the one processor, and the other one of the output ports is respectively connected to each of the plurality of sub-networks and has a respective input. A packet is transferred between a port and each output port, and the control means included in a switch connected to the plurality of partial networks and not included in any of the partial networks determines whether or not the first partial address of the packet arrives. In response, before the remaining at least one or more partial addresses arrive, a predetermined one of the last partial addresses is determined.
Or decoding a plurality of bits to control the path selection means connected to the control means, wherein the control means included in at least some of the switches of the plurality of sub-networks includes: In response to the arrival of the partial address, before the remaining at least one or more partial addresses arrive, one or more predetermined bits in the first partial address are decoded, and Controlling the connected path selection means, wherein the other specific switch among the switches of the plurality of partial networks has means for changing a transfer order of the received plurality of partial addresses; The transfer order changing means of the above-mentioned means switches the partial address necessary for the control means of the next-stage switch to control the path selecting means to all the received partial addresses. Data transfer network, characterized in that the first transfer among the dress. 3. A parallel computer comprising: a plurality of processors each having an input terminal and an output terminal; and a data transfer network for the plurality of processors, wherein the data transfer network comprises an input terminal and a data transfer network. A first and a second sub-network group having a plurality of pairs of output terminals and having a plurality of sub-networks capable of transferring data in parallel between them; Each of the plurality of switches is provided with the input terminal and the output terminal of a corresponding processor, and the input terminal of one of the partial networks belonging to the first partial network group. And a pair of output terminals and a pair of the input terminal and the output terminal of one sub-network belonging to the second sub-network group. One of the input terminal of the corresponding processor, the input terminal of one of the partial networks belonging to the first partial network group, and the input terminal of one of the partial networks belonging to the second partial network group The data transferred from one input terminal is transmitted to the output terminal of the corresponding processor, the output terminal of one partial network belonging to the first partial network group, and the second partial network according to the data. Controlling the transfer to any one of the output terminals of one of the sub-networks belonging to the group, wherein each of the plurality of sub-networks of the first and second sub-network groups includes the plurality of input terminals and A pair of output terminals having a data transfer path that couples each other without passing through the plurality of switches. Parallel computer. 4. A parallel computer comprising: a plurality of processors each having an input terminal and an output terminal; and a data transfer network for the plurality of processors, wherein the data transfer network includes an input terminal and a data transfer network. A first and a second partial network having a plurality of pairs of output terminals and capable of transferring data in parallel between them, and a plurality of switches provided corresponding to the plurality of processors; Each of the plurality of switches includes the input terminal and the output terminal of the processor, the pair of the input terminal and the output terminal of the first partial network, and the pair of the input terminal and the output terminal of the second partial network. Any of the input of the processor, the input of the first sub-network, and the input of the second sub-network. Data transferred from one input terminal
Controlling the data to be transferred to any one of the output terminal of the processor, the output terminal of the first partial network, and the output terminal of the second partial network according to the data; And a second partial network having a data transfer path that couples the plurality of pairs of input terminals and output terminals to each other without passing through the plurality of switches. 5. A parallel computer comprising: a plurality of processors each having an input terminal and an output terminal; and a data transfer network for the plurality of processors, wherein the data transfer network comprises X, Y, And a plurality of partial networks that are provided in a three-dimensional manner in the Z direction and have a plurality of pairs of input terminals and output terminals, respectively, and that can transfer data in parallel between them, and are provided corresponding to the plurality of processors. A plurality of switches, each of the plurality of switches being connected to the input terminal and the output terminal of the processor and the input terminal and the output terminal of each of the partial networks of the plurality of partial networks. Connected to a pair, and transferred from any one of the input terminal of the processor and the input terminal of each of the partial networks of the complex partial network. Control the data to be transferred to the output end of the processor in accordance with the data, to one of the output ends of the output ends of the respective partial networks of the plurality of partial networks. A parallel computer having a data transfer path that couples the plurality of pairs of input terminals and output terminals to each other without passing through the plurality of switches. 6. The switch according to claim 3, wherein said switch has a switch controller for selecting a transfer path in response to a part of transfer destination address information in transfer data. A parallel computer according to any of the above. 7. The switch according to claim 6, wherein said switch has a memory for storing information for determining which part of said transfer destination address information is for determining said transfer path. A parallel computer according to the item.