Performing optimized collective operations in an irregular subcommunicator of compute nodes in a parallel computer

• US 10,382,527 B2
• Filed: 10/16/2013
• Issued: 08/13/2019
• Est. Priority Date: 10/16/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Davis, Kristan D., Faraj, Daniel A.
• Primary Examiner(s): Dollinger, Tonia L
• Assistant Examiner(s): Sayoc, Kristoffer L S
• Application Number:
  US14/055,402
• Publication Number:
  US 20150106419A1
• Time in Patent Office: 2,127 Days
• Field of Search: 709201, 709223, 709224
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

In a parallel computer, performing optimized collective operations in an irregular subcommunicator of compute nodes may be carried out by: identifying, within the irregular subcommunicator, regular neighborhoods of compute nodes; selecting, for each neighborhood from the compute nodes of the neighborhood, a local root node; assigning each local root node to a node of a neighborhood-wide tree topology; mapping, for each neighborhood, the compute nodes of the neighborhood to a local tree topology having, at its root, the local root node of the neighborhood; and performing a one way, rooted collective operation within the subcommunicator including: performing, in one phase, the collective operation within each neighborhood; and performing, in another phase, the collective operation amongst the local root nodes.

Claims

1. A method of performing optimized collective operations in an irregular subcommunicator of compute nodes in a parallel computer, the method comprising:

identifying, within the irregular subcommunicator of the compute nodes in the parallel computer, regular neighborhoods of compute nodes within the irregular subcommunicator of the compute nodes in the parallel computer, wherein the irregular subcommunicator of the compute nodes in the parallel computer has topological communication gaps and the regular neighborhoods of the compute nodes in the parallel computer are logical planes with no topological communication gaps in each neighborhood, wherein identifying regular neighborhoods of compute nodes within the irregular subcommunicator of the compute nodes in the parallel computer comprises;

establishing, by each respective compute node within the irregular subcommunicator of the compute nodes in the parallel computer, at least one logical plane that includes the respective compute node, wherein establishing the at least one logical plane comprises;

identifying, in a positive direction of a first dimension, each logical plane that includes the respective compute node, a first compute node of the irregular subcommunicator that is one or more hops away from the respective compute node in a positive direction of a second dimension, wherein the second dimension is orthogonal to the first dimension;

identifying, in a negative direction of the first dimension, each logical plane that includes the respective compute node and a second compute node of the irregular subcommunicator that is one or more hops away from the respective compute node in the positive direction of the second dimension;

selecting, for each neighborhood from the compute nodes of the neighborhood, a local root node;

assigning each local root node to a node of a neighborhood-wide tree topology;

mapping, for each neighborhood, the compute nodes of the neighborhood to a local tree topology having, at its root, the local root node of the neighborhood; and

performing a one way, rooted collective operation within the irregular subcommunicator including;

performing, in one phase, the collective operation within each neighborhood and performing in another phase, the collective operation amongst the local root nodes.

2. The method of claim 1, wherein:

performing the one way, rooted collective operation further comprises performing a gather operation;

performing the collective operation within each neighborhood further comprises performing a gather operation within each neighborhood in a first phase; and

performing the collective operation amongst the local root nodes further comprises performing a gather operation amongst the local root nodes in a second phase.

3. The method of claim 1, wherein:

performing the one way, rooted collective operation further comprises performing a broadcast operation;

performing the collective operation amongst the local root nodes further comprises performing a broadcast operation amongst the local root nodes in a first phase beginning at the root node of the neighborhood-wide tree topology; and

performing the collective operation within each neighborhood further comprises performing a broadcast operation within each neighborhood in a second phase beginning, within each neighborhood, at the local root node of the neighborhood.

4. The method of claim 1, wherein:

performing the one way, rooted collective operation further comprises performing a reduce operation;

performing the collective operation within each neighborhood further comprises performing a reduce operation within each neighborhood in a first phase, including performing an arithmetic or logical function on contribution data of the reduce operation within the neighborhood; and

performing the collective operation amongst the local root nodes further comprises performing a reduce operation amongst the local root nodes in a second phase including performing the arithmetic or logical function on contribution data of the reduce operation amongst the local root nodes.

5. The method of claim 1, wherein performing the one way, rooted collective operation further comprises performing an allgather operation comprising a gather operation followed by a broadcast operation.

6. The method of claim 1, wherein performing the one way, rooted collective operation further comprises performing an allreduce operation comprising a reduce operation followed by a broadcast operation.

7. An apparatus for performing optimized collective operations in an irregular subcommunicator of compute nodes in a parallel computer, the apparatus comprising a computer processor, a computer memory operatively coupled to the computer processor, the computer memory having disposed within it computer program instructions that, when executed, cause the apparatus to carry out the steps of:

identifying, within the irregular subcommunicator of the compute nodes in the parallel computer, regular neighborhoods of compute nodes within the irregular subcommunicator of the compute nodes in the parallel computer, wherein the irregular subcommunicator of the compute nodes in the parallel computer has topological communication gaps and the regular neighborhoods of the compute nodes in the parallel computer are logical planes with no topological communication gaps in each neighborhood, wherein identifying regular neighborhoods of compute nodes within the irregular subcommunicator of the compute nodes in the parallel computer comprises;

establishing, by each respective compute node within the irregular subcommunicator of the compute nodes in the parallel computer, at least one logical plane that includes the respective compute node, wherein establishing the at least one logical plane comprises;

identifying, in a positive direction of a first dimension, each logical plane that includes the respective compute node, a first compute node of the irregular subcommunicator that is one or more hops away from the respective compute node in a positive direction of a second dimension, wherein the second dimension is orthogonal to the first dimension;

