JPH061432B2 - Data alignment device - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a data sorting device that sorts a data set in ascending or descending order of data values.

[Conventional technology]

Generally, a data sorting device merges two sorted data subsets and multiple comparison units that double the number of data included in the sorted data subsets to 1, 2, 4, ... It is configured to be connected in cascade. The conventional data alignment device can be roughly classified into two types according to the configuration of the comparison unit. Hereinafter, they will be referred to as the A system and the B system.

First, an A-system data alignment device will be described with reference to FIGS.

FIG. 6 is a diagram showing a device configuration example of the A system, 10 is a data alignment device, 20 is a data input terminal of the device 1, 30 is a data output terminal of the device 1, and 40-1 to 40-U are comparison units. Is. Each comparison unit has a memory 603 that stores one of the sorted data subsets input from the input terminal 601, has the same size as the memory 603, and stores the other of the sorted data subsets from the input terminal 601. Memory 604, read / write circuit 605 for reading / writing data from / to memories 603 and 604, memory 60
Register 606 for storing 1 byte of data of No. 3 and register 60 for storing 1 byte of data of memory 604
7, a comparator 608 for comparing the values of the data stored in the registers 606 and 607, a register 6 according to the comparison result
It comprises a multiplexer 609 that establishes a path for transferring the data stored in either 06 or 607 to the output terminal 602. Here, the size of the memories 603 and 604 is one data in the comparison unit 40-1.
-2 for 2 data, 40-3 for 4 data, 4
0-U has a size capable of storing 2 ^U-1 data.

FIG. 7 shows a time chart of an example of merge processing of the data subset pairs in the comparison unit 40-3 of FIG. 7th
The figure shows the merging process of two data subset pairs each consisting of four 1-byte data. In FIG. 7, reference numeral 700 is a data pair comparison process, and 701 is a memory 6.
A process of reading one byte from 03 and storing it in the register 606, a process 702 of reading one byte from the memory 604 and storing it in the register 607, and a process 703 of the register 606.
And the value of the data stored in 607 are compared, and the data in one register is selected by the multiplexer 609 according to the comparison result, and the data is output from the output terminal 602 to the comparison unit 4
A process of writing one byte of data to the memory 603 or 604 from the comparison unit 40-2 via the input terminal 601 at the same time of transferring to 0-4 is shown. 7
04 is data having a size of 1 byte. 705-
1 and 706-1 are sequentially input from the input terminal 601 1
The seventh sorted data subset pair, and 707-1 is the sorted output data subset after merging with respect to the data subset pair. Similarly, 705-2 and 706-2 are the second sorted input data subset pair, and 707-2 is the sorted output data subset after the merging for the data subset pair.

With respect to the example of FIG. 7, the processing state in the comparison unit 40-3 is shown in FIG. In FIG. 8, “∧” and “∨” indicate that the data in the registers 606 and 607 are smaller, and “x” indicates that they are not compared. Reference numeral 800 denotes a partition of the data subsets in the memories 603 and 604, 800-1 is a partition of the data subsets 705-1 and 705-2, and 800-2 is a partition of the data subsets 706-1 and 706-2. Show. The time corresponds to the time and processing 701, 702, 703 in FIG.

By the way, in the A-system data alignment device, as shown in FIG. 6, since there is only one data read / write circuit for the memories 603 and 604, reading / writing can be performed only sequentially. Therefore, as shown in FIG. 7, three processes are required for reading / writing to / from the memory for the process of 1 byte. Also, the output of the next data subset cannot be performed until all the data subsets of the memories 603 and 604 have been output. In the example of FIG. 7, the data subsets 705-1 and 706-1 are stored in the memories 603, 6 respectively.
After the data is input to 04, when the output of the data subset 705-1 is completed, the input of the next data subset 705-2 is started. Therefore, depending on the value of the data, there is a vacancy in the input of the data subset, as shown in FIG. For these two reasons, the method A has a drawback that the processing time is slow.

Next, a B-system data alignment device will be described with reference to FIGS.

