Method for vectorizing heapsort using horizontal aggregation simd instructions
AssigneeOracle International Corporation
InventorsBenjamin Schlegel, Pit Fender, Harshad Kasture, Matthias Brantner, Hassan Chafi
Life of this patent
Estimating the term…
Abstract
Techniques are provided for vectorizing Heapsort. A K-heap is used as the underlying data structure for indexing values being sorted. The K-heap is vectorized by storing values in a contiguous memory array containing a beginning-most side and end-most side. The vectorized Heapsort utilizes horizontal aggregation SIMD instructions for comparisons, shuffling, and moving data. Thus, the number of comparisons required in order to find the maximum or minimum key value within a single node of the K-heap is reduced resulting in faster retrieval operations.
Claims20
A method comprising:
- trueing a root node of a heap such that valid heap properties are maintained, the heap having a plurality of key values, wherein the plurality of key values are in a heap region within an original region of memory,
- wherein the heap comprises a plurality of nodes, each node of the plurality of nodes comprising K slots, wherein the plurality of nodes includes the root node and a plurality of parent nodes, each parent node of the plurality of parent nodes having K child nodes, each child node of the K child nodes being a child of a parent slot in a respective parent node;
- for multiple iterations:
- performing a SIMD operation to generate a minimum key value and an index of a root slot in a root node that holds the minimum key value;
- adding the minimum key value in a temporary array of size K, wherein all key values in the temporary array are added from the root node;
- moving a last key value at the end of the heap region into the root slot associated with the index;
- trueing the root slot such that valid heap properties are maintained;
- when the temporary array satisfies one or more criteria, moving all key values in the temporary array to a sorted region of the original region of memory formerly occupied by the heap region, thereby storing all keys in the sorted region in a numerical order.
One or more non-transitory storage media storing sequences of instructions which, when executed by one or more processors, cause:
- trueing a root node of a heap such that valid heap properties are maintained, the heap having a plurality of key values, wherein the plurality of key values are in a heap region within an original region of memory,
- wherein the heap comprises a plurality of nodes, each node of the plurality of nodes comprising K slots,
- wherein the plurality of nodes includes the root node and a plurality of parent nodes, each parent node of the plurality of parent nodes having K child nodes, each child node of the K child nodes being a child of a parent slot in a respective parent node;
- for multiple iterations:
- performing a SIMD operation to generate a minimum key value and an index of a root slot in a root node that holds the minimum key value;
- adding the minimum key value in a temporary array of size K, wherein all key values in the temporary array are added from the root node;
- moving a last key value at the end of the heap region into the root slot associated with the index;
- trueing the root slot such that valid heap properties are maintained;
- when the temporary array satisfies one or more criteria, moving all key values in the temporary array to a sorted region of the original region of memory formerly occupied by the heap region, thereby storing all keys in the sorted region in a numerical order.
Dependencies are inferred from the claim text.