Patent ID: 7536432
Filing Date: 2009-05-19
Classification: G06F,Y10S

Abstract:
1. A method for performing parallel sorting processing using a parallel processor, where (i) one unsorted data string, or (ii) two or more sorted partial data strings are received as an input, the method comprising: if the input is one unsorted data string, a first step of dividing the unsorted data string to generate a plurality of unsorted partial data strings; a second step of assigning a processor to said plurality of unsorted partial data strings respectively; a third step of sorting each of said plurality of unsorted partial data strings independently by the assigned processor based on an arbitrary algorithm, to generate sorted partial data strings, the arbitrary algorithm sorting the plurality of unsorted partial data strings each in one of either ascending or descending order; a fourth step of creating an input data string pair for sorting using two of the sorted partial data strings which were acquired in the third step or a seventh step or that were received as the input, and dividing the pair into sets of partial data string pairs respectively under a predetermined division condition; a fifth step of editing control information relating to parallel processing of merge processing, the control information for parallel sorting of the plurality of divided partial data string pairs, the control information being information regarding at least the location of the plurality of divided partial data string pairs and the number of the plurality of divided partial data string pairs; a sixth step of assigning to the plurality of divided partial data string pairs a processor group for merging of the plurality of divided partial data string pairs; the seventh step of performing merge processing by the assigned processor and outputting sorted partial data strings; and a step of repeating said fourth step to said seventh step using the merge-processed sorted partial data strings as said sorted partial data strings, wherein the above steps are applied when one unsorted data string is provided, and the first to the third steps are unnecessary if two or more sorted data strings are provided, and a repeat of said fourth to seventh steps ends when the merge-processed sorted partial data strings are merged into one data string; if only two sorted data strings are provided, the fourth to seventh steps are executed only once, and the repeat is not required, wherein the following items are satisfied as the predetermined division condition in said fourth step, when a condition where data string pair (D is established, where x is a half value of the number of data of the partial data string pair {(D 11 , n 11 ), (D 21 , n 21 )}, and is also the number of data of D 11 and D 21 when n 11 =n 21 , and wherein said fourth step has the following functions: (1) an operation to divide a sorted data string pair {(D (2) specifying a data position in the data string by an index value, the value sequentially increments with the index value of a first data in the data string D if n (3) an area dividing function, comprising: a step of setting said x as an initial value of a boundary index value for index variables i and j for specifying individual data in said data strings D a comparison step of comparing a key value of data indicated by the index variable i of the data string D a step of adding 1 to an index variable of the data with a greater key value, subtracting 1 from an index variable of the data with a smaller key value, then branching processing to said comparison step, if the key value of the data indicated by the index variable i of D a step of adding 1 to the index variable of data with a greater key value, and subtracting 1 from the index variable of data with a smaller key value, then branching processing to said comparison step, if a magnitude relationship of the key value of data indicated by the index variable i of D a step of regarding the data indicated by the index variable i and the data indicated by the index variable j as a division boundary respectively, if the key value of the data indicated by the index variable i of D a step of comparing a greater one of the key value of D