JPS6327732B2 - - Google Patents

Description

[Detailed description of the invention]

(1) Technical field of the invention The present invention relates to a dedicated sorting processing device for sorting data at high speed in an electronic computer, and in particular uses a basic unit that compares three pieces of data simultaneously in order to shorten processing time. The present invention also relates to a parallel sorting processing device in which data transfer is duplicated. (2) Background of the Technology A large portion of the data processing performed on electronic computers involves sorting multiple numbers or keys. Therefore, if this processing could be executed with simple dedicated hardware, it would be highly effective in reducing the load on the central processing unit. In addition, the hardware structure required for this is
It is desirable that the structure be simple and suitable for LSI implementation. (3) Prior art and problems Conventionally, the basic unit 1 shown in Fig. 1 has been used as a dedicated processing device that has a repeating structure suitable for LSI implementation and executes sorting in parallel, and this As shown in the figure, a device configured by cascading a plurality of devices is known. In Fig. 1, 2 is an input section that has registers A and B that accept two pieces of data, 3 is a comparison/switch section, and 4 is an output section that has registers C and D that store data resulting from comparison operations. be. The basic unit 1 in FIG. 1 determines the magnitude of the values stored in A and B of the input section 2 using a comparison/switch section 3, and sets the smaller one to C of the output section 4 and the larger one to D. Stores the value. The basic unit 1 has two symmetrical connection patterns shown in FIGS. 2a and 2b, which are switched and used according to the operation phase when performing the sorting process. Figure a shows a pattern in the data reading phase, and Figure b shows a pattern in the data output phase. FIG. 3 shows a circuit of a conventional sorting processing apparatus constructed by cascading the above-mentioned basic units in a repeating structure. In the same figure, 5 to 7
is an illustrative example of the basic unit,
Further, the solid connecting lines are according to the pattern of FIG. 2a, and the dotted connecting lines are according to the pattern of FIG. 2b. x ₁ to x _o indicate the n pieces of input data to be sorted that are input from the data inlet of this device, and y ₁ to y _o indicate the n pieces of sorted input data that are output from the data outlet of the device. Show data. In this case, the numbers (or keys) to be sorted
Let n be the number of basic units required = [n/2] ... (i) Time required for sorting = 2n ... (ii). Here, [n/2] represents the smallest integer greater than n/2. FIG. 4 is an explanatory diagram of the operation of the conventional device shown in FIG. 3. This diagram shows six numbers 4, 3, 1,
5, 2, and 6 sorting processing is shown as an example. The sorting operation will be explained below with reference to FIG. First, a read phase operation is performed according to the solid line connection pattern. First, in step 0, a sufficiently large number (represented by ∞) is set in the output sections of all units. Next, input the input into A ₁ , perform a comparison, and calculate C _i , D _i (i=1,
2, 3), and put the next input into A ₁ again, and set the value of C _i in B _i (i = 1, 2, 3),
Enter the value of D _i-1 in A _i (i=2, 3). This operation is repeated from step 1 to step 6 until all inputs are read. Here, the operation is switched to the data output phase operation according to the connection pattern indicated by the dotted line. Therefore, from step 7 to step 12, the
Output the contents of C ₁ and put the value of D _i in A _i (i=1,
2, 3), enter the value of C _{i +1} in B _i (i = 1, 2).
Enter a sufficiently large number (∞) in _B3 . Then,
Perform a comparison and update the values of C _i and D _i (i=
1, 2, 3). By repeating this operation until all data is output, in step 12, results sorted in ascending order are obtained. Therefore, as shown in equation (ii), sorting requires twice as much time as the number of data. (4) Object of the Invention An object of the present invention is to provide a processing device that has the repeating regularity of a circuit structure like the conventional method and can perform sorting at a higher speed. (5) Structure of the Invention In order to achieve the above object, the present invention duplicates the data transfer paths between the basic units and simultaneously transfers the data between the basic units.
The basic unit is designed to be able to transfer 3 pieces of data in parallel, and to compare 3 pieces of data at the same time.It consists of an input section that accepts 3 pieces of data in parallel, and an input section that accepts 3 pieces of data in parallel. The basic system consists of a comparison operation section that simultaneously compares three pieces of data and changes the arrangement in order of size, and an output section that holds and outputs the three data whose arrangement has been changed by the comparison operation section in parallel. The units are connected in cascade to form a parallel sorting processing device having a data inlet and a data outlet, and have a data read phase and a data output phase, and in the data read phase, the input part of each basic unit is
two of the two data inputs are connected in parallel to the upper two data outputs of the data inlet or a basic unit adjacent to the data inlet side, and the remaining one is connected to the lowest data output of the basic unit, and In the data output phase, the outputs of each basic unit are such that the top two of its three data outputs are connected in parallel to the two data inputs of the basic unit, and the remaining lowest data output is connected to the data exit or to the data output of the basic unit. It is connected to one of the data inputs of the basic unit adjacent to the data exit side, and in the data reading phase, data is inputted in parallel two by two from the above data inlet, and in the data output phase, data is outputted one by one from the above data exit. It is characterized by (6) Examples of the invention The present invention will be described in detail below using examples. FIG. 5 shows the configuration of a basic unit used in an embodiment of the present invention. In the same figure,
8 is a basic unit, 9 is an input section, and U, V, and W are registers that store three input data. Reference numeral 10 denotes a comparison/switch section, which has the function of simultaneously comparing the contents of U, V, and W, and arranging the data in descending order according to the result and outputting the result. 11 is an output section, which includes a register X for storing comparison result data;
It follows from Y and Z. The relationship between the data size and the register arrangement is XYZ. 6a and 6b show connection patterns when a sorting processing apparatus is constructed using the basic pattern of FIG. 5. Figure a shows a pattern in the data reading phase, in which data is transferred to and from the outside through two input lines 12 and 13 and two output lines 1.
4 and 15 in parallel. That is, the top two data (values of Y and Z) of the comparison results are simultaneously output to other higher-level basic units, while the two new data are simultaneously input to U and V. The minimum data of the comparison result in register X is
Via the connection line 16, it is applied to the input section W of the same unit as input data for the next comparison operation. FIG. 5B shows a connection pattern in the data output phase of the sorting process. Here, data transfer with the outside is performed by one connection line 17, 18, as in the conventional basic unit. As the data output, the minimum value of the comparison result is taken out from register X. Also, registers Y and Z
The upper two data at 1 are sent to registers U and V of the same unit via connection lines 19 and 20, and are used as input data in the next comparison operation. FIG. 7 shows an embodiment of a sorting processing apparatus constructed by cascading the basic units shown in FIG. 5 in a repeating structure. In the same figure, 2
1 to 23 are the basic units, the solid connection lines are the patterns in the reading phase, the dotted connection lines are the patterns in the output phase, x _o , ... x ₄ , x ₂ and
x _o-1 , . . . x ₃ , x ₁ represent input data divided into two groups, and y ₁ , y ₂ , . . . y _o represent output data as a result of sorting, respectively. The input data is sent to unit 2 in parallel, one from each group, for each step operation in the read phase.
1, and one output data is output from the unit 21 for each step operation of the output phase. FIG. 8 shows a fourth example using the embodiment device shown in FIG.
It is an explanatory diagram of operation when sorting processing is performed on the same data 4, 3, 1, 5, 2, and 6 as in the case of the figure. In operation, first at step 0, the output parts X _i , Y _i , Z _i of all basic units are initialized to a sufficiently large number (denoted as ∞). Now begin the data loading phase. In step 1, U ₁ ,
Input data 2 and 6 to V ₁ at the same time,
W ₁ is the value of X ₁ , U ₂ and V ₂ are the values of Y ₁ and Z ₁ ,
The values of X ₂ are entered into W ₂ and compared, and the results are stored in X _i , Y _i , and Z _i (i=1, 2). This operation continues until step 3, when all inputs are entered. Here, the operation is switched to the data output phase. This time, output is performed from _X1 . At this time, U _i and _Vi have Y _i and Z _i (i=1, 2), respectively.
The value of is entered, and the value of X ₂ is entered into W ₁ . next,
A comparison is made and the values of X _i , Y _i , Z _i are updated (i
=1,2). If you repeat this operation from step 4 to step 9 until all data is output, in step 9 the results will be sorted in ascending order.
123456 is obtained. Generally, when performing the above operations in a device configured as shown in FIG. 7, min(X _i , Y _i , Z _i ) min(X _i+1 , Y _i+1 , Z _i+1 ) (i=1, 2,...[n/3]-1)...(iii) holds true. Therefore, if data P with the jth size is in unit k, where k>j, then
There are at least j values smaller than P. Since this is a contradiction, P must always exist in a unit k' where k'≦j. Further, if k'=j, if it does not exist at the position of X, there will be j or j+1 items smaller than P, which is a contradiction. Therefore, when all input is read, the situation is as follows.

[Table] Therefore, one value is output from X ₁ , and X, Y,
When updating Z,

【table】

Claims (1)

[Claims] 1. An input section that accepts three pieces of data in parallel, a comparison operation section that simultaneously compares the three data received by the input section and changes the arrangement in order of size, and a comparison operation section that changes the arrangement by the comparison operation section. A basic unit consisting of an output unit that holds three pieces of data and outputs them in parallel is connected in cascade to form a parallel sorting processing device having a data input and a data output, and has a data reading phase and a data output phase, In the data loading phase, the input section of each basic unit is such that two of its three data inputs are connected in parallel to the data inlet or to the upper two data outputs of the basic unit adjacent to the data inlet side, and the remaining one is connected to the lowest data output of the elementary unit in question, and in the data output phase the output of each elementary unit connects the top two of its three data outputs in parallel to the two data inputs of the elementary unit in question. connected,
The remaining lowest data output is connected to the above data exit or one of the data inputs of the basic unit adjacent to the data exit side, and in the data reading phase, two data items are input in parallel from the above data inlet, and the data is output. Phase is a parallel sorting processing device characterized by outputting data one by one from the data exit.