SIMD instruction sorting pre-sorted source register's data elements into a first ascending order destination register and a second descending destination register
View Patent ↗A computer-implemented method is provided for performing bitonic merge operations. The computer-implemented includes receiving a plurality of first values in a first hardware register from a first input stream in ascending order, receiving a plurality of second values in a second hardware register from a second input stream in descending order, performing a bitonic merge operation on the first and second values in the first and second hardware registers, and reversing comparison operations performed by one or more comparators in the bitonic merge operation, outputs of the one or more comparators being loaded into the second hardware register so that output values of the second hardware register are arranged in descending order and placed into an output stream.
1. A computer-implemented method executed with a processor for performing merge operations by a sorting module, the method comprising:
performing, by the processor, a merge operation on a plurality of smaller values received in a first hardware register from a first input stream in ascending order and a plurality of larger values received in a second hardware register from a second input stream in descending order; and
reversing, by the processor, comparison operations performed by one or more comparators in the merge operation, outputs of the one or more comparators being loaded into the first and second hardware registers so that, concurrently, a first portion of the smaller value outputs are arranged in ascending order and a second portion of the larger value outputs are arranged in descending order and both outputs are concurrently placed into a single output stream.
2. The method of claim 1 , wherein outputs of the comparison operations are reversed.
3. The method of claim 1 , wherein a reverse operation instruction is prevented in each iteration.
4. The method of claim 1 , wherein a reverse operation instruction is performed when the second values are read from a memory.
5. The method of claim 1 , wherein the merge operations are implemented with Single Instruction Multiple Data (SIMD) instructions.
6. The method of claim 1 , wherein the output values of the second hardware register are arranged in a different order than output values of the first hardware register.
7. A computer system for performing merge operations, the computer system comprising:
a memory; and
at least one processor in communication with the memory, wherein the computer system is configured to:
perform, by the processor, a merge operation on a plurality of smaller values received in a first hardware register from a first input stream in ascending order and a plurality of larger values received in a second hardware register from a second input stream in descending order; and
reverse, by the processor, comparison operations performed by one or more comparators in the merge operation, outputs of the one or more comparators being loaded into the first and second hardware registers so that, concurrently, a first portion of the smaller value outputs are arranged in ascending order and a second portion of the larger value outputs are arranged in descending order and both outputs are concurrently placed into a single output stream.
8. The computer system of claim 7 , wherein outputs of the comparison operations are reversed.
9. The computer system of claim 7 , wherein a reverse operation instruction is prevented in each iteration.
10. The computer system of claim 7 , wherein a reverse operation instruction is performed when the second values are read from a memory.
11. The computer system of claim 7 , wherein the merge operations are implemented with Single Instruction Multiple Data (SIMD) instructions.
12. The computer system of claim 7 , wherein the output values of the second hardware register are arranged in a different order than output values of the first hardware register.
13. A non-transitory computer readable storage medium comprising a computer readable program for performing merge operations, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
performing, by the processor, a merge operation on a plurality of smaller values received in a first hardware register from a first input stream in ascending order and a plurality of larger values received in a second hardware register from a second input stream in descending order; and
reversing, by the processor, comparison operations performed by one or more comparators in the merge operation, outputs of the one or more comparators being loaded into the first and second hardware registers so that, concurrently, a first portion of the smaller value outputs are arranged in ascending order and a second portion of the larger value outputs are arranged in descending order and both outputs are concurrently placed into a single output stream.
14. The computer readable storage medium of claim 13 , wherein outputs of the comparison operations are reversed.
15. The computer readable storage medium of claim 13 , wherein a reverse operation instruction is prevented in each iteration.
16. The computer readable storage medium of claim 13 , wherein a reverse operation instruction is performed when the second values are read from a memory.
17. The computer readable storage medium of claim 13 , wherein the merge operations are implemented with Single Instruction Multiple Data (SIMD) instructions.