FIG. 9 is a diagram showing a device configuration example of the B system, and the data alignment device 10 has a configuration in which the comparison units 40-1 to 40-U are connected in cascade, as in FIG. Each comparison unit has a memory 903 for storing a sorted data subset input from the input terminal 901, a memory 904 having a size of 1 data, a read / write circuit 905 of the memory 903, and a size of 1 byte. Register 906
907 and 910, a comparator 908 for comparing the values of the data stored in the registers 906 and 907, and a register 90
Data output terminal 9 outputs either data 6 or 907.
It is composed of a multiplexer 909 for selecting a route to be transferred to the H.02. The size of the memory 903 is the same as in the case of FIG.
2 data, 40-3 4 data, 40-
U has a size capable of storing 2 ^U-1 pieces of data.

FIG. 10 is a time chart showing an example of merging processing of data subset pairs in the comparison unit 40-3 of FIG. In FIG. 10, reference numeral 1000 denotes a data pair comparison process, which is divided into two processes 1001 and 1002. In the process 1001, the multiplexer 909 selects one of the following operations from the data of one of the registers 906 and 907 by the multiplexer 909, and the data output terminal 9
This is a process of simultaneously performing the operation of outputting to 02, and the operation from is as follows.

Data is input from the data input terminal 901 and stored in the register 907 via the memory 904.

Data is input from the data input terminal 901 and stored in the register 910.

1 byte of data is read from the memory 903 and stored in the register 906.

In addition to the above operation, the data in the register 906 is stored in the register 907.

A process 1002 stores the data in the register 910 in the memory 90.
In this processing, the values of the data in the registers 906 and 907 are compared with each other in the comparator 908 at the same time as being stored in No. Reference numeral 1003 indicates data having a size of 1 byte. 1004 is one sorted input data subset, 1
005 is the other sorted input data subset, 1006
Is the output data subset after merging.
The result of merging 05-1 is 1006-1, which is 100
The result of merging 4-2 and 1005-2 is 1006-2.

FIG. 11 shows the details of the processing in the comparison unit 40-3 for the example of FIG. 11th
In the figure, since the data size is 1 byte, the unused memory 904 is omitted. 1100 is a partition of a data subset in the memory 903, 1100-1 is a partition of the data subsets 1004-1 and 1005-1, 1
100-2 is a data subset 1004-1 and 1004-
2 division 1100-3 is a data subset 1005-
1 and 1004-2 and 1100-4 are the data subset 10
The division between 04-2 and 1005-2 is shown. Reference numeral 1101 denotes a pointer that connects data included in one data subset in the memory 903. The time corresponds to the time and processes 1001 and 1002 in FIG.

As shown in FIG. 10, in the B-system data alignment device,
Since there is no time for input / output of the data subset,
Although the processing time can be shortened, it has a drawback that the control is very complicated. That is, in the case of the process 1001 in FIG. 10, there are many processes. Also, the memory 9
Up to three data subsets are stored in 03, and data management is complicated. In the example of FIG. 10, at the time of data input at time 9, the data subset 100 is stored in the memory 903.
Data of 4-1, 1004-2 and 1004-3 are stored.

[Object of the Invention]

An object of the present invention is to provide a data alignment device that can be easily controlled and can shorten the data alignment time.

[Characteristics of the Invention]

According to the present invention, each comparison unit of the data alignment device is provided with two memories, and two data are input to the comparison unit.
One of the features is that the data is copied and stored in one memory at the same time, and the merge processing is performed using the data in these memories.

Example of Invention

FIG. 1 is a diagram showing a configuration example of a data alignment device according to the present invention. In FIG. 1, the data alignment device 10 has a configuration in which a plurality of comparison units 40-1 to 40-U are connected in cascade. 20 is a 1-byte wide data input terminal of the device 10, 3
Reference numeral 0 is a 1-byte width data output terminal of the device 10, 101 is a 1-byte width data input terminal of the comparison unit, and 102 is a 1-byte width data output terminal of the comparison unit. Each of the comparison units 40-1 to 40-U includes
The memory 103 that stores one sorted data subset input from the input terminal 601, the memory 104 that stores the other sorted data subset, and the memories 103 and 10.
4, read / write circuits 105-1, 105-2 for respectively reading and writing data, register 106 for storing 1 byte of data in memory 103, register 107 for storing 1 byte of data in memory 104, register 106.
And a comparator 108 for comparing the values of the data stored in 107 and 107, a multiplexer 109 for selecting a route for transferring the data of one of the registers 106 and 107 to the output terminal 102, and a comparison result signal from the comparator 108. , And a control circuit 110 for controlling each part of the comparison unit on the basis thereof. The sizes of the memories 103 and 104 are one data in the comparison unit 40-1, 40-2.
2 data, 40-3 4 data, 40-
U has a size capable of storing 2 ^U-1 pieces of data.

