Sorting for data-parallel computing devices

Abstract

Aspects of the disclosure relate to determining relevant content in response to a request for information. One or more computing devices 170 may load data elements into registers 385 A- 385 B, wherein each register is associated with at least one parallel processor in a group of parallel processors 380 A- 380 B. For each of the parallel processors, the data elements loaded in its associated registers may be sorted, in parallel, in descending order. The sorted data elements, for each of the parallel processors, may be merged with the sorted data elements of other processors in the group. The merged and sorted data elements may be transposed and stored.

1 . A method for sorting data in parallel on a computing device comprising:
 defining, for the computing device, one or more grids, each grid including a plurality of processor groups, each processor group including a set of parallel processors associated with a shared memory;   loading, by each group according to a slab load kernel, data elements into a slab associated with that group, the associated slab having a set of registers, the data elements being loaded in a transposed order, wherein each register is associated with at least one parallel processor in the group;   for each of the parallel processors in the group, sorting, in parallel, the data elements loaded in the registers of the associated slab in descending order;   for each of the parallel processors, merging the sorted data elements with the sorted data elements of other processors in the group; and   storing, by the parallel processors for each processor group of each grid, the merged and sorted data elements.   
     
     
         2 . The method of  claim 1 , wherein the size of the slab is defined by the number of processors in the processor group and the number of registers in the slab. 
     
     
         3 . The method of  claim 1 , wherein the loaded data elements are sorted sequentially within a single processor of the group, with each single processor sorting the data elements in its respective registers simultaneously. 
     
     
         4 . The method of  claim 1 , wherein merging the sorted data elements of a single processor of the group with the sorted data elements of other processors in the group includes partitioning rows of the registers in the slab and writing into the shared memory by each processor in the processor group. 
     
     
         5 . The method of  claim 1 , further comprising merging each sorted slab of a group together. 
     
     
         6 . The method of  claim 1 , wherein each processor group is controlled by a same instruction at any point in time. 
     
     
         7 . The method of  claim 1 , wherein each slab of a group is generated simultaneously or concurrently. 
     
     
         8 . The method of  claim 1 , wherein loading the data elements in the transposed order includes not performing either inter-processor communication or processor rank comparison operations. 
     
     
         9 . The method of  claim 1 , wherein multiple slabs of each group are sorted simultaneously. 
     
     
         10 . The method of  claim 1 , wherein merging the sorted data elements with the sorted data elements of other processors in the group includes partitioning rows of the registers in a predetermined manner according to one or more device hardware or performance characteristics. 
     
     
         11 . The method of  claim 1 , wherein merging the sorted data elements with the sorted data elements of other processors in the group includes merging a predefined number of slabs in the group in parallel. 
     
     
         12 . A system for sorting data in parallel comprising:
 one or more computing devices having one or more grids, each grid including a plurality of processor groups, each processor group including a set of parallel processors;   a plurality of shared memories, each shared memory being associated with a given one of the plurality of processor groups; and   a slab load kernel executable by the one or more computing devices, the slab load kernel having instructions comprising:   wherein the instructions comprise:
 loading, by each group, data elements into a slab associated with that group, the associated slab having a set of registers, the data elements being loaded in a transposed order, wherein each register is associated with at least one parallel processor in the group; 
 for each of the parallel processors in the group, sorting, in parallel, the data elements loaded in the registers of the associated slab in descending order; 
 for each of the parallel processors, merging the sorted data elements with the sorted data elements of other processors in the group; and 
 storing, by the parallel processors for each processor group of each grid, the merged and sorted data elements. 
   
     
     
         13 . The system of  claim 12 , wherein the one or more computing devices are graphics processing units. 
     
     
         14 . The system of  claim 12 , further comprising an application programming interface that controls the loading, sorting and merging via access to the slab load kernel. 
     
     
         15 . The system of  claim 12 , wherein merging the sorted data elements with the sorted data elements of other processors in the group includes merging a predefined number of slabs in the group in parallel. 
     
     
         16 . The system of  claim 12 , wherein the size of the slab is defined by the number of processors in the processor group and the number of registers in the slab. 
     
     
         17 . The system of  claim 12 , wherein the loaded data elements are sorted sequentially within a single processor of the group, with each single processor sorting the data elements in its respective registers simultaneously. 
     
     
         18 . A non-transitory computer readable medium comprising instructions, which when executed by one or more processors, cause the one or more processors to perform the steps of:
 defining one or more grids, each grid including a plurality of processor groups, each processor group including a set of parallel processors associated with a shared memory;   loading, by each group according to a slab load kernel, data elements into a slab associated with that group, the associated slab having a set of registers, the data elements being loaded in a transposed order, wherein each register is associated with at least one parallel processor in the group;   for each of the parallel processors in the group, sorting, in parallel, the data elements loaded in the registers of the associated slab in descending order;   for each of the parallel processors, merging the sorted data elements with the sorted data elements of other processors in the group; and   storing, by the parallel processors for each processor group of each grid, the merged and sorted data elements.   
     
     
         19 . The non-transitory computer readable medium of  claim 18 , wherein merging the sorted data elements with the sorted data elements of other processors in the group includes merging a predefined number of slabs in the group in parallel. 
     
     
         20 . The non-transitory computer readable medium of  claim 18 , wherein the size of the slab is defined by at least one of the number of processors in the processor group or the number of registers in the slab.