Multiprocessor system, and its information processing method

The present invention is an information processing method in a shared memory type multiprocessor system in which a plurality of processors share a memory for parallel processing, and in particular, a large-scale tabular data on the shared memory is sorted in parallel by the plurality of processors. Regarding the information processing method to be performed.

The present invention also relates to a shared memory multiprocessor system that implements such an information processing method.

The present invention further relates to a program for realizing such an information processing method.

The present invention further relates to a storage medium on which such a program is recorded.

Nowadays, computers have been introduced in various places in society as a whole, and networks such as the Internet have permeated, and large-scale data has been accumulated and processed here and there.

On the other hand, efficient algorithms have been developed to process large-scale data. Sorting is a frequent process when processing large-scale data, especially large-scale tabular data. Radix (RADIX) sort and counting (COUNTING) sort (also called counting sort or distribution counting sort) are known as efficient sorting algorithms. Counting sort is an efficient algorithm that is sometimes used to sort each digit of radix sort, but for its application, 1) The sort target is an integer 2) Know the upper and lower limits of the integers to be sorted 3) The difference between the upper and lower limits of the integers to be sorted is not too large. There is a precondition.

On the other hand, the present inventor has proposed a data management mechanism suitable for searching, aggregating, and sorting large-scale tabular data at high speed (see Patent Document 1). This data management mechanism has an information block for representing each item value of the item of tabular data. In this information block, the item values belonging to the items of the tabular data are represented by the item value numbers assigned to each item value and the array of the actual item values arranged in the order of the item value numbers. An array in which the item value numbers corresponding to the item values of each record are arranged in the order of record numbers is prepared, and the item values of each record are specified by finding the value corresponding to the item value numbers of the record from the array of item values. To. In addition, the record to be processed in the tabular data is specified by an array in which the record numbers are arranged in order.

The information block is a table in which the item values corresponding to the above item value numbers are stored in the order of the item value numbers in which the item values belonging to the items are ordered (integerized) for each item of the tabular data. .. The item value itself can be any type of data, such as a number (integer, fixed point, floating point, etc.) or a string. Therefore, this data management mechanism is characterized in that all types of data values can be handled as integers called item value numbers. That is, according to this data management mechanism, for example, when sorting character string type data, the character string type data is not sorted as it is as a sort target, but corresponds to the value of the character string type data. The item value number can be sorted as a sort target. At this time, the sort result is represented by an array in which the record numbers are arranged in order. As described above, the data management mechanism based on the information block proposed by the present inventor is excellent in that it satisfies the preconditions 1) to 3) above for applying the counting sort.

On the other hand, parallel processing has been attempted in order to execute the enormous amount of calculations required to process large-scale data at high speed. Various parallel sorting algorithms have also been proposed for sorting. Generally, the parallel processing architecture is roughly classified into "distributed memory type" and "shared memory type". In the distributed memory type, each processor has its own local memory, and these are combined to build a system. With this method, it is theoretically possible to design a hardware system that incorporates hundreds to tens of thousands of processors. However, the distributed memory type has technical problems such as complexity of data division management and low efficiency of communication between processors. On the other hand, the shared memory type is a method in which a plurality of processors share one huge memory space. In this method, the traffic between the processor group and the shared memory becomes a bottleneck, so it is considered that it is not easy to construct a system using more than 100 processors in reality.

However, under such circumstances, in recent years, a personal computer configured as a shared memory type multiprocessor system using a plurality of CPUs has become available. The standard CPU used in this type of personal computer operates with an internal clock that is about 5 to 6 times that of the memory bus, and is equipped with an automatic parallel execution function and pipeline processing function inside. Approximately 1 data can be processed in 1 clock (memory bus).<patcit num="1"><text>International Publication WO00 / 10103</text></patcit>

<p> Therefore, it is desirable to combine an efficient sorting algorithm with a shared memory multiprocessor system to process large-scale tabular data.</p><p> Counting sort, which is known as an efficient sorting algorithm, is constrained by the preconditions 1) to 3) above, so unless the data management mechanism based on the above information block proposed by the present inventor is adopted. , Difficult to apply to the processing of large-scale tabular data. Furthermore, the technology for parallel sorting large-scale tabular data in a shared memory multiprocessor system is not yet known.</p><p> Therefore, an object of the present invention is to propose an information processing method for sorting large-scale tabular data on a shared memory in parallel by a plurality of processors by using a data management mechanism based on the above information block. Is.</p><p> Another object of the present invention is to provide a shared memory type multiprocessor system that implements such an information processing method.</p><p> Furthermore, an object of the present invention is to provide a program for realizing such an information processing method.</p><p> Furthermore, an object of the present invention is to provide a storage medium on which such a program is recorded.</p>