FIG. 2 is a diagram showing transitions of processing states in each comparison unit in FIG. 1, and 200 to 205 are states,
206 indicates the direction of transition. Each state 200-20
Reference numeral 5 includes a writing process and a reading process.

Now, the two sorted data subsets to be merged are respectively R and S in the order in which they are input to the comparison unit 40-i (i = 1, 2, ... U), and the sorted data portions input subsequent to S are input. Let T be the set. State A of 200 comprises the following processing.

Writing process: One byte of R data is input from the data input terminal 101, copied and stored in the memories 103 and 104.

 Read processing: Do nothing.

The state A is repeated until all the data of R are input, and then the state B of 201 is entered. State B consists of the following processing.

Writing process: One byte of S data is input from the data input terminal 101 and stored in either the memory 103 or 104.

Read processing: One byte of R or S data is read from the memory 103 and stored in the register 106 in the memory 10.
One byte of S or R data is read from 4 and stored in the register 107 at the same time.
The value of the data stored in 7 is compared by the comparator 108, and the comparison result is notified to the control circuit 110.

State B is processed only for the first byte at the beginning of S.
If there is remaining data in S, transition to state C, and if not, transition to state E. State C 203 includes the following processing.

Writing process: One byte of S data is input from the data input terminal 101 and stored in the memory in which all Rs are not stored. At the same time, one of the registers 106 and 107 is selected by the multiplexer 109 according to the instruction from the control circuit 110, and the data is output to the data output terminal 102.

 Read process: The same as the read process of state B.

State C is repeated until all the data of S are input. If the final byte of the final data of either R or S stored in the memories 103 and 104 is output in the next process, the state E is entered, and if not, the state D is entered. State D 204 includes the following processing.

Write process: One byte of T data is input from the data input terminal 101, copied and stored in the memories 103 and 104. At the same time, one of the registers 106 and 107 is selected by the multiplexer 109 according to the instruction from the control circuit 110, and the data is output to the data output terminal 102.

 Read process: The same as the read process of state B.

State D is repeated until the last byte of the final data of either R or S stored in memory 103 or memory 104 is output in the next process, and then state E is entered. The state E of 205 includes the following processing.

Write process: One byte of T data is input from the data input terminal 101, and the memory 103 or the memory 104
Of these, R or S is stored in the memory on the side where all are output, or the memory opposite to the memory on the side where this processing is output. At the same time, one of the registers 106 and 107 is selected by the multiplexer 109 according to the instruction from the control circuit 110, and the data is output to the data output terminal 102.

Read process: If R or S remains from the memory 102, 1 byte of R or S data is read, and if not, 1 byte of T data is read, and the register 106 is read.
At the same time, the 1-byte data is read from the memory 104 and stored in the register 107 as in the memory 103. (Here, the comparison is not performed, and the control circuit 110 instructs to output the data from the register storing the R or S data in the next process).

The state E is repeated until the last byte of the remaining R or S final data is output in the next process, that is, the state E is repeated until all the data of T is completely input, and then the state C is entered. Here, T is equal to R of the next merged data subset pair.

The state transition process of FIG. 2 is performed simultaneously in each comparison unit. The above processing can be easily realized by using, for example, a microprocessor for the control circuit 110 of each comparison unit.

FIG. 3 is a time chart showing a processing example according to the present invention. In this example, the comparison units 40-1, 40-2, 4 are shown.
By 0-3, 8 pieces of data having a size of 1 byte are aligned. In FIG. 3, 300 is a 1-byte process, 301 is a write process, 302 is a read process, 303
Is 1-byte data, 304 is a sorted data subset,
305 shows the state of FIG. Also, process 300
The time required for is 1 hour.

