# US 2023/0054136 A1 · Processing device for a parallel computing system and method for performing collective operations

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

- Number: US 2023/0054136 A1
- Document ID: US20230054136A1
- Status: Published application
- Kind: A1
- Application number: 17/980,851
- Filed: 2022-11-04
- Published: 2023-02-23
- Earliest claimed: 2020-05-08
- Applicants: Huawei Technologies Co., Ltd.
- Inventors: Solal AMOUYAL; Alex MARGOLIN; Ben-Shahar BELKAR
- Web page: https://patentgrep.com/patent/US20230054136A1

## CPC

- 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)}
- G06F 8/452: {Loops}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The disclosure relates to a parallel computing system comprising a plurality of processing devices for performing an application. Each processing device is configured to obtain a local result, wherein a global result of a collective operation depends on the local results of the plurality of processing devices, and to distribute the local result of the processing device to one or more of the other processing devices, in response to determining that the global result is based only on the local result of the processing device, that is a likelihood that the global result is based only on the local result of the processing device is greater than a likelihood threshold value, or that the global result is based only on the local result of the processing device and a further local result of a further processing device of the plurality of processing devices.

## Claims

### Claim 1

A processing device for a parallel computing system, wherein the parallel computing system comprises a plurality of processing devices for performing an application, including one or more collective operations, wherein the processing device is configured to:
obtain a local processing result, wherein a global processing result of a collective operation depends on the local processing results of the plurality of processing devices; and
distribute the local processing result of the processing device to one or more of the other processing devices in response to determining that:
(a) the global processing result of the collective operation is based only on the local processing result of the processing device;
(b) a likelihood that the global processing result of the collective operation is based only on the local processing result of the processing device is greater than a likelihood threshold value; or
(c) the global processing result of the collective operation is based only on the local processing result of the processing device and a further local processing result of a further processing device of the plurality of processing devices.

### Claim 2 (depends on 1)

The processing device of claim 1, further configured to broadcast the local processing result of the processing device to the other processing devices in response to determining that the global processing result of the collective operation is based on the local processing result of the processing device.

### Claim 3 (depends on 2)

The processing device of claim 2, wherein the collective operation is a logical or bitwise “AND” operation or a logical or bitwise “OR” operation.

### Claim 4 (depends on 1)

The processing device of claim 1, wherein the collective operation is a logical or bitwise “XOR” operation, and wherein the processing device is further configured to broadcast the local processing result of the processing device to the other processing devices (201) in response to determining that the global processing result of the collective operation is based only on the local processing result of the processing device and the further local processing result of the further processing device.

### Claim 5 (depends on 4)

The processing device of claim 4, further configured to receive the further local processing result from the further processing device and to perform the logical or bitwise “XOR” operation based on the local processing result of the processing device and the further local processing result of the further processing device.

### Claim 6 (depends on 1)

The processing device of claim 1, further configured to distribute the local processing result of the processing device to a selected subset of the other processing devices for performing the collective operation with the selected subset of the other processing devices, wherein, for each processing device of the selected subset of the other processing devices, a likelihood that the global result of the collective operation is based only on the local processing result of the processing device is greater than a likelihood threshold value.

### Claim 7 (depends on 6)

The processing device of claim 6, wherein the parallel computing system is configured to adjust the selected subset during a run-time of the application.

### Claim 8 (depends on 6)

The processing device of claim 6, further configured to store, for each collective operation of the application, at least one of the global processing result of the collective operation or an identifier of the processing device providing the global processing result of the collective operation.

### Claim 9 (depends on 8)

The processing device of claim 8, further configured to determine the likelihood that the global result of the collective operation is based only on the local processing result of the processing device based on a comparison between the local processing result and one or more global processing results stored for one or more preceding collective operations of the application.

### Claim 10 (depends on 6)

The processing device of claim 6, wherein the collective operation is a maximum operation for obtaining a maximum of the local processing results of the plurality of processing devices or a minimum operation for obtaining a minimum of the local results of the plurality of processing devices.

### Claim 11 (depends on 6)

The processing device of claim 6, further configured to execute an iterative loop and to terminate the iterative loop based on a conditional statement depending on the global processing result of the collective operation.

### Claim 12 (depends on 11)

The processing device of claim 11, further configured to broadcast the local processing result of the processing device to the other processing devices in response to determining that the global processing result of the collective operation is based only on the local processing result of the processing device and the global processing result of the collective operation triggers the processing device to terminate the iterative loop.

### Claim 13 (depends on 11)

The processing device of claim 11, further configured to store, for the iterative loop, at least one of a number of iterations before terminating the iterative loop or a threshold value defined by the conditional statement for terminating the iterative loop.

### Claim 14 (depends on 13)

The processing device of claim 13, further configured to:
determine a likelihood that the conditional statement of the iterative loop is fulfilled in a further iteration of the iterative loop;
broadcast the local processing result of the processing device to the other processing devices; and
terminate the iterative loop in response to determining that the likelihood that the conditional statement is fulfilled in a further iteration of the iterative loop is greater than a likelihood threshold value.

### Claim 15 (depends on 14)

The processing device of claim 14, further configured to determine the likelihood that the conditional statement of the iterative loop is fulfilled in a further iteration of the iterative loop based on the stored number of iterations for terminating one or more preceding iterative loops.

### Claim 16 (depends on 14)

The processing device of claim 14, further configured, in case the conditional statement of the iterative loop is not fulfilled in a further iteration of the iterative loop, to continue executing the iterative loop in response to determining that the likelihood that the conditional statement is fulfilled in a further iteration of the iterative loop is greater than a likelihood threshold value.

### Claim 17 (depends on 11)

The processing device of claim 11, wherein the collective operation is a sum operation of the plurality of local processing results.

### Claim 18

A parallel computing system comprising a plurality of processing devices, wherein each processing device in the plurality of processing devices is configured to:
obtain a local processing result, wherein a global processing result of a collective operation depends on the local processing results of the plurality of processing devices; and
distribute the local processing result of the processing device to one or more of the other processing devices of the plurality of processing devices in response to determining that:
(a) the global processing result of the collective operation is based only on the local processing result of the processing device;
(b) a likelihood that the global processing result of the collective operation is based only on the local processing result of the processing device is greater than a likelihood threshold value; or
(c) the global processing result of the collective operation is based only on the local processing result of the processing device and a further local processing result of a further processing device of the plurality of processing devices.

### Claim 19 (depends on 18)

The parallel computing system of claim 18, wherein the plurality of processing devices are configured to define a tree topology.

### Claim 20

A method for performing an application, including one or more collective operations, in a parallel computing system having a plurality of processing devices, wherein, for each processing device, the method comprises:
obtaining a local processing result, wherein a global processing result of a collective operation depends on one or more of the local processing results of the plurality of processing devices; and
distributing the local processing result of the processing device to one or more of the other processing devices in response to determining that:
(a) the global processing result of the collective operation is based only on the local processing result of the processing device;
(b) a likelihood that the global processing result of the collective operation is based only on the local processing result of the processing device is greater than a likelihood threshold value; or
(c) the global processing result of the collective operation is based only on the local processing result of the processing device and a further local processing result of a further processing device of the plurality of processing devices.