<p> The present invention corresponds to the above item value numbers in the order (either ascending or descending order) of the item value numbers in which the item values belonging to the items are ordered (integerized) for each item of the tabular data. It relies on a data management mechanism based on information blocks, which is a table in which item values are stored. The item value itself can be any type of data, such as a number (integer, fixed point, floating point, etc.) or a string. By adopting this data management mechanism, all types of data values can be handled as integers called item value numbers. That is, according to this data management mechanism, when sorting any type of data, the item value number corresponding to the value of the data is not sorted as it is as the sort target. It can be sorted as a sort target. Therefore, the data management mechanism based on this information block meets the prerequisites for applying the counting sort. Further, since the record to be processed in the tabular data is specified by the array in which the record numbers are arranged in order, the sort result is represented by the array in which the record numbers are arranged in order.</p><p> The present invention provides an information processing method for sorting large-scale tabular data on a shared memory in parallel by a plurality of processors by applying such a data management mechanism to a shared memory type multiprocessor system. , Realize a shared memory type multiprocessor system that implements the information processing method. Therefore, according to the present invention, first, the record to be processed is divided and assigned to a plurality of processors. Each processor then counts the number of local occurrences of the item value number associated with the record being processed. Next, the number of local occurrences of the item value number counted by each processor is converted into the global cumulative number of the item value numbers, that is, the cumulative number commonly used among a plurality of processors. Finally, each processor rearranges the order of the assigned records by using this global cumulative number as a pointer. Therefore, according to the present invention, in a shared memory multiprocessor system, records can be sorted in parallel with respect to an item value (for example, an integer value, a fixed-point number, a floating-point number, a character string, etc.) of an item of the record. It is possible.</p><p> The allocation of the record to be processed to a plurality of processors, the counting of the number of occurrences locally, and the rearrangement of the order of the allocated records can be processed by the plurality of processors in parallel. In addition, the calculation of the global cumulative number may use parallel processing of multiple processors, but since the memory can be accessed sequentially and the hit rate to the cache is high, only one or some processors can be used. You can take charge and maintain high speed.</p><p> The above principle of the present invention is carried out by the following various aspects.</p><p> The first aspect of the present invention is an information processing method for rearranging the record order according to the item value of a predetermined item of a record in a shared memory type multiprocessor system. In the shared memory type multiprocessor system, the record number of the record of the tabular data is stored according to the predetermined record order, and the item value number corresponding to the item value of the predetermined item of the record of the tabular data is the record number. The shared memory that stores the item value number array stored according to the above and the item value array in which the item values of the tabular data are stored according to the order of the item value numbers corresponding to the item values, and the shared memory can be accessed. It includes a plurality of processors. The information processing method according to the present invention The step of dividing the record number array and assigning it to the first plurality of processors, In each processor of the first plurality of processors, a step of counting the number of occurrences of an item value number corresponding to a record included in a part of the assigned record number array, and a step of counting the number of occurrences of the item value number corresponding to the record. The step of dividing the range of the item value numbers and assigning them to the second plurality of processors, In each of the second plurality of processors, the assigned item value numbers are in the order of the item value numbers, and within the range in which the item value numbers match, in the order of the parts of the record number array. Steps to convert the number of occurrences of each to the cumulative number, In each of the first plurality of processors, the allotted record number array is used as a pointer by using the cumulative number of the item value numbers corresponding to the records included in the allotted record number array. A step to store the record numbers contained in the part of the record number array in a further record number array, and including.</p><p> This information processing method achieves parallelization of the counting process of the number of occurrences of the item value number, parallelization of the conversion process from the number of occurrences to the cumulative number, and further parallelization of the process of creating the record number array. Therefore, the present invention makes it possible to sort large-scale tabular data in parallel in a shared memory multiprocessor system by extending the counting sorting technique to suit a shared memory multiprocessor environment. Of the multiple processors that make up the multiprocessor system, any first plurality of processors are in charge of each part of the record number array, and any second plurality of processors are the item value numbers. Responsible for each part of the range. It should be noted that the number of the first plurality of units and the number of the second plurality of units may be all or a part of the processors constituting the multiprocessor system.</p><p> Further, the information processing method of the present invention can sort large-scale tabular data in parallel in multiple stages in a shared memory type multiprocessor system by introducing the concept of radix sort for item value numbers. For example, when the size of the item value number array is large, it is possible to improve the processing efficiency if the item value number array can be compressed and used. Therefore, the information processing method according to the present invention is: A step of setting the radix of the item value number according to the range of the item value number, and Regarding the current digit in order from the least significant digit to the most significant digit of the item value number expressed by the radix, the record number array is used as the current record number array for the first time, and further record number arrays are used for the second and subsequent times. As the current record number array, the step of repeating the sorting process and including. As a result, parallel sorting processing is performed for each digit of the item value number in order from the least significant digit to the most significant digit. The sort process is The step of dividing the current record number array and assigning it to the first plurality of processors, In each processor of the first plurality of processors, a step of counting the number of occurrences of the value of the current digit of the item value number corresponding to the record included in the part of the assigned record number array, and The step of dividing the value range of the current digit of the item value number and assigning it to the second plurality of processors, and In each processor of the second plurality of processors, the record number array is within the range in which the values of the current digits of the item value numbers match in the order of the values of the current digits of the item value numbers. A step of converting the number of occurrences of each of the values of the current digit of the assigned item value number into a cumulative number according to the order of the parts. In each of the first plurality of processors, the cumulative number of the current digit values of the item value numbers corresponding to the records included in the assigned record number array is used as a pointer. , A step of storing the record numbers contained in the assigned part of the record number array in a further record number array, and including.</p><p> According to the present invention, since the sorting process for the current digit is repeated in order from the least significant digit to the most significant digit of the item value number, sorting related to the item value number is realized according to the concept of radix sort. Therefore, it is possible to sort large-scale tabular data in parallel in a shared memory multiprocessor system.</p><p> In the above multi-step parallel sorting, the step of converting the number of occurrences of each occurrence of the value of the current digit of the item value number into the cumulative number is executed in parallel by the second plurality of processors. However, this step may be faster with multiple processors without having to run it in parallel. This is because the processing of this step is performed sequentially, so that the cache hit rate is high. Therefore, the information processing method according to the present invention is: A step of setting the radix of the item value number according to the range of the item value number, and Regarding the current digit in order from the least significant digit to the most significant digit of the item value number expressed by the radix, the record number array is used as the current record number array for the first time, and further record number arrays are used for the second and subsequent times. As the current record number array, the step of repeating the sorting process and Including The sort process The step of dividing the current record number array and assigning it to the plurality of processors, In each processor, a step of counting the number of occurrences of the value of the current digit of the item value number corresponding to the record included in the part of the assigned record number array, and In at least one processor, the allocation is performed in the order of the values of the current digit of the item value number, and within the range in which the values of the current digits of the item value number match, in the order of the parts of the record number array. The step of converting the number of occurrences of each of the current digit values of the item value number to the cumulative number, and In each of the processors, the cumulative number of values of the current digit of the item value number corresponding to the record included in the portion of the assigned record number array is used as a pointer to obtain the assigned record number array. A step to store the record numbers contained in the part in an additional record number array, including.</p><p> In this information processing method, the range of the current digit of the item value number is not divided into a plurality of processors, and at least one processor, preferably one processor, is the value of the current digit of the item value number. Converts the number of occurrences of to the cumulative number in order. Also in this case, since the sorting process for the current digit is repeated in order from the least significant digit to the most significant digit of the item value number, sorting related to the item value number is realized according to the concept of radix sort. Therefore, it is possible to sort large-scale tabular data in parallel in a shared memory multiprocessor system.</p><p> Further, in order to achieve the above object, the present invention has a record number array in which record numbers of tabular data records are stored according to a predetermined record order, and item values corresponding to item values of predetermined items of tabular data records. A shared memory that stores an item value number array in which numbers are stored according to record numbers, and an item value array in which item values of tabular data are stored in the order of item value numbers corresponding to the item values. Multiple processors that can access the shared memory, In a shared memory multiprocessor system equipped with A step of dividing the record number array and assigning it to the plurality of processors, In each of the plurality of processors, the order of the records included in the part of the assigned record number array is changed according to the item value number corresponding to the record, and the record number of the record is further changed to the record number. Steps to store in an array and Provide an information processing method for rearranging the record order according to the item value of a predetermined item of the record including.</p><p> Further, in order to achieve the above object, the present invention is a record number array in which record numbers of tabular data records are stored according to a predetermined record order, and item values corresponding to item values of predetermined items of tabular data records. A shared memory that stores an item value number array in which numbers are stored according to record numbers, and an item value array in which item values of tabular data are stored in the order of item value numbers corresponding to the item values. Multiple processors that can access the shared memory, In a shared memory multiprocessor system equipped with A step of setting the radix of the item value number according to the range of the item value number, and The record numbers in the record number array are rearranged with respect to the upper digit of the item value number expressed by the radix, and an intermediate record number array divided in the order of the value of the upper digit of the item value number is generated. Steps to do and The step of allocating a processor for each division of the intermediate record number array and A step in which each processor assigned to each division rearranges the record numbers in the division of the intermediate record number array in the order of the lower digit value of the item value number. Provide an information processing method for rearranging the record order according to the item value of a predetermined item of the record including.</p><p> A second aspect of the present invention is a shared memory type multiprocessor system including a shared memory and a plurality of processors that can access the shared memory, and carrying out the above-mentioned information processing method of the present invention. In the shared memory type multiprocessor system of the present invention, the shared memory has a record number array in which record numbers of tabular data records are stored according to a predetermined record order, and item values of predetermined items of tabular data records. Stores the item value number array in which the corresponding item value numbers are stored according to the record numbers, and the item value array in which the item values of the tabular data are stored in the order of the item value numbers corresponding to the item values. Thereby, the shared memory type multiprocessor system of the present invention can utilize the data management mechanism based on the block information.</p><p> Each processor A means for determining the part of the record number array that the own processor is in charge of, A means for counting the number of occurrences of the item value number corresponding to the record included in the part of the record number array, and A means for determining the range of the item value number that the own processor is in charge of, A means for converting the number of occurrences of each item value number in the range in charge into a cumulative number according to the order of the item value numbers and the order of the parts of the record number array within the range in which the item value numbers match. A means for storing the record numbers included in the part of the record number array in a further record number array by using the cumulative number of the item value numbers corresponding to the records included in the part of the record number array as a pointer. including.</p><p> Since each processor can operate in parallel, parallelization of the count of the number of occurrences, parallelization of conversion to the cumulative number of occurrences, and further parallelization of creation of the record number array are realized.</p><p> When converting the number of occurrences of item value numbers to cumulative numbers, it is necessary to propagate the obtained cumulative numbers in the order of item value numbers. Therefore, the cumulative number obtained by the means for converting the number of appearances of the processor in charge of the preceding range in the range of the item value numbers into the cumulative number is the cumulative number of appearances of the processor in charge of the immediately preceding range. Referenced by means of conversion.</p><p> Further, in the shared memory type multiprocessor system of the present invention, by introducing the concept of radix sort regarding the item value number, large-scale tabular data is sorted in parallel in multiple stages, so that each processor can sort the data in parallel. A means for setting the radix of the item value number according to the range of the item value number, and The current digit is set in order from the least significant digit to the most significant digit of the item value number expressed by the radix, the first time the record number array is used as the current record number array, and the second and subsequent record numbers are further recorded. A means to set the array as the current record number array and repeat the sorting process, including. As a result, the parallel sort processing for each digit from the least significant digit to the most significant digit of the item value number is executed in order. Further, the means for repeating the sort process is A means for determining the part of the record number array that the own processor is in charge of, A means for counting the number of occurrences of the value of the current digit of the item value number corresponding to the record included in the part of the record number array, and A means for determining the range of the current digit value of the item value number that the own processor is in charge of, Within the range where the current digit value of the item value number matches the order of the current digit value of the item value number, the current item value number within the range in charge is in accordance with the order of the parts of the record number array. A means to convert the number of occurrences of each digit value to a cumulative number, Using the cumulative number of the current digit values of the item value number corresponding to the record included in the part of the record number array as a pointer, the record number included in the part of the record number array is further converted into the record number array. Means of storage and including. As a result, parallel sorting processing for each digit of the item value number is realized. According to the present invention, in the sort process for each digit of the item value number, a plurality of processors simultaneously count the number of occurrences, convert the number of occurrences into a cumulative number, and create a further record number array. Execute.</p><p> Further, since the conversion to the cumulative number of occurrences is shared by a plurality of processors, in the present invention, the number of occurrences of the processor in charge of the preceding range of the current digit range of the item value number is cumulative. The cumulative number obtained by the means for converting to a number is referred to by the means for converting the number of occurrences of the processor in charge of the immediately preceding range into a cumulative number.</p><p> Furthermore, the shared memory multiprocessor system according to the present invention, which sorts large-scale tabular data in parallel in multiple stages, accumulates at least one, preferably one, of the number of occurrences of each of the current digit values. It is also possible to run on the processor of. Therefore, in the shared memory type multiprocessor system according to the present invention, each processor has a means for setting the base number of the item value number according to the range of the item value number and the maximum of the item value number expressed by the base number. The current digit is set in order from the lower digit to the most significant digit, the first time the record number array is set as the current record number array, and the second and subsequent record number arrays are set as the current record number array, and the sort is performed. Includes means of repeating the process.</p><p> The means for repeating the sort process of each processor is a means for determining a part of the record number array that the own processor is in charge of, and a means for determining the current digit value of the item value number corresponding to the record included in the part of the record number array. Includes means for counting the number of occurrences.</p><p> Further, the means for repeating the sort process of at least one processor is the record number array within the range in which the values of the current digits of the item value numbers match in the order of the values of the current digits of the item value numbers. A means for converting the number of occurrences of each of the values of the current digit of the item value number into a cumulative number according to the order of the parts of.</p><p> Further, the means for repeating the sort process uses the cumulative number of the current digit values of the item value numbers corresponding to the records included in the record number array portion as a pointer to the record number array portion. Includes means to store the included record numbers in an additional record number array.</p><p> According to the present invention, each processor does not need to determine the range of the current digit value of the item value number that the own processor is in charge of, and a plurality of processors share the process of converting the number of occurrences into the cumulative number. This simplifies the configuration of a shared memory multiprocessor system because it does not have to be done.</p><p> Further, according to the third aspect of the present invention, a program for realizing such an information processing method is provided.</p><p> Further, according to a fourth aspect of the present invention, a storage medium on which such a program is recorded is provided.</p>

