Back to results
US 12,619,553 B2Granted
Method and apparatus to sort a vector for a bitonic sorting algorithm
AssigneeTexas Instruments Incorporated
InventorsTimothy David Anderson, Mujibur Rahman
Life of this patent
Estimating the term…
Abstract
A method is provided that includes performing, by a processor in response to a vector sort instruction, sorting of values stored in lanes of the vector to generate a sorted vector, wherein the values in a first portion of the lanes are sorted in a first order indicated by the vector sort instruction and the values in a second portion of the lanes are sorted in a second order indicated by the vector sort instruction; and storing the sorted vector in a storage location.
Claims20
A method comprising:
- first sorting, by a processing circuit in response to executing a first instruction, a first half of a set of vector values in a first direction;
- second sorting, by the processing circuit in response to executing a second instruction, a second half of the set of vector values in a second direction;
- generating, by the processing circuit in response to the first sorting and the second sorting, a first sorted set of vector values;
- moving, by a vector permutation logic circuit in the processing circuit, a first half of the first sorted set of vector values to a second half of a first output vector;
- moving, by the vector permutation logic circuit in the processing circuit, a second half of the first sorted set of vector values to a first half of the first output vector;
- comparing, by the processing circuit in response to executing a third instruction, the first sorted set of vector values with the first output vector to generate a second output vector and a third output vector;
- moving, by the vector permutation logic circuit in the processing circuit, a second half of the third output vector to a second half of a fourth output vector;
- moving, by the vector permutation logic circuit in the processing circuit, a first half of the second output vector to a first half of the fourth output vector;
- third sorting, by the processing circuit in response to executing the first instruction, a first half of the fourth output vector in the first direction;
- fourth sorting, by the processing circuit in response to executing the first instruction, a second half of the fourth output vector in a fourth direction;
- and
- outputting, by the processing circuit in response to the third sorting and the fourth sorting, a second sorted set of vector values.
9 more elements
A non-transitory computer-readable medium having executable instructions stored thereon, configured to be executable by one or more processors for causing the one or more processors to:
- perform a first sort of a first half of a set of vector values in a first direction in response to executing a first instruction;
- perform a second sort of a second half of the set of vector values in a second direction in response to executing a second instruction;
- generate a first sorted set of vector values based on the first sort and the second sort;
- move, using a vector permutation logic circuit, a first half of the first sorted set of vector values to a second half of a first output vector;
- move, using the vector permutation logic circuit, a second half of the first sorted set of vector values to a first half of the first output vector;
- compare the first sorted set of vector values with the first output vector to generate a second output vector and a third output vector in response to executing a third instruction;
- move, using the vector permutation logic circuit, a second half of the third output vector to a second half of a fourth output vector;
- move, using the vector permutation logic circuit, a first half of the second output vector to a first half of the fourth output vector;
- perform a third sort of the first half of the fourth output vector in a third direction in response to executing the first instruction;
- perform a fourth sort of the second half of the fourth output vector in a fourth direction in response to executing the first instruction;
- and
- generate a second sorted set of vector values based on the third sort and the fourth sort.
9 more elements
A system comprising:
- a processing circuit configurable to:
- perform a first sort of a first half of a set of vector values in a first direction in response to executing a first instruction;
- perform a second sort of a second half of the set of vector values in a second direction in response to executing a second instruction;
- and
- generate a first sorted set of vector values in response to the first sort and the second sort;
- and
- a vector permutation logic circuit coupled to the processing circuit and configurable to:
- move a first half of the first sorted set of vector values to a second half of a first output vector;
- and
- move a second half of the first sorted set of vector values to a first half of the first output vector,
- wherein the processing circuit is configurable to compare the first sorted set of vector values with the first output vector to generate a second output vector and a third output vector in response to executing a third instruction,
- wherein the vector permutation logic circuit is configurable to:
- move a second half of the third output vector to a second half of a fourth output vector;
- and
- move a first half of the second output vector to a first half of the fourth output vector, and
- wherein the processing circuit is configurable to:
- perform a third sort of a first half of the fourth output vector in the first direction;
- perform a fourth sort of a second half of the fourth output vector in a fourth direction;
- and
- output a second sorted set of vector values in response to the third sorting and the fourth sorting.
17 more elements
Dependencies are inferred from the claim text.