Shared-memory multiprocessor system and method for processing information

• US 7,801,903 B2
• Filed: 05/22/2006
• Issued: 09/21/2010
• Est. Priority Date: 05/24/2005
• Status: Active Grant

• Current Assignee: ESS Holding (BVI) Limited
• Original Assignee: Turbo Data Laboratories, Inc.
• Inventors: Furusho, Shinji
• Primary Examiner(s): Fleurantin; Jean B
• Application Number:
  US11/883,264
• Publication Number:
  US 20080215584A1
• Time in Patent Office: 1,583 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 707600-831, 711/114, 711/148, 711/165, 711/170, 711/147, 711/153, 711/173
• US Class Current: 707/752
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations

Abstract

Large-scale table data stored in a shared memory are sorted by a plurality of processors in parallel. According to the present invention, the records subjected to processing are first divided for allocation to the plurality of processors. Then, each processor counts the numbers of local occurrences of the field value sequence numbers associated with the records to be processed. The numbers of local occurrences of the field value sequence numbers counted by each processor is then converted into global cumulative numbers, i.e., the cumulative numbers used in common by the plurality of processors. Finally, each processor utilizes the global cumulative numbers as pointers to rearrange the order of the allocated records.

Claims

1. An information processing method of rearranging an order of records according to field values of the records in a predetermined field in a shared-memory multiprocessor system including a shared memory to store a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and further including n (n≧

1) processors operable to access the shared memory, said information processing method comprising;

a step of dividing the record number array into n1 (n1≦

n) portions to allocate the n1 divided portions of the record number array to n1 processors among the n processors, respectively;

a step of counting, by each of the n1 processors, numbers of occurrences of the field value sequence numbers associated with the record numbers contained in an allocated portion of the record number array;

a step of dividing a range of the field value sequence numbers into n2 (n2≦

n) ranges to allocate the n2 divided ranges of the field value sequence numbers to n2 processors among the n processors, respectively;

a step of converting, by each of the n2 processors, the respective numbers of occurrences of the field value sequence numbers counted by the n1 processors into cumulative numbers in an order of the field value sequence numbers where the field value sequence numbers are different from each other and in an order of the portions of the record number array where two or more processors have counted the numbers of occurrences of a common field value sequence number; and

a step of utilizing, by each of the n1 processors, as pointers the cumulative numbers of the field value sequence numbers associated with the record numbers contained in the allocated portion of the record number array, thereby storing the record numbers contained in the allocated portion of the record number array in a new record number array.

2. An information processing method of rearranging an order of records according to field values of the records in a predetermined field in a shared-memory multiprocessor system including a shared memory to store a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and further including n (n≧

1) processors operable to access the shared memory, said information processing method comprising;

a step of dividing the record number array into n1 (n1≦

n) portions to allocate the n1 divided portions of the record number array to n1 processors among the n processors;

a step of counting, by each of the n1 processors, numbers of occurrences of the field value sequence numbers associated with the record numbers contained in an allocated portion of the record number array;

a step of dividing a range of the field value sequence numbers into n2 (n2≦

n) ranges to allocate the n2 divided ranges of the field value sequence numbers to n2 processors among the n processors;

a step of using each of the n2 processors to perform, with respect to the field value sequence numbers allocated to the n2 processors, (i) deriving a sum of the numbers of occurrences counted by each of the n1 processors and carrying over the sum between the n2 processors in an order of the ranges of the field value sequence numbers, and (ii) converting the numbers of occurrences into cumulative numbers in an order of the field value sequence numbers where the field value sequence numbers are different from each other and in an order of the portions of the record number array where two or more processors have counted the numbers of occurrences of a common field value sequence number, followed by adding the carried over sum to the cumulative numbers so as to covert the number of occurrences into cumulative numbers separately for each of the field value sequence numbers associated with the record numbers contained in the respective portion of the record number array allocated to each of the n1 processors; and

a step of utilizing, by each of the n1 processors, as pointers the cumulative numbers obtained separately for each of the field value sequence numbers associated with the record numbers contained in the allocated portion of the record number array, thereby storing the record numbers contained in the allocated portion of the record number array in a new record number array.

3. An information processing method of rearranging an order of records according to field values of the records in a predetermined field in a shared-memory multiprocessor system including a shared memory to store a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and further including n (n≧

1) processors operable to access the shared memory, said information processing method comprising;

a step of selecting, by at least one processor, radix representation of the field value sequence numbers in response to a range of the field value sequence numbers so as to divide the field value sequence numbers into an upper-order digit and a lower-order digit;

