Sorting for data-parallel computing devices
AssigneeGoogle Inc.
InventorAllan Stuart Mackinnon, JR.
Life of this patent
Estimating the term…
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 385A-385B, wherein each register is associated with at least one parallel processor in a group of parallel processors 380A-380B. 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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.