JPS59220838A - Associative memory device - Google Patents

Abstract

PURPOSE:To realize high throughput and large capacity in an associative memory device on the whole by providing an address modification unit, etc., and eliminating the need for plural selective separating operation which specified the throughput in the past. CONSTITUTION:When information data is registered, the registered data is transferred to the address modification unit 103 through a search memory CAM unit 101, RAM unit 102, and control unit 104. The circuit 103 reads flag information and pointer information from the address position (word) of this information, and generates the address of another data part related by the same ID part in the RAM on the basis of said pieces of information to perform the writing to the circuit 102. When retrieval is performed, the same ID part is not registered in the circuit 101, so the plural selective separating operation which specified the throughput in the past is made unnecessary, so even when the number of ID parts increases, the time required for the retrieval processing is constant and the high throughput and large capacity of the device are obtained on the whole.

Description

[Detailed description of the invention] Mori (kL A M : 1 (andotn Acce
The present invention relates to an improvement of an associative memory device which is an essential component of ss Mernor main υ.

[Prior art]

The associative memory device has five indexes (as shown in Figure 1).
Information data 10 consisting of ID) part J1 and data part ]2
is stored, and by inputting the ID part, it is read out to the data part 12 associated with the corresponding ID part J1,
This is used for access such as rewriting. Conventionally, such an associative memory device consists of only tAM or CAM and R.
It has been constructed using AM f.

FIG. 2 shows an example of a conventional associative memory device constructed using only RAM, and FLAM addition is based on an address decoder 21, a data section n, and a valid tag 1. This operation uses the input ID part as an address, selects the corresponding data part 22 by decoding it with the address decoder 21 of the IIJ part, and if the valid tag is, for example, 1'', the corresponding data part 22 is This means that access is permitted.

In this way, the operation of giving an n-bit ID field and accessing a t-bit data field is basically the I
This can be realized using only tAM.

However, assuming that the ID part is n bits, the number M of items 11) is generally MK2°, and despite this, the method shown in Figure 2 requires an approximately AM of 2° words. . For this reason, when n is large (if n is large, it is unrealistic to rely on a huge amount of resources. For example, when n = 16, 216
= 64 K '7-de, 232 Ki 4 when n=32,
It becomes the G word.

Furthermore, in a typical content addressable memory device, it is necessary to handle information data having different data sections in the same ID section.

Figure 3 is a conceptual diagram showing an example of the correspondence between the ID section and data.
M]1 corresponds to Data and Data3. Second
In the configuration using only RAM as shown in the figure, since the ID section is used as a so-called address, the -IIJ section cannot handle information data having different data sections. This is a fatal drawback as an associative memory device.

The solution to this problem was a configuration method using CAM and RAM.

FIG. 4 shows an example of a conventional associative memory device configured using CAM and l (AM). 40 is a CAM consisting of a 10 part 41 and an address encoder 42, and 43 is a RAM which is an address decoder a and a data address decoder. Consists of part 45.CA
M40 inputs the IIJ section and searches for ID41 in the CA M40, and when the corresponding ID is obtained, it is encoded by the address encoder 4o and sent to ItA.
The address is M43. In It A M 43,
By decoding the manually entered address with the address decoder 44, the data section 45 is selected, and the selected data section V is accessed for rewriting, etc. To handle information data with the same ID part and different data parts as shown in the figure, use CAM40F.
Store multiple same 10's in 'j6' and write those IIJ
All you have to do is assign a different code to .