a step of counting, by at least one processor, numbers of occurrences of values of the upper-order digit of the field value sequence numbers associated with the record numbers contained in the record number array, converting the numbers of occurrences into cumulative numbers according to an order of the values of the upper-order digit of the field value sequence numbers, and rearranging the record numbers in the record number array by utilizing as pointers the cumulative numbers of the values of the upper-order digit of the field value sequence numbers, thereby generating an intermediate record number array which are partitioned into n1 (sn) sections according to the order of the values of the upper-order digit of the field value sequence numbers;

a step of allocating, by at least one processor, the n1 sections of the intermediate record number array to n1 processors among the n processors, respectively; and

a step of counting, by each of the processors allocated to the respective sections, numbers of occurrences of values of the lower-order digit of the field value sequence numbers associated with the record numbers contained in an allocated section of the intermediate record number array, converting the numbers of occurrences into cumulative numbers according to an order of the values of the lower-order digit of the field value sequence numbers, and rearranging the record numbers in the allocated section of the intermediate record number array in the order of the values of the lower order digit of the associated field value sequence numbers by utilizing as pointers the cumulative numbers of the values of the lower-order digit of the field value sequence numbers.

4. A shared-memory multiprocessor system comprising a shared memory and n (n≧

1) processors operable to access the shared memory, wherein the shared memory stores a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and each of the processors includes;

a part to determine which one of n1 (n1≦

n) portions of the record number array is to be of processed by a corresponding processor;

a part to count numbers of occurrences of the field value sequence numbers associated with the record numbers contained in the portion of the record number array;

a part to determine which one of n2 (n2≦

n) ranges of the field value sequence numbers is to be processed by a corresponding processor;

a part to convert respective numbers of occurrences of the field value sequence numbers contained in the range of processed by the corresponding processor into cumulative numbers in an order of the field value sequence numbers where the field value sequence numbers are different from each other and in an order of the portions of the record number array where two or more processors have counted the numbers of occurrences of a common field value sequence number; and

a part to utilize as pointers the cumulative numbers of the field value sequence numbers associated with the record numbers contained in the portion of the record number array, thereby storing the record numbers contained in the portion of the record number array in a new record number array.

5. The shared-memory multiprocessor system as claimed in claim 4, wherein the cumulative numbers obtained by the part to convert the numbers of occurrences into the cumulative numbers in a processor processing an immediately preceding range of the field value sequence numbers are referred to by the part to convert the numbers of occurrences into the cumulative numbers in a processor processing an immediately following range.

6. A program for use in a shared-memory multiprocessor system including a shared memory to store a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and further including n (n≧

1) processors operable to access the shared memory, said program causing each of the processors to perform;

a function to determine which one of n1 (n1≦

n) portions of the record number array is to be processed by a corresponding processor;

a function to count numbers of occurrences of the field value sequence numbers associated with the record numbers contained in the portion of the record number array;

a function to determine which one of n2 (n2≦

n) ranges of the field value sequence numbers is to be processed by a corresponding processor;

a function to convert respective numbers of occurrences of the field value sequence numbers contained in the range processed by the corresponding processor into cumulative numbers in an order of the field value sequence numbers where the field value sequence numbers are different from each other and in an order of the portions of the record number array where two or more processors have counted the numbers of occurrences of a common field value sequence number; and

a function to utilize as pointers the cumulative numbers of the field value sequence numbers associated with the record numbers contained in the portion of the record number array, thereby storing the record numbers contained in the portion of the record number array in a new record number array.

7. A computer-readable record medium having a program of claim 6 recorded therein.

8. A program for use in a shared-memory multiprocessor system including a shared memory to store a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and further including a plurality of processors operable to access the shared memory, said program causing each of the processors to perform:

a function to select radix representation of the field value sequence numbers in response to a range of the field value sequence numbers;

a function to control sorting of a digit of interest by selecting the digit of interest successively from a least significant digit to a most significant digit in the radix representation of the field value sequence numbers, by use of the record number array as a current record number array for a first time sorting and by use of a new record number array as a current record number array for a second time sorting and onward;

a function to determine a portion of the record number array that is to be processed by a corresponding processor;

a function to count numbers of occurrences of values of the digit of interest in the field value sequence numbers associated with the record numbers contained in the portion of the record number array;

a function to determine a range of the values of the digit of interest in the field value sequence numbers that is to be processed by a corresponding processor;

a function to convert the respective numbers of occurrences of the values of the digit of interest of the allocated field value sequence numbers within the range processed by the corresponding processor into cumulative numbers in an order of the values of the digit of interest of the field value sequence numbers where the values of the digit of interest of the field value sequence numbers are different from each other and in an order of the portions of the record number array where two or more processors have counted the numbers of occurrences of a common value of the digit of interest of the field value sequence numbers; and

