SORTING AN ARRAY CONSISTING OF A LARGE NUMBER OF ELEMENTS

• US 20160171030A1
• Filed: 12/10/2015
• Published: 06/16/2016
• Est. Priority Date: 12/12/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: INOUE, HIROSHI
• Granted Patent: US 10,642,901 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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 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; 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.

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 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.

5. 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.

6. 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.

7. The apparatus according to claim 6, 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.

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 number of bits of the key is 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.

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

12. 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.

19. A computer program product for causing a computer to function as a system that executes a multiway merging process which generates one output sequence from N input sequences on an array consisting of a large number of elements, the program causing the computer to implement the functions of the apparatus according to claim 1.

13. An apparatus for merge-sorting an array consisting of a large number of elements by utilizing a multiway merging process which generates one output sequence from a plurality of input sequences, the apparatus comprising:

a storage unit configured to store the array consisting of a large number of elements; and

a sorted-array generation unit configured to;

(i) produce an input sequence by pairing, for each element, a key for use in a comparison during sorting with an index identifying the element, where one element in the array consisting of a large number of elements or one sorted array of elements makes an input sequence for the multiway merging process, (ii) execute the multiway merging process on a plurality of input sequences without rearranging the elements based on which input sequences have been produced, and (iii) rearrange the elements stored in the storage unit in accordance with output sequences generated so as to generate a sorted array of elements which will make an input sequence for the multiway merging process at a following stage,

wherein, after an initial stage of processing, processing by the sorted-array generation unit is iteratively executed using all of the large number of elements as the base of input sequences for the multiway merging process, processing at each stage following the initial stage is performed by executing processing that repeats the processing by the sorted-array generation unit using all sorted arrays that were generated by the multiway merging process in the preceding stage as the base of new input sequences for the multiway merging process, which generates a sorted array in which all of the large number of elements are sequentially sorted.

20. A computer program product for causing a computer to function as a system that merge-sorts an array consisting of a large number of elements by utilizing a multiway merging process which generates one output sequence from a plurality of input sequences, the program causing the computer to implement the functions of the apparatus according to claim 13.

14. A method 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 method comprising the steps of:

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; and

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.

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

16. The method according to claim 14, 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.

17. The method according to claim 16, 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.

18. The method according to claim 16, 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.