<p> According to the present invention, it is possible to provide an information processing apparatus capable of realizing high-speed parallel sorting of large-scale tabular data in a shared memory type parallel processing environment.</p>

Hereinafter, various embodiments of the present invention will be described with reference to the accompanying drawings.

[Computer system configuration] FIG. 1 is a schematic diagram of an embodiment of a computer system that implements an information processing method for rearranging the order of records according to the item values of predetermined items of records according to the present invention. As shown in Figure 1, this computer system 10 has p processors (CPUs) 12-1, 12-2, ... 12-p that control the entire system and individual components by executing programs. , Shared memory for storing work data, for example, RAM (Random Access Memory) 14, ROM for storing programs, etc. (Read Only) Provided between Memory) 16, fixed storage medium 18 such as a hard disk, CD-ROM driver 20 for accessing CD-ROM 19, CD-ROM driver 20, and an external terminal connected to an external network (not shown). It is equipped with an interface (I / F) 22, an input device 24 consisting of a keyboard and a mouse, and a CRT display device 26. The CPU 12, RAM 14, ROM 16, external storage medium 18, I / F 22, input device 24, and display device 26 are connected to each other via a bus 28. Although not shown, each CPU may have its own local memory.

The program for rearranging the record order according to the item value of a predetermined item of the record according to the present embodiment may be stored in the CD-ROM 19, read by the CD-ROM driver 20, or stored in the ROM 16 in advance. It may have been done. Further, what is once read from the CD-ROM 19 may be stored in a predetermined area of the external storage medium 18. Alternatively, the program may be supplied from the outside via a network (not shown), an external terminal, and an I / F22.

Further, the shared memory type multiprocessor system according to the embodiment of the present invention is realized by causing the computer system 10 to execute a program that rearranges the record order according to the item value of a predetermined item of the record.

[Data management mechanism based on information blocks] FIG. 2 is a diagram showing an example of tabular data for explaining the data management mechanism. This tabular data is stored in the computer as a data structure as shown in FIG. 3 by using the data management mechanism proposed in the above-mentioned International Publication No. WO00 / 10103.

As shown in FIG. 3, the array 301 (hereinafter, this array is abbreviated as "OrdSet") that associates the sequence number of each record of the tabular data with the sequence number of the internal data is The order number of the internal data is arranged as a value for each record in the tabular format. In this example, all the tabular data is represented as internal data, so the record number of the tabular data and the sort order number of the internal data match.

