Patent ID: 7752421

Claim:
A method for parallel-prefix broadcast for a parallel-prefix operation on a parallel computer, the parallel computer comprising a plurality of compute nodes, the plurality of compute nodes organized into at least one operational group of compute nodes for collective parallel operations of the parallel computer, each compute node in the at least one operational group assigned a unique rank, and the at least one operational group coupled for data communications through a global combining network, the method comprising: configuring, on each ranked compute node, a parallel-prefix contribution buffer for storing a parallel-prefix contribution of the ranked compute node; configuring, on each ranked compute node, a parallel-prefix results buffer for storing results of a parallel-prefix operation, the parallel-prefix results buffer having a position for each compute node that corresponds to the rank of the compute node; and repeatedly for each position in the parallel-prefix results buffer: processing in parallel by each ranked compute node in the at least one operational group, including: determining, by the ranked compute node, whether a current position in the parallel-prefix results buffer is to include a contribution of the ranked compute node, if the current position in the parallel-prefix results buffer is not to include the contribution of the ranked compute node, contributing an identity element for the parallel-prefix operation, and if the current position in the parallel-prefix results buffer is to include the contribution of the ranked compute node, contributing the parallel-prefix contribution of the ranked compute node for the parallel-prefix operation, performing, by each ranked compute node, the parallel-prefix operation using the contributed identity elements and the contributed parallel-prefix contributions, yielding a result from the parallel-prefix operation, and storing, by each ranked compute node, the result in the position in the parallel-prefix results buffer.