JPH08171479A - Sort device - Google Patents

Abstract

(57) [Abstract] [Purpose] To provide a high-speed sorting device suitable for a parallel computing unit. A data distribution means 20 having a distribution method according to two modes determined by a mode signal D2, a two-input sorting means 30 for sorting and outputting two data selected by the data distribution means 20, Upon receiving the mode signal D2, the data distribution means 20 receives the sorted data.
The data storage means 1 is switched to the position determined by
An output data switching means 60 for storing in 0 is provided, and a sort calculator for partial sort having no conditional branch is configured. [Effect] By performing a partial sort having no conditional branch, it is possible to perform a high-speed sort process with a constant calculation time.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a sort device which is used as a sort circuit formed on an integrated circuit and is particularly suitable for parallel operation.

[0002]

2. Description of the Related Art Conventionally, many methods have been considered for a method of speeding up sorting. Most of them achieve high speed by reducing the number of comparisons used in sorting. In order to sort the n number array a (n) using the fast sort, the minimum average value of the number of comparisons performed is theoretically nlogn times (n is 2).
Power of). The smallest number of theoretical average comparisons is required, and the most commonly used sort that is easy to implement on a computer is the merge sort.

In the merge sort, first, n arrays a (n) are divided into n / 2 groups. The number of constituent elements in each group is two. Next, each group is compared and sorted. Two arbitrary sets are selected from the n / 2 groups thus sorted, and the two sets are sorted. In this case, the number of comparisons required for sorting is at most 3
Times. Do the same for the remaining groups. The result is n / 4 groups with 4 sorted arrays. The same operation is repeated until the number of groups becomes one. This will ultimately result in an array with n sorted elements. This sorting is advantageous in that the number of comparisons is reduced by dividing the array into groups, sorting by a small number, and then sorting between the groups.

Common to other high-speed sorts such as the binary tree method and the quick sort, including the merge sort, are as follows. That is to reduce the number of comparisons in the next step by performing partial sorting in advance. Here, when sorting is performed on a computer, since the time-consuming part is comparison, the reduction in the number of comparisons directly leads to speeding up of sorting. Further, most of the patent publications related to the conventional sorting method relate to the partial sorting method.

[0005]

When the merge sort or the binary tree method is used, the number of comparisons as a whole can be reduced, and high-speed sort can be performed. However, in these sorts, one comparison must be performed and the next comparison must be performed while observing the result. In other words, although the number of comparisons decreases, each partial sort must be performed sequentially. This is especially true for merge sorts and quick sorts.
Furthermore, the size and number of partial sorts change depending on the conditions of each stage of sorting. In other words, when a partial sort is performed using a parallel computer, the number of groups differs for each stage, so there are some parts where the operation stops. For example, consider a case where the eight number arrays are divided into four groups and the merge sort is performed using a parallel computer having four computers. In the first sort, the four computers are allotted to the sorts of each group. After that, the two groups are merged and the two groups are compared. However, in each group, one comparison is performed, and the next comparison is performed while observing the result, so the comparison can be performed only once. Therefore, when comparing two groups after merging, only two computers can be used. Therefore, the remaining two computers are in the dormant state. And in the next comparison,
For the same reason, only one computer will be used. Therefore, the remaining three computers are in a dormant state. In other words, there is a problem in that even if a parallel computer is used, the functions cannot be fully utilized.

As described above, when a conventional sort is used to implement a sort circuit on a computer, since the sorts within each group are sequential, partial sorts take time, and the total sort time is long. It has the drawback of decreasing. Therefore, when trying to realize a sorting circuit on a parallel computer, there is a drawback that the efficiency of operation is lowered because some circuits are not used. Further, since the sorting is performed while the condition is judged, the calculation time is not constant. Therefore, when incorporated in a device as an arithmetic unit, there is a drawback that the pipeline is difficult to assemble.

An object of the present invention is to realize a high-speed sort suitable for parallel computation by providing a sort method in which the size of partial sorts is fixed from beginning to end and sorting within groups is not sequential in each stage. To provide a device.