However, in that case, if the valley ID is selected for the inputted part 11), whether it is 7'L or not is corresponding to the word J4f4 L
, it is necessary to select one of them (this is a so-called multiple selection separation operation), and the time required for this operation is:
Basically, it is proportional to the number M of it+ to be separated. Therefore, if M is large (if M is large, it will take an extremely long time. This means that in the configuration shown in FIG. 4, the throughput is limited by the multiple selection separation operation, and the throughput cannot be improved. - As explained above, in conventional associative memory devices, j
It requires a large amount of resources, cannot handle information data with different data parts in the same ID part, or
When the number M of D is increased, there is a drawback that the throughput of the device increases (decreases).

[Object of the invention] The object of the present invention is to solve the above-mentioned conventional drawbacks, and to solve the above-mentioned problems,
The object of the present invention is to realize a content addressable memory device with high throughput.

[Summary of the invention]

The main point of the present invention is that in an associative memory device configured using a CAM unit and an AM unit, the ID section is
The data section and the control information (flag information) added in relation to the data section are stored in the AM unit, and the same control information (flag information) is stored in the RAM unit. This is achieved by providing an address modification unit that generates addresses in the RAM of other data sections associated with the ID section.

[Embodiments of the invention]

FIG. 5 is a block diagram of one embodiment of the present invention.

In FIG. 5, 101 is a CAM unit, 102 is an R
AM unit, 103, address modification unit, 104
is a control circuit, and the IL A M unit 102 includes a decoder section 108, a data section 109, a flag section 110, and a pointer section 111. The CAM unit 101 has the same configuration as 40 in FIG. ) CAM unit 1
The decoder section 108 and data section 109 of 02 are also 4 in FIG.
4 and 45, but the flag section 110 contains the same ID as the ID section to which the data section of the corresponding word is associated.
The pointer section 111 stores flag information indicating whether or not there is another data section associated with this section.
Stores address information within the M unit. 105 is CA
10 input lines to the M unit 101, 106 is an address information output line for the CAM unit 101, 107 is the same (selected word presence/absence signal output line for the CAM unit 101), and 112 is a data section for the RAM unit 102. (113 is the RAM unit) Address information input line to 102 (114 is the RAM unit 102)
115 is a flag information line, 1ti-
18 is itcAM unit 101, RAM-+
-=t 102, control the address modification unit 103 1
This is a control signal line for

Now, the operations of the associative memory device include information data registration and verification processing. Registration of information data is to register information data consisting of IIJ section and data section into memory,
In this case, as shown in FIG. 3, registration of different data sections in the same ID section must also be allowed. The search process is performed by searching the input I for the registered information data.
This is a process in which a search is performed using the D section, and the data section corresponding to the selected IL) section is retrieved and rewritten accessed. Hereinafter, it will be explained that these operations can also be realized in the embodiment of the present invention shown in FIG.

Data (1) Information to be registered The ID part of the data is C from line 105.
input to the AM unit 101, and the CAM unit) 101
A search is made to see if the corresponding ID section has already been registered. (,'AM unit) The search results for each word 101 are notified to the control circuit 104 via the selected word presence/absence signal line 107.

(2) The control circuit 104 monitors the selected word presence/absence signal line 107, and if the ID part within the CAMA4 unit 101 is not registered, the 111th part of the information data to be registered in the empty word of the CAM unit lo1, The CAI~
4 unit 101 address position 1 associated with i
The information data to be registered is written to the address position of t A M unit) 102 through the data section line 112.

On the other hand, if the corresponding section 11) has already been registered in the CA A4 unit 101, the address information of that word is transferred from the cAM unit) 101 to the address modification unit) 103 via m106, and the next step (3) is performed. Move on to the operation.

(3) The address modification unit 10'3 inputs the address information transferred from the CAM unit 10L to the RAM unit 1o2 via the line 113, and outputs flag information and pointer information from the corresponding address position (word).

The control circuit 104 manually inputs the flag information read from the tAM unit 102 via the line 115, and connects the data section of the corresponding word to other data related by the same ID section as the IJ section. (RA Al unit)
It is determined whether or not it is stored in 102. Then, if there is another data section with the same ID section ifL: stored, the process moves to operation (4), and if it is not stored, the process moves to operation (5).

+4) It A M unit 1o2 color readout 1
This pointer information is transferred to the address modification unit (103) via line 114, and the address modification unit (103) transfers the pointer information to the RAM unit (10) via line 113.
2, and the flag information and pointer information are not read from the address position indicated by the pointer information. This operation is continued until a word that is not stored in another data section related by the same ID section is read, and from the flag information, the same word is read out.
If it is determined that the data section with the ID section no longer exists, the process moves to step (5).

(5) Rewrite the flag information of the read word with content indicating that other data corresponding to the same ID part as the ID part to which the data part of the corresponding word is related is stored, and A new address is generated at 103 and stored in the pointer section of the read word, and the data section to be registered is written at this new address position in the RAM unit 102 via line 112. It's crowded.

The above operations complete the registration of information data.

At the time of this registration, multiple identical ID sections are not stored in the CAM unit 101. Registration of multiple data sections to the same ID section generally does not occur very often, and when multiple data sections do not exist for the same ID section, the registration operation is only performed by f3) and (2) above. Well, fast enough. Note that various algorithms may be used to generate new address information in the address modification unit 103, but a description thereof will be omitted.

