Patent ID: 7624107
Filing Date: 2009-11-24
Classification: G06F,Y10S

Abstract:
1. A method for performing a radix sort operation, the method comprising: associating a first thread group with a first set of sort keys and a second thread group with a second set of sort keys, wherein each thread in the first thread group corresponds to a different one of the sort keys in the first set of sort keys, and each thread in the second thread group corresponds to a different one of the sort keys in the second set of sort keys, and wherein each sort key comprises an identical number of sub-keys; selecting a first sub-key for each thread in the first thread group and for each thread in the second thread group; determining a value for the first sub-key for each thread in the first thread group; tabulating a first number of occurrences of each radix symbol in a plurality of radix symbols based on the values of the first sub-key determined for the threads in the first thread group, wherein each radix symbol corresponds to a different sub-key value; determining a value for the first sub-key for each thread in the second thread group; tabulating a second number of occurrences of each radix symbol in the plurality of radix symbols based on the values of the first sub-key determined for the threads in the second thread group; performing a prefix sum operation across each radix symbol and the first number of occurrences of the radix symbol and the second number of occurrences of the radix symbol to produce a first prefix sum output list; modifying the first prefix sum output list to produce a first set of prefix sum offsets; and reordering data associated with the sort keys based on the first set of prefix sum offsets to produce a first set of reordered data.