[0008]

A sorting device according to the present invention comprises:
A sorting device for sorting 2N data, comprising data storage means, mode switching means, N data distribution means (N: natural number), N 2-input sorting means, and output data switching means, The data storage means stores 2N pieces of input data, outputs 2N pieces of data, the input data is connected to the output data switching means, the output data is connected to the data distribution means, and the mode switching means is A mode signal is generated, and the mode signal is connected to the data distribution means and the output data switching means, m
The second data distribution means (m: a natural number from 1 to N) receives the mode signal, and in the first mode, 2m−1th and 2mth data from the 2N pieces of data in the data storage means. If the second mode is selected, the 2mth and 2th data from the 2N pieces of data in the data storage means are selected.
The m + 1st data is selected, and the data is connected to the mth two-input sorting means, the Nth data distributing means receives the mode signal, and if the first mode, 2N pieces of the data storing means are received. 2N-1 from the data of
If the second mode is selected, the 1st and 2Nth data are selected and the 1st and 2Nth data are selected from the 2N pieces of data in the data storage means.
Select the Nth data, and the data is the Nth 2
The two-input sorting means are connected to the input sorting means, and the two data selected by the data distributing means are sorted and output, and the output is connected to the output data switching means, and the output data switching means is connected to the output data switching means. Upon receiving the mode signal, the sorted data is switched to a position determined by the data distribution means and stored in the data storage means, and the output data switching means switches the mode when all the data are stored. The means switches the mode in response to the mode switching signal, and repeats the above operation until the number of switching times of the mode switching means reaches 2N-1.

Another sort device of the present invention is a data storage means, a mode switching means, N data distribution means (N: natural number), N 2-input sort means, address holding means, and N address exchanges. And a means for sorting 2N data, wherein said data storage means stores 2N input data, outputs 2N data to said data distribution means, and said mode switching means A mode signal is generated, the mode signal is connected to the data distributing means and the address exchanging means, the address holding means holds the address of the data in the data storing means, and the output is connected to the data distributing means, The m-th data distribution means (m: a natural number from 1 to N-1) receives the mode signal, and if the first mode, 2 of the address holding means. The data of the addresses written at the -1st and 2mth are selected from the 2N pieces of data in the data storage means, and in the second mode, the data are written at the 2mth and 2m + 1th addresses of the address holding means. The address data is selected from the 2N pieces of data in the data storage means, the data is connected to the m-th two-input sorting means, and the N-th data distribution means receives the mode signal, In the 1st mode, the data at the 2N-1th and 2Nth addresses of the address holding means is selected from the 2N pieces of data in the data storing means. In the second mode, the address holding means of the address holding means is selected. The data at the first and 2Nth written addresses are selected from the 2N pieces of data in the data storage means,
The data is connected to the N-th two-input sort means, and the two-input sort means compares the data selected by the data distribution means and outputs a sort signal when it is necessary to replace the data, and the output is the above-mentioned. If the input / output of the address of the m-th address exchanging means is connected to the address holding means, the mode signal is in the first mode, and the sort signal is generated, the address holding means of the address holding means is connected. If the address of the 2m-1th position and the address of the 2mth position are exchanged, and the mode signal is in the second mode and a sort signal is generated, the address of the 2mth position of the address holding means and 2m + 1.
The address of the second position is exchanged, and the output of the N-th two-input sort means is such that the input / output of the address is connected to the address holding means, the mode signal is the first mode, and the sort signal is generated. 2N of address holding means
-If the address at the 1st position and the address at the 2Nth position are exchanged, and the mode signal is in the second mode and the sort signal is generated, the address at the 1st position and the 2Nth position of the address holding means. When the address holding means completes the exchange of all the addresses, the mode switching means receives the value of the mode switching signal to switch the mode, and the above operation is performed by the number of times of switching of the mode switching means. Is repeated until becomes 2N-1.

[0010]

