JPH0551999B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to an associative memory device, that is, a memory device that can perform addressing based on stored contents.

(Prior art and its problems) This type of associative memory device is an important device used as a component of an electronic computer. An example of the application of associative memory is ``Ultra-high-performance electronic computers using large-scale projects'' (edited by the Agency of Industrial Science and Technology, Ministry of International Trade and Industry,
Published by Japan Industrial Technology Promotion Association (July 1947)
Mentioned in PP45-48. According to this, the associative memory device stores which address of the main memory device corresponds to a sector of the buffer memory, and enables address conversion from a logical address to a physical address to be performed at high speed by searching the contents.

Additionally, Nikkei Electronics (published on October 27, 1980), pages 102 to 136, describe list processing, image processing, and applications to Dentabase.

Regarding the associative memory elements used in this type of associative memory device, there are already many references, such as ``logical memory'' published in ``Information Processing Handbook.''
(Published by Ohmsha in May 1947, edited by Information Processing Society of Japan,
It is introduced in PP13-96-PP13-99).
According to this, this type of associative memory device requires an associative memory element having a configuration in which each memory element that can store information is provided with a coincidence detection circuit that checks whether the stored content matches the search information. Therefore, compared to memory elements used in ordinary memory devices that are accessed by supplying an address indicating the storage location of desired data, conventional associative memory elements have a more complex structure.
It had the disadvantage that the cost per bit was several tens of times higher.

In order to eliminate this drawback, an associative memory device has been considered in which a normal memory element is used in the information storage section and a match detection circuit is provided for each word. However, this associative memory device has a drawback in that it requires a number of search operations corresponding to the number of bits.

Furthermore, a first normal storage element which takes the search information as an address input and stores data information, and a second normal storage element which takes the data information or the read output of the first normal storage element as an address input and stores the search information. An associative memory device using a memory element was published in 1973.
-73039. However, although this associative memory device has the advantage of being able to be constructed using ordinary memory elements, as the number of bits of search information or data information increases, the number of memory elements required increases significantly, resulting in an increase in price. have.

(Object of the Invention) The present invention easily solves the above-mentioned conventional drawbacks, and provides a high-speed, large-capacity, low-cost, and highly functional associative memory device that is composed of ordinary memory elements that are accessed by supplying addresses. It is about providing.

Another object of the present invention is to provide an associative memory device that is capable of performing a search operation by masking a portion of search information.

(Structure of the Invention) That is, according to the present invention, a counting means for counting the number of input data, a storage means in which storage elements are arranged in a matrix, and all row selection lines of the storage means are connected in parallel during a registration operation. A row selection means selectively drives a row selection line specified by input data during a search operation, and a column selection line of a storage means specified by a registered address and the contents of the counting means during a registration operation. column selection means that drives in parallel a plurality of column selection lines specified by the contents of the counting means during a search operation, and a column selection means that drives in parallel a plurality of column selection lines specified by the contents of the counting means during a search operation, and a column selection means that drives in parallel a plurality of column selection lines specified by the contents of the counting means during a search operation, and a column selection means that drives all columns of the storage means write data generation means for supplying the write data to the write data line; matching processing means for taking in the read signal of each column of the storage means designated by the contents of the counting means every time input data is given and determining whether or not there is a match; , and encoding means connected to this output.

(Example) The present invention will be explained in more detail below using the drawings.

FIG. 1 is an explanatory diagram of an embodiment of an associative memory device according to the present invention. This associative memory device receives search information as input data 101, and uses a search address 162 where information matching the search information is stored.
A counter 170 serving as a counting means for input data 101 and a storage means 110 in which storage elements are arranged in a matrix are connected to this by a row selection line 121, and all the row selection lines 121 are connected to each other during a registration operation. A row selection means 120 drives the row selection lines 121 designated by the input data 101 during the search operation in parallel, and is connected to the storage means 110 by each column selection line 131, and during the registration operation, the row selection means 120 drives the row selection line 121 specified by the input data 101. Column selection means 130 drives the column selection line 131 specified by the output 175 of the column selection line 131 and drives in parallel a plurality of column selection lines 131 specified by the contents of the counter 170 during the search operation; The storage means 11 is connected to a write data line 141 that supplies write data to the storage element.
0 and inverts only the write data line 141 designated by the input data 101, the write data generating means 140 supplies the write data to the write data line 141, and the storage means 100 receives the read signal 1.
Matching processing means 15 which inputs 51 sequentially and judges whether information matching the search information is registered or not.
0, and an encoding means 160 which takes this output as input and outputs a matching signal 161 of "1" and a search address 162 indicating the position of "1" if "1" is included therein. There is.

The storage means 110 is constituted by a conventional storage element that is accessed by providing an address indicating the storage location of desired data. Assuming that the memory structure of this content addressable memory device is N words M×K bits, the memory structure of the storage means 110 is 2M rows and N×K columns, that is, ^2M rows and N×K columns ^.
The number of words is N×K bits. Also, input data 1
The number of bits in 01 is M bits, and the registered address is 132.
Then, the number of bits of the search address 162 is log ₂ ^N bits. Also, the number of bits in the counter 170 is log ₂ ^K
Becomes a bit. As shown in FIG.
Consists of blocks. Blocks correspond to words in this content addressable memory. A block is specified using a registered address 132, and a column within the block is specified using a counter 170. M×K bits of search information and registration information are divided into M bits of input data 101, and are divided into K times sequentially from the top to the row selection means 120 and write data generation means 14.
Sent to 0. The registration information sent as the K pieces of input data 101 is stored in each column of the block specified by the registration address 132 of the storage means 110 for each input data 101.

FIG. 2 is an explanatory diagram of the storage contents of the storage means 110. The figure shows, as an example, registration information A consisting of four M-bit partial data A ₀ , A ₁ , A ₂ , A ₃ .
The storage contents of the storage means 110 when registered in the registration address 132 of . The registration information A is sequentially stored in each column in the J block of the storage means 110, starting from the upper partial data _A0 . As shown in the figure,
Each column in J block contains partial data A ₀ , A ₁ ,
Only the rows specified by A ₂ and A ₃ will be "1".

The registration operation and search operation will be explained in more detail. First, the four M-bit data shown above
A registration operation for registering registration information A consisting of A ₀ , A ₁ , A ₂ , and A ₃ at address J will be described. Here, data A ₀ is the upper part of registered information A,
Assume that data A ₃ is the lowest part, and the upper data
Supply sequentially from A ₀ . Next, a search operation based on the same information will be explained. At the start of both operations, an initialization signal 111 is supplied and the matching processing means 150
The initial value of the counter 170 is set.

In the case of a registration operation, an initial setting signal 111 is given and an operation mode signal 1 of "1" indicating a registration operation is given.
03 and the registered address 132 of address J are first supplied. This clears the contents of the counter 170 and specifies the 0th column of the storage means 110.
Next, when the data A ₀ which is the upper part of the registration information A is supplied as the input data 101 and the write pulse signal 104 is supplied, the decoding result of the data A ₀ is stored in the 0th column in the Jth block of the storage means 110. be done. Since the counter 170 increments at the rising edge of the clock signal 112, the output 175 of the counter 170 increments at the end of this write and specifies the next first column in the J block of the storage means 110.

By the above operation, partial data of registered information A
A ₀ is written. Furthermore, partial data A ₁ ,
The registration information A is registered by supplying A ₂ and A ₃ as input data 101 and performing the partial data write operation three times. As a result, the stored contents of the J block of the storage means 110 become as shown in FIG.

Next, the operation when a search is performed using the same search information A in a state where registration information A is registered at address J will be described. This associative memory device can perform search operations by masking part of the search information, but
A search operation without mask processing will be explained.

In the search operation, an operation mode signal 103 of "0" is supplied. Further, an initial setting signal 111 is applied to set the contents of the counter 170 and matching processing means 150 to initial values. Next, partial data A ₀ of search information A,
A ₁ , A ₂ , and A ₃ are sequentially input as input data 101 together with a clock signal 112 of a negative pulse signal. As a result, the contents of the counter 170 are incremented each time the clock signal 112 is input, and the row selection means 120 sequentially selects the data A ₀ in the 0th column, the data A 1 in the 1st column, and the data A ₁ in the 2nd column of the storage means 110. Data of A ₂ ,
Row selection line 121 specified by data A ₃ in the third column
to drive. As a result, the 0th column in each block of the storage means 110 connected to this row selection line 121,
The contents of the first, second and third columns are clock signal 1.
12 is sequentially outputted as a read signal 151 and supplied to the matching processing means 150. Since the storage means 110 stores the contents shown in FIG. 2, the read signals 151 of each column of the J block in response to the input of data A ₀ , A ₁ , A ₂ , and A ₃ are all "1". . A read signal 151 of "1" indicates that partial data matching the partial data of search information A is registered. The matching processing means 150 determines whether or not matching is achieved based on whether the read signals 151 for each partial data A ₀ , A ₁ , A ₂ , A ₃ of the search information A are all "1". In this example, the read signals 151 of the 0th, 1st, 2nd, and 3rd columns of the J block of the storage means 110 are all "1", so
It is determined that information matching search information A is stored in the block. Therefore, matching processing means 15
The J-th bit of the matching result signal 152, which is an output of 0, becomes "1" indicating a match.

This matching signal 152 is provided to encoding means 160. The encoding means 160 outputs a matching signal 161 indicating that the matching result signal 152 of "1" is input, and its bit position as a search address 162. A match signal 161 indicates that information matching the search information is registered in the associative memory, and a search address 162 indicates its storage address. In this example, J of the storage means 110
Since registration information A is stored in the block,
Address J is output as search address 162.

Note that when multiple matching is performed when a plurality of pieces of information matching the search information A are registered, a matching result signal 152 of "1" of multiple bits is generated. In this case, a plurality of matched search addresses 162 can be obtained by providing a decoder that receives the search address 162 as an input and supplies a reset signal to the matching processing means 150 designated by the decoder.

Furthermore, by inhibiting the clock signal 112 to the matching processing means 150 when partial data of the search information to be masked is input, mask processing can be performed for each input data 101.

As described above, this associative memory device can be constructed by using the storage means 110 of ^2M words and NK bits of ordinary storage elements to form an N word and MK bits associative memory device, resulting in a reduction in price. Further, the search operation and registration operation are performed by memory access K times, and high-speed operation is possible.

FIG. 3 is an explanatory diagram of one embodiment of the row selection means 120 used in the associative memory device of FIG. 1. This row selection means includes a decoder 310 that receives input data 101 as registration information and search information, and an OR gate 320 that performs a logical sum of each output of the decoder 310 and an operation mode signal 103 to drive a row selection line 121 of the storage means 110. It consists of.

Operation mode signal 103 of “1” indicating registration operation
When the row selection lines 121 are supplied, all outputs of the OR gates 320 become "1", and all the row selection lines 121 are driven in parallel. However, when an operation mode signal 103 of "0" indicating a search operation is supplied, only the row selection line 121 specified by the input data 101 serving as search information is driven. As a result, all the rows of the storage means 110 are driven in parallel during the registration operation, and only the rows designated by the search information are selectively driven during the search operation.

FIG. 4 is an explanatory diagram of one embodiment of the column selection means 130 used in the associative memory device of FIG. 1. This column selection means includes a block decoder 410 which receives the registered address 132 as input, and an operation mode signal 103.
an inverter 420 that inverts the output of the block decoder 410; an OR gate 430 that performs the logical sum of this output and each output of the block decoder 410;
75 as a data input, the output of an OR gate 430 as an enable input, and a column decoder 440 whose output is connected to each column selection line 131 of the storage means 110.

Each column decoder 440 selects a column within each block of storage means 110, and block decoder 410 selects a block of storage means 110.

Operation mode signal 103 is “1” during registration operation.
Since block decoder 410 is supplied with column decoder 440 specified by registered address 132,
A “1” signal is supplied only to the enable input of the device. The column decoder 440 drives only the column select line 131 designated by the output 175 of the counter 170. That is, registered address 132 and counter 1
Only the column selection line 131 designated by the output 175 of 70 is driven.

During the search operation, the operation mode signal 103 is “0”.
is supplied, the OR gate 430 sets “1” to the enable inputs of all column decoders 440.
signal is supplied. As a result, each column decoder 440 drives the column selection line 131 specified by the output 175 of the counter 170 in parallel.

FIG. 5 is an explanatory diagram of one embodiment of the write data generating means 140 used in the associative memory device of FIG. 1. The decoder 510 inputs the partial data of the registration information as the input data 101, and supplies the write data line 141 with write data in which only the specified row of the storage means 110 becomes "1". Therefore, the registration information is stored in the storage means 1 as shown in FIG.
10.

FIG. 6 is an explanatory diagram of one embodiment of the matching processing means 150 used in the associative memory device shown in FIG. 1.
In FIG. 1, the matching processing means of FIG. 5 are used in a number equal to the number of words N of the associative memory device. This alignment processing means reads the read signal 15 of the storage means 110.
It includes an AND gate 610 that receives 1 as an input, and a register 620 that temporarily stores its output.

The register 620 is set by the initial setting signal 111 at the start of the search operation, and is set by the clock signal 112.
The output of AND gate 610 is taken in in synchronization with .
Assuming that the read signals 151 for partial data A ₀ to _{A K-} 1 of search information A are respectively E ₀ to E _K-1 (K=4 in FIG. 1), each time partial data is input to the register 620, The AND of the read signal 151 thereto is accumulated. Therefore, when all partial data input is completed, the register 620 contains E ₀ .
The logical operation results of E ₁ ...E _K-1 are stored. That is, the output of the register 620 becomes a matching result signal 152 indicating whether or not the information stored in the block of the storage means 110 that outputs this read signal 151 matches the search information A.

(Effects of the Invention) As explained above, the content addressable memory device according to the present invention can be constructed using an inexpensive ordinary memory element that is accessed by supplying an address indicating the storage location of desired data. An N word M.times.K bit content addressable memory device can be constructed from a 2M word ^M.times.K bit ordinary memory element.

Therefore, if 1 megabit semiconductor technology is used, for example, if the number of columns in a block is 8 and the number of bits of input data 101 is 6 bits, a 2 kiloword, 48 bit content addressable memory device can be realized in one chip. Compared to a generally commercially available semiconductor associative memory, such as the associative memory IC8220 manufactured by Signetics, which has 4 words and 2 bits, the associative memory device according to the present invention can be said to have an extremely large capacity.

Further, the search operation and registration operation of this content addressable memory device can be completed by accessing the memory elements several times, and is faster than conventional word serial/bit parallel or word parallel/bit serial content addressable memory devices.

Furthermore, it is also possible to perform a search operation by masking part of the search information, and to perform multiple matching processing in the case of matching at multiple addresses.

That is, according to the present invention, a high-speed, large-capacity, low-cost, and highly functional associative memory device can be realized. When such an associative memory device is used as a storage device of an information processing system, it is possible to realize an information processing system that can perform associative processing and comparison processing in databases, pattern recognition, artificial intelligence, etc. at high speed.

In the above description, "1" is stored only in the row specified by the registration information of the storage means 110, but "0" may also be stored. Further, although the columns in the blocks of the storage means 110 are arranged adjacent to each other, it is also possible to arrange the same columns of each block together. In this case, the counter 170
specifies the upper row, and the registered address 132 specifies the lower row. Therefore, the column selection means 130,
Write data generation means 140, matching processing means 15
0 can be modified in various ways.

In addition, the registered address 132 and the search address 16
It is also possible to reduce the number of input/output terminals by making them common.

Therefore, the above description is not intended to limit the scope of the claimed invention.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of one embodiment of the associative memory device according to the present invention, FIG. 2 is an explanatory diagram of the storage contents of the storage means 110, and FIG. 3 is an explanatory diagram of one embodiment of the row selection means 120 of FIG. Figure 4 shows the column selection means 1 in Figure 1.
FIG. 5 is an explanatory diagram of an embodiment of the write data generating means 140 of FIG. 1. FIG. 6 is a diagram showing an embodiment of matching processing means. 110... Storage means, 120... Row selection line, 1
30... Column selection means, 140... Write data generation means, 150... Matching processing means, 160... Encoding means, 310, 510... Decoder, 3
20, 430...OR gate, 410...Block decoder, 440...Column decoder, 420...
Inverter, 610...and gate, 620...
…register.

Claims (1)

[Claims] 1 counting means for counting the number of input data;
A storage means in which storage elements are arranged in a matrix, and a row selection device that drives all row selection lines of the storage means in parallel during a registration operation and selectively drives row selection lines specified by input data during a search operation. selectively drives the column selection line of the storage means specified by the registered address and the contents of the counting means during the registration operation, and drives in parallel a plurality of column selection lines specified by the contents of the counting means during the search operation. column selection means for inverting only the row specified by the input data, write data generation means for supplying write data to write data lines of all columns of the storage means, and storage means specified by the contents of the counting means. What is claimed is: 1. An associative memory device comprising: matching processing means for taking in a column read signal every time input data is given and determining whether or not there is matching; and encoding means connected to the output.