US 12,769,701 B2 · In-network parallel prefix scan

Abstract

Methods and apparatus for in-network parallel prefix scan. In one aspect, a dual binary tree topology is embedded in a network to compute prefix scan calculations as data packets traverse the binary tree topology. The dual binary tree topology includes up and down aggregation trees. Input values for a prefix scan are provided at leaves of the up tree. Prefix scan operations such as sum, multiplication, max, etc. are performed at aggregation nodes within the up tree as packets containing associated data propagate from the leaves to the root of the up tree. Output from aggregation nodes in the up tree are provide as input to aggregation nodes in the down tree. In the down tree, the packets containing associated data propagate from the root to its leaves. Output values for the prefix scan are provided at the leaves of the down tree.

Claims18

Dependent claims

A method for performing a prefix scan computation, comprising:

implementing first and second binary aggregation trees in a feed-forward network topology;
inserting input array values in leaves of the first binary aggregation tree;
performing prefix scan operations at nodes in the first and second binary aggregation trees in conjunction with routing data along edges in the first and the second binary aggregation trees to compute output values for the prefix scan;
and
providing the output values of the prefix scan at leaves of the second binary aggregation tree.

2 more elements

A system comprising:

a network comprising a plurality of interconnected switches having collective engines;
a plurality of cores, coupled to the network;
and
a memory, operatively coupled to the plurality of cores,
wherein the system is configured to,
insert, via a portion of the plurality of cores, an array of input values for which a prefix scan is to be performed,
perform the prefix scan for the array of input values using the collective engines within the network to generate a prefix scan result;
and
output values in the prefix scan result to a portion of the plurality of cores,
wherein a dual binary tree topology including a plurality of nodes comprising the collective engines is embedded in the network to compute prefix scan operations at the plurality of the nodes using the collective engines,
wherein the dual binary tree topology comprises an up tree having a first plurality of the nodes and including a first plurality of leaves and a first root, wherein input values for the prefix scan are provided as inputs at the first plurality of leaves and a first set of the prefix scan operations are performed at the first plurality of the nodes as data propagates from the first plurality of leaves toward the root of the up tree.

8 more elements

Dependencies are inferred from the claim text.

In-network parallel prefix scan

Life of this patent

In-network parallel prefix scan

Life of this patent

Abstract

Claims18