Operation: Sorting using the present invention is performed with 2N data strings a
An example will be described in which (1), a (2), a (3) .... a (2N-1), a (2N) (N: natural number) are sorted in ascending order. This sorting is realized by alternately repeating certain steps (first mode and second mode) shown below, 2N-1 times.

The first step of the data storage means is the first mode, for example, 2N data strings a (1) and a (2), a (3) and a (are generated by one of the two kinds of data distribution means. 4), a
Create a group such as (2m-1) and a (2m) (m: natural number from 1 to N). Then, N groups are completed.

Next, sorting is performed within each group. Here, the sorting means comparing the sizes of a (2m-1) and a (2m), and if a (2m-1) is large, a (2m-1) and a (2
Replace the value of m) and keep it if a (2m) is large. These 2N groups are sorted using N 2-input sorting means. Up to this point is the first step, and the mode of the mode switching means is switched here.

The next step is a (2) and a (3), a (4) and a (5), a (2m) and a (2m + 1) by the remaining data distribution means.
Create a group such as (m: natural number from 1 to N-1). Here, when m = N, a (1) and a (2N) are grouped. The number of created groups is N. Similarly, N two-input sorting means are used for sorting, and the mode of the mode switching means is switched. Repeat the above two steps until the number of steps becomes 2N-1
That is, the mode switching is repeated in sequence until the number of switching times becomes 2N-1. This completes the sort. Here first
Either the mode or the second mode may be started for the first time, but they are always performed alternately.

In this method, the number of times required for comparison is N * (2N
-1) times. When sorting is performed using such a configuration, the number of groups in which partial sorting is performed in each step is always N, and the number of elements in partial sorting is always 2. That is, the N partial sorts are independent of each other, and it is not necessary to perform sequential operations. That is, at each step, the N two-input sorting means all operate.

Therefore, the number of comparisons is 2N such as the binary tree method.
Although the number of steps required for sorting increases by N * (2N-1) times compared with * log (2N) times, the number of steps required for sorting is 2N-1 steps compared with the average step 2N * log (2N) times of the binary tree method. It becomes a short step, and a faster sort can be realized than the binary tree method. Also, with the above configuration, the division method of the partial sort is always constant throughout the sort, and does not depend on the calculation result of the previous step. Therefore, since a conditional branch circuit is not required, sort division can be realized at high speed. Also, since sorting is always performed a fixed number of times, it becomes easy to incorporate it into a hardware as a dedicated arithmetic unit.

[0016]

【Example】

(Embodiment 1) The construction of an embodiment according to claim 1 of the present invention will be described with reference to FIG. Consider a case where 2N pieces of data are sorted in descending power.

Reference numeral 10 is a data storage means. Reference numeral 20 denotes N data distribution means. Reference numeral 30 is a 2-input sort means. Reference numeral 90 denotes a mode switching means, which includes a counter 50 and an even / odd determination means 40. Reference numeral 60 is an output data switching means. The sorting method of the present embodiment has two modes. The first mode is defined as the counter 50 value is even, and the second mode is defined as the counter 50 value is odd. A timer 100 is set to generate a step end signal (mode switching signal) D6 when either the first mode or the second mode ends. The data storage means 10 stores 2N pieces of data, and simultaneously transfers the 2N pieces of data value D1 to the N pieces of data distribution means 20, respectively. Each of the N data distribution units 20 includes an even-stage data distribution unit 21 and an odd-stage data distribution unit 22.

M-th even-numbered stage data distribution means 21-m
(M is an integer from 1 to N) is the 2m-1th number and 2 out of the 2N pieces of data sent from the data storage means 10.
The m-th data is selected and the m-th two-input sorting means 3 is selected.
Send to 0-m. Similarly, the m-th odd stage data distribution means 2
2-m selects the 2m-th number and the 2m + 1-th data from the 2N pieces of data, and the m-th 2-input sort means 30-
send to m. However, when m = N, the odd number stage data distribution means 22
-N selects the first data and the Nth data in the data D1 and sends them to the Nth two-input sorting means.

