Topology-Aware Fabric-Based Offloading of Collective Functions

• US 20110113083A1
• Filed: 11/11/2009
• Published: 05/12/2011
• Est. Priority Date: 11/11/2009
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Voltaire Limited (NVIDIA Corporation)
• Inventors: Shahar, Yiftah
• Granted Patent: US 9,110,860 B2
• Time in Patent Office: Days
• US Class Current: 709/201
• CPC Class Codes: G06F 15/17393 having multistage networks, e.g. broadcasting scattering, gathering, hot spot contention, combining/decombining
• 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 49/356 for storage area networks
• CPC Class Codes: H04L 49/358 Infiniband Switches

Abstract

A computing method includes accepting a notification of a computing task for execution by a group of compute nodes interconnected by a communication network, which has a given interconnection topology and includes network switching elements. A set of preferred paths, which connect the compute nodes in the group via at least a subset of the network switching elements to one or more root switching elements, are identified in the communication network based on the given interconnection topology and on a criterion derived from the computing task. The network switching elements in the subset are configured to forward node-level results of the computing task produced by the compute nodes in the group to the root switching elements over the preferred paths, so as to cause the root switching elements to calculate and output an end result of the computing task based on the node-level results.

Claims

1. A computing method, comprising:

accepting a notification of a computing task for execution by a group of compute nodes interconnected by a communication network, which has a given interconnection topology and includes network switching elements;

identifying, based on the given interconnection topology and on a criterion derived from the computing task, a set of preferred paths in the communication network that connect the compute nodes in the group via at least a subset of the network switching elements to one or more root switching elements; and

configuring the network switching elements in the subset to forward node-level results of the computing task produced by the compute nodes in the group to the root switching elements over the preferred paths, so as to cause the root switching elements to calculate and output an end result of the computing task based on the node-level results.

2. The method according to claim 1, wherein determining the preferred paths comprises selecting one or more of the network switching elements to serve as the root switching elements.

3. The method according to claim 1, wherein determining the preferred paths comprises selecting two or more root switching elements, and comprising configuring a given compute node to receive two or more end results from the respective root switching elements and to reduce the two or more end results to a single end result.

4. The method according to claim 1, wherein configuring the network switching elements comprises causing a given network switching element in the subset to reduce a respective portion of the node-level results forwarded thereto to a single interim result, and to forward the interim result to one of the root switching elements.

5. The method according to claim 1, wherein configuring the network switching elements comprises notifying a Central Processing Unit (CPU) in a given network switching element in the subset of an identity of another switching element to which the node-level results are to be forwarded, so as to cause the CPU to configure a switching fabric in the given network switching element to forward the node-level results to the other switching element.

6. The method according to claim 1, and comprising configuring a given compute node in the group to reduce multiple results of the computing task produced in the given compute node, so as to produce a single node-level result, and to forward the single node-level result to one of the root switching elements.

7. The method according to claim 1, wherein configuring the network switching elements comprises configuring the root switching elements to forward the end result to a specified compute node.

8. The method according to claim 1, wherein configuring the network switching elements comprises configuring the root switching elements to forward the end result to all the compute nodes in the group.

9. The method according to claim 1, and comprising detecting a change in the interconnection topology, and modifying the set of the preferred paths responsively to the detected change.

10. The method according to claim 1, wherein the computing task comprises a Message Passing Interface (MPI) function.

11. A computing method, comprising:

for a computing task that is assigned for execution by a group of compute nodes, receiving multiple node-level results of the computing task from the compute nodes by two or more network switching elements that are different from the compute nodes assigned to execute the computing task;

reducing a respective portion of the node-level results received in each network switching element to produce a respective single interim result, and forwarding the interim results to one or more root switching elements; and

computing and outputting an end result of the computing task by the root switching elements.

12. The method according to claim 11, wherein the computing task specifies an operation to be performed by each of the compute nodes in the group on respective local data, and wherein reducing the node-level results comprises performing the specified operation on the respective portion of the node-level results by each of the switching elements, so as to produce the interim results.

13. A computing apparatus, comprising:

an interface coupled to communicate with a communication network, which includes network switching elements that interconnect compute nodes according to a given interconnection topology; and

a processor, which is configured to accept a notification of a computing task for execution by a group of the compute nodes, to identify, based on the given interconnection topology and on a criterion derived from the computing task, a set of preferred paths in the communication network that connect the compute nodes in the group via at least a subset of the network switching elements to one or more root switching elements, and to configure the network switching elements in the subset to forward node-level results of the computing task produced by the compute nodes in the group to the root switching elements over the preferred paths, so as to cause the root switching elements to calculate and output an end result of the computing task based on the node-level results.

14. The apparatus according to claim 13, wherein the processor is configured to select one or more of the network switching elements to serve as the root switching elements.

15. The apparatus according to claim 13, wherein the processor is configured to select two or more root switching elements, and to configure a given compute node to receive two or more end results from the respective root switching elements and to reduce the two or more end results to a single end result.

16. The apparatus according to claim 13, wherein the processor is configured to cause a given network switching element in the subset to reduce a respective portion of the node-level results forwarded to the given network switching element to a single interim result and forward the interim result to the root switching elements.

17. The apparatus according to claim 13, wherein the processor is configured to notify a Central Processing Unit (CPU) in a given network switching element in the subset of an identity of another switching element to which the node-level results are to be forwarded, so as to cause the CPU to configure a switching fabric in the given network switching element to forward the node-level results to the other switching element.

18. The apparatus according to claim 13, wherein the processor is configured to configure a given compute node in the group to reduce multiple results of the computing task produced in the given compute node, so as to produce a single node-level result, and forward the single node-level result to the root switching elements.

19. The apparatus according to claim 13, wherein the processor is configured to detect a change in the interconnection topology, and to modify the set of the preferred paths responsively to the detected change.

20. A computing system comprising two or more network switching elements, which are configured to receive multiple node-level results of a computing task that is assigned for execution by a group of compute nodes different from the switches, to reduce a respective portion of the node-level results received in each network switching element to produce a respective single interim result, and to forward the interim results to one or more root switching elements so as to cause the root switching elements to compute and output an end result of the computing task.

21. The system according to claim 20, wherein the computing task specifies an operation to be performed by each of the compute nodes in the group on respective local data, and wherein each network switching element is configured to reduce the node-level results by performing the specified operation on the respective portion of the node-level results received at the network switching element.