JPS627578B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a parallel classification processing device that sorts and outputs a plurality of numerical values in order of value.

Classifying and processing large amounts of information is one of the strengths of digital computers, and is one of the most important processes that is indispensable for handling files and the like. Among these, the operation of sorting multiple numbers in order of size (largest or smallest) is an example of the simplest and basic classification process, and is performed by repeating simple numerical comparisons. Ru.

The issue here is the time spent on classification processing. Particularly when there is a large amount of information to be classified and processed, if the above-described simple repetitive operation is applied, an enormous amount of processing time will be required in proportion to the amount of data. For this reason, efforts are being made to shorten the processing time by applying variously devised classification algorithms.

Furthermore, as an example of a method to solve such a problem, Tominaga and Hirayama, "A Method of Content Addressing in File Memory," Institute of Electronics and Communication Engineers Electronic Computer Research Group Material, January 21, 1972, Material No.
A parallel classification processing method was proposed in EC71-61 (1972-01) (hereinafter referred to as Document 1). According to this method, the basic cell is a classification circuit that compares two binary values bit by bit, determines the order of magnitude, and outputs the data.These classification cells are arranged in an array, and are combined regularly with each other. They are combined to form a parallel classification processing device to achieve faster processing. In this case, the advantage is that the structure of each classification cell that makes up the device is simple, but in order to simultaneously classify and process a large amount of information, it is necessary to install a number of classification cells according to the amount of data. The biggest drawback is that the processing time increases as the equipment becomes larger.

On the other hand, advances in integration technology have made it possible to accommodate large-scale, complex circuits on chips such as LSIs. Considering this fact in conjunction with the configuration method of the parallel classification processing device described above, increasing the functions of the basic cells moderately can be a means of simplifying the device configuration, but an increase in processing time cannot be avoided. do not have.

In view of the above circumstances, an object of the present invention is to provide a parallel classification processing device that is configured with fewer basic cells, reduces the amount of circuitry, and is capable of high-speed classification processing.

According to the present invention, there is a first classification cell that inputs two numerical values, sorts them in order of magnitude, and outputs them, and inputs four numerical values consisting of two sets of two numerical values arranged in the order of magnitude. , and second classification cells that are sorted and output in order of size,
The first classification cells are arranged in a first column, the second classification cells are arranged in a plurality of columns after the second column, and each of the classification cells after the second column is arranged in an array. The two types of classification cells are regularly interconnected in accordance with a predetermined rule so that two output signals are supplied from each adjacent classification cell in the previous row. A parallel classification processing device is obtained in which a plurality of input numerical values are classified in parallel, rearranged in order of size, and output.

Next, the present invention will be explained in detail with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention, and shows, as an example, the configuration of an apparatus that performs parallel classification processing of 12 numerical values. 1 ₁ , 1 ₂
..., ₁₆ are first classification cells, each having two input/output signal lines. 2 ₁ , 2 ₂ ,…
..., 2 ₁₅ are second classification cells, each having four input/output signal lines. 100 _1,100
2 , _. 200 ₁ , 200 ₂ , . . . , 200 ₁₂ are external output signal lines of this device, and the above-mentioned 12 numerical values are rearranged in order of magnitude and output in parallel. Further, external input signal lines 100 ₁ and 100 ₂ are input signal lines of the classification cell 1 ₁ and external input signal lines 100 ₃ and 1
₀₀₄ is an input signal line of the classification cell ₁₂ , and similarly external input signal lines ₁₀₀₁₁ and ₁₀₀₁₂ are input signal lines of the classification cell ₁₆ . 101 ₁ and 101 ₂ are output signal lines of the classification cell 1 ₁ , and 101 ₃ and 101 ₄ are output signal lines of the classification cell 1 ₂ , both of which are also input signal lines of the classification cell 2 ₁ . 201 _1,2
01 ₂ , 201 ₃ , 201 ₄ are output signal lines of the classification cell 2 ₁ , and output signal lines 201 ₁ , 20
1 ₂ is a part of the input signal line of the classification cell 2 ₆ , and output signal lines 201 ₃ and 201 ₄ are also part of the input signal line of the classification cell 2 ₄ . 201 ₅ , 201 ₆ , 20
2 ₁ , 202 _2, etc. are also output signal lines of each classification cell, and are also input signal lines of the next column of classification cells. External output signal lines 200 ₁ , 200 ₂ , ..., 200 ₁₂
is also the output signal line of the classification cell in the last column,
For example, the external output signal lines 200 ₁ and 200 ₂ are part of the output signal line of the classification cell 2 ₁₁ , and the external output signal line 2
00 ₃ and 200 ₄ are some output signal lines of the classification cell 2 ₁₄ .

The first classification cells 1 ₁ , 1 _{2 .} . . , 1 ₆ are for ordering and outputting two input numerical values. As an example, classified cell 1 ₁ is input signal line 100
₁ and ₁₀₀₂ are compared, and the smaller one is outputted to the output signal line ₁₀₁₁ , and the larger one is outputted to the output signal line ₁₀₁₂ .

