Merging and sorting arrays on an SIMD processor

1. A method comprising:

splitting an input array into multiple sub-arrays across multiple processing elements;

merging the multiple sub-arrays into multiple vectors, wherein each of the multiple vectors contains one element from each of the multiple sub-arrays;

sorting the multiple vectors by comparing and swapping one or more vector elements among the multiple vectors, wherein said comparing and said swapping comprises performing a set of compare-swap instructions on a first set of one or more registers, and wherein the number of compare-swap instructions in the set of compare-swap instructions is represented as NlogN+1, wherein N is a predetermined value; and

writing-back results of said sorting on a second set of one or more registers;

wherein said splitting, said merging, said sorting, and said writing-back are carried out by at least one computing device.

2. The method of claim 1 , wherein said sorting comprises sorting the multiple vectors via an odd-even network.

3. The method of claim 2 , comprising:

applying the odd-even network directly across the multiple vectors.

4. The method of claim 1 , wherein said sorting comprises sorting the multiple vectors via a bitonic network.

5. The method of claim 4 , comprising:

applying the bitonic network directly across the multiple vectors.

6. The method of claim 1 , comprising:

selecting a sub-array size.

7. The method of claim 6 , wherein said splitting comprises splitting the input array into multiple sub-arrays of the selected sub-array size.

8. The method of claim 6 , wherein said selecting comprises selecting the sub-array size based on a latency value.

9. The method of claim 6 , wherein said selecting comprises selecting the sub-array size based on a capacity to hide vector load latency.

10. The method of claim 1 , wherein each of said multiple processing elements comprises a given width.

11. The method of claim 1 , comprising:

generating the set of compare-swap instructions for said sorting.

12. A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computing device to cause the computing device to:

split an input array into multiple sub-arrays across multiple processing elements;

merge the multiple sub-arrays into multiple vectors, wherein each of the multiple vectors contains one element from each of the multiple sub-arrays;

sort the multiple vectors by comparing and swapping one or more vector elements among the multiple vectors, wherein said comparing and said swapping comprises performing a set of compare-swap instructions on a first set of one or more registers, and wherein the number of compare-swap instructions in the set of compare-swap instructions is represented as N log N+1, wherein N is a predetermined value; and

write-back results of said sorting on a second set of one or more registers.

13. The computer program product of claim 12 , wherein said sorting comprises sorting the multiple vectors via an odd-even network or a bitonic network.

14. The computer program product of claim 12 , wherein the program instructions further cause the computing device to:

select a sub-array size.

15. A system comprising:

a memory; and

at least one processor coupled to the memory and configured for:

splitting an input array into multiple sub-arrays across multiple processing elements;

merging the multiple sub-arrays into multiple vectors, wherein each of the multiple vectors contains one element from each of the multiple sub-arrays;

sorting the multiple vectors by comparing and swapping one or more vector elements among the multiple vectors, wherein said comparing and said swapping comprises performing a set of compare-swap instructions on a first set of one or more registers, and wherein the number of compare-swap instructions in the set of compare-swap instructions is represented as N log N+1, wherein N is a predetermined value; and

writing-back results of said sorting on a second set of one or more registers.

16. A method comprising:

selecting a desired sub-array size based on one or more parameters;

splitting an input array into multiple sub-arrays of the selected size across multiple simple instruction, multiple data (SIMD) lanes;

merging the multiple simple instruction, multiple data (SIMD) lanes into multiple vectors, wherein each of the multiple vectors contains one element from each of the multiple sub-arrays;

sorting the multiple vectors by performing a set of compare-swap instructions, applied to the multiple vectors, on a first set of one or more registers, wherein the number of compare-swap instructions in the set of compare-swap instructions is represented as N log N+1, wherein N is a predetermined value; and

writing-back results of said sorting on a second set of one or more registers;

wherein said selecting, said splitting, said merging, said sorting, and said writing-back are carried out by at least one computing device.

17. The method of claim 16 , wherein said sorting comprises sorting the multiple vectors via an odd-even network.

18. The method of claim 17 , comprising:

applying the odd-even network directly across the multiple vectors.

19. The method of claim 16 , wherein said sorting comprises sorting the multiple vectors via a bitonic network.

20. The method of claim 19 , comprising:

applying the bitonic network directly across the multiple vectors.