For example, regarding gender, it can be seen that the sequence number of the internal data corresponding to record 0 of the tabular data is "0" from the array OrdSet301. The actual gender value for the record whose sort order number is "0", that is, "male" or "female", is a value list 303 in which the actual values are sorted according to a predetermined order (hereinafter, the value list is referred to as "VL". It can be obtained by referring to the pointer array 302 (hereinafter, the pointer array is abbreviated as "VNo") to the pointer array 302 (hereinafter, the pointer array is abbreviated as "VNo"). The pointer array 302 stores pointers that point to the elements in the actual value list 303 according to the order of the sequence numbers stored in the array OrdSet301. As a result, the item value of the gender corresponding to the record "0" of the tabular data is (1) the sequence number "0" corresponding to the record "0" is extracted from the array OrdSet301, and (2) the pointer to the value list. Extract the element "1" corresponding to the sequence number "0" from the array 302, and (3) the pointer to the value list from the value list 303. The element "woman" pointed to by the element "1" extracted from the array 302. Can be obtained by taking out.

Item values can be obtained for other records as well as for age and height.

In this way, the tabular data is represented by a combination of the value list VL and the pointer array VNo to the value list, and this combination is particularly referred to as an "information block". In FIG. 3, information blocks relating to gender, age and height are shown as information blocks 308, 309 and 310, respectively.

If a single computer is a single memory (which may be physically multiple, but a single memory in the sense that it is located and accessed in a single address space), that memory The array OrdSet of the ordinal set, the value list VL and the pointer array VNo that compose each information block may be stored. However, in order to hold a large number of records, the memory capacity increases with the size, so it is desirable to be able to process these large numbers of records in parallel.

Therefore, in the present embodiment, a plurality of processors access the record data stored in the shared memory, and high-speed sorting is realized by parallel processing of the plurality of processors.

[Parallel sort] Next, an information processing method for rearranging the record order according to the item value of a predetermined item of the record in the shared memory type multiprocessor system according to the embodiment of the present invention, that is, a parallel sorting method will be described. 4A and 4B are diagrams showing the data structure to be sorted. The tabular data 401 shown in Figure 4A is an easy-to-understand representation of the data structure to be sorted in a matrix format, including 20 records from record 0 to record 19, where each record is age and region. It is composed of two items. The data structure 402 shown in FIG. 4B represents the data structure stored in the shared memory 14 of the computer system 10. The record number array (OrdSet: representing an ordered set) 403 in FIG. 4B is an array that stores record numbers 0 to 19 in a predetermined order. In this example, the record numbers are stored in the order of 0 to 19. Age and region data are stored in the form of information block 404 and information block 405, respectively. The age information block 404 is an item value number array (hereinafter also referred to as VNo: value number) 406 in which item value numbers corresponding to age item values are stored in the order of record numbers, and an age item value. Is composed of an item value array (hereinafter also referred to as VL: value list) 407 stored in the order of the item value numbers corresponding to the item values. Similarly, in the regional information block 405, the item value number array 408 in which the item value numbers corresponding to the regional item values are stored in the order of the record numbers and the item numbers in which the regional item values correspond to the item values It is composed of an array of item values 409 stored in order. The p processors 12-1, ..., 12-p of the computer system 10 can access these data on the shared memory 14.

FIG. 5 is a flowchart of the parallel sorting method according to the embodiment of the present invention. In this embodiment, the number of CPUs is four, and an example in which all CPUs operate in parallel is considered. It should be noted that the total number of CPUs in the system and the number of CPUs operating in parallel are not limited to this example. Further, in the following, for convenience of explanation, a case where the age items are sorted in ascending order of age will be considered. In addition, the elements of the age item value array are arranged in ascending order of age. The parallel sorting method consists of five steps from step 501 to step 505.

Step 501: Divide the record number array into four and allocate each part to four CPUs (see Figure 6).

Step 502: Each CPU counts in parallel the number of occurrences of the item value number corresponding to the record contained in the part of the assigned record number array (see Figures 7A, B to 9A, B).

Step 503: Assign a range of item value numbers, that is, five values from item value number 0 to item value number 4, to the four CPUs. For example, CPU-0 is assigned item value numbers 0 and 1, and CPU-1 to CPU-3 are assigned item value numbers 2 to 4 one by one (see Figure 10A).

Step 504: Each of the four CPUs accumulates the number of occurrences of each of the assigned item value numbers according to the order of the item value numbers and the order of the parts of the record number array within the range where the item value numbers match. (See Figures 10A and B).

Step 505: The four CPUs use the cumulative number of item value numbers corresponding to the records included in the allocated record number array part as a pointer, and the record numbers included in the allocated record number array part. Is stored in an additional record number array (see Figures 11A, B to 13A, B).

Next, each step will be described in detail.

FIG. 6 is an explanatory diagram of the initialization step 501 of the parallel sorting method. Four records are assigned to each of the four CPUs from CPU-0 to CPU-3 in order from the beginning of the record number array. For example, CPU-0 is responsible for the first OrdSet [0] to the fifth OrdSet [4] of the record number array (x in OrdSet [x] represents the subscript of the array OrdSet). Further, the shared memory 14 is provided with count arrays Count-0, Count-1, Count-2 and Count-3 for counting the number of occurrences of the item value number, and is associated with each CPU. The number of Count arrays is the same as the number of CPUs, and the array size of Count arrays is the same as the size of VL arrays. The elements of the Count array are initialized with 0.

7A and 7A to 9A and 9B are explanatory views of the count-up step 502 of the parallel sorting method. In substep 1 of FIG. 7A, for example, CPU-0 reads the value 0 of OrdSet [0], reads the value 1 of VNo [0] with the read value 0 as a subscript, and subscripts this value 1. As a result, the value 0 of Count-0 [1] is incremented to 1. Similarly, CPU-1 reads the value 5 of OrdSet [5], reads the read value 5 as a subscript, reads the value 2 of VNo [5], and uses this value 2 as a subscript, Count-1 [2]. ] Value 0 is incremented to 1. The same applies to CPU-2 and CPU-3. In substep 2 of FIG. 7B, for example, CPU-0 reads the value 1 of OrdSet [1], reads the value 1 of the read value 1 as a subscript, reads the value 3 of VNo [1], and subscripts this value 3. Increment the value 0 of Count-0 [3] to 1. The same applies to CPU-1, CPU-2 and CPU-3. As shown in FIGS. 8A and B and FIG. 9A, each processor reads each element of the array OrdSet in charge of its own processor, reads the element of the array VNo using the element as a subscript, and further reads the element of the array VNo. Increment the elements of the corresponding Count array with the elements as subscripts. As a result, a count-up result as shown in FIG. 9B is obtained. The element Count-0 [i] of the array Count-0 in Figures 9A and B is the item value of the age corresponding to each record in the range from OrdSet [0] to OrdSet [4] of the array OrdSet in charge of CPU-0. It represents the number of occurrences of the number i. For example, Count-0 [0] indicates that the item value number 0 in the range in charge of CPU-0 appears once, and Count-3 [1] indicates the item in the range in charge of CPU-3. Indicates that the value number 1 appears twice.

10A and 10B are explanatory views of cumulative numbering steps 503 and 504 of the parallel sorting method. In this example, cumulative numbering is performed in ascending order of item value numbers corresponding to ascending sort. CPU-0 is in charge of accumulating the first and second rows (that is, item value numbers 0 and 1) of the array Count, and CPU-1 to CPU-3 are 3 to 5 of the array Count, respectively. Responsible for accumulating the line (that is, item value numbers 3 to 5). As shown in Figure 10A, the cumulative numbering is done with priority given to the horizontal direction of the array Count (that is, the rows with matching subscripts), and then the cumulative number of preceding rows is changed to the cumulative number of subsequent rows. By adding, the total cumulative number is determined. It should be noted that each CPU can execute the cumulative numbering in the horizontal direction in parallel.

In general, the count value of the item value number j (0 j q-1) counted up by CPU-i, which is the i-th (0 i p-1) CPU, is counted [i] [j], and the cumulative total. Expressing a number as Count'[i] [j], the cumulative numbering can be described as follows. Count'[0] [0] = 0 Count'[i] [0] = Count'[i-1] [q-1] + Count [i-1] [q] where i&gt; 1 Count'[i] [j] = Count'[i] [j-1] + Count [i] [j-1] where j&gt; 1 Thus, in the cumulative number operation, it is necessary to propagate the offset Count'[i-1] [q-1] from the preceding row to the next row. Therefore, in the present embodiment, the CPU is responsible for the calculation of the cumulative numbering, but one processor may be selected and the cumulative numbering may be performed independently by that processor.

Figure 10B shows the order of cumulative numbering in a vertical row. For example, in FIG. 10B, the line (1) Count-0: 0 indicates that the count value 1 of the first element Count-0 [0] of the array Count-0 is converted to the cumulative number 0. That is, 1,2,2,0,2,0,2,2,0,2,0,1,1,1,0,1,1,0,1,1 When the series of count values is accumulated, 0,1,3,5,5,7,7,9,11,11,13,13,14,15,16,16,17,18,18,19 become.

11A, B to 13A, B are explanatory views of transfer step 505, which stores record numbers in a further record number array. In the transfer step, each CPU reads the record number within the range it is in charge of from the record number array OrdSet, then reads the item value number from the pointer array VNo using that record number as a subscript, and further, this item value. Using the number as a subscript, read the cumulative value from the cumulative Count array associated with the own processor, point to this read cumulative value, store the record number in the further record number array OrdSet', and count. Increment the cumulative number of the array by 1.

For example, in substep 1 of Figure 11A, CPU-0 reads the value 0 of OrdSet [0] (ie, record number 0), then the value 1 of VNo [0], and the associated Count. Read the value 5 of Count-0 [1] of the array, set the record number 0 to OrdSet [5], and increment the value of Count-0 [1] to 6. The transfer process of this record number proceeds as in substep 2 of FIG. 11B, substeps 3 and 4 of FIGS. 12A and B, and substep 5 of FIG. 13A, and finally shown in FIG. 13B. An additional record number array OrdSet'is obtained.