Search process (1) Input the ID section to the CAM unit 1o1 via the line 105, and search whether or not the corresponding ID section exists in the CAM unit 101. At this time, the control line 104 monitors the selected word presence/absence signal output to w1o7, and if the corresponding ID section does not exist, the process ends. If there is an ID part corresponding to the ID part input in the CAM unit 101 and that word is selected, the address information of the word is sent from the CA''M unit 101 via a line 106 to the address modification unit).
103, and proceed to the next operation (2).

(2) The address modification unit 103 inputs the address information transferred from the CAM unit 101 to the RAM unit 1o2 via line 03, and reads or rewrites the data section 109 at the corresponding address position via line 112. I do. At this time, the contents of the flag section 110 and pointer section 111 at the address location are also read out, and the flag information is input to the control circuit 104 through the line 115, so that there is no other data section having the same ID section. Determine whether it is stored or not. If there is another data section having the same -ID section, the read pointer information is transferred to the address modification unit 1o3 via the line 114, and the process moves to the next step (3).

(3) The address modification unit inputs the transferred pointer information to the RAM unit 102 via the i 113 and accesses the RAM unit 102 again.

Thereafter, the same operation is repeated until it is determined from the flag information that there is no other data section having the same -ID section.

In the embodiment shown in FIG. 5, during search processing, since the same-ID section is not registered in the CAM unit 101, the multiple selection and separation operation that was necessary in the past becomes unnecessary, and the number M of IDs becomes large. However, the time required for search processing is constant, and throughput does not decrease. Furthermore, the registration of information data occupies a smaller proportion of the overall operation than the search process.

Note that the CAM unit 101, the RAM unit 102,
By pipelining the operation of the address modification unit 103, even higher throughput can be achieved. Furthermore, in this embodiment, the R'AM unit 1o
In this method, a separate address management mechanism is provided, and the pointer information in RAM unit 102 is used to access data sections one after another.
Record the information 1. [Effects of the Invention] As described above, the associative memory device according to the invention provides the following advantages. .

(1) Since the multiple selection and separation operation that defined the throughput of conventional associative memory devices is no longer necessary, a high throughput associative memory device ft can be realized.

(2) Similar to (1) above, since the multiple selection separation operation is no longer necessary, the throughput does not decrease even if the number of IDs becomes large, and a large-capacity content addressable memory device is realized while maintaining high throughput. can.

(3) It only requires a CAM unit with the same number of hoods as the required number of Ij), and the RAM
Compared to the conventional associative memo ') Rflt, which is constructed using only the associative memory, there is no waste of resources (and the cost of the associative memory device can be reduced).

(4) When attempting to construct an associative memory LSI in which a CAM unit is created using semiconductor integrated circuit technology,
In the present invention, since the functions required of the CAM unit are extremely simple, the associative memo IJ L S
It becomes possible to increase the speed and capacity of I itself. This leads to an even larger capacity and higher throughput of the associative memory device as a whole.

[Brief explanation of the drawing]

FIG. 1 is a conceptual diagram of information data stored in an associative memory device, FIG. 2 is a diagram showing an example of a conventional associative memory device configured using RAM, and FIG. 3 is a diagram showing an example of a conventional associative memory device configured using a RAM. FIG. 4 is a diagram showing an example of a conventional associative memory device constructed using CAM and RAM, and FIG. 5 is a block diagram showing an embodiment of the present invention. 101...CAM unit, 102...RAM
unit, 103...address modification unit), 104
...Control circuit, 108...Decoder section, 1
09...Data section, 110...Flag section, 11
1... Pointer section. Representative Patent Attorney Makoto Suzuki Figure 1 119 Figure 3 Figure 4

Claims (1)

[Claims] (1) An index section and a data section associated with the index section are stored, and by inputting the index section, the data section stored in relation to the index section can be read or In an associative memory device that performs access such as rewriting, an index part is stored and a content search memo I is used to search for the nature of the corresponding index part in the index part that is manually generated.
A J((,:AiV) unit and a flag section indicating the presence or absence of other data associated with the same index section as the data section and the index section associated with the data section are stored. Random access memory (R
If the flag part in the AA4) unit and the above) tAM unit indicates that there is other data in the same index part that is associated with the data part, the data should be stored. and an address modification unit that generates address information within the unit, accesses the H, A + V+ unit with the search output of the CAM unit, and associates a flag section associated with the corresponding data section with the data section. If it indicates that there is other data in the same index section, the address rl f
A content addressable memory device characterized in that an It AM unit is accessed again based on address information generated by an ffi unit.