Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-06-11
2001-12-11
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C235S375000, C235S436000, C340S146200
Reexamination Certificate
active
06330559
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system for merge sorting, i.e., data sequencing by comparison of number size, using database processing hardware.
2. Description of the Related Art
Generally, a record that is an element of a database consists of a plurality of fields. The process of sequencing records in an ascending or descending order using a particular field as a key is referred to as sorting. The process of reorganizing a plurality of sorted record arrays into one sorted record array is referred to as merging.
When performing sorting or merging using software, as a large amount of data is transferred within a processor, a memory, and a supplementary memory device such as a disk, a great deal of processing time is required. In contrast, a hardware pipeline merge sorting device can be provided to perform sorting at a high speed.
FIG. 10
is a block diagram showing a configuration of a pipeline merge sorting device described, for example, in “VLSI Sort Processor” (Information Processing, Vol. 31, No.4, 1990).
FIG. 10
includes linearly connected sort processors
1000
,
1001
,
1002
, and
1003
, and memory units
1010
,
1011
,
1012
, and
1013
connected to respective sort processors.
In the pipeline merge sorting device, the n
th
sort processor receives from the n−1
th
sort processor an input of two sets of sorted record arrays each comprising 2
n−1
records. The n
th
sort processor merges the two sets of record arrays and outputs one set of sorted record array comprising 2
n
records. The first record array of the two sets of record arrays is stored in the memory units connected to respective sort processors. The sorting process using the pipeline merge sorting device is shown in FIG.
11
.
FIG. 11
illustrates an example of transitional changes a record array undergoes when processed by two-way merge sorting. Generally in K-way merge sorting, the n
th
sort processor receives from the n−1
th
sort processor an input of K sets of sorted record arrays each comprising K
n−1
records. The n
th
sort processor merges the K sets of record arrays and outputs one set of sorted record array comprising K
n
records.
FIG. 12
is a diagram showing a configuration of a sort processor performing 8-way merge sorting using a tournament tree system.
FIG. 12
includes comparison nodes
1100
-
1120
, eight registers
1200
-
1207
retaining data to be introduced into the tournament circuit, and a register
1210
retaining data winning a comparison. Data from registers
1200
and
1201
are input to the comparison node
1100
corresponding to a first round match of the tournament. The output from this node
1100
serves as one of the two inputs to the comparison node
1110
corresponding to a second round match. As the other input to the node
1110
, the output from the comparison node
1101
corresponding to a different first round match is received. The output from the node
1100
serves as one of the two inputs to the comparison node
1120
corresponding to the third round match, or the final round. The output from the node
1120
serves as the input to the register
1210
.
FIG. 13
is a block diagram illustrating in greater detail a comparison node shown in FIG.
12
. Both data X and data Y serve as inputs to the comparator
1500
and the selector
1510
. Selection is performed in the selector
1510
in accordance with the comparison result from the comparator
1500
. The selector
1510
then outputs data Z.
The operation performed in the configuration of
FIGS. 12 and 13
will now be explained. A sorted record array, such as the one shown in
FIG. 4
, is input word by word to the input registers
1200
-
1207
. Each of the records in a record array comprises a key and a main record portion. Initially, the first word of the key of each foremost record in record arrays
0
-
7
is set in each of the registers
1200
-
1207
, and respective subsequent words are sequentially set in the registers as necessary.
However, in conventional 8-way merge sorting, eight record arrays must constantly be supplied to the input registers
1200
-
1207
. Record arrays are generally stored in a common memory and read out via a common data path. As the eight record arrays constantly vie for readout, merge-sorting performance is degraded.
To prevent such performance degradation, Japanese Patent Laid-Open Publication No. Hei 4-247571 discloses a data processing apparatus with an improved exchange and selection system, wherein, for example, 16-way merge sorting is executed by constantly comparing five records. This execution process corresponds to executing 8-way merge sorting by comparison of four records.
The above art, however, requires processes for initializing the registers comprising the tournament tree, for which extra clock cycles are necessary. More specifically, in 8-way merge sorting, for example, an extra clock cycle is inserted after every eight records in the first sort processor of the pipeline merge sorting device. This insertion may lead to performance degradation of the entire pipeline merge sorting device.
As such, in conventional K-way merge sorting, there remains the problem of performance degradation due to either the contending readouts of record arrays from memory or the requirement of extra clock cycles for initializing the registers of the tournament tree.
SUMMARY OF THE INVENTION
The present invention was created in an attempt to solve the above-described problem. The object of the present invention is to provide a merge sorting apparatus capable of performing merge sorting at a high speed.
To accomplish this object, the merge sorting apparatus of the present invention for sequencing records including one or more data items in an ascending or descending order by comparing the data items sequentially set in a plurality of input registers in every predetermined processing cycle, comprising a comparison tournament circuit having a plurality of comparison nodes connected in a tournament tree shape thereby forming a plurality of pathways starting with each of said input registers, each of said plurality of comparison nodes outputting one of two input data items as a result of performing a comparison processing of the two input data items and further outputting a comparison result of said comparison processing; and a comparison control circuit for determining, in accordance with the comparison results output by said comparison nodes, setting of validity flag information indicating validity of a data item to be subsequently input into each of said comparison nodes, and for supplying said determined validity flag information to corresponding each of said comparison nodes; wherein, in the following processing cycle, when the validity flag information transmitted from said comparison control circuit to each of said comparison nodes indicates that both of the two input data items are valid, each of said comparison nodes determines which input data item to output based on relative number sizes of the input data items and outputs the determined input data item, when the validity flag information indicates that only one of the two input data items is valid, each of said comparison nodes outputs said one of the input data items, and, when the validity flag information indicates that both of the two input data items are invalid, each of said comparison nodes outputs no input data items; and said comparison control circuit sets the validity flag information corresponding to the input data item not output in the data comparison processing to indicate invalidity, and, upon completion of a record comparison processing, sets the validity flag information corresponding to each of the input data items in each of said comparison nodes to indicate validity when the validity flag information corresponding to the comparison nodes connected at a stage below and outputting input data items to said each of said comparison nodes indicates validity, thereby allowing execution of merge sorting without initializing said comparison tou
Black Thomas
Leydig , Voit & Mayer, Ltd.
Mitsubishi Denki & Kabushiki Kaisha
Veillard Jacques
LandOfFree
Merge sorting apparatus with comparison nodes connected in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Merge sorting apparatus with comparison nodes connected in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Merge sorting apparatus with comparison nodes connected in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574605