The N 2-input sorting means 30 compare the given two data and sort them in descending power. That is, the m-th two-input sorting means 30-m sorts the two pieces of data D3 sent from the m-th data distributing means 20-m in descending order, and outputs the sorted data D4-m to the output data switching means 60. send.

The accidental judgment means 40 sends a accidental judgment signal (mode signal) D2 from the data of the counter 50. That is, if the data of the counter 50 is an odd number, the evenness determination signal D2
Thereby, the odd-numbered stage data distributing means 22 in the data distributing means 20 is selected. If the data of the counter 50 is an even number, the even number stage data distribution means 21 is selected. However, if the data of the counter 50 is even, the operation of selecting the odd-numbered data distribution means 22 in the data distribution means 20 and selecting the number of even-numbered data distribution means 21 may be performed. The counter 50 has an initial value set to 1, and a step end signal (mode switching signal) from the timer 100.
When receiving D6, the counter value is incremented by one. The output data switching means 60 includes N 2-input sorting means 30.
The data D4 is received from the data storage device 10 and converted into 2N data D5 and sent to the data storage means 10.

FIG. 5 shows the details of the output data switching means 60, and (Table 1) shows the case of sorting to the descending power when 2N = 4. The selectors S1 to S1 in the first mode and the second mode are shown.
The output of S3 is shown. Each of the 2-input sorts 30-1 and 30-2 sorts into a descending power and outputs the larger value as E1 and E3 and the smaller value as E2 and E4. The output data switching means 60 has selectors S1 to S3 inside, and changes the contents of the data D5 in response to the evenness judgment signal D2 and outputs the data. As shown in (Table 1), when the evenness determination signal D2 is an even number (first mode), the larger one of the data D4-m of the m-th two-input sorting means 30-m is 2 of the data storage means 10.
The output data D5 is output such that the smaller one is stored in the 2m-th position at the (m-1) th position. Accidental judgment signal D2
Is an odd number (second mode), the larger one of the data D4-m of the m-th two-input sort means 30-m is stored at the 2m-th position of the data storage means 10, and the smaller one is stored at the 2m + 1-th position, The output data D5 is output so that the larger data of D4-N is stored in the first position and the smaller data of the D4-N is stored in the 2Nth position. The above operation is performed by the counter 5
The value of 0 repeats until N-1. When this operation ends,
The data storage means 10 contains values for which sorting has been completed.

In the present embodiment, the case of sorting in descending power was explained, but in the case of sorting in ascending power, 2
Input sort 30 sorts into ascending powers, and the smaller value is E
If you output 1, E3 and the larger value as E2, E4,
The operation shown in (Table 1) may be performed in accordance with the accidental decision signal D2.

[0023]

[Table 1]

FIG. 2 shows 4 having a size of a3>a2> a1.
A case where the numbers are arranged in the order of a1, a2, a3, a1 is shown as an example to show a method of sorting in descending power by the sorting method having the configuration of FIG.

First, the counter 50 is set to 1. a
1, a2, a3, a1 are stored in the data storage means 10 in this order. The data storage means 10 is the data distribution means 20.
The data D1 to be sent to is sent in this order. Since the value of the counter 50 is 1, the advent determination unit 40 outputs the adjacency determination signal D2 as an odd number. Since the even number determination signal D2 of the N data distribution units 20 is an odd number, the odd number stage data distribution unit 22 is included.
Is selected. First odd-stage data distribution means 22-1
Selects the data a2 and a3 of the data stored at the second address and the third address of the data storage means 10, and selects the selected data D3-1 to the 2-input sort means 30-1.
Send as. The second odd-stage data distribution means 22-2 selects the data of a1 and a1 which are the data stored at the first address and the fourth address of the data storage means 10, and selects 2 as the selection data D3-2. Input sort means 3
Send to 0-2.

The 2-input sort means 30-1 receives the input a
Compare the data of 2, a3, and if a3 is larger, then a2 and a
After exchanging the data of No. 3, it is sent to the output data switching means 60 as the output data D4-1. The same operation is performed in the 2-input sort means 30-2, and the output data D4-2 having the contents of a1 and a1 is sent to the output data switching means 60. The output data switching means 60 combines the outputs of the two partial sorts and outputs them as the output data D5 to the data storage means 10, and then the timer 100 sends a step end signal D6 to the counter 50.

