JPH0632225B2 - Associative memory device - Google Patents

Description

The present invention relates to an associative memory that performs an associative operation for designating contents and searching where the contents (hereinafter referred to as search data) are stored. The present invention relates to a high-speed associative memory device that executes an associative operation on continuous data at high speed.

[Background of the Invention]

As described in Information Processing Handbook of Information Processing Society of Japan, in an associative memory with a simple configuration, associative operation that matches search input with all stored contents and reads the position as address when matching information is found The RAM operation for reading and writing information is divided according to this address. In order to perform the above-mentioned associative action, it is necessary to change the addresses one by one and compare the stored contents with the search input,
If there are N stored contents, the agreement will be made after N / 2 comparisons on average. Therefore, NK / 2 comparisons are required for the associative operation for continuous K data.

Japanese Unexamined Patent Publication (Kokai) No. S58-58 has been published as an associative memory device.
-200449 "Associative Memory Device" and Japanese Patent Laid-Open No. 59-59
No. 8195 "Associative memory system" is known.

[Object of the Invention]

An object of the present invention is to provide a high-speed associative memory device in which an associative operation with respect to a plurality of continuous data is fast.

[Outline of Invention]

A feature of the present invention is, as an associative memory device, a data memory, a counter that increments the address of the data memory, a search data memory that stores a plurality of search data, and a specific search data in the search data memory. Comparison of selecting means for selecting and outputting, and a specific comparison range of the search data selected by the selecting means and a portion of the data read from the data memory corresponding to the specific comparison range of the search data. And a stop means for stopping the stepping of the counter when they coincide with each other, and a data read from the data memory and the search data memory in the search data memory when the stop means operates. Each data and
When all bits match as a result of the comparison by the second comparing means for sequentially comparing all the bits up to the number of times determined by the specific comparison range, the counter is incremented after the comparison is completed. Resuming means for resuming from the next address that has been stopped.

As a result, since the search of the search data memory is used together with the search of the data memory, the associative operation with respect to a plurality of continuous search data can be speeded up as compared with the conventional search of only the data memory. .

Example of Invention

FIG. 1 shows an embodiment of the present invention. Reference numeral 10 is a data memory for storing data, in which a directory is stored. 20 is a search data memory for storing data to be searched, 30 is a register for temporarily holding search data of one word,
Reference numeral 35 is a signal line for giving the latch timing of the register, which is omitted in the figure, but is controlled by the output of the arithmetic unit (ALU) 90. Reference numeral 40 is a comparator for comparing the output of the data memory 10 with the output of the register 30.
Is an address counter that gives the address of the data memory 10. Reference numeral 60 is a gate for controlling whether to give a count clock to the counter 50, 70 is a clock signal, and 80 is a 1-bit register controlled by the output of the ALU 90. The ALU 90 controls the entire operation, and its operation is defined by the program stored in the memory omitted in FIG. 100
Is an address register for holding an address for the search data memory 20, 105 is a signal for instructing the latch of this register, and is generated by the ALU 90 similarly to 35. Reference numeral 110 denotes an OR gate, which produces a signal for stopping the operation of the counter 50 by ORing the overflow output of the counter 50 and the coincidence output of the comparator 40.

2 (A) to (C) are flow charts showing the operation of the present invention. FIG. 3 shows an example for explaining the operation. The output address for the search data and the area for setting the searched flag are realized on the search data memory. The data is all 8 bits, the search data is a decimal eight-word logical address from 0 to 7, and 2,0,7 are addresses / 10, / 18, / in the directory.
It is assumed to be stored in 1A. However, / XX represents a hexadecimal number. XX in the directory indicates that the data is unrelated to the search data, and the physical address corresponding to the logical address is stored in the odd address.

The operation of FIG. 1 will be described below with reference to FIG. First, the address of the search data memory is set as / 0, and the content is stored in the register 30. This content is 0 in decimal as shown in FIG. Whether or not the data has already been searched is checked by the searched flag realized in the search data memory, and if searched, it is further checked in step 290 whether or not the operation has been completed for all searched data.
If it is completed, the operation is terminated, and if it is not completed, the address of the search data memory is incremented by step 300 and the process returns to step 200. The determination in step 210 is performed because the search is not necessarily completed in the address order of the search data memory.

The address counter 50 is cleared at step 220, the register 80 is set at step 230, the clock 70 is guided to the address counter 50, and counting is started. Address counter 50 can be cleared by ALU9
Although it depends on the output of 0, it is omitted in this figure.

