SIMD merge-sort and duplicate removal operations for data arrays

1. A method for performing high speed merging and sorting of two or more data streams comprising:

loading a first set of sorted data elements from a first sorted input stream into a first hardware vector register, and loading a second set of sorted data elements from a second sorted input stream into a second hardware vector register, wherein the quantity of data elements loaded into the first register is equal to the quantity of data elements loaded into the second register;

using single instruction multiple data (SIMD) instructions for performing a merge sort operation resulting in combining data elements loaded into said vector registers into a single sorted sequence, said merge sort operation based upon comparison of data elements from the first and second vector registers;

placing first and second portions of the single sorted sequence into the first and second vector registers, respectively, wherein the first vector register contains a first sorted portion of the sequence with smaller data elements and the second vector register contains a second sorted portion of the sequence with larger data elements;

placing contents of the first vector register with the smaller data elements into a single output stream; and

loading a next set of sorted data elements from one of the input streams into the first vector register and repeating the merge sort operation and output of sorted data elements into the single output stream until the input streams are completely merged, including removing duplicate data elements from the single output stream in an operation selected from the group consisting of: removing duplicate data elements collectively when the first and second input streams are completely merged, and removing duplicate data elements by comparing proximate elements each time elements of the first vector register are placed into the single output stream.

2. The method of claim 1 , further comprising denoting a position to read a next data element with a pointer and advancing a position of the pointer after loading data elements from one of the input streams.

3. The method of claim 2 , further comprising comparing a first element after the pointer in the first input stream to a first element after the pointer in the second input stream and loading, into the first vector register, data elements from an input stream with a smaller first element.

4. The method of claim 1 , wherein the merge sort operation is performed by invoking a SIMD instruction selected from the group consisting of: a vector minimum instruction and a vector maximum instruction.

5. A computer system comprising:

a single instruction multiple data (SIMD) processor configured to employ Virtual Machine Extensions (VMX) instructions to perform high speed merging and sorting of two or more data streams, the instructions comprising:

instructions to load a first set of sorted data elements into a first hardware vector register from a first sorted input stream;

instructions to load a second set of sorted data elements into a second hardware vector register from a second sorted input stream, wherein the quantity of loaded elements is constant;

SIMD instructions to perform a merge sort operation resulting in combining data elements loaded into said vector registers into a single sorted sequence, said merge sort operation based upon comparison of data elements from the first and second vector registers;

instructions to place first and second portions of the single sorted sequence into the first and second vector registers, respectively, wherein the first vector register contains a first sorted portion of the sequence with smaller data elements and the second vector register contains a second sorted portion of the sequence with larger data elements;

instructions to place contents of the first vector register into a single output stream; and

instructions to load a next set of sorted data elements from one of the input streams into the first vector register and to repeat the merge sort operation and output of sorted data elements into the single output stream until the input streams are completely merged, including removing duplicate data elements from the single output stream in an operation selected from the group consisting of: removing duplicate data elements collectively when the first and second input streams are completely merged, and removing duplicate data elements by comparing proximate elements each time elements of the first vector register are placed into the single output stream.

6. The system of claim 5 , further comprising a pointer to denote a position to read a next data element and instructions to advance the pointer to read the next data element after loading a certain number of data elements from one of the input streams.

7. The system of claim 6 , further comprising instructions to compare a first element after the pointer in the first input stream to a first element after the pointer in the second input stream, and to load the constant number of data elements into the first vector register from an input stream with a smaller first element.

8. The system of claim 5 , wherein the merge sort operation is performed by invoking a SIMD instruction selected from the group consisting of: a vector minimum instruction, and a vector maximum instruction.

9. An article comprising:

a computer readable data storage device, including computer program instructions configured to perform high speed merging and sorting of two or more data streams, the instructions comprising:

instructions to load a set number of sorted data elements into a first hardware vector register from a first sorted input stream;

instructions to load the set number of sorted data elements into a second hardware vector register from a second sorted input stream;

single instruction multiple data (SIMD) instructions to perform a merge sort operation for combining data elements loaded into said vector registers into a single sorted sequence, said merge sort operation based upon comparison of data elements from the first and second vector registers;

instructions to place first and second portions of the single sorted sequence into the first and second vector registers, respectively, wherein the first vector register contains a portion of the sequence with smaller data elements and the second vector register contains a portion of the sequence with larger data elements;

instructions to place contents of the first vector register into a single output stream; and

instructions to load a next set of sorted data elements from one of the input streams into the first vector register and instructions to repeat the merge sort operation and output of sorted data elements into the single output stream until the input streams are completely merged, including removing duplicate data elements from the single output stream in an operation selected from the group consisting of: removing duplicate data elements collectively when the first and second input streams are completely merged, and removing duplicate data elements by comparing proximate elements each time elements of the first vector register are placed into the single output stream.

10. The article of claim 9 , further comprising instructions to advance a pointer denoting the position to read a next data element after loading the set number of data elements from one of the input streams.

11. The article of claim 10 , further comprising instructions to compare a first element after the pointer in the first input stream to a first element after the pointer in the second input stream, and to load the set number of data elements into the first register from an input stream with a smaller first element.