As shown in (Table 1), the output data switching means 60 determines that the larger number of D4-1 data is 2 in the data storage means 10 since the evenness judgment signal D2 is an odd number (second mode). The third data is stored in the data storage means 10 and the smaller data is stored in the third data storage means 10. That is, the data of a3 and a2 are respectively the second position and 3 of the data storage means 10.
Stored in the th position. Similarly, the larger data of D4-2 is stored in the first position of the data storage means 10, and the smaller data of D4-2 is stored in the fourth position of the data storage means 10. This is one step. After the step is completed, the data storage means 10 stores data in the order of a1, a3, a2, a1.

The second step begins with the addition of 1 to the counter 50 to reach 2. Since the evenness determination signal D2 from the evenness determination means 40 is an even number, the even number stage data distribution means 21 is selected. The even number stage data distribution means 21-1 selects the first data and the second data of the data storage means 10. The even number stage data distribution means 21-2 selects the third data and the fourth data of the data storage means 10. Then, the values of the selection data D3-1 are a1 and a3,
The values of the selection data D3-2 are a2 and a1. When this is sorted by the two 2-input sorting means 30, the data of D4-1 becomes a3, a1 and the data of D4-2 becomes a2, a1. By the output data switching means 60, the data of D5
a3, a1, a2, a1, and the data storage means 10 in this order
Stored in. After that, the timer 100 sends a step end signal to the counter 50. The above is the second step.

Similarly, the steps are advanced, and the sorting is completed when the third step is completed. Here, the 2-input sorting means 30-1 and 30-2 can be operated independently of each other. Therefore, if a parallel computer forming N 2-input sorting means is used, the input sorting means 30
-1 and 30-2 can be calculated simultaneously. That is, the N partial sorts performed by the 2-input sort means are simultaneously performed. Moreover, there are only two distribution methods for partial sorting: the even-numbered stage data distribution means 21 and the odd-numbered stage data distribution means 22, and there is no conditional branch depending on the sort operation result. Therefore, the data distributing means has a simpler structure than the conventional sorting method, and when realized by a circuit, a high-speed distributing means can be realized by a small circuit. Therefore, in a parallel computer, 2
It is possible to realize a sort operation that is faster than the sort method such as the branch method. Moreover, since the time required for partial sorting is the same as the time required for overall sorting, it becomes easy to incorporate the device into a device as a dedicated computing unit.

(Embodiment 2) FIG. 3 shows the construction of an embodiment according to claim 2 of the present invention. The output data switching means 60 of FIG. 1 is eliminated, and instead N address exchange means 70 are used.
And one address holding means 80 are connected. The output of the 2-input sort means 30 is not a data but a large or small decision signal, which is N number of address exchange means 70.
It is connected to the. The address signal D8 output from the address holding means 80 is connected to the data distribution means 20.

The address holding means 80 holds 2N addresses indicating the positions where 2N pieces of data are stored in the data storage means 10. The data selecting means 20 indicates the address D in the address holding means 80.
8 data are selected from the data storage means 10 and output to the 2-input sort means 30. That is, the first data distribution means 20-1 with an odd value of the counter 10 selects the first and second data of the data storage means 10 in the case of FIG. 1, but in the case of FIG. 3, the data storage means 20-1. From 10, the first written address and the second written address of the address holding means are selected. 2 Input sort means 3
0 is given the data D3 from the data distribution means 20 and makes a comparison. As a result of the comparison, when two numbers have to be exchanged for sorting, the two-input sorting means 30 issues the sort signal D7.

