Apparatus and method for collective communication in a parallel computer system

1. A parallel computer system, comprising:

a plurality of network switches in which each network switch of the plurality of network switches is directly connected to each other network switch of the plurality of network switches; and

a plurality of nodes in which each node of the plurality of nodes is directly connected to only one network switch of the plurality of network switches, wherein

each network switch of the plurality of network switches is directly connected to two or more nodes of the plurality of nodes; and

each node of the plurality of nodes is configured to:

determine a first destination node of data, to be transmitted by the node performing the determination, at a given time so that a first destination network switch is different from a second network switch, the first destination network switch being a network switch of the plurality of network switches directly connected to the first destination node, the second network switch being a network switch of the plurality of network switches directly connected to a second destination node of data transmitted by a source node of the plurality of nodes other than the node performing the determination, and the source node being directly connected to a source network switch that is a network switch of the plurality of network switches to which the node performing the determination is directly connected; and

transmit the data to the determined first destination node, wherein

a number of nodes directly connected to each network switch of the plurality of network switches is a predetermined number of d, d being a positive integer equal to 1 or more,

a number of the plurality of network switches is the predetermined number of d, and

a number of the plurality of nodes is d 2 .

2. The parallel computer system of claim 1 , wherein the plurality of nodes perform all-to-all communication among the plurality of nodes.

3. The parallel computer system of claim 1 , wherein

a consecutive node number is assigned to each node of the plurality of nodes, according to a predetermined connection relationship between the plurality of nodes and the plurality of network switches,

each node calculates a destination node number according to a calculation expression of (d*o+(s+(o+i/d+i) % d) % d)+d*(i/d)) % d 2 , where s is a node number assigned to the node performing the calculation, s being a positive integer equal to 1 or more, i is a number indicating a time and being a positive integer equal to 1 or more, o is a predetermined offset value that is determined based on the predetermined connection relationship and being a positive integer equal to 1 or more, and % is modulus operator, and

each node determines, as the first destination node at time i, a node with the calculated destination node number.

4. The parallel computer system of claim 1 , wherein

a consecutive node number is assigned to each node of the plurality of nodes, according to a predetermined connection relationship between the plurality of nodes and the plurality of network switches,

each node calculates a destination node number according to a calculation expression of ((s % d)*d+(i+o) % d+(i/d)*d) % d 2 , where s is a node number assigned to the node performing the calculation, s being a positive integer equal to 1 or more, i is a number indicating a time and being a positive integer equal to 1 or more, o is a predetermined offset value that is determined based on the predetermined connection relationship and being a positive integer equal to 1 or more, and % is modulus operator, and

each node determines, as the first destination node at time i, a node with the calculated destination node number.

5. The parallel computer system of claim 1 , wherein

a consecutive node number is assigned to each node of the plurality of nodes, according to a predetermined connection relationship between the plurality of nodes and the plurality of network switches,

each node calculates a destination node number according to a calculation expression of ((s/d+(s % d+i/d) % d+1)% (d+1))*d+(s % d+i) % d, ford satisfying 0≤i≤d*d−1, and according to a calculation expression of (s/d*d)+(s % d+i) % d for i satisfying d*d≤i≤d*(d+1)−1, where d is a number of nodes connected to each network switch of the plurality of network switches and being a positive integer equal to 1 or more, s is a node number assigned to the node performing the calculation, s being a positive integer equal to 1 or more, i is a number indicating a time and being a positive integer equal to 1 or more, and % is modulus operator, and

each node determines, as the first destination node at time i, a node with the calculated destination node number.

6. The parallel computer system of claim 1 , wherein each node of the plurality of nodes is connected to only one network switch of the first plurality of first network switches.

7. A parallel computer system, comprising:

a first plurality of first network switches;

a second plurality of second network switches in which each network switch of the second plurality of second network switches is directly connected to at least two network switches out of the first plurality of first network switches; and

a plurality of nodes in which each node of the plurality of nodes is directly connected to only one network switch of the first plurality of first network switches, wherein

each network switch of the first plurality of first network switches is directly connected to two or more nodes of the plurality of nodes,

any two network switches out of the first plurality of first network switches are connected via one network switch of the second plurality of second network switches, and

each node of the plurality of nodes is configured to:

determine a first destination node of data, to be transmitted by the node performing the determination, at a given time so that a first destination network switch is different from a second network switch, the first destination network switch being directly connected to the first destination node, the second network switch being directly connected to a second destination node of data transmitted by a source node of the plurality of nodes other than the node performing the determination, and the source node being directly connected to a third network switch to which the node performing the determination is directly connected; and

transmit the data to the determined first destination node, wherein

a number of nodes directly connected to each network switch of the plurality of network switches is a predetermined number of d, d being a positive integer equal to 1 or more,

a number of the plurality of nodes is d 3 ,

a number of the plurality of first network switches is d 2 , and

a number of the second plurality of second network switches is a sum of d(d−1)/2 and an integer to which d/2 is rounded up.

8. The parallel computer system of claim 7 , wherein each network switch of the first plurality of first network switches is configured to:

receive data from a node directly connected to the each first network switch,

transmit, when a destination node of the received data is directly connected to the each first network switch, the received data to the destination node of the received data, and

transfer, when the destination node of the received data is not directly connected to the each first network switch, transfer the received data to one network switch of the second plurality of second network switches that connects the each first network switch and a destination first network switch that is a first network switch of the first plurality of first network switches directly connected to the destination node of the received data.

