JP3583799B2 - Method of using associative memory and associative memory - Google Patents

Description

[0001]
[Industrial applications]
The present invention relates to a conventional general use of an associative memory and an associative memory having a hardware configuration adapted to the use.
[0002]
[Prior art]
Conventionally, each digital data is stored in each of a plurality of arranged memory words, search data is input, and the input search data has a bit pattern that matches all or a predetermined part of the bit pattern. 2. Description of the Related Art An associative memory (Content Addressable Memory) for searching a memory word in which digital data is stored has been proposed.
[0003]
FIG. 2 is a circuit block diagram illustrating an example of the associative memory.
The associative memory 10 is provided with a large number of memory words 11_1, 11_2,..., 11_n composed of m-bit memory cells arranged in the horizontal direction in FIG. The associative memory 10 also includes a search register 12 into which one-word search data is input and latched. The search data latched by the search register 12 has all or a predetermined part of the bit pattern, and each memory word 11_1, .., 11_n, the bit patterns of the data corresponding to the bit patterns are compared with the corresponding bit patterns, and the match provided for each of the memory words 11_1, 11_2,. .., 14_n of the lines 14_1, 14_2,..., 14_n have coincidence signals of logic “1” (5 V in this case) on the coincidence lines 14_1, 14_2,. Is output. The other matching lines 14_1, 14_2,..., 14_n remain at logic '0' (here, 0V).
[0004]
The signals output to the match lines 14_1, 14_2, ..., 14_n are stored in the respective match flag registers 15_1, 15_2, ..., 15_n. Here, as an example, as shown, '0', '1', '1', '0', ..., '0', '0' are respectively stored in the match flag registers 15_1, 15_2, ..., 15_n. It shall be stored. The signals stored in these match flag registers 15_1, 15_2,..., 15_n are input to an address encoder 16, and from this address encoder 16, a match flag register storing a logic “1” signal (here, a match flag register). 15_2 and two of the match flag registers 15_3) are output. Here, it is assumed that the smaller the subscript, the higher the priority is. Therefore, here, the memory address corresponding to the match flag register 15_2 is output. The address signal AD output from the address encoder 16 is input to the decoder 17 as needed. The decoder 17 decodes the input address signal AD to input the address signal of the word lines 18_1, 18_2,..., 18_n provided corresponding to the respective memory words 11_1, 11_2,. An access signal (here, a signal of logic “1”) is output to one of the word lines (here, word line 18_2) corresponding to AD. Thus, the data stored in the memory word 11_2 corresponding to the word line 18_2 to which the access signal has been output is read out to the output register 19.
[0005]
Next, by changing the signal stored in the match flag register 15_2 to “0”, the address of the memory word 11_3 corresponding to the match flag register 15_3 can be obtained.
As described above, the associative memory 10 searches the contents (data) stored in a large number of memory words 11_1, 11_2,..., 11_n using all or predetermined data of the search data, and Is a memory configured to obtain the address of a memory word having the following formula, and to read out the entire data stored in the memory word as needed.
[0006]
When the data stored in the associative memory as described above is data to which a plurality of attributes are added, a search may be inconvenient.
FIG. 3 is a diagram showing an array of data with attributes stored in the associative memory.
A large number of memory words constituting the associative memory are grouped into groups of four, and the first memory word in each group stores, for example, data with "attribute 0" of "name". In the second memory word, for example, data with “attribute 1”, such as “birth date”, is stored. Similarly, the third and fourth memory words in each group are respectively assigned “attribute 2”. , "Attribute 3" is stored. Here, each data stored in each memory word is indicated by alphabetical letters A, B,... Hereinafter, a set of data groups to which each attribute is added as described above is referred to as a “data set”.
[0007]
Here, the data of the attribute 0 described at the top of FIG. 3 is “A”, and the data of the attribute 1 described in the next row is also “A”. In some cases, bit pattern data is stored.
In this case, if it is desired to search only data “A” belonging to attribute 0 (for example, a person whose name is “A”), and input data “A” as search data, only data “A” belonging to attribute 0 is searched. However, the data "A" belonging to the other attributes 1, 2, and 3 are also searched at the same time, and it is necessary to perform an operation such as searching again for the data belonging to the attribute 0 from the data searched after the search. There is a problem that the operation is extremely complicated and the search takes a long time.
[0008]
A solution to such a problem has been proposed by the present applicant (see Japanese Patent Application No. 5-184747). Hereinafter, this proposal will be described.
FIG. 4 is a memory structure diagram according to the above proposal.
The upper k bits (for example, 2 bits) of a memory word composed of m bits (for example, 16 bits) constituting an associative memory are defined as an area for storing attribute data representing attributes, and the remaining mk bits (for example, 16-2 = 14 bits) is determined as an area for storing the original data with these attributes, and both the attribute and the data are stored in each memory word. In the search, the search is performed using both the attribute and the data. For example, if a search is performed using both “attribute 0” and data “A”, the data shown at the top of FIG. 4 is searched.
[0009]
FIG. 5 is a block diagram of an associative memory for further explaining the above concept. The associative memory is essentially the same as the associative memory shown in FIG. 2 except that the drawing is slightly different for convenience of explanation. Have been. The same blocks as the blocks of the associative memory shown in FIG. 2 are denoted by the same numbers as those shown in FIG.
[0010]
The attribute data is stored in the upper 2 bits of each of the m-bit memory words 11_1, 11_2,..., 11_n, and the data with each attribute is stored in the remaining m-2 bits. In the search, the upper two bits of the search register 12 are used as an attribute search register 12_1 storing attribute data for search, and the remaining part of the search register 12 (the search data register 12_2 has been described with reference to FIG. 2). At this time, a search register in the original meaning is used, and the search is performed by storing the attribute data and the search data in the original meaning in the search register 12. Thereby, the attribute represented by the attribute data used in the search is added. The search for the desired stored data is performed, that is, the search for the same stored data having different attributes is excluded.
[0011]
Next, an example of an associative memory configured to store attribute data in a fixed manner will be described.
Although FIG. 5 can be used as it is for the description of the associative memory configured to store attribute data in a fixed manner, the configuration of each memory word 11_1, 11_2,. Different from memory word of memory.
[0012]
FIG. 6 is a circuit diagram showing a configuration of one memory word among a large number of memory words forming the associative memory. This circuit is an example of a circuit configuration based on SRAM and detecting a match with search data by a NAND type match detection circuit.
The illustrated memory word includes a bit cell group 20 including a first attribute bit cell 20_1 and a second attribute bit cell 20_2 and a memory cell group including memory cells 21_1,..., 21_m having an m-bit (for example, 16-bit) SRAM structure. 21 are formed.
[0013]
In the first attribute bit cell 20_1, two transistors T1 and T2 serially connected to each other between the bit line Zb1 and the bit bar line Zb1_ are formed, and a transistor is connected to a connection point of these two transistors T1 and T2. The gate electrode of TC1_1 is connected. The gate of transistor T1 is set to logic '1' and the gate of transistor T2 is set to logic '0'. At this time, when "1" is applied to the bit line Zb1 and "0" which is an inverted signal thereof is applied to the bit bar line Zb1_ connected to the attribute search register 12_1 shown in FIG. '1' of the line Zb1 is applied to the gate of the transistor TC1_1, and the transistor TC1_1 is also turned on. This state is a state in which the content fixedly stored in the first attribute bit cell 20_1 matches the input attribute data for search with respect to the first attribute bit cell 20_1. Conversely, when '0' is applied to the bit line Zb1 and '1' is applied to the bit bar line Zb1_, the gate of the transistor TC1_1 becomes '0' and the transistor TC1_1 is turned off. This is an unmatched state for the first attribute bit cell 20_1.
[0014]
Similarly, in the example shown in FIG. 6, in the second attribute bit cell 20_2, the data stored therein is opposite to the data stored in the first attribute bit cell 20_1, and the signal from the attribute search register 20_1 is When they are '0' (bit line Zb2 is '0' and bit bar line Zb2_ is '1'), a match is made.
That is, in the example shown in FIG. 6, when two of the attribute bits are (1, 0), the state is "match".
[0015]
The memory cells 21_1,..., 21_m have values applied to the gates of the transistors T1, T2 set by the Q nodes and Q_ nodes of the SRAM accessed by the decoder 17, and the match detection operation is performed by the attribute memory. This is the same as the case of the cells 20_1 and 20_2.
In a NAND type match detection circuit 30 including transistors TC1_1, TC1_2, TC2_1,..., TC2_m and the like serially connected to each other, a control transistor TC0 is configured at the left end of the drawing, and a match detection amplifier 31 is configured at the right end of the drawing. And is controlled by the control clock φ. First, the control clock φ becomes '0', and the input node of the match detection amplifier 31 is precharged by the precharge transistor 31a, whereby the output of the inverter 31b becomes '0'. At this time, the control transistor TC0 is kept off.
[0016]
Each bit line, each bit bar line Zb1, Zb1_; Zb2, Zb2_: Db1, Db1_...; Dbm, Dbm_; search data is input in advance from the attribute search register 12_1 and the search data register 12_2; Match / mismatch is determined for each of the bit cells 20_1, 20_2 and each of the memory cells 21_1,..., 21_m. For the matching cells, the corresponding transistors TC1_1, TC1_2, TC2_1,. Becomes '1' and the transistor turns on.
[0017]
When the control clock φ becomes "1" in this state, the input node of the inverter 31b of the NAND type match detection circuit 31 corresponding to only the memory word in which all the cells match is discharged, and the match of "1" from the inverter 31b is obtained. A signal is output, and '1' is stored in the corresponding match flag register 15.
At this time, if there is no match between the attribute data as well as the stored data stored in the memory cells 21_1,..., 21_m, a match signal cannot be obtained. Therefore, by defining this attribute data according to the attribute of each data constituting each data set, it becomes possible to search for each attribute of each data set. In the associative memory in which the attribute data is created in advance in hardware as described above, the attribute data may be set as one of the control data in the attribute search register 12_1 shown in FIG. Accordingly, it is possible to configure a system capable of accessing the outside without reducing the bit length of one word of the associative memory.
[0018]
[Problems to be solved by the invention]
As described above, when both attributes and data are stored in each memory word and search is performed using both the attributes and data, processing of unused memory words becomes a problem. For example, when five data of attributes I to V are stored as a data set in the associative memory using the associative memory in which 128 memory words are formed, three out of 128 memory words that cannot be divided by 5 The memory word becomes unused.
[0019]
If the remaining three memory words are left as they are, there is a concern that data that happens to be stored in the memory word and the search data may match. Further, it is defined that the remaining three memory words are in an empty state where valid data to be searched is not stored (actually, each memory word has a flag register, and valid data is stored in the corresponding memory word). A flag for identifying whether the data is stored or the memory word is empty is stored), and when writing new data to the memory word, the remaining memory word is designated and one data set is written. A situation may occur in which all the constituent data is not written.
[0020]
In view of the above circumstances, an object of the present invention is to provide a method of using an associative memory that effectively processes surplus memory words and an associative memory in which surplus memory words are effectively processed.
[0021]
[Means for Solving the Problems]
A method of using the associative memory of the present invention to achieve the above object is to store each digital data in each of a plurality of arranged memory words in a freely writable manner, input search data, and input all or all of the input search data. A method of using an associative memory for retrieving a memory word in which digital data having a bit pattern matching a predetermined partial bit pattern is stored,
Among the plurality of memory words, the first memory word used for the search stores digital data in one of the first areas where the first memory word is divided into two, and the first memory word is stored in the first memory word. Attribute data representing attributes of digital data stored in the first area is stored in a second area of the word excluding the first area, and is used for retrieval among the plurality of memory words. Storing attribute data having a value different from any of the attribute data stored in the first memory word in the second area of the second memory word that is not performed;
By inputting a set of predetermined attribute data and predetermined digital data into the associative memory as search data, the specified attribute data corresponding to the input predetermined digital data and being displayed is represented in the associative memory. A memory word storing digital data having an attribute is searched.
[0022]
The associative memory of the present invention that achieves the above object stores digital data in each of a plurality of arranged memory words, inputs search data, and inputs all or a predetermined part of the input search data. An associative memory for searching a memory word in which digital data having a bit pattern matching the bit pattern of
A first memory word used for retrieval among the plurality of memory words represents a first area in which each digital data is writably stored and an attribute of the digital data stored in the first area. A second area in which the attribute data is writable or fixedly stored, and
The second memory word that is not used for searching among the plurality of memory words is the attribute data whose value is different from any of the attribute data stored in the first memory word. It has a second region.
[0023]
[Action]
A method of using the associative memory according to the present invention is to perform a search by writing attribute data having a value different from any of the attribute data used in the search into the remaining memory words, and perform the search. Since attribute data having a value different from that of any of the attribute data used for the search is written in the remaining memory words, it is prevented that a match is detected in the remaining memory words.
[0024]
【Example】
Hereinafter, examples of the present invention will be described.
FIG. 1 is a diagram showing an example of a memory map of a memory word in the present invention.
The associative memory of this embodiment includes 128 memory words 11_1, 11_2,..., 11_128. Each memory word 11_1, 11_2,. , 11_128_1, and second areas 11_1_2, 11_2_2,..., 11_128_2 for storing attribute data. It is assumed that a data set including five data to which attributes IV are assigned is stored in the associative memory.
[0025]
In that case, three extra memory words 11_126,..., 11_128 that are not divisible by 5 are generated, and the second area 11_126_2,..., 11_128_2 of the memory words 11_126,. A value different from any of I to V, for example, attribute VII is stored. In this case, the attribute and the data do not match, and therefore the attribute and the data do not match as a whole, so that careless erroneous search is prevented.
[0026]
【The invention's effect】
As described above, according to the present invention, accidental erroneous search is prevented even if a memory word has a surplus.
[Brief description of the drawings]
FIG. 1 is a diagram showing an example of a memory map of a memory word in the present invention.
FIG. 2 is a circuit block diagram illustrating an example of an associative memory.
FIG. 3 is a diagram showing an array of data with attributes stored in an associative memory.
FIG. 4 is a memory structure diagram.
FIG. 5 is a block diagram of an associative memory.
FIG. 6 is a circuit diagram showing a configuration of one memory word among a large number of memory words configuring an associative memory.
[Explanation of symbols]
10 associative memory 11_1, 11_2, ..., 11_128 memory word 11_1_1, 11_2_1, ..., 11_128_1 first area 11_1_2, 11_2_2, ..., 11_128_2 second area

