# US 2011/0238956 A1 · Collective Acceleration Unit Tree Structure

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

- Number: US 2011/0238956 A1
- Document ID: US20110238956A1
- Status: Published application
- Kind: A1
- Application number: 12/749,100
- Filed: 2010-03-29
- Published: 2011-09-29
- Earliest claimed: 2010-03-29
- Assignees: International Business Machines Corporation
- Inventors: Lakshminarayana B. Arimilli; Bernard C. Drerup; Paul F. Lecocq; Hanhong Xue
- Web page: https://patentgrep.com/patent/US20110238956A1

## CPC

- G06F 15/17318: {Parallel communications techniques, e.g. gather, scatter, reduce, roadcast, multicast, all to all}
- H04L 12/56: {Packet switching systems}
- H04L 45/02: Topology update or discovery
- H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)}
- H04L 61/30: Managing network names, e.g. use of aliases or nicknames (name-to-address mapping H04L61/45)
- H04L 61/3015: Name registration, generation or assignment
- H04L 61/4552: Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- H04L 69/329: in the application layer [OSI layer 7]
- H04L 45/306: {Route determination based on the nature of the carried application}
- Y10S 707/9994: Distributed or remote access
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A mechanism is provided in a collective acceleration unit for performing a collective operation to distribute or collect data among a plurality of participant nodes. The mechanism receives an input collective packet for a collective operation from a neighbor node within a collective tree. The input collective packet comprises a tree identifier and an input data field and wherein the collective tree comprises a plurality of sub trees. The mechanism maps the tree identifier to an index within the collective acceleration unit. The index identifies a portion of resources within the collective acceleration unit and is associated with a set of neighbor nodes in a given sub tree within the collective tree. For each neighbor node the collective acceleration unit stores destination information. The collective acceleration unit performs an operation on the input data field using the portion of resources to effect the collective operation.

## Claims

### Claim 1

A method, in a data processing system, for performing a collective operation to distribute or collect data among a plurality of participant nodes, the method comprising:
receiving, in a collective acceleration unit, an input collective packet for a collective operation from a neighbor node within a collective tree, wherein the input collective packet comprises a tree identifier and an input data field and wherein the collective tree comprises a plurality of sub trees;
mapping, by the collective acceleration unit, the tree identifier to an index, wherein the index identifies a portion of resources within the collective acceleration unit and is associated with a set of neighbor nodes in a given sub tree within the collective tree, and wherein for each neighbor node the collective acceleration unit stores destination information; and
performing, by the collective acceleration unit, an operation on the input data field using the portion of resources to effect the collective operation.

### Claim 2 (depends on 1)

The method of claim 1, wherein mapping the tree identifier to the index comprises looking up the tree identifier in a content addressable memory.

### Claim 3 (depends on 1)

The method of claim 1, wherein the portion of resources comprises an arithmetic logic unit and a portion of buffer space in the collective acceleration unit.

### Claim 4 (depends on 3)

The method of claim 3, wherein performing the operation on the input data field comprises storing the input data field in the portion of buffer space for the index.

### Claim 5 (depends on 3)

The method of claim 3, wherein performing the operation on the input data field comprises receiving a previous result data field from the portion of buffer space for the index associated with the collective operation and using the arithmetic logic unit to perform an arithmetic operation on the previous result data field and the input data field to form a current result data field and storing the current result data field in the portion of buffer space for the index.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
selecting a destination neighbor node from the set of neighbor nodes;
generating an output collective packet based on a result of the operation, wherein the output collective packet comprises destination information for the destination neighbor node; and
sending the output collective packet to the destination neighbor node.

### Claim 7 (depends on 6)

The method of claim 6, wherein selecting the destination neighbor node comprises:
setting a destination neighbor select value; and
providing the destination neighbor select value to a first multiplexer, wherein the first multiplexer selects a sub identifier corresponding to the destination neighbor node; and
providing the destination neighbor select value to a second multiplexer, wherein the second multiplexer selects a destination identifier corresponding to the destination neighbor node,
wherein the destination information for the destination neighbor node comprises the selected sub identifier and the destination identifier corresponding to the destination neighbor node.

