Method for vectorizing Heapsort using horizontal aggregation SIMD instructions
US11016778B2 · kind B2 · utility
0Cited by
5References
20Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Mar 12, 2019 |
| Grant date | May 25, 2021 |
| Priority date | — |
| Expiry date | Mar 12, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/3887
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.