METHOD AND SYSTEM OF NETWORK TRANSFER ADAPTIVE OPTIMIZATION IN LARGE-SCALE PARALLEL COMPUTING SYSTEM

• US 20130144973A1
• Filed: 11/26/2012
• Published: 06/06/2013
• Est. Priority Date: 12/01/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: LI, Yan, LIN, Hai Bo, ZHANG, Yue, ZHENG, Kai
• Granted Patent: US 9,369,350 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3017 where the computing system is implementing multitasking multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3065 Monitoring arrangements determined by the means or processing involved in reporting the monitored data error or fault reporting or logging G06F11/0766
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/26 using dedicated tools for LAN [Local Area Network] management
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 67/1004 Server selection for load balancing

Abstract

A method and system for performing network transfer adaptive optimization in a large-scale parallel computing system. The method of network transfer adaptive optimization includes forming a message to be transferred through the network based on obtained information related to a task executed by computing nodes, wherein the message includes identification information of the computing nodes to perform data transfer and corresponding sink nodes, and an amount of data the computing nodes to transfer to the corresponding sink nodes; transferring the message to a network layer; and forming a new data transfer pattern for data transfer between the computing nodes and the corresponding sink nodes in accordance with the received message.

Claims

1. A method of network transfer adaptive optimization in a large-scale parallel computing system, the method comprising:

forming a message to be transferred through the network based on obtained information related to a task executed by computing nodes, wherein the message includes identification information of the computing nodes to perform data transfer and corresponding sink nodes, and an amount of data said computing nodes to transfer to said corresponding sink nodes;

transferring said message to a network layer; and

forming a new data transfer pattern for data transfer between said computing nodes and said corresponding sink nodes in accordance with a received message.

2. The method of network transfer adaptive optimization according to claim 1, wherein said forming a new data transfer pattern for data transfer between said computing nodes and said corresponding sink nodes includes:

determining whether locations of said sink nodes are needed to be adjusted in accordance with network information of the network layer and the received message; and

if it is determined that the locations of said sink nodes are needed to be adjusted, replacing the sink nodes in said message with re-selected sink nodes.

3. The method of network transfer adaptive optimization according to claim 2, wherein said replacing the sink nodes in said message with the re-selected sink nodes includes:

replacing the sink nodes in said message in turn from a most preferred selected sink node, and when the amount of data of the replaced sink nodes reaches a capacity of the most preferred selected sink node, continuing to replace the sink nodes in said message with a secondarily preferred selected sink node.

4. The method of network transfer adaptive optimization according to claim 2, wherein said determining whether the locations of said sink nodes are needed to be adjusted includes:

calculating a sum of distances from each location at which a sink node may be located in said large-scale parallel computing system to each of all the computing nodes;

selecting a desired number of locations in turn from a possible location with a smallest distance as the locations of said sink nodes; and

if the selected locations are different from the locations indicated by identification information of the sink nodes included in said message, determining that the adjustment is required.

5. The method of network transfer adaptive optimization according to claim 4, wherein said sum of distances is a weighted sum after weighting the distances using the amount of data.

6. The method of network transfer adaptive optimization according to claim 3, wherein said message further includes a task attribute of said task, said task attribute indicating whether multicast is required by said task, and

wherein said method further comprises:

if said message indicates that multicast is required by said task, setting a multicast group, by a network engine, directed to each computing node and all the sink nodes.

7. The method of network transfer adaptive optimization according to claim 1, wherein said forming a new data transfer pattern for data transfer between said computing nodes and said corresponding sink nodes includes:

re-selecting a data transfer path between said computing nodes and said corresponding sink nodes in accordance with network information of said network layer and the received message.

8. The method of network transfer adaptive optimization according to claim 7, wherein said re-selecting a data transfer path between said computing nodes and said corresponding sink nodes includes:

marking each link between said computing nodes and said corresponding sink nodes in said message using said amount of data as a load;

calculating a weight value of the load for each link based on acquired network information; and

selecting the data transfer path between said computing nodes and said corresponding sink nodes based on the weight value of the load.

