Method for sorting data using SIMD instructions

• US 20070156685A1
• Filed: 12/28/2005
• Published: 07/05/2007
• Est. Priority Date: 12/28/2005
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Komatsu, Hideaki, Moriyama, Takao, Inoue, Hiroshi
• Application Number:
  US11/320,095
• Publication Number:
  US 20070156685A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 7/36 Combined merging and sorting

Abstract

A method and apparatus are provided to perform fast data sorting by using SIMD instruction. Data comparison and swapping is executed with SIMD instructions in parallel and without conditional branching.

Claims

1. A method for sorting a data array comprising:

invoking a comb sort algorithm for sorting a data set using a combination of SIMD instructions selected from a group consisting of;

min and max instructions, and compare and select instructions;

swapping data based upon a comparison in said algorithm.

2. The method of claim 1, further comprising invoking an inter-slot data comparison process followed by a data swapping.

3. The method of claim 1, further comprising invoking a quick sort algorithm to reduce data size.

4. The method of claim 1, further comprising dividing said data sets into a plurality of groupings prior to invoking said comb sort algorithm.

5. The method of claim 4, further comprising invoking a merge sort algorithm to combine said groupings upon completion of the step of swapping said data.

6. The method of claim 1, wherein

said data set is a data structure, and said data structure includes keys and additional data;

and

further comprising applying a permutation instruction to a key comparison result obtained through parallel compare and select instructions of said comb sort algorithm.

7. The method of claim 1, wherein

said data set is a data structure, and said data structure includes keys and additional data;

and

further comprising applying results of key comparison obtained by parallel compare instructions to other data.

8. An article comprising:

a computer useable medium having computer useable program code for sorting a data array, said medium comprising;

computer useable code for invoking a comb sort algorithm to sort a data set using a combination of SIMD instructions selected from a group consisting of;

min and max instructions, and compare and select instructions;

computer useable code for swapping data based upon a comparison in said algorithm.

9. The article of claim 8, further comprising computer useable code for invoking an inter-slot data comparison process followed by a data swapping.

10. The article of claim 8, further comprising computer useable code for invoking a quick sort algorithm to reduce data size.

11. The article of claim 8, further comprising computer useable code for dividing said data sets into a plurality of groupings prior to invoking said comb sort algorithm.

12. The article of claim 11, further comprising computer useable code for invoking a merge sort algorithm to combine said groupings upon completion of the computer useable code for swapping said data.

13. The article of claim 8, wherein

said data set is a data structure, and said data structure includes keys and additional data;

and

further comprising computer useable code for applying a permutation instruction to a key comparison result obtained through parallel compare and select instructions of said comb sort algorithm.

14. The article of claim 8, wherein

said data set is a data structure, and said data structure includes keys and additional data;

and

further comprising computer useable code for applying results of key comparison obtained by parallel compare instruction to other data.

15. The article of claim 8, wherein the medium is a recordable data storage medium.