14A to 14C and 15A and 15B are diagrams showing the results of applying the parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B. In this example, ascending sort by age was performed, so records having 16 years, 18 years, 20 years, 21 years, and 23 years as age item values are arranged in order of age in the resulting record number array OrdSet'. You can see that there is. In addition, the order of records with matching ages is stored in the original record number array OrdSet.

Although the above parallel sorting method describes an example of ascending sorting related to age, this parallel sorting method can be similarly applied to descending order sorting related to age. Descending sort is performed in the same way as ascending sort, but the cumulative numbering order is different from ascending sort. 16A and 16B are explanatory views of the cumulative numbering steps of the parallel (descending) sorting method according to the embodiment of the present invention. As shown in Figure 16A, the cumulative numbering is done by giving priority to the horizontal direction of the array Count (that is, the rows with matching subscripts), and then the cumulative number of the trailing rows is changed to the cumulative number of the preceding rows. By adding, the total cumulative number is determined. It should be noted that each CPU can execute the cumulative numbering in the horizontal direction in parallel.

In general, the count value of the item value number j (0 j q-1) counted up by CPU-i, which is the i-th (0 i p-1) CPU, is counted [i] [j], and the cumulative total. Expressing a number as Count'[i] [j], the cumulative numbering can be described as follows. Count'[p-1] [0] = 0 Count'[i] [0] = Count'[i + 1] [q-1] + Count [i + 1] [q] where i&gt; 1 Count'[i] [j] = Count'[i] [j-1] + Count [i] [j-1] where j&gt; 1 Thus, in the cumulative number operation, it is necessary to propagate the offset Count'[i + 1] [q-1] from the back row to the front row. Therefore, in the present embodiment, the CPU is responsible for the calculation of the cumulative numbering, but one processor may be selected and the cumulative numbering may be performed independently by that processor. Figure 16B shows the order of cumulative numbering in a vertical row. In FIG. 16B, for example, the line (1) Count-0: 4 indicates that the count value 1 of the first element Count-0 [4] of the array Count-0 is converted to the cumulative number 0.

17A and 17B to 19A and 19B are explanatory views of transfer step 505 of the parallel sorting method in descending order. In the transfer step, each CPU reads the record number within the range it is in charge of from the record number array OrdSet, then reads the item value number from the pointer array VNo using that record number as a subscript, and further, this item value. Using the number as a subscript, read the cumulative value from the cumulative Count array associated with the own processor, point to this read cumulative value, store the record number in the further record number array OrdSet', and count. Increment the cumulative number of the array by 1.

20A and 20B and 21A to 21C are diagrams showing the results of applying the descending parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B. In this example, the records are sorted in descending order by age, so in the resulting record number array OrdSet', records having age items of 23, 21, 20, 18, and 16 are arranged in order of age. You can see that there is. In addition, the order of records with matching ages is stored in the original record number array OrdSet.

[Parallel totalization operation] Next, the cumulative numbering step 504 described in the above embodiment will be described more specifically. When the count result shown in FIG. 9B is obtained, the cumulative numbering as shown in FIGS. 10A and 10B is performed. Since the cumulative numbering is performed in parallel, the value range of the target item value number is assigned to each CPU. Item value numbers 0 and 1 are assigned to CPU-0, item value number 2 is assigned to CPU-1, item value number 3 is assigned to CPU-2, and item value number 4 is assigned to CPU-3. Therefore, if the elements of the Count array are represented in the form of Count [i] [j] as described above (i is the number of the CPU in charge of counting and j is the item value number), the cumulative number of each CPU is calculated. Scope of responsibility: -CPU-0 charge range (item value numbers 0 and 1) Count [0] [0] = 1 Count [1] [0] = 2 Count [2] [0] = 2 Count [3] [0] = 0 Count [0] [1] = 2 Count [1] [1] = 0 Count [2] [1] = 2 Count [3] [1] = 2 -CPU-1 charge range (item value number 2) Count [0] [2] = 0 Count [1] [2] = 2 Count [2] [2] = 0 Count [3] [2] = 1 CPU-2's range of responsibility (item value number 3) Count [0] [3] = 1 Count [1] [3] = 1 Count [2] [3] = 0 Count [3] [3] = 1 -CPU-3 charge range (item value number 4) Count [0] [4] = 1 Count [1] [4] = 0 Count [2] [4] = 1 Count [3] [4] = 1 Is obtained.

When such a range of responsibility is determined, first, when each CPU-i calculates the subtotal Sum [i] of the count within the range of responsibility, Sum [0] = 11 Sum [1] = 3 Sum [2] = 3 Sum [3] = 3 Is obtained. The calculation of this subtotal is parallel processing.

Next, if this subtotal is propagated in order from CPU-0 to CPU-3 and the cumulative number of subtotals Aggr_sum [i] is calculated, Aggr_sum [0] = 0 Aggr_sum [1] = Aggr_sum [0] + Sum [0] = 11 Aggr_sum [2] = Aggr_sum [1] + Sum [1] = 14 Aggr_sum [3] = Aggr_sum [2] + Sum [2] = 17 Is obtained. The cumulative number of subtotals is defined so that the beginning is 0.

Finally, each CPU-i converts the Count value to the cumulative number in the range of responsibility, and adds the calculated cumulative number of subtotals Aggr_sum [i] to the cumulative number of the Count value to obtain the final count. Get the cumulative number Count'. This Count'calculation is also parallel processing. This will -CPU-0 charge range (item value numbers 0 and 1) Count'[0] [0] = 0 + Aggr_sum [0] = 0 + 0 = 0 Count'[1] [0] = Count' [0] [0] + Count [0] [0] = 0 + 1 = 1 Count'[2] [0] = Count'[1] [0] + Count [1] [0] = 1 + 2 = 3 Count'[3] [0] = Count'[2] [0] + Count [2] [0] = 3 + 2 = 5 Count'[0] [1] = Count'[3] [0] + Count [3] [0] = 5 + 0 = 5 Count'[1] [1] = Count'[0] [1] + Count [0] [1] = 5 + 2 = 7 Count'[2] [1] = Count'[1] [1] + Count [1] [1] = 7 + 0 = 7 Count'[3] [1] = Count'[2] [1] + Count [2] [1] = 7 + 2 = 9 -CPU-1 charge range (item value number 2) Count'[0] [2] = 0 + Aggr_sum [1] = 9 + 2 = 11 Count'[1] [2] = Count' [0] [2] + Count [0] [2] = 11 + 0 = 11 Count'[2] [2] = Count'[1] [2] + Count [1] [2] = 11 + 2 = 13 Count'[3] [2] = Count'[2] [2] + Count [2] [2] = 13 + 0 = 13 CPU-2's range of responsibility (item value number 3) Count'[0] [3] = 0 + Aggr_sum [2] = 0 + 14 = 14 Count'[1] [3] = Count'[0] [3] + Count [0] [3] = 14 + 1 = 15 Count'[2] [3] = Count'[1] [3] + Count [1] [3] = 15 + 1 = 16 Count'[3] [3] = Count'[2] [3] + Count [2] [3] = 16 + 0 = 16 -CPU-3 charge range (item value number 4) Count'[0] [4] = 0 + Aggr_sum [3] = 0 + 17 = 17 Count'[1] [4] = Count'[0] [4] + Count [0] [4] = 17 + 1 = 18 Count'[2] [4] = Count'[1] [4] + Count [1] [4] = 18 + 0 = 18 Count'[3] [4] = Count'[2] [4] + Count [2] [4] = 18 + 1 = 19 Is obtained.

This result is consistent with the cumulative numbering result shown in Figure 10B.

[Multi-step parallel sorting] Parallel sorting based on the above counting sort can be combined with the idea of radix sort. When the size of the item value array VL is large, that is, when the number of item value numbers is large, the item value numbers are expressed in radix and the above parallel sort is performed for each digit to perform efficient sorting. It is possible to achieve it. Hereinafter, such a multi-step parallel sorting method will be described. In particular, in the multi-step parallel sort according to the present embodiment, the final sort is completed by starting from the lowest digit, performing sort processing on the current digit in order, and finally performing sort processing on the highest digit. To do.