9. The parallel computer system of claim 7 , wherein the plurality of nodes perform all-to-all communication among the plurality of nodes.

10. The parallel computer system of claim 7 , wherein

a consecutive node number is assigned to each node of the plurality of nodes, according to a predetermined connection relationship between the plurality of nodes and the plurality of network switches,

a plurality of groups are set based on the predetermined connection relationship so that each node of the plurality of nodes belongs to one of the plurality of groups each assigned a different group number,

each node of the plurality of nodes is configured to calculate a destination node number according to a calculation expression of ((s % d)*d+(i+o) % d+(i/d)*d) % d 2 +g, where g is a group number assigned to a group to which the each node belongs, s is a node number assigned to the node performing the calculation, s being a positive integer equal to 1 or more, i is a number indicating a time and being a positive integer equal to 1 or more, o is a predetermined offset value that is determined based on the predetermined connection relationship and being a positive integer equal to 1 or more, and % is modulus operator, and

each node determines, as the first destination node at time i, a node with the calculated destination node number.

11. The parallel computer system of claim 7 , wherein each node of the plurality of nodes is connected to only one network switch of the plurality of network switches.

12. A method of controlling a parallel computer system including a plurality of network switches in which each network switch of the plurality of network switches is directly connected to each other network switch of the plurality of network switches and a plurality of nodes in which each node of the plurality of nodes is directly connected to only one network switch of the plurality of network switches, the each network switch of the plurality of network switches being directly connected to two or more nodes of the plurality of nodes, the method comprising:

determining, by each node of the plurality of nodes, a first destination node of data, to be transmitted by the node performing the determination, at a given time so that a first destination network switch is different from a second network switch, the first destination network switch being a network switch of the plurality of network switches directly connected to the first destination node, the second network switch being a network switch of the plurality of network switches directly connected to a second destination node of data transmitted by a source node of the plurality of nodes other than the node performing the determination, and the source node being directly connected to a source network switch that is a network switch of the plurality of network switches to which the node performing the determination is directly connected; and

transmitting, by each node of the plurality of nodes, data to the determined first destination node, wherein

a number of nodes directly connected to each network switch of the plurality of network switches is a predetermined number of d, d being a positive integer equal to 1 or more,

a number of the plurality of network switches is the predetermined number of d, and

a number of the plurality of nodes is d 2 .

13. The method of claim 12 , wherein each node of the plurality of nodes is connected to only one network switch of the plurality of network switches.

14. An information processing apparatus serving as one node of a plurality of nodes in which each node of the plurality of nodes is directly connected to only one network switch of a plurality of network switches, the one network switch of the plurality of network switches being directly connected to two or more nodes of the plurality of nodes, the information processing apparatus comprising:

a processor configured to:

determine a first destination node of data, to be transmitted at a given time so that a first destination network switch is different from a second destination network switch, the first destination network switch being a network switch of the plurality of network switches directly connected to the first destination node, the second network switch being a network switch of the plurality of network switches directly connected to a second destination node of data transmitted by a source node of the plurality of nodes other than the one node, and the source node being directly connected to a source network switch that is a network switch of the plurality of network switches to which the one node is directly connected; and

transmit data to the determined first destination node; and

a memory coupled to the processor, the memory configured to store information identifying the information processing apparatus among the plurality of nodes, wherein

a number of nodes directly connected to each network switch of the plurality of network switches is a predetermined number of d, d being a positive integer equal to 1 or more,

a number of the plurality of network switches is the predetermined number of d, and

a number of the plurality of nodes is d 2 .

15. The information processing apparatus of claim 14 , wherein each node of the plurality of nodes is connected to only one network switch of the plurality of network switches.

16. A method of controlling a parallel computer system including a first plurality of first network switches, a second plurality of second network switches, and a plurality of nodes in which each node of the plurality of nodes is directly connected to only one network switch of the first plurality of first network switches, the method comprising:

directly connecting each node of the plurality of nodes to only one network switch of the first plurality of first network switches;

directly connecting each network switch of the second plurality of second network switches to at least two network switches out of the first plurality of first network switches;

directly connecting two or more nodes of the plurality of nodes to each network switch of the first plurality of first network switches;

connecting any two network switches out of the first plurality of first network switches via one network switch of the second plurality of second network switches;

determining, by each node of the plurality of nodes, a first destination node of data, to be transmitted by the node performing the determination, at a given time so that a first destination network switch is different from a second network switch, the first destination network switch being a network switch of the first plurality of first network switches directly connected to the first destination node, the second network switch being a network switch of the first plurality of first network switches directly connected to a second destination node of data transmitted by a source node of the plurality of nodes other than the node performing the determination, and the source node being directly connected to a source network switch that is a network switch of the first plurality of first network switches to which the node performing the determination is directly connected; and

transmitting, by the node of the plurality of nodes, data to the determined first destination node, wherein

a number of nodes directly connected to each network switch of the plurality of network switches is a predetermined number of d, d being a positive integer equal to 1 or more,

a number of the plurality of nodes is d 3 ,

a number of the plurality of first network switches is d 2 , and

a number of the second plurality of second network switches is a sum of d(d−1)/2 and an integer to which d/2 is rounded up.

17. The method of claim 16 , wherein the connecting each node of the plurality of nodes to one network switch of the plurality of first network switches comprises connecting each node of the plurality of nodes to only one network switch of the plurality of first network switches.