Method and system for bin coalescing for parallel divide-and-conquer sorting algorithms
AssigneeNVIDIA Corporation
InventorDuane MERRILL
Life of this patent
Estimating the term…
Abstract
A system and method for performing sorting. The method includes partitioning a plurality of keys needing sorting into a first plurality of bins, wherein the bins are sequentially sorted. The plurality of keys is capable of being sorted into a sequence of keys using a corresponding ordering system. The method includes coalescing a first pair of consecutive bins, such that when coalesced the first pair of bins falls below a threshold. The method also includes ordering keys in the first coalesced pair to generate a first sub-sequence of keys in the sequence of keys.
Claims20
A non-transitory computer readable medium having computer executable instructions for causing a computer system to perform a method for sorting, wherein said method comprises:
- partitioning a plurality of keys needing sorting into a first plurality of bins that are sequentially sorted, wherein said plurality of keys is capable of being sorted into a sequence of keys using a corresponding ordering system;
- coalescing a first pair of consecutive bins, such that when coalesced said first pair of bins falls below a threshold;
- and
- ordering keys in said first coalesced pair to generate a first sub-sequence of keys in said sequence of keys.
A computer system comprising:
- a processor;
- and
- memory coupled to said processor and having stored therein instructions that, if executed by a computer system, causes said computer system to execute a method for sorting, comprising:
- partitioning a plurality of keys needing sorting into a first plurality of bins that are sequentially sorted, wherein said plurality of keys is capable of being sorted into a sequence of keys using a corresponding ordering system;
- coalescing a first pair of consecutive bins, such that when coalesced said first pair of bins falls below a threshold;
- and
- ordering keys in said first coalesced pair to generate a first sub-sequence of keys in said sequence of keys.
Dependencies are inferred from the claim text.