JPH0519797B2 - - 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 content addressable memory device is an important device used as a component of an electronic computer. An example of the reaction of an associative memory device is ``Ultra-high-performance electronic computer using a large-scale project'' (edited by the Agency of Industrial Science and Technology, Ministry of International Trade and Industry,
PP45 (published by Japan Society for the Promotion of Industrial Science and Technology, July 1947)
~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.

[Purpose of the invention]

The object of the present invention is to easily solve the above-mentioned conventional drawbacks and to provide a high-speed, large-capacity, and low-cost associative memory device that is constructed of ordinary memory elements that are accessed by supplying an address.

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

Furthermore, another object of the present invention is to provide an associative memory device that allows search operations not only for matching but also for size relationships as search conditions.

[Structure of the invention]

That is, according to the present invention, there is 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 driven in parallel during a registration operation to perform a search. A row selection means selectively drives a row selection line designated by input data during operation, and a storage means designated by a registered address and contents of a counting means during registration operation. Column selection means that sequentially and selectively drives the column selection lines specified by the contents of the counting means during the search operation, and write data that inverts only the rows specified by the input data and the column selection lines specified by the input data. write data generation means that sequentially supplies write data inverted from a row of the storage means to the write data line of each row of the storage means; An associative memory device is obtained which includes a search processing means for inputting each time a given search condition is received and determining whether or not the input matches a given search condition, and an encoding means connected to the 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 registration information and search information as input data 101 and outputs a search address 162 in which information that satisfies the given search information and search conditions is stored. A counter 170 serving as a counting means for counting a number, a storage means 110 in which storage elements are arranged in a matrix, and a row selection line 121 are connected to the counter 170, and all row selection lines 121 are driven in parallel during a registration operation. A row selection means 120 that drives a row selection line 121 designated by input data 101 during a search operation is connected to the storage means 110 through each column selection line 131, and selects a column that matches the registered address 132 and the contents of the counter 170 during a registration operation. line 1
column selection means 130 for driving the column selection line 131 specified by 31 and driving in parallel the column selection lines 131 for two adjacent columns in each block specified by the contents of the counter 170 during the search operation; Means 11
It is connected to the storage means 110 by a write data line 141 that supplies write data to the storage elements of each row of 0, and only the write data line 141 specified by the input data 101 has inverted data and input data 101.
The write data generation means 140 selectively supplies the inverted data from the write line 141 specified by the match column selection signal 133 to the write data line 141 as write data, and the read signals 151, 151' of the storage means 110 Search processing means 150 that determines whether a given search condition is satisfied
This output is input, and if it contains "1", it becomes "1" along with the matching signal 161 of "1".
The search address 162 indicating the location of the search address 162 is provided.

The memory structure of this associative memory device is N words M×K
In the case of bits, the storage means 110 has ^2M rows 2×N×
It is composed of ordinary memory elements arranged in a matrix of K columns. That is, the storage configuration of the storage means 110 is
2 ^N words 2 x N x K bits. Further, the number of bits of the counter 170 is log ₂ K bits. The storage means 110 is composed of N blocks, where 2K columns separated by broken lines are defined as blocks. This block corresponds to a word in the content addressable memory and is specified by a registration address 132. M.times.K bits of search information and registration information are divided into M bits of input data 101 and inputted K times sequentially from the top. The registration information sent as K pieces of input data 101 is stored in pairs in each two columns within the block specified by the registration address 132.

FIG. 2 is an explanatory diagram of the storage contents of the storage means 110. The figure shows, as an example, the storage contents of the storage means 110 when registration information A consisting of four M-bit partial data A ₀ , A ₁ , A ₂ , A ₃ is registered in the registration address 132 of address J. . Storage means 11
Partial data A ₀ , A ₁ , A ₂ ,
“1” is stored only in the row specified by _A3 . In the 1st, 3rd, 5th, and 7th columns, which are odd-numbered columns, write inverts from “0” to “1” from the rows specified by partial data A ₀ , A ₁ , A ₂ , and A ₃ respectively. Data is stored.

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 initial setting signal 111 is supplied, and the search processing means 1
50 and the counter 170 are set to initial values.

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. As a result, the contents of the counter 170 are cleared, and the contents of the J block of the storage means 110 are cleared.
Specify columns. When data A ₀ , which is the upper part of the next registered information A, is supplied as the input data 101 and a match column selection signal 132 of "0" is supplied, the write data generating means 140 specifies the partial data A ₀ . Write data in which only the row is "1" is generated on the write data line 141. This write data is stored in the 0th column of the J block of the storage means 110 by the write pulse signal 104.
Furthermore, when the clock signal 112 of the negative pulse signal and the write pulse signal 104 are supplied together with the matching column selection signal 133 of "1", the data is input from the row specified by the partial data A ₀ to the first column in the J block of the storage means 110. Data inverted from "0" to "1" is written. Since counter 170 increments at the rising edge of clock signal 112, the contents of counter 170 at the end of this write increment, designating the first column in preparation for the next partial data.

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

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 the search processing means 150 to initial values. Next, partial data of search information A
A ₀ , A ₁ , A ₂ , and A ₃ are inputted as input data 101 in sequence along 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 column selection means 130 selects the 0th column, the 1st column, the 2nd column, and the 3rd column in all blocks of the storage means 110. The column selection lines 131 of the fourth and fifth columns and the sixth and seventh columns are paired and sequentially driven. Therefore, the read signal 151, 151' of each block of the storage means 110 becomes the contents of the column designated by the counter 170. Also,
At the same time, row selection means 120 sequentially selectively drives row selection lines 121 specified by partial data A ₀ , A ₁ , A ₂ , and A ₃ in synchronization with clock signal 112 .
This row selection line 121 and the driven column selection line 131
The contents of the storage means 110 connected to the search processing means 150 are output as read signals 151 and 151' for even and odd columns in synchronization with the clock signal 112 for each block, and are supplied to the search processing means 150. When the partial data of the search information and the partial data of the information stored in the storage means 110 match, or when the former is large or the former is small, the read signals 151 and 151' of the even and odd columns are respectively (1,1),
(0,1), (0,0). In this example, since the storage means 110 stores information as shown in FIG. 2, partial data A ₀ , A ₁ ,
The read signals 151 and 151' of even and odd columns in J block for A ₂ and A ₃ are both (1, 1).
becomes.

Each 2-bit read signal 151, 151' from each two columns of the storage means 110 is sent to the search processing means 150.
supplied to In addition, each search condition processing means 150
is supplied with 3-bit search condition data 102 indicating search conditions of large, small, and match. Each 2-bit read signal 151, 151' input to each search processing means 150 is the search condition data 102.
Only when the search condition is satisfied, the search processing means 150 generates a search result signal 152 of "1" and supplies it to the encoding means 160.

FIG. 3 shows the correspondence between the search conditions for generating a search result signal 152 of "1", which means that the search conditions are satisfied, and the 2-bit read signals 151, 151'. As shown in FIG. 3, the search condition for small is satisfied in the case of read signals 151, 151' of (0,0), and the search condition for small or match is (0,0).
Or read signal 151, 15 of (1, 1)
The encoding means 160 inputs the search result signal 152 and contains the search result signal 152 of "1".
is included, it becomes “1” along with matching signal 161.
A search address 162 indicating the location of the search result signal 152 is output to an external device. The matching signal 161 contains search information and information satisfying the search conditions in the storage means 11.
0, and its address or column is indicated by search address 162.

Next, search information A is divided into K pieces of M-bit partial data A ₀ , A ₁ , ..., A _i , ..., A _k-1 (A ₀ is the upper one) and supplied as input data 101. do. The storage means 110 read signals 151, 151' for each partial data A _i are the registration information partial data and the search information A encoded and stored in two adjacent columns of the storage means 110 by the write data generation means 140. The results of comparison with data A _i are shown. Each read signal 151 in an even column indicates a = (match) result, and each read signal 151' in an odd column indicates a (great or match) result. The read signals 151 and 151' of even and odd columns for each partial data A _i are respectively
Assuming E _i , Li (i= _{0 to k-1} ), the comparison result between the search information A and the registered information stored in each two columns of the storage means 110, that is, the matching result E indicating a match between the former and the latter, A large result L indicating that the former is larger than the latter and a small result S indicating that the former is smaller than the latter are expressed by equations (1), (2), and (3), respectively.

E=E ₀・E ₁・…・E _i・…・E _k-1 …(1) L=L ₀・₀ +L ₁・₁・E ₀ +…+L _i・_i・
E ₀・E ₁・…・E _i-2 ＋…＋L _k-1・_k-1・E ₀・E ₁・…・E _K-2
…(2) S= ₀・₁・E ₀ +…+ _i・E ₀・E ₁・…・E _i-2
+... + _k-1・E ₀・E ₁・...・E _k-2 ...(3) The search processing means 150 uses the read signals 151, 151' for each partial data as the clock signal 112.
, and performs the logical operations of equations (1), (2), and (3). In addition, the search result R indicating whether the search condition is satisfied is determined by the match condition signal E _c , large condition signal L _c , and small condition signal S _c given as search condition data 102 indicating the search condition (4). It is determined by the formula.

R=E·E _c +L·L _c +S·S _c (4) This search result R is output as a search result signal 152.

Search result signal 152 is supplied to encoding means 160. The encoding means 160 converts the matching signal 161 indicating that the search result signal 152 of "1" is input and its bit position into the search address 1.
Output as 62. A match signal 161 indicates that information satisfying the search information and search conditions is registered in this associative memory device, and the search address 16
2 indicates its storage address.

Note that during multiple matching when multiple pieces of information satisfying the search information and search conditions are registered, a search result signal 1 of "1" is sent from the multiple search processing means 150.
52 occurs. In this case, the search address 162
is input, and the search processing means 15 specified by it is
By providing a decoder that supplies a reset signal to 0, multiple search addresses 16 that satisfy the search conditions can be
2 can be found.

Moreover, by inhibiting the clock signal 112 to the search 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. That is, by masking the clock signal 112, logical operations of equations (1), (2), and (3) regarding partial data A _i of the search information input at the masked period, that is, E _i and (2) are performed. The formula L _i・_i・E ₀・E ₁・…・E _i-2 and
_i , E ₀ , E ₁ , ..., E _i-2 in equation (3) are removed and mask processing is performed. To perform this masking process,
An OR gate is provided to control the supply of the clock signal 112 to the search processing means 150, and the clock signal 11 is supplied to the search processing means 150 via this OR gate.
2 should be supplied.

As explained above, the associative memory device according to the present invention can be constructed by providing an inexpensive ordinary memory element.
Furthermore, a search operation for an N word M×K bit content addressable memory device can be performed by accessing the storage means 110 K times, and high-speed search processing is possible. Furthermore, multiple matching processing and masking processing are also possible. In addition to searching based on matching conditions, searching based on size relationships is also possible.

FIG. 4 is an explanatory diagram of an embodiment of the row selection means 120 used in the associative memory device of FIG. 1. This row selection means 121 includes a decoder 410 that receives input data 101 as registration information and search information;
It consists of an OR gate 420 which performs a logical sum of each output and the operation mode signal 103 and drives the row selection line 121 of the storage means 110.

Operation mode signal 103 of “1” indicating registration operation
In the case where is supplied, all the outputs of the OR gate 420 become "1", and all the row selection lines 121 are driven. 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 during the registration operation, and only the rows designated by the search information are driven during the search operation.

FIG. 5 is an explanatory diagram of an embodiment of the column selection means 130 used in the associative memory device of FIG. 1. This column selection means includes a block decoder 510 that receives the registered address 132 as an input, a column decoder 520 that receives the output 175 of the counter 170 as an input, and an inverter 530 that inverts the operation mode signal 103.
an inverter 550 that inverts the matched column selection signal 133;
Alternatively, the output of 570 is input, and the storage means 1
AND gate 5 that drives 10 column selection lines 131
It consists of 80. AND gate 5 surrounded by a broken line
Each output of 80 is connected to a column select line within a block of storage means 110. A block decoder 51 is connected to the first input of each AND gate 580 surrounded by a dashed line.
0 are connected to each other, and each output of the column decoder 520 is connected to the second input. Furthermore, the output of the third OR gate 560 or 570 is connected to the third input. OR gates 560 and 570 are column selection lines 1 for even and odd columns of storage means 110, respectively.
31 selections.

During the search operation, the operation mode signal 103 is “0”.
is supplied, so OR gates 540, 560,
Each output of 570 becomes "1", and the storage means 110
Two columns of column select lines 131 designated by column decoders 520 in each block are driven in parallel.

Operation mode signal 103 is “1” during registration operation.
is supplied to block decoder 510, column decoder 520, or gate 560 or 57.
0, the registered address 132 and counter 170
One column select line 131 designated by the output 175 of the column select signal 133 and the match column select signal 133 is selectively driven.

FIG. 6 is an explanatory diagram of one embodiment of the write data generating means 140 used in the associative memory device of FIG. 1. This write data generation means is a decoder 610 that receives input data 101 as registration information.
, an AND gate 620, and an OR gate 630. If the registration information is A, the write data line 141 has the storage means 11 shown in FIG.
Write data corresponding to the content of 0 is supplied.
The match column selection signal 133 of "0" or "1" generates write data corresponding to the first column or the second column in FIG. 2. That is, when the matching column selection signal 133 of "0" is supplied, the output of each AND gate 620 becomes "0", and write data is generated in which only the write data line 141 designated by the registration information becomes "1". When the matching column selection signal 133 of "1" is supplied, the output of the decoder 610 is also supplied to the lower write data line 141 via the AND gate 620 and the OR gate 630, and the write data line specified by the value greater than or equal to the registered information 141 to generate write data of "1".

FIG. 7 is an explanatory diagram of an embodiment of the search processing means 150 used in the associative memory device of FIG. This search processing means includes first, second, and third registers 7.
10,720,730 and AND gate 104
0,1041,1042,1043,1044,
1045 and or gate 1050, 1051, 1
052, 1053 and inverters 1060, 10
61.

This search processing means uses the above equations (1), (2), and (3) to calculate the intermediate results of comparison processing E′ _i =E ₀・E ₁・…・E _i (i=0~k−1) ……( 5) L′ _i = L _i・_i・E′ _i-1 (i=0~k-1, E′ _-1 =
1) ...(6) S' _i = _i・E' _i-1 (i = 0 ~ k-1, E' _-1 = 1)
...Introducing (7) and replacing equations (1), (2), and (3) with the following (8), (9), and (10), respectively.
)
It is determined by the formula.

E=E′ _k-1 ……(8) L= _k-1 〓L′ _i ⁱ⁼⁰ ……(9) S= _k-1 〓S′ _i ⁱ⁼⁰ ……(10) First, search information Before partial data A _i is input, an initial setting signal 111 is applied, the first register 710 is set, and the second and third registers 72 are set.
0.730 is reset. Then, each time partial data A _i is input, read signals 151, 15
1' is input, and in synchronization with the clock signal 112, the first register 710 and the AND gate 740 execute the logical operation of equation (5). When input of all partial data A _i is completed, the matching result E of equation (8) is stored in the first register 710. Similarly, the second register 720, the OR gate 750, and the AND gate 741
and the inverter 760 and the first register 710 are
Executes the logical operations of equations (6) and (9), and registers the third register 7.
30, the OR gate 751, the AND gate 742, the inverter 761, and the first register 710.
Execute the logical operations in equations (7) and (10). Therefore, when input of all partial data A _i is completed, a large result is stored in the second register 720 and a small result S is stored in the third register 730.

These first, second, and third registers 710,
The matching relationship E, major relationship L, and minor relationship S stored in 720 and 730 are subjected to a logical operation based on equation (4) with the matching condition signal 712, major relationship signal 713, and minor relationship signal 711, which are the search condition data 102. This is performed using AND gates 743, 744, 745 and an OR gate 752. This search result R is output from the OR gate 752 as a search result signal 152. This signal 152 becomes "1" when the search condition is satisfied.

〔Effect of the invention〕

As described above, the content addressable memory device according to the present invention can be constructed using inexpensive ordinary memory elements that are accessed by supplying an address indicating the storage location of desired data. An N word M.times.K bit associative memory device can be constructed from a ^2M word N.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, a 48 kilobit content addressable memory device consisting of 1 kiloword and 48 bits can be realized in one chip. can. Generally available semiconductor associative memory, such as the associative memory manufactured by Signetics.
Compared to IC8220, which is 4 words and 2 bits,
It can be said that the associative memory device according to the present invention has an extremely large capacity.

In addition, search operations and registration operations in this content addressable memory device can be completed with one or several accesses to the normal storage elements, and are faster than conventional word serial/bit parallel or word parallel/bit serial content addressable memory devices. be.

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. Furthermore, as search conditions, it is possible to search not only for matching conditions but also for size relationships.

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 explanation, "1" is stored in only the rows specified by the registration information in the even columns of the storage means 110, and "1" is stored in the rows specified by the registration information value or more in the odd columns. . This is an example of a storage method, and it is also possible to store "1" or "0" in a row specified as less than or equal to the value of registered information in an odd column, and write data to the storage means 110. As the storage method, various combinations of these methods can be selected. Therefore, the write data generating means 14
0 and the search processing means 150 can be easily modified depending on the method of storing write data in the storage means 110.

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 does not limit the scope of the claims of the present invention.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of an embodiment of an associative memory device according to the present invention, FIG. 2 is an explanatory diagram of the storage contents of the storage means, FIG. 3 is an explanatory diagram showing the relationship between search conditions and read signals, and FIG. 4 is an explanatory diagram of an embodiment of the row selection means of FIG. 1, FIG. 5 is an explanatory diagram of an embodiment of the column selection means of FIG. 1, and FIG. 6 is an explanatory diagram of an embodiment of the write data generation means of FIG. 1. FIG. 7 is an explanatory diagram of an embodiment of the search processing means of FIG. 1. 110...Storage means, 120...Line selection means,
130... Column selection means, 140... Write data generation means, 150... Search processing means, 160...
Encoding means, 170...Counter, 410,
610...decoder, 420, 540, 560,
570, 630, 750, 751, 752...OR gate, 510...Block decoder, 520
... Column decoder, 530, 550, 760, 76
1... Inverter, 580, 620, 740, 7
41,742,743,744,745...And gate, 710...First register, 720...
...Second register, 730...Third 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. and the two column selection lines of the storage means specified by the registered address and the contents of the counting means during the registration operation are selectively driven one column at a time, and the column selection lines specified by the contents of the counting means during the search operation are selectively driven. Column selection means for driving column selection lines in parallel; write data that inverts only the row specified by the input data; and write data that inverts from the row specified by the input data, sequentially to the write data line of each row of the storage means. Each time input data is given, the read signals of two columns of each of the write data generation means supplied to the storage means and the storage means specified by the contents of the counting means are inputted, and whether or not these match the given search conditions is determined. What is claimed is: 1. An associative memory device comprising: search processing means for determining the search processing means; and encoding means connected to the output.