The second classification cells 2 ₁ , 2 ₂ , . . . , 2 ₁₅ input two sets of two ordered numerical values, and output these four numerical values in an ordered manner. As an example, classified cell 2 ₁ is classified on the one hand and classified cell 1 ₁ on the other hand.
Input two numerical values ordered by the signal line 10
1 ₁ and 101 ₂ , and input the two numerical values ordered in the classification cells 1 ₂ to the input signal line 101.
₃ and 101 ₄ , and compare these four numerical values and output them in order from the smallest value to the output signal lines 201 ₁ , 201 ₂ , 201 ₃ , and 201 ₄ . To give a further example, the classification cell ₂₄ has two input signal lines 201 ₃ and 201 that have the largest values output from the classification cell ₂₁ on one side.
₄ , the smaller two of the numerical values output from the classification cell 2 ₂ are input to the other input signal lines 201 ₅ , 201
₆ , respectively, and output signal lines 202 ₁ , 202 in order from the smallest value of these four numerical values.
₂ , 202 ₃ , and 202 ₄ .
In other classified cells, the order of the output numerical values and the correspondence with their output signal lines are exactly the same.

Note that in the above description, the number of each signal line is one or more, and this will be described later.

The regularity of the arrangement and interconnection of each classification cell has been explained above, and it is easily inferred that the parallel classification processing device of the present invention for any number of numerical values can be configured in accordance with this rule.

Next, details of each classification cell will be explained.

FIG. 2 is a circuit diagram showing a specific configuration of the first classification cell according to the first embodiment. 11 is a comparison circuit. 12 and 13 are selection circuits. The two input numbers X ₁ and X ₂ are respectively input to the input signal line 10.
It is supplied to the comparison circuit 11 and selection circuits 12 and 13 through 0 ₁ and 100 ₂ . 110 is a comparison circuit 11
This output signal line supplies a 1-bit signal indicating the magnitude relationship between the two numerical values X ₁ and X ₂ determined by the comparison circuit 11 to the selection circuits 12 and 13 . The _selection circuit 12 is controlled by the output signal of the comparison circuit 11, and if X ₁ and X ₂ are the two numerical values X ₁ and X ₂ , then
If X ₁ > X ₂ , select one of X ₂ and output. The selection circuit 13 outputs one of the two numerical values X ₁ and X ₂ by selecting inversely to the above. That is, the smaller of the two input numbers is sent to the output signal line ₁₀₁₁ , and the larger one is sent to the output signal line 101.
Obtained to ₂ .

In addition, input/output signal lines 100 ₁ , 100 ₂ , 10
1 ₁ , 101 ₂ include the same number of bits as the number of bits representing the input numerical value.

FIG. 3 is a circuit diagram showing a specific configuration of the first classification cell according to the second embodiment. This circuit corresponds to the judgment circuit described in Document 1, so
Keep the explanations brief. 51 and 52 are inverters. 53, 54, . . . , 65 are NAND circuits. This circuit is a sequential circuit, and NAND circuit 5
5, 56 and 57, 58 form a flip-flop to store the internal state. NAND circuit 5
9, 60, . . . , 65 produce output signals determined by the input signal and internal state. A reset signal line 111 supplies a reset signal for setting the internal state to the initial state. Two numbers to be entered
The upper bits of X ₁ and X ₂ are sequentially supplied one bit at a time through input signal lines 100 ₁ and 100 ₂ , respectively. The inverter 51 and the NAND circuit 53 and the inverter 52 and the NAND circuit 54 respectively determine the magnitude of the two numerical values X ₁ and X ₂ bit by bit. Once the magnitude relationship of X ₁ and X ₂ is determined,
The internal state shifts from the initial state to another state showing that relationship, and thereafter maintains that state until a reset signal is applied. The smaller one of the two numerical values X ₁ and X ₂ inputted by this circuit operation is outputted to the output signal line ₁₀₁₁ , and the larger one is outputted to the output signal line ₁₀₁₂ in order from the most significant bits.

As is clear from the above explanation, the input/output signal line 10
0 ₁ , 100 ₂ , 101 ₁ , and 101 ₂ are each one signal line.

FIG. 4 is a circuit diagram showing a specific configuration of the second classification cell.