### Claim 8 (depends on 7)

The method of claim 7, wherein the tree identifier comprises an inclusive portion that is unique for the collective tree and a sub tree portion that is unique for the index and wherein the sub tree portion comprises a sub identifier.

### Claim 9 (depends on 8)

The method of claim 8, wherein generating the output collective packet comprises:
combining the inclusive portion of the tree identifier with the selected sub identifier to form a new tree identifier.

### Claim 10 (depends on 9)

The method of claim 9, wherein generating the output collective packet comprises:
combining the new tree identifier, the selected destination identifier, and the result of the operation to form the output collective packet.

### Claim 11

A data processing system, comprising:
a plurality of processor nodes; and
a network interface communicatively coupled to at least one of the plurality of processor nodes,
wherein the network interface comprises a collective acceleration unit,
wherein the collective acceleration unit comprises a storage device;
wherein the collective acceleration unit is configured to receive an input collective packet for a collective operation from a neighbor node within a collective tree, wherein the input collective packet comprises a tree identifier and an input data field and wherein the collective tree comprises a plurality of sub trees;
wherein the collective acceleration unit is configured to map the tree identifier to an index within the collective acceleration unit, wherein the index identifies a portion of resources within the collective acceleration unit and is associated with a set of neighbor nodes in a given sub tree within the collective tree, and wherein for each neighbor node the collective acceleration unit stores destination information; and
wherein the collective acceleration unit is configured to perform an operation on the input data field using the portion of resources to effect the collective operation.

### Claim 12 (depends on 11)

The data processing system of claim 11, wherein the collective acceleration unit comprises a content addressable memory and wherein mapping the tree identifier to the index comprises looking up the tree identifier in the content addressable memory.

### Claim 13 (depends on 11)

The data processing system of claim 11, wherein the portion of resources comprises an arithmetic logic unit and a portion of the storage device in the collective acceleration unit.

### Claim 14 (depends on 13)

The data processing system of claim 13, wherein performing the operation on the input data field comprises storing the input data field in the portion of the storage device for the index.

### Claim 15 (depends on 13)

The data processing system of claim 13, wherein performing the operation on the input data field comprises receiving a previous result data field from the portion of the storage device for the index associated with the collective operation and using the arithmetic logic unit to perform an arithmetic operation on the previous result data field and the input data field to form a current result data field and storing the current result data field in the portion of the storage device for the index.

### Claim 16 (depends on 11)

The data processing system of claim 11, wherein the collective acceleration unit is further configured to:
select a destination neighbor node from the set of neighbor nodes;
generate an output collective packet based on a result of the operation, wherein the output collective packet comprises destination information for the destination neighbor node; and
send the output collective packet to the destination neighbor node.

### Claim 17 (depends on 16)

The data processing system of claim 16, wherein selecting the destination neighbor node comprises:
setting a destination neighbor select value; and
providing the destination neighbor select value to a first multiplexer, wherein the first multiplexer selects a sub identifier corresponding to the destination neighbor node; and
providing the destination neighbor select value to a second multiplexer, wherein the second multiplexer selects a destination identifier corresponding to the destination neighbor node,
wherein the destination information for the destination neighbor node comprises the selected sub identifier and the destination identifier corresponding to the destination neighbor node.

### Claim 18 (depends on 17)

The data processing system of claim 17, wherein the tree identifier comprises an inclusive portion that is unique for the collective tree and a sub tree portion that is unique for the index and wherein the sub tree portion comprises a sub identifier.

### Claim 19 (depends on 18)

The data processing system of claim 18, wherein generating the output collective packet comprises:
combining the inclusive portion of the tree identifier with the selected sub identifier to form a new tree identifier.

### Claim 20 (depends on 19)

The data processing system of claim 19, wherein generating the output collective packet comprises:
combining the new tree identifier, the selected destination identifier, and the result of the operation to form the output collective packet.

### Claim 21