identifying, in a negative direction of the first dimension, each logical plane that includes the respective compute node and a second compute node of the irregular subcommunicator that is one or more hops away from the respective compute node in the positive direction of the second dimension;

selecting, for each neighborhood from the compute nodes of the neighborhood, a local root node;

assigning each local root node to a node of a neighborhood-wide tree topology;

mapping, for each neighborhood, the compute nodes of the neighborhood to a local tree topology having, at its root, the local root node of the neighborhood; and

performing a one way, rooted collective operation within the irregular subcommunicator including;

performing, in one phase, the collective operation within each neighborhood and performing in another phase, the collective operation amongst the local root nodes.

8. The apparatus of claim 7, wherein:

performing the one way, rooted collective operation further comprises performing a gather operation;

performing the collective operation within each neighborhood further comprises performing a gather operation within each neighborhood in a first phase; and

performing the collective operation amongst the local root nodes further comprises performing a gather operation amongst the local root nodes in a second phase.

9. The apparatus of claim 7, wherein:

performing the one way, rooted collective operation further comprises performing a broadcast operation;

performing the collective operation amongst the local root nodes further comprises performing a broadcast operation amongst the local root nodes in a first phase beginning at the root node of the neighborhood-wide tree topology; and

performing the collective operation within each neighborhood further comprises performing a broadcast operation within each neighborhood in a second phase beginning, within each neighborhood, at the local root node of the neighborhood.

10. The apparatus of claim 7, wherein:

performing the one way, rooted collective operation further comprises performing a reduce operation;

performing the collective operation within each neighborhood further comprises performing a reduce operation within each neighborhood in a first phase, including performing an arithmetic or logical function on contribution data of the reduce operation within the neighborhood; and

performing the collective operation amongst the local root nodes further comprises performing a reduce operation amongst the local root nodes in a second phase including performing the arithmetic or logical function on contribution data of the reduce operation amongst the local root nodes.

11. The apparatus of claim 7, wherein performing the one way, rooted collective operation further comprises performing an allgather operation comprising a gather operation followed by a broadcast operation.

12. The apparatus of claim 7, wherein performing the one way, rooted collective operation further comprises performing an allreduce operation comprising a reduce operation followed by a broadcast operation.

13. A computer program product for performing optimized collective operations in an irregular subcommunicator of compute nodes in a parallel computer, the computer program product disposed upon a non-transitory computer readable medium, the computer program product comprising computer program instructions that, when executed, cause a computer to carry out the steps of:

identifying, within the irregular subcommunicator of the compute nodes in the parallel computer, regular neighborhoods of compute nodes within the irregular subcommunicator of the compute nodes in the parallel computer, wherein the irregular subcommunicator of the compute nodes in the parallel computer has topological communication gaps and the regular neighborhoods of the compute nodes in the parallel computer are logical planes with no topological communication gaps in each neighborhood, wherein identifying regular neighborhoods of compute nodes within the irregular subcommunicator of the compute nodes in the parallel computer comprises;

establishing, by each respective compute node within the irregular subcommunicator of the compute nodes in the parallel computer, at least one logical plane that includes the respective compute node, wherein establishing the at least one logical plane comprises;

identifying, in a positive direction of a first dimension, each logical plane that includes the respective compute node, a first compute node of the irregular subcommunicator that is one or more hops away from the respective compute node in a positive direction of a second dimension, wherein the second dimension is orthogonal to the first dimension;

identifying, in a negative direction of the first dimension, each logical plane that includes the respective compute node and a second compute node of the irregular subcommunicator that is one or more hops away from the respective compute node in the positive direction of the second dimension;

selecting, for each neighborhood from the compute nodes of the neighborhood, a local root node;

assigning each local root node to a node of a neighborhood-wide tree topology;

mapping, for each neighborhood, the compute nodes of the neighborhood to a local tree topology having, at its root, the local root node of the neighborhood; and

performing a one way, rooted collective operation within the irregular subcommunicator including;

performing, in one phase, the collective operation within each neighborhood and performing in another phase, the collective operation amongst the local root nodes.

14. The computer program product of claim 13, wherein:

performing the one way, rooted collective operation further comprises performing a gather operation;

performing the collective operation within each neighborhood further comprises performing a gather operation within each neighborhood in a first phase; and

performing the collective operation amongst the local root nodes further comprises performing a gather operation amongst the local root nodes in a second phase.

15. The computer program product of claim 13, wherein:

performing the one way, rooted collective operation further comprises performing a broadcast operation;

performing the collective operation amongst the local root nodes further comprises performing a broadcast operation amongst the local root nodes in a first phase beginning at the root node of the neighborhood-wide tree topology; and

performing the collective operation within each neighborhood further comprises performing a broadcast operation within each neighborhood in a second phase beginning, within each neighborhood, at the local root node of the neighborhood.

16. The computer program product of claim 13, wherein:

performing the one way, rooted collective operation further comprises performing a reduce operation;

performing the collective operation within each neighborhood further comprises performing a reduce operation within each neighborhood in a first phase, including performing an arithmetic or logical function on contribution data of the reduce operation within the neighborhood; and

performing the collective operation amongst the local root nodes further comprises performing a reduce operation amongst the local root nodes in a second phase including performing the arithmetic or logical function on contribution data of the reduce operation amongst the local root nodes.

17. The computer program product of claim 13, wherein performing the one way, rooted collective operation further comprises performing an allgather operation comprising a gather operation followed by a broadcast operation.

18. The computer program product of claim 13, wherein performing the one way, rooted collective operation further comprises performing an allreduce operation comprising a reduce operation followed by a broadcast operation.