Sorting an array consisting of a large number of elements

• US 10,642,901 B2
• Filed: 12/10/2015
• Issued: 05/05/2020
• Est. Priority Date: 12/12/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Inoue, Hiroshi
• Primary Examiner(s): Alam, Shahid A
• Application Number:
  US14/965,190
• Publication Number:
  US 20160171030A1
• Time in Patent Office: 1,608 Days
• Field of Search: 707753
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: G06F 7/06 Arrangements for sorting, selecting, merging, or comparing data on individual record carriers
• CPC Class Codes: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence

Abstract

Sorting an array consisting of large number of elements. The present invention provides an apparatus for executing a multiway merging process which generates one output sequence from N input sequences on an array consisting of a large number of elements. The apparatus includes: an input sequence production unit configured to produce an input sequence by pairing a key from an element for use in a comparison during sorting with an index identifying the element for each element or sorted array of elements; an execution unit configured to execute the multiway merging process on N input sequences without rearranging the elements based on which input sequences have been produced; and a generation unit configured to rearrange the elements constituting the input sequences according to an output sequence that has been generated by the multiway merging process in the execution unit so as to generate a sorted array of elements.

Claims

1. An apparatus, the apparatus comprising:

an input sequence production unit configured to produce an input sequence by pairing a key from an element for use in a comparison during sorting with an index identifying the element for each element or sorted array of elements;

an execution unit configured to execute the multiway merging process on N input sequences without rearranging the elements based on which input sequences have been produced;

a generation unit configured to rearrange the elements constituting the input sequences according to an output sequence that has been generated by the multiway merging process in the execution unit so as to generate a sorted array of elements; and

a number of bits of the key determined so that a combination of the key and the index has a first number of bits until the number of elements contained in input sequences for the multiway merging process reaches a predetermined threshold, and when the number of elements exceeds the predetermined threshold, the number of bits of the key is determined so that the combination has a second number of bits which is greater than the first number of bits.

2. The apparatus according to claim 1, wherein N is an integer equal to or greater than 3.

3. The apparatus according to claim 1, wherein a unit of processing is defined as a series of processes including the execution unit executing the multiway merging process and the generation unit rearranging the elements, based on which input sequences have been produced, according to an output sequence generated so as to generate a sorted array and the unit of processing is executed in a plurality of stages in sequence.

4. The apparatus according to claim 3, wherein for the unit of processing performed at an initial stage among the plurality of stages, processing by the execution unit on each set of N input sequences is iteratively executed multiple times in accordance with a number of elements contained in the array consisting of a large number of elements and the number of sorted arrays, where one element in the array consisting of a large number of elements or one sorted array of elements makes an input sequence, and the generation unit rearranges the elements, based on which input sequences have been produced, in accordance with the plurality of output sequences generated so as to generate a plurality of sorted arrays.

5. The apparatus according to claim 4, wherein for the unit of processing performed at each stage following the unit of processing at the initial stage, processing by the execution unit is executed for each set of N sorted arrays among the sorted arrays that have been generated by the multiway merging process in the unit of processing at a preceding stage, the processing by the execution unit being executed once or multiple times in accordance with the number of the sorted arrays that have been generated.

6. The apparatus according to claim 1, wherein if only one output sequence is generated, the generation unit rearranges the large number of elements in accordance with the one output sequence generated so as to generate a sorted array in which all of the large number of elements are sequentially sorted.

7. The apparatus according the claim 1, wherein if a plurality of output sequences are generated by the execution unit, the generation unit rearranges the elements constituting each input sequence in accordance with the plurality of output sequences generated so as to generate a plurality of sorted arrays which will be subjected to the multiway merging process in a following stage.

8. The apparatus according to claim 1, wherein if the number of input sequences is less than N in the series of processes defining the unit of processing,

the execution unit executes the multiway merging process on the less than N input sequences;

and

the generation unit rearranges the elements, based on which input sequences have been produced, in accordance with the output sequence that has been generated based on the less than N input sequences so as to generate a sorted array.

9. The apparatus according to claim 1, wherein numbers that are sequentially assigned to input sequences for the multiway merging process are used for the indices.

10. The apparatus according to claim 1, wherein the first number of bits is 32 and the second number of bits is 64.

11. The apparatus according to claim 1, wherein in the series of processes defining the unit of processing, the multiway merging process is executed using SIMD instructions.

12. A computer-implemented method, the method comprising:

producing an input sequence by pairing, per element or sorted array of elements, a key from an element for use in a comparison during sorting with an index identifying the element;

executing the multiway merging process on N input sequences without rearranging the elements based on which input sequences have been produced;

rearranging the elements, based on which the input sequences have been produced, according to an output sequence that has been generated by the multiway merging process in the executing step so as to generate a sorted array of elements; and

determining a number of bits of the key so that a combination of the key and the index has a first number of bits until the number of elements contained in input sequences for the multiway merging process reaches a predetermined threshold, and when the number of elements exceeds the predetermined threshold, determining the number of bits of the key so that the combination has a second number of bits which is greater than the first number of bits.

13. The method according to claim 12, wherein N is an integer equal to or greater than 3.

14. The method according to claim 12, wherein a unit of processing is defined as a series of processes including executing the multiway merging process in the executing step and rearranging the elements, based on which the input sequences have been produced, according to an output sequence generated so as to generate a sorted array in the generating step, and the unit of processing is executed in a plurality of stages in sequence.

15. The method according to claim 14, wherein if a plurality of output sequences are generated in the executing step, the generating step rearranges the elements, based on which input sequences have been produced, in accordance with the plurality of output sequences generated so as to generate a plurality of sorted arrays which will be subjected to the multiway merging process in a following stage.

16. The method according to claim 14, wherein if only one output sequence is generated, the generating step rearranges the large number of elements in accordance with the one output sequence generated so as to generate a sorted array in which all of the large number of elements are sequentially sorted.

17. A computer program product, the computer program product comprising:

one or more computer readable hardware storage devices and program instructions stored on the one or more computer readable hardware storage devices, the program instructions comprising;

program instructions to produce an input sequence by pairing, per element or sorted array of elements, a key from an element for use in a comparison during sorting with an index identifying the element;

program instructions to execute the multiway merging process on N input sequences without rearranging the elements based on which input sequences have been produced;

program instructions to rearrange the elements, based on which the input sequences have been produced, according to an output sequence that has been generated by the multiway merging process in the executing step so as to generate a sorted array of elements; and

program instructions to determine a number of bits of the key so that a combination of the key and the index has a first number of bits until the number of elements contained in input sequences for the multiway merging process reaches a predetermined threshold, and when the number of elements exceeds the predetermined threshold, program instructions to determine the number of bits of the key so that the combination has a second number of bits which is greater than the first number of bits.