A collective acceleration unit, comprising:
a separating component;
a content addressable memory;
a storage device; and
an arithmetic logic unit,
wherein the separating component is configured to receive an input collective packet for a collective operation from a neighbor node within a collective tree and separate the input collective packet into a tree identifier and an input data field, wherein the collective tree comprises a plurality of sub trees;
wherein the content addressable memory is configured to map the tree identifier to an index within the collective acceleration unit, wherein the index identifies a portion of resources within the collective acceleration unit and is associated with a set of neighbor nodes in a given sub tree within the collective tree, and wherein for each neighbor node the collective acceleration unit stores destination information; and
wherein the arithmetic logic unit is configured to perform an operation on the input data field to effect the collective operation.

### Claim 22 (depends on 21)

The collective acceleration unit of claim 21, wherein the portion of resources comprises the arithmetic logic unit and a portion of the storage device.

### Claim 23 (depends on 22)

The collective acceleration unit of claim 22, wherein performing the operation on the input data field comprises storing the input data field in the portion of the storage device for the index.

### Claim 24 (depends on 22)

The collective acceleration unit of claim 22, wherein performing the operation on the input data field comprises receiving a previous result data field from the portion of the storage device for the index associated with the collective operation, performing an arithmetic operation on the previous result data field and the input data field to form a current result data field, and storing the current result data field in the portion of the storage device for the index.

### Claim 25 (depends on 21)

The collective acceleration unit of claim 21, wherein the collective acceleration unit further comprises an arbiter, and wherein the collective acceleration unit is configured to:
select a destination neighbor node from the set of neighbor nodes; and
generate an output collective packet based on a result of the operation, wherein the output collective packet comprises destination information for the destination neighbor node,
wherein the arbiter is configured to send the output collective packet to the destination neighbor node.

### Claim 26 (depends on 25)

The collective acceleration unit of claim 25, wherein the collective acceleration unit comprises a first multiplexer and a second multiplexer and wherein selecting the destination neighbor node comprises:
setting a destination neighbor select value;
providing the destination neighbor select value to the first multiplexer, wherein the first multiplexer selects a sub identifier corresponding to the destination neighbor node; and
providing the destination neighbor select value to the second multiplexer, wherein the second multiplexer selects a destination identifier corresponding to the destination neighbor node,
wherein the destination information for the destination neighbor node comprises the selected sub identifier and the destination identifier corresponding to the destination neighbor node.

### Claim 27 (depends on 26)

The collective acceleration unit of claim 26, wherein the tree identifier comprises an inclusive portion that is unique for the collective tree and a sub tree portion that is unique for the index and wherein the sub tree portion comprises a sub identifier.

### Claim 28 (depends on 27)

The collective acceleration unit of claim 27, wherein the collective acceleration unit comprises a first combining component and wherein the first combining component is configured to combine the inclusive portion of the tree identifier with the selected sub identifier to form a new tree identifier.

### Claim 29 (depends on 28)

The collective acceleration unit of claim 28, wherein the collective acceleration unit comprises a second combining component and wherein the second combining component is configured to combine the new tree identifier, the selected destination identifier, and the result of the operation to form the output collective packet.

### Claim 30

A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a collective acceleration unit, causes the collective acceleration unit to:
receive, in the collective acceleration unit, an input collective packet for a collective operation from a neighbor node within a collective tree, wherein the input collective packet comprises a tree identifier and an input data field and wherein the collective tree comprises a plurality of sub trees;
map, by the collective acceleration unit, the tree identifier to an index within the collective acceleration unit, wherein the index identifies a portion of resources within the collective acceleration unit and is associated with a set of neighbor nodes in a given sub tree within the collective tree, and wherein for each neighbor node the collective acceleration unit stores destination information; and
perform, by the collective acceleration unit, an operation on the input data field using the portion of resources to effect the collective operation.

### Claim 31 (depends on 30)

The computer program product of claim 30, wherein the computer readable program is stored in a computer readable storage medium in a data processing system and wherein the computer readable program was downloaded over a network from a remote data processing system.

### Claim 32 (depends on 30)

The computer program product of claim 30, wherein the computer readable program is stored in a computer readable storage medium in a server data processing system and wherein the computer readable program is downloaded over a network to a remote data processing system for use in a computer readable storage medium with the remote system.
