JPS627579B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an apparatus for classifying and processing a plurality of numerical values, and more specifically, the present invention relates to a device for classifying and processing a plurality of numerical values, and more specifically, a device for arranging a plurality of binary values input in parallel and sequentially bit by bit in an array. The present invention relates to a parallel classification processing device that performs classification processing through a plurality of classification cells.

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 a plurality of numerical values 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.

The problem here is the time spent on classification processing. Particularly when there is a large amount of information to be classified, if the above-mentioned simple repetitive operations are 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 using file memory," Institute of Electronics and Communication Engineers Computer Research Group Material, January 21, 1972, Material No. EC71.
-61 (1972-01) (hereinafter referred to as Document 1), proposed a method for parallel classification processing. This method is based on a classification cell that compares two binary values bit by bit, determines the order of magnitude, and outputs it, and these classification cells are regularly arranged in an array and a parallel classification processing device is used. has been configured to achieve faster processing. In this case, the advantage is that the individual classification cells that make up the device have a simple structure, but in order to simultaneously classify a large amount of information, it is necessary to install a number of classification cells that correspond to the amount of data. is necessary,
The biggest drawback is that the processing time increases as the device becomes larger.

On the other hand, advances in integration technology have made it possible to accommodate complex and large-scale circuits on a single LSI chip. Considering this fact together with the above-mentioned method of configuring the device, increasing the function of the classification cell to an appropriate degree and reducing the number of elements composing the device is a means of downsizing the device and achieving faster processing. However, an increase in processing time cannot be avoided.

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 classification cells and can be made smaller and faster.

According to the present invention, the first classification cell inputs two numerical values, sorts them in order of size, and outputs them, and the second classification cell inputs three numerical values, sorts them in order of size, and outputs them. The two types of classification cells are arranged in an array according to a predetermined rule and connected to each other, and a plurality of binary values inputted sequentially from the upper bits are input to the classification cells. A parallel classification processing device is obtained, which is characterized in that classification processing is performed in parallel through groups, and the results are sorted 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 for explaining a first embodiment of a parallel classification processing device according to the present invention.

1 is a parallel classification processing device according to the present invention, and shows, as an example, a configuration for sorting 12 binary values in order of size. 11,12,...,2
1 and 22 are 12 shift registers, each of which stores a binary value to be ordered.
21, 22, ..., 27 are two input/output classification cells, which have the same function as the judgment circuit described in Document 1, and when two binary values are input sequentially from the upper bit, these two This is a sequential circuit that rearranges the decimal values in order of size and outputs them in order from the most significant bits. 31, 32, ..., 40 are three input/output classification cells, which have the same function as the "three input/output classification device" filed on the same date by the same applicant as the present invention, and have three binary values. This is a sequential circuit which rearranges these three binary values in order of size and outputs them sequentially from the most significant bits. 101, 102, . . . , 112 are output signal lines of each shift register 11, 12, . Input signal lines 101, 102, and 103 are input to a three-input/output classification cell 31. Similarly, the input signal lines 104, . . . , 111, 112 form a set of three in order, and are input to the corresponding three input/output classification cells 32, . 2
01, 202, ..., 212 are parallel classification processing devices 1
It is an output signal line of the shift registers 11, 12, . Further, the output signal line 201 is also the first output signal line of the three-input/output classification cell 31. 202' and 203' are the second and third output signal lines of the three input/output classification cell 31, and at the same time, the three input/output classification cells 37,
It is also one input signal line of the two-input/output classification cell 21. 204' is the first output signal line of the three-input/output classification cell 32, and at the same time is the first output signal line of the two-input/output classification cell 21.
It is also the other input signal line. 203″, 20
4'' are the first and second output signal lines of the two-input/output classification cell 21, and are also the input signal lines of the three-input/output classification cells 37 and 35, respectively.As described in this example, according to the present invention, The parallel classification processing device 1 is constructed by regularly combining two types of classification cells.