When the address exchanging means 70 receives the sort signal 70-m from the m-th two-input sorting means 30-m,
When the even-number determination signal D2 is an even number (first mode), the 2m-1th address and the 2mth address written in the address holding means 80 are exchanged, and an odd number (second mode). In the case of, the address written in the 2m-th address of the address holding means 80 and the address written in the 2m + 1-th address are exchanged. FIG. 6 shows the details of the address exchanging means 70, and (Table 2) shows the case of sorting to the descending power when 2N = 4. The selector S in the first mode and the second mode is shown.
The outputs of 1 to S4 are shown. The address exchanging means 70 has selectors S1 to S8 therein, and by the evenness judgment signal D2,
S1 to S4 are controlled, and S5 to S7 are controlled by D7-1 and D7-2.
Control S8. That is, from Table 2
Thus, in the first mode, S1 to S4 output E2, and in the second mode, S1 to S4 output E1.
When the sort signal D7 is issued, S5 to S8 select the outputs of S1 to S4, respectively, otherwise, S5.
.About.S8 select the output D9 from the address holding means. However, it is 1 when the contingency determination signal D2 is odd and m = N.
Exchange the address written in the th and the address written in the Nth. When the address holding means completes the exchange of all addresses, the timer 100 outputs the step end signal D6 to the counter 50. The operation of the other parts is the same as the operation of the configuration of FIG. When the above operation is completed, the address in the data storing means 10 of the mth largest data is written in the mth position of the address holding means 80.

[0033]

[Table 2]

FIG. 4 shows 4 having a size of a3>a2> a1.
A case where numbers are arranged in the order of a1, a2, a3, a1 is shown as an example to show a method of descending to the power in the sorting method having the configuration of FIG.

First, the counter 50 is set to 1. a
1, a2, a3, a1 are stored in the data storage means 10 in this order. The data storage means 10 is the data distribution means 20.
The data D1 to be sent to is sent in this order. In the address holding means 80, the address position and the address number initially match. The value of the counter 50 of the contingency judgment means 40 is 1
Therefore, the side-by-side determination signal D2 is output as an odd number. Since the even number determination signal D2 is an odd number in the N data distribution units 20,
The odd-numbered data distribution means 22 selects the selected data D3-
1 is sent to the 2-input sort means 30-1. The first odd-numbered data distribution means 22-1 is composed of data a2, which is the data indicating the second address of the address holding means 80, and a2, which is the data indicating the third address of the address holding means 80. Select a3, which is the data indicating a certain 3, from the data storage means 10, and select data D3.
It is sent to the 2-input sort means 30-1 as 3-1.

The second odd-numbered data distribution means 22-2 inserts the data a1 indicating the first address of the address holding means 80 and the fourth address of the address holding means 80. Is the data shown
The data a1 indicated by 4 is selected from the data storage means 10 and the 2-input sort means 3 is selected as the selected data D3-2.
Send to 0-2. 2-input sort means 30-1 is input
When the data of a2 and a3 are compared and a3 is larger, the sort signal D7-1 is issued to the address exchanging means 70-1. In this case, since a3 is larger, the sort signal D7-1
Will be issued. The same operation is performed by the 2-input sort means 30-2. In this case, the 2-input sort means 30-
Since the two numbers a1 and a1 compared in 2 have the same size,
The sort signal D7-2 is not issued.

As shown in (Table 2), the address exchanging means 70 receives the sort signal D7 and holds the address holding means 80.
Exchange addresses. In this case, the address exchange means 7
Since 0-1 receives the sort signal D7-1, a2 and a
Swap 2 and 3, which are the addresses of 3. Since the address exchanging means 70-2 has not received the sort signal D7-2, the addresses 1 and 4 of a1 and a1 are not interchanged.
After the address exchange is completed, the address holding means sends the step end signal D6 to the counter 50. This is one step. After the end of the step, the address holding means 80 stores the addresses in the order of 1, 3, 2, 4.

