Sorting elements in a memory array by comparing element vectors
AssigneeImagination Technologies Limited
InventorFabrizio Cabaleiro
Life of this patent
Estimating the term…
Abstract
A method comprising comparing pairs of elements in an array. The method comprises generating two new vectors from an original array in memory, each comprising one part of each pair to be compared. The two new vectors are compared to generate a mask which indicates which of each pair of elements is less. Based on the mask, elements of the vectors can be swapped as necessary. This could be using a XOR algorithm or a merge algorithm. The vectors are then written back to the original array in memory. This process can be repeated on elements of an array as part of a bitonic sorting algorithm.
Claims20
A machine implemented method of sorting a plurality of elements in a first array in memory, using vector instructions in a CPU, the method comprising:
- generating, by a CPU, a first vector with elements of the first array specified by a first reference vector, the first vector having the first elements of each pair of elements to be compared;
- generating, by a CPU, a second vector with elements of the first array specified by a second reference vector, the second vector having the second elements of each pair of elements to be compared;
- comparing, by a CPU, respective elements of the first vector and the second vector to generate a mask to indicate which of the respective elements of the first and second vector is more or less;
- processing the first vector and the second vector to swap the positions of only elements of the first vector and second vector indicated by the mask;
- and
- sorting the plurality of elements in said first array into an order determined by the processing of the first and second vectors.
Dependencies are inferred from the claim text.