Patent ID: 7725518

Claim:
A method for performing a parallel prefix sum operation, the method comprising: partitioning an input list of data elements into a plurality of sub-lists that includes a first sub-list and a second sub-list, wherein the first and second sub-lists have a size of K*(J+1)+L data elements, and wherein K is an interleave size of a local memory structure, (J+1) is a number of threads concurrently processing sub-lists, and L is a factor; performing, by threads executing within a processing core, a first prefix sum operation on the first sub-list to generate a first intermediate prefix sum sub-list, and performing a second prefix sum operation on the second sub-list to generate a second intermediate prefix sum sub-list, wherein a last element of the first intermediate prefix sum sub-list comprises a first sub-list accumulated sum value, and a last element of the second intermediate prefix sum sub-list comprises a second sub-list accumulated sum value; performing, by threads executing within the processing core, a second prefix sum operation across the first and second sub-list accumulated sum values to generate a first accumulated sum value and a second accumulated sum value; and adding, by threads executing within the processing core, the first accumulated sum value to each data element of the second intermediate prefix sum sub-list to produce a third intermediate prefix sum sub-list, wherein a combination of the first intermediate prefix sum sub-list and the third intermediate prefix sum sub-list is equivalent to a prefix sum over the first sub-list and the second sub-list.