a function to utilize as pointers the cumulative numbers of the values of the digit of interest in the field value sequence numbers associated with the record numbers contained in the portion of the record number array, thereby storing the record numbers contained in the portion of the record number array in a new record number array.

9. A program for use in a shared-memory multiprocessor system including a shared memory to store a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and further including a plurality of processors operable to access the shared memory, said program causing each of the processors to perform:

a function to select radix representation of the field value sequence numbers in response to a range of the field value sequence numbers;

a function to control sorting of a digit of interest by selecting the digit of interest successively from a least significant digit to a most significant digit in the radix representation of the field value sequence numbers, by use of the record number array as a current record number array for a first time sorting and by use of a new record number array as a current record number array for a second time sorting and onward;

a function to determine a portion of the record number array that is to be processed by a corresponding processor; and

a function to count numbers of occurrences of values of the digit of interest in the field value sequence numbers associated with the record numbers contained in the portion of the record number array,

wherein at least one processor is caused by the program to perform the function to convert the respective numbers of occurrences of the values of the digit of interest of the field value sequence numbers into cumulative numbers in an order of the values of the digit of interest of the field value sequence numbers where the values of the digit of interest of the field value sequence numbers are different from each other and in an order of the portions of the record number array where two or more processors have counted the numbers of occurrences of a common value of the digit of interest of the field value sequence numbers, and

wherein said each of the processors are caused by the program to further perform a function to utilize as pointers the cumulative numbers of the values of the digit of interest in the field value sequence numbers associated with the record numbers contained in the portion of the record number array, thereby storing the record numbers contained in the portion of the record number array in a new record number array.

10. A program for use in a shared-memory multiprocessor system including a shared memory to store a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and further including n (n≧

1) processors operable to access the shared memory, said program causing;

each of n1 processors among the n processors, to which n1 (n1 sn) divided portions of the record number array are allocated, to perform a function to count numbers of occurrences of the field value sequence numbers associated with the record numbers contained in an allocated portion of the record number array;

each of n2 processors among the n processors, to which n2 (n2≦

n) divided ranges of a range of the field value sequence numbers are allocated, to perform a function of, with respect to the field value sequence numbers allocated to the n2 processors, (i) deriving a sum of the numbers of occurrences counted by each of the n1 processors and carrying over the sum between the n2 processors in an order of the ranges of the field value sequence numbers, and (ii) converting the numbers of occurrences into cumulative numbers in an order of the field value sequence numbers where the field value sequence numbers are different from each other and in an order of the portions of the record number array where two or more processors have counted the numbers of occurrences of a common field value sequence number, followed by adding the carried over sum to the cumulative numbers so as to covert the number of occurrences into cumulative numbers separately for each of the field value sequence numbers associated with the record numbers contained in the respective portion of the record number array allocated to each of the n1 processors; and

each of the n1 processors to perform a function to utilize as pointers the cumulative numbers obtained separately for each of the field value sequence numbers associated with the record numbers contained in the allocated portion of the record number array, thereby storing the record numbers contained in the allocated portion of the record number array in a new record number array.

11. A program for use in a shared-memory multiprocessor system including a shared memory to store a record number array in which record numbers of table data records are stored according to a predetermined record order, a field value sequence number array in which field value sequence numbers corresponding to field values of the table data records in the predetermined field are stored in such a manner as to be associated with the record numbers, and a field value array in which the field values of the table data are stored according to an order of the field value sequence numbers corresponding to the field values, and further including n (n≧

1) processors operable to access the shared memory, said program causing at least one processor to perform;

a function to select radix representation of the field value sequence numbers in response to a range of the field value sequence numbers so as to divide the field value sequence numbers into an upper-order digit and a lower-order digit; and

a function to count numbers of occurrences of values of the upper-order digit of the field value sequence numbers associated with the record numbers contained in the record number array, to convert the numbers of occurrences into cumulative numbers according to an order of the values of the upper-order digit of the field value sequence numbers, and to rearrange the record numbers in the record number array by utilizing as pointers the cumulative numbers of the values of the upper-order digit of the field value sequence numbers, thereby generating an intermediate record number array which are partitioned into n1 (≦

n) sections according to the order of the values of the upper-order digit of the field value sequence numbers,

wherein each of a plurality of processors allocated to the respective sections of the intermediate record number array is caused by the program to perform a function to count numbers of occurrences of values of the lower-order digit of the field value sequence numbers associated with the record numbers contained in an allocated section of the intermediate record number array, to convert the numbers of occurrences into cumulative numbers according to an order of the values of the lower-order digit of the field value sequence numbers, and to rearrange the record numbers in the allocated section of the intermediate record number array in the order of the values of the lower-order digit of the associated field value sequence numbers by utilizing as pointers the cumulative numbers of the values of the lower-order digit of the field value sequence numbers.