Claims (2)

Digital data is stored in each of a plurality of arranged memory words in a freely writable manner, search data is input, and digital data having a bit pattern that matches all or a predetermined part of the input search data is stored. In a method of using an associative memory to search for a memory word in which data is stored,
Digital data is stored in one of the first areas of the plurality of memory words, the first memory word being used for searching, and the first memory word is divided into two. Attribute data representing an attribute of digital data stored in the first area is stored in a second area of the word excluding the first area, and is not used for retrieval among the plurality of memory words. Storing attribute data having a value different from any of the attribute data stored in the first memory word in the second area of the second memory word;
By inputting a set of predetermined attribute data and predetermined digital data to the associative memory as the search data, predetermined attribute data corresponding to the input predetermined digital data and input is stored in the associative memory. A method of using an associative memory, characterized in that a search is made for a memory word in which digital data having a representative attribute is stored. Digital data is stored in each of a plurality of arranged memory words, search data is input, and digital data having a bit pattern that matches all or a predetermined part of the input search data is stored. In an associative memory that searches for a given memory word,
A first memory word used for retrieval among the plurality of memory words represents a first area in which each digital data is writably stored and an attribute of the digital data stored in the first area. A second area in which the attribute data is writable or fixedly stored, and
The second memory word that is not used for retrieval among the plurality of memory words is the attribute data whose value is different from any of the attribute data stored in the first memory word. An associative memory having a second area.

Images