The second step begins with the addition of 1 to the counter 50 to reach 2. Since the evenness determination signal D2 from the evenness determination means 40 is an even number, the even number stage data distribution means 21 is selected. The even-numbered stage data distribution unit 21-1 indicates the data indicated by 1 which is the data indicated by the first address of the address holding unit 80 and the data indicated by 3 which is the data indicated by the second address of the address holding unit 80. From the data storage means 10. The second even-numbered data distribution means 22-2 is the data indicated by 2, which is the data indicated by the third address of the address holding means 80, and the data indicated by 4, which is the data indicated by the fourth address of the address holding means 80. The data shown is selected from the data storage means 10. In this case, the data of D3-1 is a
1, a3, and the data of D3-2 are a2, a1. Here, when sorting is performed by the 2-input sort means 30, the sort signal D7-1 is issued and the sort signal D7-2 is not issued. Therefore, the address exchange means 70-1 exchanges the addresses, and the addresses stored in the address holding means 80 become 3,1,2,1. After that, the address holding means 8
0 sends a step end signal to the counter 50. The above is the second step.

Similarly, the steps are advanced, and the sorting is completed when the third step is completed. With such a configuration, sorting can be performed without rewriting the data in the data storage unit 10. Since the data in the data storage means 10 is not rewritten at all, when the circuit is used to implement this device, the data storage means 10 can be used as a low speed and small device. Since the data amount of information when describing an address is much smaller than the data amount of the data storage means, it is possible to downsize the entire device and not to rewrite all the data every time. It is possible to reduce the power consumption for driving the.

[0040]

When sorting is performed using such a configuration of the present invention, the number of groups for which partial sorting is performed at each step is always N, and N is a 2-input sort means that operates efficiently. It will be. Therefore, the number of comparisons increases to N * (2N-1) times compared to 2N * log (2N) times such as the binary tree method, but the number of steps required for sorting is the average step 2N * log of the binary tree method. The number of steps is as short as 2N-1 steps compared to (2N) times, and a faster sorting than the binary tree method can be realized.

Further, with the above configuration, the division method of the partial sort is always constant throughout the sort, and the sorting is always performed in a constant cycle, so that it can be easily incorporated into a hardware as a dedicated arithmetic unit.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a sorting device according to a first embodiment of the present invention.

FIG. 2 is a diagram showing a data flow of the sorting apparatus of the embodiment.

FIG. 3 is a configuration diagram of a sorting device according to a second embodiment of the present invention.

FIG. 4 is a diagram showing a data flow of the sorting apparatus of the embodiment.

5 is a detailed diagram of the output data switching means of FIG.

FIG. 6 is a detailed diagram of the address exchange means of FIG.

[Explanation of symbols]

 10 data storage means 20 data distribution means 21 even-numbered data distribution means 22 odd-numbered data distribution means 30 2 input sort means 40 even / odd determination means 50 counter 60 output data switching means 70 address exchanging means 80 address holding means 90 mode switching means 100 timer

Claims (7)

