Patent Document ID: 7953684
Application ID: 11669600
Patent Flag: 1

Claim One:
1. A method implemented by processors in a parallel computing environment for performing large message global reduce operations at a plurality of N′ processes each having at least one input data vector, comprising the steps of: dividing the N′ processes into two subgroups, S 0 and S 1 , where S 0 comprises 2*r processes and S 1 comprises N′−2*r processes, where r=N′−N, with N being the largest power of two less than N′; performing paired data exchange and local reduce operations at the processes in S 0 , whereby r processes in S 0 obtain partial reduce results of first half vectors and the other r processes in S 0 obtain partial reduce results of second half vectors; consolidating the half vectors of the partial reduce result into a set of remaining processes, said set comprising N processes; wherein if r is an even integer, said consolidating comprises: sending the partial reduce results of the first half vector from r sending processes of S 0 to r receiving processes of S 0 , where the sending and receiving processes have partial reduce results of a same half of the vector; performing local reduce operations at said receiving processes, whereby each receiving process has a half vector of partial reduce results; and performing paired exchange and local reduce operations at the processes of S 1 , whereby half processes in S 1 have partial reduce results of the first half vector and the rest of the processes have partial reduce results of the second half vector; wherein if r is an odd integer, said consolidating comprises: dividing the S 0 processes into r−1 sending processes, r−1 receiving processes and two other processes; sending half vectors of partial reduce results from r−1 sending processes of S 0 to r−1 receiving processes of S 0. said sending and receiving processes have partial reduce results of a same half vector; performing local reduce operations at said r−1 receiving processes, whereby each receiving process has a half vector of partial reduce results; and sending the half vector of partial reduce results from the first said other process of S 0 to a process of S 1 ; sending the other half vector of input data from the process of S 1 to the second said other process of S 0 ; performing local reduce operations at said process of S 1 and said second other process of S 0 , whereby each process has partial reduce results of a half vector; and performing paired exchange and local reduce operations at the rest of the processes of S 1 , whereby half of the rest of the processes in S 1 have partial reduce results of a first half vector and the other half of the processes in S 1 have partial reduce results of a second half vector; performing successive recursive halving and recursive doubling at the set of remaining processes until each process in the set of remaining process has a half vector of the complete reduce results; and providing a full vector of the complete reduce results at every process.