Even in one example of the multi-step parallel sorting method according to the implementation of the present invention, the data structure of FIG. 4B used in the above example of the parallel sorting method is used. In this embodiment, the number of CPUs is four, and an example in which all CPUs operate in parallel is considered. It should be noted that the total number of CPUs in the system and the number of CPUs operating in parallel are not limited to this example. Further, in the following, for convenience of explanation, a case where the age items are sorted in ascending order of age will be considered. In addition, the elements of the age item value array are arranged in ascending order of age. In the data structure of Fig. 4B, the item value number VNo related to age can take a value from 0 to 4, so if the item value number is decomposed with the radix = 4, the item value number will be two digits, the lower digit and the upper digit. Is decomposed into. Specifically, the modulo (4) value of the item value number is the value of the lower digit, and the quotient of the item value number divided by 4 is the value of the upper digit.

FIG. 22 is a flowchart of the multi-step parallel sorting method according to the embodiment of the present invention. The multi-step parallel sorting method consists of five steps from step 2201 to step 2205.

Step 2201: Select the radix of the item value number according to the range of the item value number (base = 4 in this example), set the initial record number array OrdSet to the current record number array, and set the lowest of the item value numbers. (In this example, the modulo (4) value of the item value number) is set to the current digit.

Step 2202: Divide the current record number array and assign it to 4 processors.

Step 2203: In each of the four processors, count the number of occurrences of the current digit value of the item value number corresponding to the record contained in the part of the assigned record number array.

Step 2204: Divide the range of values for the current digit of the item value number and assign it to four processors.

Step 2205: In each of the four processors, in the order of the current digit value of the item value number, and in the order of the part of the record number array as long as the value of the current digit of the item value number matches. , Converts the number of occurrences of each of the values of the current digit of the assigned item value number to the cumulative number.

Step 2206: In each of the four processors, use the cumulative number of occurrences of the current digit value of the item value number corresponding to the record contained in the assigned record number array as a pointer. , Stores the record numbers contained in the part of the assigned record number array in the additional record number array.

Step 2207: Determine whether the sort process has been performed up to the most significant digit of the item value number expressed in radix, and if it has been sorted to the most significant digit, end the multi-step parallel sort process.

Step 2208: If any unprocessed digits remain, set that digit to the current digit and return to step 2202 with an additional record number array as the current record number array.

In the multi-step parallel sorting method according to the embodiment of the present invention, the sorting process from step 2202 to step 2206 is the same process as the above-mentioned parallel sorting method of the present invention, and the item is replaced with the item value number. The only difference is that the value of the current digit of the value number is used.

Next, the multi-step parallel sorting method according to the embodiment of the present invention will be specifically described. In this example, the data shown in Figure 4B is sorted in ascending order of age using four CPUs. In the initialization step 2201, the sort process related to the value (lower digit value) of the age item value number Modulo 4 (MOD 4) is set as the first-stage sort process, and the second-stage sort process is performed. Set the sort process for the value of the quotient (DIV 4) divided by the age item value number 4.

In initialization step 2201, an array similar to the Count array shown in FIG. 6 is prepared. However, the array of this example is an array that counts the number of occurrences of the value of the current digit of the item value number.

23A and 23B to 25A and 25B are explanatory views of the counting step 2203 of the first stage of the multi-step parallel sorting method. In substep 1 of FIG. 23A, for example, CPU-0 reads the value 0 of OrdSet [0], reads the value 1 of VNo [0] with the read value 0 as a subscript, and modulo this value 1. Increment the value 0 of Count-0 [1] to 1 with the value 1 of 4 (MOD4) as a subscript. Similarly, CPU-1 reads the value 5 of OrdSet [5], reads the value 2 of VNo [5] with this value 5 as a subscript, and uses the value 2 of MOD4 of this value 2 as a subscript, Count-1. Increment the value 0 of [2] to 1. Hereinafter, by executing the sub-step 2 of FIG. 23B, the sub-step 3 of FIG. 24A, the sub-step 4 of FIG. 24B, and the sub-step 5 of FIG. 25A, the count-up result as shown in FIG. 25B can be obtained. The element Count-0 [i] of the array Count-0 in FIGS. 23A and B to 25A and B corresponds to each record in the range from OrdSet [0] to OrdSet [4] of the array OrdSet in charge of CPU-0. Indicates the number of occurrences of the value i in the lower digit of the item value number of the age to be used. For example, Count-0 [0] means that the value 0 of the lower digit of the item value number within the range of CPU-0 occurs once, and Count-3 [1] means CPU-3. Indicates that the number of occurrences of the value 1 in the lower digit of the item value number within the range in charge of is 2 times.

26A and 26B are explanatory diagrams of the cumulative numbering step of the first stage of the multi-step parallel sorting method. In this example, the cumulative number is accumulated in ascending order of the values of the lower digits of the item value number corresponding to the ascending sort. CPU-0 is in charge of accumulating the first line of the array Count (that is, the value 0 of the lower digit of the item value number), and CPU-1 to CPU-3 are 2 to 4 of the array Count, respectively. Responsible for accumulating the line (that is, the values 1 to 3 in the lower digits of the item value number). As shown in Figure 26A, the cumulative numbering is done with priority given to the horizontal direction of the array Count (that is, the rows with matching subscripts), and then the cumulative number of the preceding rows is changed to the cumulative number of the following rows. By adding, the total cumulative number is determined. As described above, each CPU can execute the cumulative numbering in the horizontal direction in parallel, but a single CPU may be in charge.

27A, 27A to 29A, B are explanatory diagrams of a transfer step in which the record numbers are stored in a further record number array in the first stage of the multi-step parallel sorting method. In the transfer step, each CPU reads the record number within the range it is in charge of from the record number array OrdSet, and then reads the value of the lower digit of the item value number from the pointer array VNo using that record number as a subscript. Furthermore, using the value of the lower digit of this item value number as a subscript, the cumulative value is read from the cumulative Count array associated with the own processor, and the read cumulative value is pointed to for a further record number. The record number is stored in the array OrdSet', and the cumulative value of the Count array is incremented by 1. FIG. 29B represents the record number array OrdSet'obtained in the first step as a result of such a transfer step.

In the second stage, the record number array OrdSet'obtained in the first stage is used as an initial condition, and ascending sort is performed for the value of the upper digit of the item value number of the age (DIV 4 value).

FIG. 30 shows a state in which the current record number array OrdSet'is assigned to four CPUs and each Count array is prepared in step 2202 of the second stage of the multi-step parallel sorting method according to the embodiment of the present invention. It is a figure which shows.

31A and B to 33A and 33B are explanatory views of the count step of the second stage of the multi-step parallel sorting method. In substep 1 of FIG. 31A, for example, CPU-0 reads the value 2 of OrdSet'[0], reads the value 4 of VNo [2] with the read value 2 as a subscript, and sets this value 1. The value 0 of Count-0 [1] is incremented to 1 with the value 1 of the quotient (DIV4) divided by 4 as a subscript. Similarly, CPU-1 reads the value 12 of OrdSet'[5], reads the value 4 of VNo [12] with this value 12 as a subscript, and uses the value 1 of DIV4 of this value 4 as a subscript, Count- 1 Increment the value 0 of [1] to 1. By executing sub-step 2 in FIG. 31B, sub-step 3 in FIG. 32A, sub-step 4 in FIG. 32B, and sub-step 5 in FIG. 33A, the count-up result of the second stage as shown in FIG. 33B can be obtained. can get. In FIGS. 31A, B to 33A, and B, the element Count-0 [i] of the array Count-0 is each record in the range from OrdSet'[0] to OrdSet [4] of the array OrdSet'in charge of CPU-0. Indicates the number of occurrences of the value i in the upper digit of the item value number of the age corresponding to. For example, Count-0 [0] means that the value 0 of the upper digit of the item value number within the range of CPU-0 has occurred 4 times, and Count-3 [1] means CPU-3. Indicates that the number of occurrences of the value 1 in the upper digit of the item value number within the range in charge of is 0.