100 is a synchronization signal line, and shift register 1
1, 12, . . . , 22 and all classification cells constituting the parallel classification processing device 1. Each shift register 11, 1
The 12 binary values stored in bits 2, . At this time, each classification cell 31,
21, etc. perform predetermined operations to determine the combination of input signals that are input to each, order numerical values corresponding to the input signals, and output them to respective determined output signal lines. To give an example, the three input/output classification cell 31 has input signal lines 101, 102, 1
The three binary values supplied one bit at a time via ', the largest numerical value is sequentially output one bit at a time to the third output signal line 203'. In the same way, the two input/output classification cell 21 sequentially classifies the two numerical values supplied through the input signal lines 203' and 204', sends the smaller one to the output signal line 203'', and sends the larger one to the output signal line. Output to line 204''. In this way, the input signals supplied from the input signal lines 101, 102, . . . , 112 pass through each classification cell and are propagated to the output signal lines 201, 202, . , 22 and stored. When this round of operations is completed, that is, when synchronization signals are supplied for the number of bits of the binary value and each binary value has been processed by the parallel classification processing device 1 to the lowest bit, the shift register 11 , 12, . . . , 22 provide binary values rearranged in a fixed order. Further, when this round of operations is repeated a predetermined number of times (twice in this embodiment), the binary values are completely rearranged in the order of magnitude.

By the way, I omitted it to simplify the drawing, but
Some caution is required regarding the operation timing. This is due to consideration of the propagation delay of each signal when passing through each classification cell, and each classification cell must operate by being inputted at the same timing as its two or three input signals. To do this, for example, the signal lines 201, 202, 202', etc., which transmit signals between each cell, must be connected by the number of skipped columns, for example, the signal line 201 is connected to the 5th column from the second column to the sixth column. Stage, signal line 202'
Either insert a delay equivalent to two stages in the second and third columns, or delay the synchronization signal supplied to the synchronization signal line 100 from the first column to each subsequent column for a certain period of time. Techniques used to synchronize conventional digital equipment are utilized, such as delaying the input to each sorted cell and activating it.

Next, the operation of the parallel classification processing device will be explained using a specific example.

FIGS. 2a and 2b are diagrams showing the operation of the parallel classification processing device according to the present invention.

Figures a and b show the first and second rounds of repeated operations, respectively. 10-1, 10-2, 10-3 are blocks representing numerical values stored in shift registers 11, 12, . . . , 22. 31, 21, etc. are blocks representing numerical values obtained on the respective first, second, or third output signal lines of each classification cell, and the arrangement corresponds directly to the classification cells 31, 21, etc. in FIG. An example of this is “12”, “11”,…
The 12 numbers given in the order of “1” are “1”,
This shows the sorting in the order of "2", ..., "12". The order of the numbers initially given to block 10-1 is the order of the numbers obtained in the first round of operations in block 10-2, and the order of the numbers obtained in the first round of operations is shown in block 10-3 as the second round, that is, the final result. The order of the obtained values is shown. Regardless of the order of the numbers initially given, the same result can be obtained by repeating the operation at most twice.

FIG. 3 is a block diagram showing a second embodiment of the parallel classification processing apparatus according to the present invention.

1-1 and 1-2 are first and second parallel classification processing devices, respectively, which correspond to the parallel classification processing device 1 in FIG.
It has the same configuration as . 101,...,1
12 are 12 input signal lines of the parallel classification processing device, 2
01, . . . , 212 are the same 12 output signal lines. 301, . . . , 312 are 12 output signal lines of the first parallel classification processing device 1-1, and at the same time are input signal lines of the second parallel classification processing device 1-2.

In this embodiment, the first and second parallel classification processing devices 1-1 and 1-2 having the same configuration are connected in two stages to perform the sorting process using the two-round repetitive operation described in the first embodiment. It is a one-round operation, that is, it is executed without repetition.