9. The method of network transfer adaptive optimization according to claim 8, wherein the weight value of the load is calculated from a sum of a current link load indicated by the acquired network information and a ratio of the load and bandwidth as marked for the link.

10. The method of network transfer adaptive optimization according to claim 8, further comprising:

if said message indicates that multicast is required by said task, creating a multicast tree from each computing node indicated in said message to all the sink nodes; and

for the multicast tree, executing re-selection of said data transfer path.

11. The method of network transfer adaptive optimization according to claim 8, wherein said selecting the data transfer path between said computing nodes and said corresponding sink nodes is further based on a shortest path between said computing nodes and said corresponding sink nodes.

12. The method of network transfer adaptive optimization according to claim 1, further comprising:

deciding whether said task is a shuffle critical task; and

if said task is not the shuffle critical task, ignoring said task thereby to ignore information related to said task.

13. The method of network transfer adaptive optimization according to claim 1, wherein said forming a message to be transferred through the network includes:

formatting the obtained information to form a message in a predetermined format, and wherein said predetermined format is;

<

total number of triplets>

{one or more <

computing node IDs, sink node IDs, size of amount of data>

},

wherein the total number of triplets indicates the number of triplets <

computing node ID, sink node ID, size of amount of data>

in the message.

14. The method of network transfer adaptive optimization according to claim 1, wherein said forming a new data transfer pattern includes:

filtering the received message to remove the computing nodes with a smaller amount of data and the corresponding sink nodes from said message, and

wherein said method of network transfer adaptive optimization further comprises;

feeding back information related to the formed new data transfer pattern to said computing nodes.

15. An apparatus of network transfer adaptive optimization in a large-scale parallel computing system, comprising:

an application engine configured to form a message to be transferred through a network based on obtained information related to a task executed by computing nodes, wherein the message includes identification information of the computing nodes to perform data transfer and corresponding sink nodes, and an amount of data said computing nodes to transfer to said corresponding sink nodes; and

a network engine configured to form a new data transfer pattern for the data transfer between said computing nodes and said corresponding sink nodes in accordance with a message received from the application engine.

16. The apparatus of network transfer adaptive optimization according to claim 15, wherein said application engine includes:

a network interface configured to receive said information; and

a formatter configured to format the obtained said information to form a message in a predefined format, and

wherein said predefined format is;

<

total number of triplets>

{one or more <

computing node IDs, sink node IDs, size of amount of data>

},

wherein the total number of triplets indicates the number of triplets <

computing node ID, sink node ID, size of amount of data>

in the message.

17. The apparatus of network transfer adaptive optimization according to claim 15, wherein said network engine includes:

an adjuster configured to determine whether locations of said sink nodes are needed to be adjusted in accordance with network information of a network layer of the network and in accordance with the message received, and if it is determined that the locations of said sink nodes are needed to be adjusted, replace the sink nodes in said message with re-selected sink nodes.

18. The apparatus of network transfer adaptive optimization according to claim 15, wherein said message further includes a task attribute of said task, said task attribute indicating whether multicast is required by said task, and

wherein said network engine comprises:

a multicast setter configured to, if said message indicates that multicast is required by said task, setting a multicast group, by a network engine, directed to each computing node and all the sink nodes.

19. The apparatus of network transfer adaptive optimization according to claim 15, wherein said network engine further includes:

a path selector configured to re-select a data transfer path between said computing nodes and said corresponding sink nodes in accordance with network information of a network layer of the network and in accordance with the message received.

20. The apparatus of network transfer adaptive optimization according to claim 19, wherein said path selector further includes:

group-divider configured to group said computing nodes so that said path selector selects the data transfer path directed to a root node in each group and said corresponding sink nodes.

21. A computer program product for network transfer adaptive optimization in a large-scale parallel computing system, the computer program product comprising:

a non-transitory computer readable medium; and

computer program instructions for

forming a message to be transferred through the network based on obtained information related to a task executed by computing nodes, wherein the message includes identification information of the computing nodes to perform data transfer and corresponding sink nodes, and an amount of data said computing nodes to transfer to said corresponding sink nodes,

transferring said message to a network layer, and

forming a new data transfer pattern for data transfer between said computing nodes and said corresponding sink nodes in accordance with the received message.