Next, the STOP output of the gate 110 is monitored, and if it is STOP, it is determined whether or not the cause is an overflow. If it is an overflow, it means that the search data does not exist in the data memory. In this case, step 29
According to 0, the next operation is determined depending on whether or not the search is completed. Whether or not it is an overflow is determined by the ALU 90 determining the output of the address counter 50.
If it is not an overflow in the determination of step 250, STOP was performed by the coincidence output of the comparator 40, but since the comparison in this case is not performed for all bits,
At step 260, all bits are compared. In this example, it is assumed that the comparator 40 compares only the upper 5 bits of the 8 bits. If the result of the determination at step 260 is a match, the address is read and stored, the searched flag is set, and the operation proceeds to step 290 and the subsequent steps.
In the example of FIG. 3, STOP is performed at the address / 10, but the comparison of all the bits does not match, and the flow advances to step 310 by the flow chart. At step 310, the search data "0" is compared with the contents of the directory address / 10. As a result, the latter is larger, so that the operation proceeds to step 320. In step 320, the pointer for counting the number of repetitions is cleared and the address / 10 of the search data is set in the address register 100. Below step 330,
This is an operation for determining whether or not data matching the directory data exists in the search data memory. As a result of stepping the address in step 330, the search data becomes "1", but since the comparison results in steps 340 and 350 do not match, the process proceeds to step 370. Step 37
0 determines whether all search data are compared,
In this example, since the answer is NO, the process proceeds to step 380. Step 380
Then, it is determined whether the search data are compared eight times or more. When comparing by the comparator 40, since the number of bits ignored is 3, no coincidence output is output when comparing data items separated by 8 or more. Therefore, when the pointer is 8 or more in the determination of step 380, In order to restart the search on the directory side, proceed to step 230. According to the example of FIG. 3, as a result of the judgment of step 380, the process returns to step 330, and the address is stepped. As a result, the search data becomes "2", and steps 340, 3
The results of 50 comparisons agree. Therefore, in step 360, the value of the counter at this time / 10 is stored and the searched flag is set. After that, the process proceeds to step 230 to start the comparison after / 12 in the directory. Next, it is the address / 18 that is stopped at step 240. At this time, since all the bit comparisons at steps 260 and 270 are coincident, step 280 outputs the counter output / 10.
Is stored and the searched flag is set. Step 290
It is determined that the operation has not been completed for all the search data, the address of the search data memory is incremented by 1 to / 1, and the operation is repeated from the first point of the flow.

FIG. 4 shows another embodiment of the present invention, which is a mask gate 1
The number of comparison bits of the comparator 40 is made variable by 20, 130, and the operation is the same as in the embodiment of FIG. However, the difference is that the result of calculating the power of 2 by the number of bits masking the decision value 8 of 380 in FIG. That is, in the example shown in FIGS. 1 to 3, the comparison range is the upper 5 bits of the 8-bit data, but the lower 3 bits may be different even if the upper 5 bits of the 8-bit data match. Including the case where all the bits match, the type is represented by 2 3 (= 8). As described above, the determination value shown in step 380 in the flowchart of FIG. 2 is determined by the number of masked bits (that is, not compared), and is 8 (= 2 to the power of 3).
Becomes

In the embodiment of FIG. 4, AND gates, which are the mask gates 120 and 130, mask a predetermined range of bits of the output from the search data memory and the output from the data memory. Therefore, by changing the mask data, not only the comparison range can be set to the upper 5 bits in the 8-bit data, but also the comparison range can be arbitrarily set within the range of the number of bits of the data. In that case, the number of different types of that comparison bit is
It is a value obtained by calculating the power of 2 (the number of lower bits masked).

According to the first embodiment of the present invention, assuming that the number of data in the directory is N and the number of search data is K, conventionally, the reference of the directory is NK / 2 times on average before the end of the full search. What is necessary is that if the value of exponent of 2 in the number of bits ignored by the comparator matches the number of search data, the maximum of the directory is 2N and the search data memory is K.
All searches are completed by referring to (K + 1) / 2 times.

Generally, N is larger than K, for example, N is 1000,
When K is set to 8, the average number of directory references before the present invention is 4000, whereas after the implementation of the present invention, the maximum number of directory references is 2000, and the search data memory is referred to 36 times.

According to the second embodiment of the present invention, it is possible to change the number of bits to be ignored by the comparator according to the number of search data, and reduce the number of wasteful stop in step 240 of FIG. The operation time can be minimized. For example, in the example shown in FIGS. 1 to 3,
Consider a case where the lower 2 bits of search data start from 00 and are characterized by being continuous 4. In this case, if the upper 5 bits of the 8-bit data are compared, it becomes 2
Even if the square bit of 1 is 1, the address counter for the data memory is stopped, and useless comparison is performed. In this case, it is optimal to compare the upper 6 bits of the 8-bit data.

If the number of bits to be masked can be changed depending on the number of search data as described above, the number of times of useless comparison can be reduced. Moreover, as a result, the time required to obtain the final result can be shortened.

〔The invention's effect〕

According to the present invention, it is possible to provide a high-speed associative memory device in which the number of directory references is significantly reduced and the associative operation for a plurality of continuous data is fast.

[Brief description of drawings]

FIG. 1 and FIG. 4 respectively show the structure of an embodiment of the present invention, and FIG. 2 is a flow chart for explaining the operation of FIG.
The figure shows an example of the data for explaining the operation of FIG. 10 ... Data memory, 20 ... Search data memory, 30 ... Register, 40 ... Comparator, 50 ... Address counter, 90 ... ALU, 100 ... Address register.

Claims (2)

[Claims] 1. A data memory, a counter for incrementing the address of the data memory, a search data memory for storing a plurality of search data, and a selection means for selecting and outputting specific search data in the search data memory. And a first comparison for comparing a specific comparison range of the search data selected by the selecting means with a portion of the data read from the data memory corresponding to the specific comparison range of the search data. Means for stopping the stepping of the counter when the means coincides, the data read from the data memory and each data in the search data memory when the stopping means operates, Second comparing means for sequentially comparing all bits up to a number of times determined by a specific comparison range, and if all bits match as a result of the comparison by the second comparing means, a ratio is calculated. An associative memory device comprising restarting means for restarting from the next address at which the stepping of the counter is stopped after the comparison is completed. 2. The associative memory device according to claim 1, wherein the specific comparison range can be arbitrarily set by a comparison range setting means.