Opportunistic queueing injection strategy for network load balancing

• US 7,944,842 B2
• Filed: 04/20/2007
• Issued: 05/17/2011
• Est. Priority Date: 04/20/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ratterman, Joseph D., Blocksome, Michael A., Smith, Brian E., Archer, Charles J.
• Primary Examiner(s): Juntima; Nittaya
• Assistant Examiner(s): PHAM, TITO Q
• Application Number:
  US11/738,034
• Publication Number:
  US 20080259916A1
• Time in Patent Office: 1,488 Days
• Field of Search: None
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/243 using M+N parallel active paths
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

Embodiments of the invention include a method, system, and article of manufacture that provide opportunistic queuing injection strategy used for data communication between nodes of a parallel computer system. A message may be encapsulated into a set of data packets. When the packets are sent, an opportunistic injection queue may be configured to transmit them to multiple hardware injection ports. This approach allows for complete network link saturation. In a parallel system with network links in multiple dimensions, sending message packets using more than one dimension may substantially increase network throughput.

Claims

1. A method of transmitting a message between a sending node and a receiving node of a parallel computing system, comprising:

encapsulating the message in a set of one or more data packets;

determining in how many network dimensions to transmit the set of data packets from the sending node to the receiving node based on relative positions of the receiving node and the sending node in the parallel computing system and a load of at least one network dimension;

transmitting the set of data packets from an injection queue to a plurality of hardware injection ports, wherein each hardware injection port is associated with a different communication link of the parallel computing system, and wherein each communication link of the sending node links the sending node to other nodes of the parallel computing system in a different network dimension of the multiple network dimensions; and

injecting the set of data packets onto the different communication links of the sending node.

2. The method of claim 1, wherein the compute nodes of the parallel computing system are linked using a plurality of point-to-point links.

3. The method of claim 2, wherein the plurality of point-to-point links forms a multi-dimensional torus.

4. The method of claim 1, wherein the sending node and the receiving node are in a same network plane, and wherein the set of data packets are transmitted from the sending node over communication links in two dimensions.

5. The method of claim 1, wherein the sending node and the receiving node are in different network planes, and wherein the set of data packets are transmitted from the sending node over communication links in three dimensions.

6. The method of claim 1, wherein the message is constructed according to the message passing interface (MPI) specification.

7. The method of claim 1, wherein the set of data packets arrive at the receiving node out of sequence, and wherein the receiving node is configured to reconstruct the message from the set of data packets.

8. A non-transitory computer-readable storage medium containing a program which, when executed, performs an operation of transmitting a message between a sending node and a receiving node of a parallel computing system, comprising:

encapsulating the message in a set of one or more data packets;

determining in how many network dimensions to transmit the set of data packets from the sending node to the receiving node based on relative positions of the receiving node and the sending node in the parallel computing system and a load of at least one network dimension;

transmitting the set of data packets from an injection queue to a plurality of hardware injection ports, wherein each hardware injection port is associated with a different communication link of the parallel computing system, and wherein each communication link of the sending node links the sending node to other nodes of the parallel computing system in a different network dimension of the multiple network dimensions; and

injecting the set of data packets onto the different communication links of the sending node.

9. The non-transitory computer-readable storage medium of claim 8, wherein the compute nodes of the parallel computing system are linked using a plurality of point-to-point links.

10. The non-transitory computer-readable storage medium of claim 9, wherein the plurality of point-to-point links forms a multi-dimensional torus.

11. The non-transitory computer-readable storage medium of claim 8, wherein the sending node and the receiving node are in a same network plane, and wherein the set of data packets are transmitted from the sending node over communication links in two dimensions.

12. The non-transitory computer-readable storage medium of claim 8, wherein the sending node and the receiving node are in different network planes, and wherein the set of data packets are transmitted from the sending node over communication links in three dimensions.

13. The non-transitory computer-readable storage medium of claim 8, wherein the message is constructed according to the message passing interface (MPI) specification.

14. The non-transitory computer-readable storage medium of claim 8, wherein the set of data packets arrive at the receiving node out of sequence, and wherein the receiving node is configured to reconstruct the message from the set of data packets.

15. A parallel computing system, comprising:

a plurality of compute nodes, each having at least;

a processor; and

a memory;

wherein a sending node, of the plurality of compute nodes, is configured to transmit a message to a receiving node, of the plurality of compute nodes, by;

generating a message to transmit from a sending node to a receiving node, of the encapsulating the message in a set of one or more data packets,

determining in how many network dimensions in which to transmit the set of data packets from the sending node to the receiving node based on relative positions of the receiving node and the sending node in the parallel computing system and a load of at least one network dimension;

transmitting the set of data packets from an injection queue to a plurality of hardware injection ports, wherein each hardware injection port is associated with a different communication link of the parallel computing system, and wherein each communication link of the sending node links the sending node to other nodes of the parallel computing system in a different network dimension of the multiple network dimensions; and

injecting the set of data packets onto the different communication links of the sending node.

16. The system of claim 15, wherein the compute nodes of the parallel computing system are linked using a plurality of point-to-point links.

17. The system of claim 16, wherein the plurality of point-to-point links forms a multi-dimensional torus.

18. The system of claim 15, wherein the sending node and the receiving node are in a same network plane, and wherein the set of data packets are transmitted from the sending node over communication links in two dimensions.

19. The system of claim 15, wherein the sending node and the receiving node are in different network planes, and wherein the set of data packets are transmitted from the sending node over communication links in three dimensions.

20. The system of claim 15, wherein the message is constructed according to the message passing interface (MPI) specification.

21. The system of claim 15, wherein the set of data packets arrive at the receiving node out of sequence, and wherein the receiving node is configured to reconstruct the message from the set of data packets.