# US 2015/0106419 A1 · Performing optimized collective operations in an irregular subcommunicator of compute nodes in a parallel computer

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0106419 A1
- Document ID: US20150106419A1
- Status: Published application
- Kind: A1
- Application number: 14/055,402
- Filed: 2013-10-16
- Published: 2015-04-16
- Earliest claimed: 2013-10-16
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Kristan D. Davis; Daniel A. Faraj
- Web page: https://patentgrep.com/patent/US20150106419A1

## CPC

- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- 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)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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, 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 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, 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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 7)

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.

### Claim 11 (depends on 7)

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.

### Claim 12 (depends on 7)

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.

### Claim 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 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, 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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 13)

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.

### Claim 16 (depends on 13)

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.

### Claim 17 (depends on 13)

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.

### Claim 18 (depends on 13)

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.