Reference numerals 21, 22, and 23 are first classification cells, which may be any of the first classification cells according to the first or second embodiment described above. The four input numbers A ₁ , A ₂ , B ₁ , and B ₂ have a relationship of A ₁ A ₂ and B ₁ B ₂ , respectively, and are connected to the input signal lines 101 ₁ , 101 ₂ , 101 ₃ , and 101 ₄ , respectively. Supplied. A ₁ and B ₁ are ordered in the first classification cell 21, and the smaller one is sent to the output signal line 201 ₁ ,
The larger one is output to the output signal line 211. A ₂
and _B2 are ordered in the first classification cell 22, and the smaller one is outputted to the output signal line 212, and the larger one is outputted to the output signal line ₂₀₁₄ . At this time, the smallest value is connected to the output signal line 201 ₁ .
The largest value is output to _01-4 . The remaining two numbers on the output signal lines 211 and 212 are further ordered in the first classification cell 23, and the smaller one is outputted to the output signal line ₂₀₁₂ , and the larger one is outputted to the output signal line ₂₀₁₃ . All four numbers A ₁ , A ₂ , B ₁ , B ₂ are thus ordered.

The specific configuration of the parallel classification processing device according to the present invention has been described above. Furthermore, as is clear from this description, the present device can be considered to be entirely composed of a combination of first classification cells.

Also, with reference to FIG. 1, the first classification cell 1
If ₁ , 1, ₂ and the second classification cell 2 _{, 1} are combined into one cell, it can be regarded as a third classification cell in which four numerical values are input and the values are sorted in order of magnitude. You can also do it.

Note that all the signal lines in FIG. 1 consist of a plurality of signal lines when the first classification cell according to the first embodiment is used, and when the first classification cell according to the second embodiment is used. When it is connected, it is a single signal line.

If the first classification cell according to the first embodiment is used, the number of signal lines increases, but classification processing can be performed at high speed.

If the first classification cell according to the second embodiment is used, the processing time will be increased by the number of bits of the input numerical value, but the number of signal lines will be small and the circuit will be simpler.

By the way, in this case, since it is a sequential logic circuit configuration, some care must be taken regarding the operation timing. This is due to consideration of the delay when each signal passes through each classification cell, and each classification cell must be able to operate by receiving two to four input signals at the same timing. As an example, if we look at the four input signals to the classification cells _2-6 , the signals input from the classification cells _2-1 in the second column and the classification cells _2-4 in the third column have a delay of one classification cell stage. There is a time difference.
For this purpose, the operation timing can be easily adjusted by inserting a delay corresponding to the delay time on the signal lines ₂₀₁₁ and ₂₀₁₂ . Alternatively, a synchronization signal adjusted to an appropriate timing may be supplied to each column, and in any case, this can be easily implemented using ordinary digital device design techniques.

Finally, the principle of the present invention will be specifically explained.

FIG. 5 is a data flow diagram showing how a plurality of numerical values are classified in parallel.

1 ₁ , ..., 1 ₆ etc. are the first classification cells,
2 ₁ , ..., 2 ₃ , 2 ₁₄ , ..., 2 ₁₅ etc. are the second classification cells, and the arrangement of each of these classification cells is the fourth classification cell.
Corresponds to the figure. 3 is a storage device, and as an example, there are 12 numbers to be classified as "10", "4", "12", etc.
are stored in this order. The numerical values shown in each classification cell represent the order in which the 12 numerical values are transmitted through each classification cell and how they are ordered in each classification cell. 4 is a storage device that receives the output of the classification cell in the last column, and indicates that the 12 numerical values were obtained by sorting them in the order of "1", "2", "3", etc. .

As explained above, the feature of the principle of the present invention is that, compared to the parallel classification processing device described in Document 1, each classification cell effectively utilizes the ordering information output from the classification cell in the previous row.

Therefore, according to the present invention, it is possible to obtain a high-speed parallel classification processing device that can reduce the circuit scale and is suitable for integration, and has great effects.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the configuration of a parallel classification processing device according to the present invention, FIG. 2 is a circuit diagram showing a first embodiment of a first classification cell, and FIG. 3 is a circuit diagram showing a first embodiment of a first classification cell. FIG. 4 is a circuit diagram showing a specific configuration of the second classification cell, and FIG. 5 is a diagram for explaining an example of a data flow. In the figure, 1 ₁ , 1 ₂ , ..., 1 ₆ ... first classification cell, 2 ₁ , 2 ₂ , ..., 2 ₁₅ ... second classification cell,
11... Comparison circuit, 12, 13... Selection circuit, 21,
22, 23...First classification cell, 51, 52...Inverter, 53, 54..., 65...NAND circuit, 3,
4...Storage device.

Claims (1)

[Claims] 1. A first classification cell in which two numbers are input, sorted in order of size and output, and two sets of two numbers arranged in order of size formed by combining three of the first classification cells. and a plurality of second classification cells for inputting four numerical values, sorting them in order of size, and outputting them, the first classification cell being in the first column, and the second classification cell being in the first column. The cells are arranged in an array in a plurality of columns after the second column, and each of the classification cells after the second column is accessed according to a predetermined rule. The two types of classification cells are regularly connected to each other so that two output signals are supplied from each matching cell, and a plurality of input numerical values are classified and processed in parallel, A parallel classification processing device characterized by sorting and outputting in order of size.