FIG. 34 is an explanatory diagram of the cumulative numbering step of the second stage of the multi-step parallel sorting method. In this example, the cumulative number is accumulated in ascending order of the value of the upper digit of the item value number corresponding to ascending sort. Since the number of values in the upper digit of the item value number has been reduced to two by multi-stepping, in this example, for example, CPU-0 is in charge of accumulating all values. As shown in Figure 34A, CPU-0 is Count [0] [0], Count [1] [0], Count [2] [0], Count [3] [0], Count [0] [ Cumulative counting is performed in the order of 1], Count [1] [1], Count [2] [1], and Count [3] [1]. Of course, in the case of this example, the values 0 and 1 of the upper digit of the item value number may be assigned to the two CPUs, CPU-0 and CPU-1, and the two CPUs may perform the cumulative numbering operation. ..

35A and 35A to 37A and 37B are explanatory diagrams of a transfer step in which the record numbers are stored in a further record number array in the second stage of the multi-step parallel sorting method. In the transfer step, each CPU reads the record number within the range it is in charge of from the record number array OrdSet, and then reads the value of the upper digit of the item value number from the pointer array VNo using that record number as a subscript. Furthermore, using the value of the upper digit of this item value number as a subscript, the cumulative value is read from the cumulative Count array associated with the own processor, and the read cumulative value is pointed to for a further record number. The record number is stored in the array OrdSet and the cumulative numerical value of the Count array is incremented by 1. FIG. 37B shows the record number array OrdSet obtained in the second stage as a result of such a transfer step.

Since the multi-step parallel sorting method of this embodiment is composed of two steps, the lower digit and the upper digit of the item value number, no further sorting process is performed. Therefore, the record number array OrdSet obtained in the second stage is the result of sorting the first record number array OrdSet in ascending order with respect to age.

38A to 38C and 39A and 39B are diagrams showing the results of applying the ascending multi-step parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B. In this example, ascending sort by age was performed, so records having 16 years, 18 years, 20 years, 21 years, and 23 years as age item values are arranged in order of age in the resulting record number array OrdSet. In addition, the order of the records with the same age is stored in the original record number array OrdSet. The results of this invention shown in FIGS. 14A to 14C and 15A and 15A and B are shown in FIGS. This is consistent with the result of applying the ascending parallel sorting method according to the embodiment of FIG. 4B to the data structure of FIG. 4B.

Further, although the above-mentioned multi-step parallel sorting method is ascending order sorting, the multi-step parallel sorting of the present invention also operates in descending order sorting. Further, as described above, the cumulative numbering operation at each stage of the multi-stage parallel sort may be performed in parallel by a plurality of processors, or at least one processor, preferably one processor alone. May be processed.

[Multi-stage sorting] In the above-mentioned multi-step parallel sort, the final sort is completed by starting from the lowest digit, performing sort processing on the current digit in order, and finally performing sort processing on the most significant digit. On the other hand, it is also possible to complete the final sort by starting from the most significant digit, performing sort processing on the current digit in order, and finally performing sort processing on the least significant digit. In the following, a method of increasing the number of stages of the sort process in the order of the highest level to the lowest level will be briefly described.

In this example, the data structure shown in FIG. 40 is used. In this example, the number of CPUs is one. In the following, we will consider the case of sorting the age items in ascending order of age. The total number of records is 20 from record number 0 to record number 19, and the item value numbers are 9 from 0 to 8. That is, there are nine actual age values: 15, 16, 18, 19, 20, 21, 23, 25 and 28. In the data structure of Fig. 40, the item value number VNo related to age can take a value from 0 to 8, so if the item value number is decomposed with the radix = 4, the quotient obtained by dividing the item value number by 4 is the upper digit. It is a value, and the value of the modulo (4) of the item value number is the value of the lower digit. The upper digit of the item value number can take three values of 0, 1 and 2, and the lower digit can take four values of 0, 1, 2 and 3.

First, in the first stage, the array Count-1 for counting the number of occurrences of the upper digit values 0, 1 and 2 is prepared, and the elements are initialized with 0. For example, Count-1 [0] is an area for counting the number of records in which the value of the upper digit of the item value number is 0.

Next, in order from the first element (that is, record) of the record number array OrdSet, the item value number corresponding to that element is read from the array VNo, and the value of the quotient obtained by dividing the item value number by 4 is used as a pointer. And increment the value of the element in the array Count-1. Figures 41A to 41 show the values of the upper digits of the item value numbers for the three record numbers of OrdSet [0] = 0, OrdSet [7] = 7, and OrdSet [19] = 19. It is explanatory drawing of the example of counting up the counter to be performed, and then accumulating the number. As can be seen from FIG. 41C, the number of records in which the value of the upper digit of the item value number is 0 is 12 and the number of records in which the value of the upper digit is 1 is 1 due to the count-up process of the first stage. The number of records with 7 records and the value of the upper digit is 2 is 1. Further, as shown in FIG. 41D, this count value is accumulated.

Next, the record number array OrdSet is converted into a further record number array OrdSet'using the array Aggr-1 in which the number of occurrences of the value of the upper digit of the item value number is accumulated. Specifically, if OrdSet [i] = j, read VNo [j] and divide this VNo [j] by 4 (VNo [j] DIV. If 4) is k, the value of Aggr-1 [k] is read, the record number j is set in OrdSet [Aggr-1 [k]], and Aggr-1 [k] is incremented. 42A and 42B are explanatory diagrams of the record number transfer process in such a multi-step sort, FIG. 42A shows the transfer of OrdSet [0], and FIG. 42B shows the transfer of OrdSet [19]. FIG. 43 shows the record number array OrdSet'as a result of the record number transfer in the first stage and the range in which the values of the upper digits are distributed. For example, records with a high-order digit value of 0 are distributed in the range (interval 0) from OrdSet'[0] to OrdSet'[11] of the record number array OrdSet', and records with a high-order digit value of 1. Is distributed in the range (interval 1) from OrdSet'[12] to OrdSet'[18] of the record number array OrdSet', and the record whose upper digit value is 2 is OrdSet'[19] of the record number array OrdSet'. It exists in (section 2).

Next, in the second stage of multi-step sorting, the record number is sorted by the value of the lower digit of the item value number within each section. For example, section 1 of OrdSet'is transferred to the corresponding section 1 of OrdSet'. In the second stage sort, the record number is transferred outside the section because the section is already defined by the upper digit. There is no such thing.

FIG. 44 is a diagram showing the initial state of the second stage of the multi-stage sort. In the following description, section 1 of OrdSet'will be described. For example, when there are a plurality of processors, the following processes can be parallelized by allocating processors for each section. Count-2 is an array for counting the number of occurrences of the lower digit value (0,1,2,3) of the item value number in interval 1.

FIGS. 45A to 45C are explanatory diagrams of the count-up and cumulative counting of the second stage of the multi-stage sort. By counting up sequentially starting from FIG. 45A, a count-up sequence as shown in FIG. 45B is obtained. This count-up array is cumulative as shown in Figure 45C.

Finally, by using the second cumulative number array Aggr-2 as a pointer and transferring the section 1 of the record number array OrdSet'to the section 1 of the record number array OrdSet', the multi-step sort is completed. 46A and B are explanatory diagrams of the record number transfer of the second stage of the multi-stage sort. Specifically, if OrdSet'[i] = j, VNo [j] is read and this VNo [j] is read. ] Is divided by 4 and the remainder (VNo [j] MOD 4) is k, then the value of Aggr-2 [k] is read, the record number j is set in OrdSet [Aggr-2 [k]], and Aggr -2 Increment [k]. Figure 46A shows the transfer of OrdSet'[14], and Figure 46B shows the transfer of OrdSet'[18]. Section 1 of OrdSet in FIG. 46B represents the final sort result of section 1.

Similar to section 1, by applying the second stage count-up, cumulative numbering, and record number transfer to other sections 0 and 2, the entire record number array OrdSet becomes the record number array OrdSet . Transferred and sorting is complete.