Regarding the example of FIG. 3, the comparison unit 40-1 of FIG.
Details of the movement of data within 40-2 and 40-3 are as shown in FIG. In FIG. 4, 400 is a data flow, 401 is the state shown in FIG. 2, 402 is a comparison result, and 403 is a delimiter of a data subset. The comparison result indicates that “V” is larger than the data value stored in the register 107, that is, “∧” is small, “‖” is small.
Are equal, and "x" means do not compare.

Although FIG. 3 shows an example in which the data size is 1 byte, the present invention can be easily extended to the case where the data size is arbitrary. When the data size is L bytes, the processing start time of the comparison unit 40-i (i = 1, 2, 3, ... U) is (2 ⁱ⁻¹ −1) L + i time, and the comparison of two data is performed. You can do the following: That is, when two data of size L bytes have the same value up to K bytes, the output up to K bytes is any one of the registers 106 and 107, and the next comparison byte is the next byte of each data. When the size of 2 data is judged at the K + 1 byte, the data is transferred from K + 1 byte to L
Up to bytes are output according to the size of the entire data.
The data to be compared next is the data next to the data output to the end before that, and the data that was only output halfway, and the comparison is started from the first byte of each data.

FIG. 5 is a time chart showing an example of alignment processing of two data of 4 bytes in the comparison unit 40-1, where 501 is a writing process, 502 is a reading process, and 503.
Indicates 4-byte data, 504 indicates a sorted data subset, and 505 indicates the state of FIG.

In general, N pieces of data are aligned by using “log ₂ N” comparison units, and LN + L · 2 “log ₂ N” “log ₂
It can be processed in N "-L time.

〔The invention's effect〕

As described above, according to the present invention, since two memories having the same structure are provided in one comparison unit, only one data subset at maximum exists in one memory, and
Since the data in the memory can be arranged in the order of input, the memory management becomes easy, and since there are only two state transition techniques at maximum, the control becomes easy. Furthermore, by copying data to 2 memories and reading data simultaneously from 2 memories, 1-byte comparison processing can be performed in 2 processings of writing and reading to the memory, and there is no interruption of processing between data. The advantage is that the time is short.

[Brief description of drawings]

FIG. 1 is a configuration diagram of an embodiment of a data alignment device according to the present invention, FIG. 2 is a diagram showing transitions of processing states of a comparison unit in FIG. 1, and FIG. 3 is a timing diagram showing a processing example according to the present invention. 4, FIG. 4 is a diagram showing the detailed operation of the processing example of FIG. 3, FIG. 5 is a timing diagram showing another processing example according to the present invention, and FIG. 6 is a first configuration example of a conventional data alignment device. FIG. 7, FIG. 7 is a timing chart showing the processing example of FIG. 6, FIG. 8 is a diagram showing the detailed operation of the processing example of FIG. 7, and FIG. 9 is a second diagram of the conventional data alignment device. The figure which shows the structural example, 10th
FIG. 11 is a timing chart showing the processing example of FIG. 9, and FIG. 11 is a diagram showing detailed operation of the processing example of FIG. 10 ... Data alignment device, 40-1 to 40-U ... Comparison unit, 101 ... Data input terminal, 102 ... Data output terminal, 103, 104 ... Memory, 105-1, 105-2
... Read / write circuit, 106, 107 ... Register, 1
08 ... Comparator, 109 ... Multiplexer, 110 ... Control circuit.

Claims (1)

[Claims] 1. A plurality of comparison units are connected in cascade, and in each comparison unit, two sets of aligned data subsets input from the preceding stage are aligned and merged, and the aligned data portion of the merged result. In a data sorting device that outputs a set to a latter stage and rearranges the data set in ascending or descending order of data values, each comparison unit includes a pair of memories for storing the sorted data subset input from the preceding stage. A pair of registers for storing the data read from each memory, a comparator for comparing the data values of the registers, a multiplexer for outputting the data of one of the registers to the subsequent stage, and a comparison of the comparators. When the multiplexer is controlled based on the result, the read / write of the memory is controlled, and the data input from the previous stage is controlled by 2 times.
A data alignment device, comprising: a control circuit for copying and storing the data in one memory, and discarding the copied data in the other memory when the data subsets are exhausted while merging the data in one memory.