FIG. 4 is a block diagram showing a third embodiment of the parallel classification processing device according to the present invention, and shows an example in which the entire parallel classification processing device is composed of only three input/output classification cells. 2-1, 2-2, . . . , 2-5 are blocks indicating that the same circuit configuration is connected in five stages.
Its circuit configuration is shown inside block 2-1. 41, 42, . . . , 45 are three input/output classification cells. Reference numerals 101, . . . , 111 are 11 input signal lines of the parallel classification processing device according to this embodiment, and are also input signal lines to the first stage block 2-1. Reference numerals 201, . . . , 211 are the 11 output signal lines of this parallel classification processing device, and are also the output signal lines of the final stage block 2-5. 401,...,
411 is a signal line from the first stage to the second stage, 50
1, . . . , 511 are signal lines from the second stage to the next stage. Synchronization signal lines input to all classified cells are omitted.

This configuration allows 11 binary values to be sorted in order of magnitude without repeated operations. This embodiment also means that a similar order permutation operation can be performed by repeating five rounds using only a single block 2-1, etc. The operation of this device can be easily understood if it is shown in FIG.

According to this embodiment, the number of classification cells can be significantly reduced.

FIG. 5 is a block diagram showing that the configuration of a part of the third embodiment can be changed.

2-2' is the even-numbered block 2-2 in Figure 4.
This is a block that replaces etc. Signal lines with the same reference numerals correspond to those in FIG. 41' and 43' are two-input/output classification cells, which replace the classification cells corresponding to the three-input/output classification cells 41 and 42, respectively. 42', 44', 45' are three input/output classification cells;
44 and 45. The reason why the classification cells can be replaced in this way is that the signals on the signal lines 401 and 402 or 410 and 411 are ordered in the three input/output classification cells 41 or 43, so they must be ordered again in the next stage. Because it doesn't need to be done. The explanation with reference to the figure means that the third embodiment configured only with three input/output classification cells is also equivalent to one configured with a combination of two types of classification cells.

According to the rules explained through the embodiments above, two types of classification cells are combined so that among the input signals propagated to the previous stage, adjacent and unordered ones are ordered at the next stage, and the present invention is implemented. A parallel classification processing device is configured.

It can be easily inferred that by applying this rule, a parallel classification processing device that sorts an arbitrary number of binary values in order of size can be constructed.

The problem of increasing the functionality of one classification cell and therefore increasing the amount of circuitry can be solved by advances in integration technology, so the main point is that by reducing the number of classification cells, it is possible to miniaturize the device and speed up processing. This is a major effect of this invention.

[Brief explanation of the drawing]

Fig. 1 is a block diagram showing a first embodiment of the parallel classification processing device, Fig. 2 is a diagram specifically showing the function of the parallel classification processing device, and Fig. 3 is a second embodiment of the parallel classification processing device. 4 is a block diagram showing a third embodiment of the parallel classification processing device, and FIG. 5 is a block diagram showing a partial configuration of the third embodiment. In the figure, 1...parallel classification processing device, 11, 12,..., 2
2...Shift register, 31, 32,..., 45,
42', 44', 45'...Three input/output classification cells, 2
1, 22,..., 27, 41', 43',...Two input/output classification cells, 1-1, 1-2...First and second parallel classification processing devices having the same configuration as the parallel classification processing device 1 , 2-1, 2-2,..., 2-5...Block diagram showing the same configuration, 2-2'...Block showing replacing block 2-2, 1
0-1, 10-2, 10-3... These are blocks indicating the numerical values written in the shift registers 11, 12, . . . , 22.

Claims (1)

[Claims] 1. A plurality of first classification cells into which two numerical values are input, sorted in order of size and output, and a plurality of second classification cells into which three numerical values are inputted, sorted in order of size and output, The two types of classification cells are arranged in an array according to predetermined rules and connected to each other, and a plurality of numerical values, which are input sequentially starting from the most significant bits, are classified and processed in parallel. , a parallel classification processing device characterized by sorting and outputting in order of size.