As described above, in the embodiment of the present invention, the computer system 10 is made to execute a program that rearranges the record order according to the item value of a predetermined item of the record. More specifically, in the present embodiment, the program causes each CPU to execute the above-mentioned processing step or realize the above-mentioned function as follows.

In the present embodiment, the computer system 10 is equipped with an OS (for example, Linux (registered trademark)). Initially, under the control of the OS, a CPU (eg CPU12-1) loads the program into memory (eg shared memory 14). When the program is loaded into memory, if CPU12-1, 12-2, ..., 12-p should each execute the process, each CPU has a predetermined value under the control of the OS. Realize the function. That is, each CPU reads a predetermined processing step in the program stored in the shared memory 14 and executes the processing step. On the other hand, when a specific CPU should perform processing, the specific CPU is made to realize another predetermined function under the control of the OS. That is, only a specific CPU reads another predetermined processing step in the program stored in the shared memory 14 and executes the other predetermined processing step. The storage location of the program executed by each CPU is not limited to the shared memory 14, and may be a local memory (not shown) attached to each CPU.

As described above, in the present embodiment, under the control of the OS, the program realizes a predetermined function in each CPU and, if necessary, realizes another predetermined function in a specific CPU. Can be done.

The present invention is not limited to the above embodiments, and various modifications can be made within the scope of the invention described in the claims, and these are also included in the scope of the present invention. Needless to say.

<figref num="1">FIG. 1 is a schematic view of a computer system according to an embodiment of the present invention.</figref><figref num="2">FIG. 2 is a diagram showing an example of tabular data for explaining the data management mechanism.</figref><figref num="3">FIG. 3 is an explanatory diagram of a data management mechanism according to the embodiment of the present invention.</figref><figref num="4">4A and 4B are explanatory views of a data structure to be sorted according to the embodiment of the present invention.</figref><figref num="5">FIG. 5 is a flowchart of the parallel sorting method according to the embodiment of the present invention.</figref><figref num="6">FIG. 6 is an explanatory diagram of an initialization step of the parallel sorting method according to the embodiment of the present invention.</figref><figref num="7">7A and 7B are explanatory views (No. 1) of the count-up step of the parallel sorting method according to the embodiment of the present invention.</figref><figref num="8">8A and 8B are explanatory views (No. 2) of the count-up step of the parallel sorting method according to the embodiment of the present invention.</figref><figref num="9">9A and 9B are explanatory views (No. 3) of the count-up step of the parallel sorting method according to the embodiment of the present invention.</figref><figref num="10">10A and 10B are explanatory views of the cumulative numbering steps of the ascending parallel sorting method according to the embodiment of the present invention.</figref><figref num="11">11A and 11B are explanatory views (No. 1) of the transfer step of the ascending parallel sorting method according to the embodiment of the present invention.</figref><figref num="12">12A and 12B are explanatory views (No. 2) of the transfer step of the ascending parallel sorting method according to the embodiment of the present invention.</figref><figref num="13">13A and 13B are explanatory views (No. 3) of the transfer step of the ascending parallel sorting method according to the embodiment of the present invention.</figref><figref num="14">14A to 14C are diagrams (No. 1) showing the results of applying the ascending parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B.</figref><figref num="15">15A and 15B are diagrams (No. 2) showing the results of applying the ascending parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B.</figref><figref num="16">16A and 16B are explanatory views of the cumulative numbering step of the parallel sorting method in descending order according to the embodiment of the present invention.</figref><figref num="17">17A and 17B are explanatory views (No. 1) of the transfer step of the descending parallel sorting method according to the embodiment of the present invention.</figref><figref num="18">18A and 18B are explanatory views (No. 2) of the transfer step of the descending parallel sorting method according to the embodiment of the present invention.</figref><figref num="19">19A and 19B are explanatory views (No. 3) of the transfer step of the descending parallel sorting method according to the embodiment of the present invention.</figref><figref num="20">20A and 20B are diagrams (No. 1) showing the results of applying the descending parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B.</figref><figref num="21">21A to 21C are diagrams (No. 2) showing the results of applying the descending parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B.</figref><figref num="22">FIG. 22 is a flowchart of the multi-step parallel sorting method according to the embodiment of the present invention.</figref><figref num="23">23A and 23B are explanatory views (No. 1) of the count-up step of the first stage of the multi-step parallel sorting method according to the embodiment of the present invention.</figref><figref num="24">24A and 24B are explanatory views (No. 2) of the count-up step of the first stage of the multi-stage parallel sorting method according to the embodiment of the present invention.</figref><figref num="25">25A and 25B are explanatory views (No. 3) of the count-up step of the first stage of the multi-stage parallel sorting method according to the embodiment of the present invention.</figref><figref num="26">26A and 26B are explanatory views of the cumulative numbering step of the first stage of the ascending multi-step parallel sorting method according to the embodiment of the present invention.</figref><figref num="27">27A and 27B are explanatory views (No. 1) of the first-stage transfer step of the ascending multi-stage parallel sorting method according to the embodiment of the present invention.</figref><figref num="28">28A and 28B are explanatory views (No. 2) of the first-stage transfer step of the ascending multi-stage parallel sorting method according to the embodiment of the present invention.</figref><figref num="29">29A and 29B are explanatory views (No. 3) of the first-stage transfer step of the ascending multi-stage parallel sorting method according to the embodiment of the present invention.</figref><figref num="30">FIG. 30 is an explanatory diagram of a second stage initialization step of the multi-step parallel sorting method according to the embodiment of the present invention.</figref><figref num="31">31A and 31B are explanatory views (No. 1) of the count-up step of the second stage of the multi-step parallel sorting method according to the embodiment of the present invention.</figref><figref num="32">32A and 32B are explanatory views (No. 2) of the count-up step of the second stage of the multi-step parallel sorting method according to the embodiment of the present invention.</figref><figref num="33">33A and 33B are explanatory views (No. 3) of the count-up step of the second stage of the multi-step parallel sorting method according to the embodiment of the present invention.</figref><figref num="34">FIG. 34 is an explanatory diagram of the cumulative numbering step of the second stage of the ascending multi-step parallel sorting method according to the embodiment of the present invention.</figref><figref num="35">35A and 35B are explanatory views (No. 1) of the second-stage transfer step of the ascending multi-stage parallel sorting method according to the embodiment of the present invention.</figref><figref num="36">36A and 36B are explanatory views (No. 2) of the second-stage transfer step of the ascending multi-stage parallel sorting method according to the embodiment of the present invention.</figref><figref num="37">37A and 37B are explanatory views (No. 3) of the second-stage transfer step of the ascending multi-stage parallel sorting method according to the embodiment of the present invention.</figref><figref num="38">38A to 38C are diagrams (No. 1) showing the results of applying the ascending multi-step parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B.</figref><figref num="39">39A and 39B are diagrams (No. 2) showing the results of applying the ascending multi-step parallel sorting method according to the embodiment of the present invention to the data structure shown in FIG. 4B.</figref><figref num="40">FIG. 40 is a data structure diagram for explaining multi-step sorting.</figref><figref num="41">Figures 41A to 41D are explanatory diagrams of the count-up and cumulative counting of the first stage of the multi-stage sort.</figref><figref num="42">42A and 42B are explanatory diagrams of record number transfer in the first stage of multi-stage sorting.</figref><figref num="43">FIG. 43 is an explanatory diagram of the result of the record number transfer of the first stage of the multi-stage sort.</figref><figref num="44">FIG. 44 is a diagram showing the initial state of the second stage of the multi-stage sort.</figref><figref num="45">Figures 45A to 45C are explanatory diagrams of the count-up and cumulative counting of the second stage of the multi-stage sort.</figref><figref num="46">46A and 46B are explanatory diagrams of record number transfer in the second stage of multi-stage sorting.</figref>

Code description

10 computer system 12-1,12-2, ..., 12-p CPU 14 shared memory 16 ROM 18 Fixed storage 20 CD-ROM driver 22 I / F 24 Input device 26 Display device