[Claims] 1. A sorting device for sorting 2N data, comprising data storage means, mode switching means, N data distribution means (N: natural number), N 2-input sorting means and output data switching means. And the data storage means stores 2N pieces of input data,
N pieces of data are output, the input data are connected to the output data switching means, the output data are connected to the data distribution means, the mode switching means creates a mode signal, and the mode signal is the data distribution means. And the output data switching means, the m-th data distribution means (m: natural number from 1 to N) receives the mode signal, and in the first mode, outputs 2N data of the data storage means. The 2m-1st and 2mth data are selected from the inside, and in the second mode, the 2mth and 2mth data are selected from the 2N pieces of data in the data storage means.
The m + 1st data is selected, the data is connected to the mth two-input sort means, the Nth data distribution means receives the mode signal, and if the first mode, 2N pieces of the data storage means 2N-1th and 2Nth data are selected from among the 2N data, and in the second mode, the 1st and 2Nth data are selected from the 2N data in the data storage means, and the data are N The second input sort means is connected to the second input sort means, the two input sort means sorts and outputs the two data selected by the data distribution means, and the output is connected to the output data switching means, The switching means receives the mode signal, switches the sorted data to a position determined by the data distribution means, and stores the sorted data in the data storage means, When all the data are stored in the output data switching means, the mode switching means receives the mode switching signal to switch the mode, and the above operation is performed when the number of switching times of the mode switching means is 2N.
A sorting device characterized by repeating until it becomes -1. 2. The mode switching means includes a counter and an even / odd determination means connected to the counter, the counter receives a mode switching signal and increments by 1, and the even / odd determination means determines the value of the counter. The sorting device according to claim 1, wherein an even-odd judgment signal is generated. 3. The sorting apparatus according to claim 1, wherein N pieces of said two-input sort means and said data distribution means operate simultaneously. 4. The output data switching means has N output data switching units, and the m-th output data switching unit receives the mode signal. In the first mode, the m-th output data switching unit receives the mode signal. Out of the output of the input sort means, the larger data is stored in the 2m-1th position of the data storage means, and the smaller data is stored in the 2mth position of the data storage means, and the Nth data is stored. The data with the larger output of the 2-input sort means is stored in the 2N-1th position of the data storage means, and the data with the smaller output is stored in the 2Nth position of the data storage means. Of the output of the m-th two-input sort means, the larger data is stored in the 2m-th position of the data storage means, and the smaller data is stored in the data storage means of 2m + 1.
The second data of the output of the N-th two-input sort means is stored in the first position of the data storage means, and the data of the smaller output is stored in the second position of the data storage means. 2. The sorting device according to claim 1, wherein the sorting device is stored in. 5. A 2N number of data storage means, a mode switching means, N data distribution means (N: natural number), N 2-input sort means, address holding means, and N address exchanging means. A sorting device for sorting data, wherein the data storage means stores 2N pieces of input data,
The N pieces of data are output to the data distribution means, the mode switching means produces a mode signal, the mode signal is connected to the data distribution means and the address exchange means, and the address holding means of the data storage means. Holds the address of the data, the output of which is connected to the data distribution means, and the m-th data distribution means (m: a natural number from 1 to N-1) receives the mode signal, and if the first mode The data of the addresses 2m-1th and 2mth of the address holding means are stored in the data storage means 2
If the second mode is selected from the N pieces of data, the data of the addresses 2m and 2m + 1 of the address holding means are selected from the 2N pieces of data of the data storage means, The data is connected to the m-th two-input sorting means, the N-th data distributing means receives the mode signal, and in the first mode, 2N-1 of the address holding means.
The data of the addresses written in the 2nd and 2Nth addresses are selected from the 2N pieces of data in the data storage means, and the second data is selected.
In the mode, the data of the first and 2Nth addresses of the address holding means is selected from the 2N pieces of data of the data storage means, and the data is connected to the Nth two-input sort means. The 2-input sort means outputs the sort signal when it is necessary to compare the data selected by the data distributing means and replace the data, and the output is connected to the address exchanging means, and the m-th address exchanging means is exchanged. The input / output of the address is connected to the address holding means, and if the mode signal is in the first mode and a sort signal is generated, the address of the (2m-1) th position and the 2mth position of the address holding means. If the mode signal is in the second mode and the sort signal is generated, the address of the 2mth position of the address holding means is exchanged. The address at the 2m + 1th position is exchanged with the address, and the output of the N-th two-input sort means is connected to the address holding means for input / output of the address, the mode signal is in the first mode, and the sort signal is generated. If the address signal is stored in the address holding means, the address at the (2N-1) th position and the address at the 2Nth position are exchanged. Location address and 2
The address at the Nth position is exchanged, and when all the addresses of the addresses are exchanged by the address holding means, the mode switching means receives the value of the mode switching signal to switch the mode, and the above operation is performed by the mode switching. The number of switching means is 2N
A sorting device characterized by repeating until it becomes -1. 6. The mode switching means has a counter and an even / odd determination means connected to the counter, the counter receives a value of the mode switching signal and increments by 1, and the even / odd determination means determines the value of the counter. The sorting apparatus according to claim 5, wherein an even-odd determination signal is generated. 7. The sorting apparatus according to claim 5, wherein the two-input sorting means, the data distributing means, and the address exchanging means operate N at the same time.