Patent ID: 7877573

Claim:
A method for performing a parallel prefix sum operation across a plurality of cooperative thread arrays (CTAs), the method comprising: partitioning an aggregate sequential list of data into a plurality of sequential lists of data that includes a first sequential list of data that is associated with a first CTA and second sequential list of data that is associated with a second CTA; partitioning the first sequential list of data into a first plurality of data sublists and partitioning the second sequential list of data into a second plurality of data sublists; performing a parallel prefix sum operation on the first plurality of data sublists to produce a first plurality of prefix sum sublists of data that include a first prefix sum sublist of data and a second prefix sum sublist of data, and performing a parallel prefix sum operation on the second plurality of data sublists to produce a second plurality of prefix sum sublists of data that include a third prefix sum sublist of data and a fourth prefix sum sublist of data, wherein a last element of the first prefix sum sublist of data comprises a first accumulated prefix sum sublist list value, wherein a last element of the second prefix sum sublist of data comprises a second accumulated prefix sum sublist value, wherein a last element of the third prefix sum sublist of data comprises a third accumulated prefix sum sublist value, and wherein a last element of the fourth prefix sum sublist of data comprises a fourth accumulated prefix sum sublist list value; performing a prefix sum operation across the first accumulated prefix sum sublist value and the second accumulated prefix sum sublist value to generate a first accumulated sum value and a second accumulated sum value and performing a prefix sum operation across the third accumulated prefix sum sublist value and the fourth accumulated prefix sum sublist value to generate a third accumulated sum value and a fourth accumulated sum value; adding the first accumulated sum value to each data element of the second prefix sum sublist of data to produce a fifth prefix sum sublist of data and adding the third accumulated sum value to each data element of the fourth prefix sum sublist of data to produce a sixth prefix sum sublist of data; performing a prefix sum operation to each of the first, second, third and fourth accumulated sum values to produce a first, a second, a third, and a fourth CTA accumulated sum value; adding the first CTA accumulated sum value to the fifth prefix sum sublist of data to produce a seventh prefix sum sublist of data, and adding the third CTA accumulated sum value to the sixth prefix sum sublist of data to produce an eighth prefix sum sublist of data, wherein a combination of the first, seventh, third and eighth prefix sum sublists of data is equivalent at least in part to a prefix sum operation over the aggregate sequential list of data.