CN102663051A - Method and system for searching content addressable memory - Google Patents

Abstract

The present invention provides a method and system for searching content addressable memory. The method includes: obtaining the search word; dividing the search word into N sub-search words, wherein each sub-search word corresponds to a static random access memory (SRAM) whose address width is equal to the width of the sub-search word in the content addressable memory CAM; in parallel Carry out read operation in corresponding SRAM with sub-search word as read address, obtain the matching result of each storage address on the SRAM corresponding to each sub-search word to this sub-search word; The matching result that obtains is merged processing, obtains this Find word matches in CAM.

Description

Method and system for searching content addressable memory

technical field

The invention relates to the field of integrated circuit design, in particular to a method and system for searching content addressable memory.

Background technique

CAM (Content Addressable Memory) is a special type of computer memory that is widely used in the fields of computers and communications. The function of standard memory RAM is to return the data word stored at the address according to the read address provided by the user. Unlike RAM, the function of CAM is to search all the storage to determine whether the data word is stored in it according to a data word provided by the user. If this data word is found, the matching address is returned, which is the location of the data word in memory, so CAM is the hardware embodiment of the software term associative array.

The usual CAM design principle is to search the entire storage in one operation, that is, read out each group of data in the memory, compare the externally received data with it one by one, and then perform priority decoding on it according to the comparison result. The register generates a binary match position fix and a match hit signal. There are two conventional CAM implementation methods, one is to store the data in the SRAM, and read out the content in the static random access memory (SRAM) one by one to compare with the search word when searching. The other is to store data in Registers and build memory groups. When searching, the search word is broadcast to each group of Registers for comparison, and then the priority decoder generates matching positions and matching hit signals according to the comparison results of each group.

But above-mentioned two kinds of implementation methods all have drawbacks in varying degrees, the first method is limited by the number of RAM read ports, and the delay required to complete a CAM search process is very large, L=(memory depth/RAM read port number) *Tclk, takes multiple clock cycles. On the premise that the specifications of the RAM device are determined and the ports remain unchanged, the greater the memory depth, the greater the CAM search delay. Taking a CAM implemented by a 1-read 1-write two-port SRAM as an example, if the storage depth is 64, it takes 64 clock cycles to complete a search. The second method is limited by resources and area. Although the memory group built by Register can compare the search words in parallel, it occupies a larger chip area than the SRAM with the same capacity. The larger the width of the search word data, the more obvious the difference in area, which brings great challenges to resource allocation and layout of the chip.

Therefore, how to fast CAM is an urgent problem to be solved.

Contents of the invention

The invention provides a method and system for searching content addressable memory, and the technical problem to be solved is how to quickly search CAM.

In order to solve the problems of the technologies described above, the present invention provides the following technical solutions:

A method of searching a content addressable memory (CAM), comprising:

get search word;

The search word is divided into N sub-search words, wherein each sub-search word corresponds to a static random access memory (SRAM) with an address width equal to the sub-search word width in the content addressable memory CAM;

Carry out read operation in parallel with sub-search word as read address in corresponding SRAM, obtain the matching result of each storage address on the SRAM corresponding to each sub-search word to this sub-search word;

The obtained matching results are merged to obtain the matching result of the search word in the CAM.

Preferably, the method also has the following characteristics: the matching result of each storage address on the SRAM corresponding to each sub-search word to the sub-search word is obtained in the following manner, including:

Each storage address of the SRAM corresponds to a bit vector whose length is equal to the search depth of the CAM, where each bit of the bit vector represents a valid CAM entry in turn. If a bit value of the bit vector is equal to 1, it means that the same position in the CAM If there is the same data as the sub-search word, the search is completed, and the match is successful; if all bits of the bit vector are equal to 0, it means that there is no data identical to the sub-search word in the CAM, the search is completed, and the match fails.

Preferably, the method also has the following characteristics: the obtained matching results are merged to obtain the matching results of the search word in the CAM including:

Perform a bit-by-bit AND operation on the obtained N bit vectors to obtain the matching result of the search word in the CAM.

Preferably, the method also has the following characteristics: after obtaining the matching result of the search word in the CAM, it also includes:

Perform reduction operation or operation on the obtained matching result to obtain the CAM search matching result. If the result is 1, it means that the matching is successful; if the result is 0, it means that the matching fails.

Preferably, the method also has the following characteristics: after obtaining the matching result of the search word in the CAM, it also includes:

A priority decoding operation is performed on the obtained matching result to obtain a matching item, and the matching item is used as the address of the search word in the CAM.

A system for searching content addressable memory (CAM), comprising:

obtaining means for obtaining the search word;

The division device is connected with the acquisition device, and is used to divide the search word into N sub-search words, wherein each sub-search word corresponds to a static random access memory (SRAM) whose address width is equal to the width of the sub-search word in the content addressable memory CAM;

The reading device is connected with the dividing device, and is used to use the sub-search word as the read address to perform a read operation in the corresponding SRAM in parallel, so as to obtain the information of each storage address on the SRAM corresponding to each sub-search word to the sub-search word matching result;

The processing device is used to combine the obtained matching results to obtain the matching result of the search word in the CAM.

Preferably, the system also has the following characteristics: the reading device obtains the matching result of each storage address on the SRAM corresponding to each sub-search word to the sub-search word in the following manner, including:

Each storage address of the SRAM corresponds to a bit vector whose length is equal to the search depth of the CAM, where each bit of the bit vector represents a valid CAM entry in turn. If a bit value of the bit vector is equal to 1, it means that the same position in the CAM If there is the same data as the sub-search word, the search is completed, and the match is successful; if all bits of the bit vector are equal to 0, it means that there is no data identical to the sub-search word in the CAM, the search is completed, and the match fails.

Preferably, the system also has the following characteristics:

The processing device is used to perform a bitwise AND operation on the obtained N bit vectors to obtain a matching result of the search word in the CAM.

Preferably, the system also has the following characteristics: the system also includes:

The operation device is connected with the processing device, and the obtained matching result is reduced or operated to obtain the search matching result of the CAM. If the result is 1, it means that the matching is successful; if the result is 0, it means that the matching fails.

Preferably, the system also has the following characteristics: the system also includes:

The priority decoding device is connected with the processing device, and is used for performing a priority decoding operation on the obtained matching result to obtain a matching item, and the matching item is used as the address of the search word in the CAM.

Different from the usual CAM implementation method, the embodiment provided by the present invention does not search by comparing the stored data and the search word one by one, but splits the search word into multiple sub-search words, and each sub-search word after splitting is used as The access address performs a read operation on the SRAM, and the storage word whose address value is equal to the search word is strobed. This operation implies a complete search process, and the system time overhead is only the read delay of the memory.

Description of drawings

FIG. 1 is a schematic flowchart of an embodiment of a method for searching a content-addressable memory provided by the present invention;

Fig. 2 is the schematic diagram of dividing search word in the present invention;

Fig. 3 is the schematic diagram of the median vector of the present invention;

FIG. 4 is a schematic diagram of processing the obtained bit vector provided by the present invention;

Fig. 5 is a schematic diagram of the processing mode of reduction and priority decoding operations in the present invention;

FIG. 6 is a schematic structural diagram of a system for searching a CAM in the present invention.

Detailed ways

In order to make the purpose, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments. It should be noted that, in the case of no conflict, the embodiments in the present application and the features in the embodiments can be combined arbitrarily with each other.

FIG. 1 is a schematic flowchart of an embodiment of a method for searching a content-addressable memory provided by the present invention. The method embodiment shown in Figure 1 includes:

Step 101, obtain the search word;

Step 102, divide the search word into N sub-search words, wherein each sub-search word corresponds to an SRAM whose address width is equal to the sub-search word width in the content addressable memory CAM;

The address width of the SRAM is the logarithm of the storage space size of the SRAM to 2; for example, the address width of an SRAM with a storage space size of 256 is 8.

Step 103, in parallel, use the sub-search word after division as the read address, and perform a read operation in the corresponding SRAM to obtain the matching result of each storage address on the SRAM corresponding to each sub-search word to the sub-search word;

Step 104, combining the obtained matching results to obtain the matching result of the search word in the CAM.

Different from the usual CAM implementation method, the method embodiment provided by the present invention does not search by comparing the stored data and the search word one by one, but splits the search word into multiple sub-search words, and each sub-search word after splitting The SRAM is read as the access address, and the storage word whose address value is equal to the search word is strobed. This operation implies a complete search process, and the system time overhead is only the read delay of the memory.

The method embodiment provided by the present invention is described further below:

Take the general-purpose 1R1W SRAM memory as an example, where the storage data width of the SRAM is equivalent to the CAM search depth, that is, the maximum number of searched data that the CAM can hold.

The entire CAM includes multiple SRAM storage banks, such as SRAM with a depth of 256 and SRAM with a depth of 128.

When the value of the search content is large, that is, the data width of the search word is large, if the entire search content is single-addressed, the SRAM depth will be too large (equal to the width of the search word). Therefore, the search word is divided into N sub-search words, and each sub-search word corresponds to a piece of SRAM memory whose address width is equal to the width of the sub-search word.

Fig. 2 is a schematic diagram of dividing search words in the present invention. In the schematic diagram shown in Figure 2, the search word (SearchWord) is divided into N sub-search words (SubWord) with a base of 8. When the search word width is 39, it is divided into 5 parts, and the width of each sub-search word is in turn For 8, 8, 8, 8, 7. That is, the first four sub-search words correspond to an SRAM with a storage space of ²⁸ , and the last one corresponds to an SRAM with a storage space of ²⁷ .

After the divided sub-search words are obtained, the sub-search words are used as read addresses, and the SRAM corresponding to each sub-search word is read in parallel.

Among them, each storage address of the SRAM corresponds to a bit vector whose length is equal to the search depth of the CAM, where each bit of the bit vector represents a CAM valid entry in turn, and the SRAM is represented by configuring the value of each bit of the bit vector Whether there is the same data as the sub-search word at the same position in .

Specifically, the content stored in the SRAM is a bit vector whose width is equal to the search depth of the CAM, and each bit of the bit vector refers to a valid entry of the CAM, 1 indicates that the entry is valid, and 0 indicates that the entry is invalid. The position of the bit that is 1 in the bit vector in the bit vector indicates the matching address of the valid entry in the CAM. A certain bit value of the bit vector is equal to 1, indicating that the same data as the sub-search word exists in the same position in the CAM, the search is completed, and the matching is successful. All bits of the bit vector are equal to 0, indicating that there is no data identical to the sub-search word in the CAM, the search is completed, and the match fails.

Fig. 3 is a schematic diagram of a bit vector in the present invention. In the schematic diagram shown in Figure 3, the data width is equivalent to the bit vector of the CAM search depth D, where each bit of the bit vector refers to a valid entry in the SAM, and when the attribute value of the bit is 1, it indicates the entry Valid; when the attribute value of this bit is 0, it means that the entry is invalid.

The bit vectors in the SRAM memory corresponding to the N sub-search words are read out in parallel, and each bit vector represents the matching information of the sub-search word where it is located. The merging operation of N bit vectors, that is, the bit-by-bit AND (&) operation of binary operands of the same data width input by N, calculates the matching information of a full-width search word in the CAM.

FIG. 4 is a schematic diagram of processing the obtained bit vector provided by the present invention. In the schematic diagram shown in Figure 4, the bit vector (BitVecN) corresponding to N sub-search words is carried out bit by bit "AND" operation, when the output result is 1, then calculate the bit vector corresponding to the search word of full width ( BitVector)

After the merging operation is completed, a reduction operation or (|) operation and a priority decoding (pri-encoder) operation are performed on the merging result. The result of the reduction operation or operation of merging bit vectors is the search matching result of CAM, 1 indicates that the match is successful, and 0 indicates that the match fails. The result of the priority decoding operation of the merge bit operation is the address of the matching item of the CAM in the CAM.

FIG. 5 is a schematic diagram of the processing manner of the reduction and priority decoding operations in the present invention. In the schematic diagram shown in Figure 5, the bit vector (BitVector) obtained by the merge operation is used as the operand, and the priority decoding and the reduction operation are performed respectively, and the matching CAM effective entry address (MatchedAddr) and the CAM search matching result (IsMatched) are calculated .

In addition, the write operation of CAM is controlled by the logic control unit: the priority decoder finds the CAM empty item, and then initiates a write operation to the storage word whose address is equal to the written data through the write port of the SRAM, and the written content is the original value of the address. The bit vector corresponding to the stored word and the write is 1, and the other bits are 0, which is the calculation result of the bitwise OR operation.

The beneficial effect of the method embodiment of the present invention is: the implementation based on SRAM has smaller circuit area than the method based on Register. The one-to-one comparison method of full traversal is replaced by the method of searching content addressing, without additional comparison logic. Only one clock cycle is needed to output the matching result and the matching data address, which greatly improves the search efficiency, reduces the transaction processing delay, and improves the system throughput.

Corresponding to the above method, the present invention also provides a system for searching content addressable memory CAM, including:

obtaining means for obtaining the search word;

The division device is connected with the acquisition device, and is used to divide the search word into N sub-search words, wherein each sub-search word corresponds to a static random access memory (SRAM) whose address width is equal to the width of the sub-search word in the content addressable memory CAM;

The reading device is connected with the dividing device, and is used to use the sub-search word as the read address to perform a read operation in the corresponding SRAM in parallel, so as to obtain the information of each storage address on the SRAM corresponding to each sub-search word to the sub-search word matching result;

The processing device is used to combine the obtained matching results to obtain the matching result of the search word in the CAM.

Wherein, the reading device obtains the matching result of each storage address on the SRAM corresponding to each sub-search word to the sub-search word in the following manner, including:

Each storage address of the SRAM corresponds to a bit vector whose length is equal to the search depth of the CAM, where each bit of the bit vector represents a valid CAM entry in turn. If a bit value of the bit vector is equal to 1, it means that the same position in the CAM If there is the same data as the sub-search word, the search is completed, and the match is successful; if all bits of the bit vector are equal to 0, it means that there is no data identical to the sub-search word in the CAM, the search is completed, and the match fails.

Preferably, the processing device is configured to perform a bitwise AND operation on the obtained N bit vectors to obtain a matching result of the search word in the CAM.

Optionally, the system also includes:

The operation device is connected with the processing device, and the obtained matching result is reduced or operated to obtain the search matching result of the CAM. If the result is 1, it means that the matching is successful; if the result is 0, it means that the matching fails.

Optionally, the system also includes:

The priority decoding device is connected with the processing device, and is used for performing a priority decoding operation on the obtained matching result to obtain a matching item, and the matching item is used as the address of the search word in the CAM.

The following is an application example to illustrate:

FIG. 6 is a schematic structural diagram of a system for searching a CAM in the present invention. In the system shown in FIG. 6, the system includes three units, that is, a search word interval division unit, an SRAM memory unit and a logic control unit. The search word unit is responsible for receiving the CAM search enable (SearchEn) and the CAM search content, and divides the CAM search content, namely the search word (SearchWord), into N subsections. Each sub-interval corresponds to a sub-search word (SubWord), which drives the read operation address of the SRAM memory unit. Search word division unit to output the read enable signal of each chip SRAM simultaneously, SRAM memory unit receives read enable signal and starts read operation effectively, reads out the bit vector (BitVecN) on the corresponding address, and outputs on the port. After receiving the N bit vectors sent by the memory control unit, the logic control unit merges them, reduces them and first decodes them, calculates the final search matching result (IsMatched) and matching address (MatchedAddr), and outputs them on the port.

The beneficial effect of the system embodiment of the present invention is: the implementation based on SRAM has smaller circuit area than the method based on Register. The one-to-one comparison method of full traversal is replaced by the method of searching content addressing, without additional comparison logic. Only one clock cycle is needed to output the matching result and the matching data address, which greatly improves the search efficiency, reduces the transaction processing delay, and improves the system throughput.

The above is only a specific embodiment of the present invention, but the scope of protection of the present invention is not limited thereto. Anyone skilled in the art can easily think of changes or substitutions within the technical scope disclosed in the present invention. Should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be based on the protection scope described in the claims.

Claims (10)

1. the method for a search content addressable memory CAM is characterized in that, comprising:

Obtain and search word;

To search stroke and be divided into N son and search word, wherein each son searches that an address width equals the SRAM SRAM that this son is searched word width among the word corresponding content addressable memory CAM;

Concurrently with son search word as read the address correspondence in SRAM, carry out read operation, obtain each son and search the pairing SRAM of word and go up each memory address is searched word to this son matching result;

Matching result to obtaining merges processing, obtains this and searches the matching result of word in CAM.

2. method according to claim 1 is characterized in that, said each son is searched the pairing SRAM of word and gone up each memory address and this son is searched the matching result of word and obtained through following mode, comprising:

An all corresponding length is equal to the bit vector of CAM search depth on each memory address of SRAM; Wherein each of bit vector representes that successively a CAM effectively enters the mouth; If a certain place value of bit vector equals 1; Exist with son on the equivalent locations among the expression CAM and search the identical data of word, search is accomplished, and matees successfully; If all positions of bit vector all equal 0, explain not exist among the CAM and search the identical data of word that search is accomplished, the coupling failure with son.

3. method according to claim 2 is characterized in that, the matching result that obtains is merged processing, obtains this and searches the matching result of word in CAM and comprise:

To N the bit vector that obtains carry out by turn with operation, obtain this and search the matching result of word in CAM.

4. method according to claim 2 is characterized in that, also comprises after this searches the matching result of word in CAM obtaining:

The matching result that obtains is reduced computing or operation, obtain the search matched result of CAM, if the result is 1, expression is mated successfully; If the result is 0, the failure of expression coupling.

5. method according to claim 2 is characterized in that, also comprises after this searches the matching result of word in CAM obtaining:

Matching result to obtaining carries out preferential decoded operation, obtains an occurrence, and this occurrence is searched the address of word in CAM as this.

6. the system of a search content addressable memory CAM is characterized in that, comprising:

Deriving means is used to obtain and searches word;

Classification apparatus links to each other with said deriving means, is used for being divided into N son and searching word searching stroke, and wherein each son searches that an address width equals the SRAM SRAM that this son is searched word width among the word corresponding content addressable memory CAM;

Read apparatus links to each other with said classification apparatus, be used for concurrently with son search word as read the address correspondence carry out read operation at SRAM, obtain each son and search the pairing SRAM of word and go up each memory address is searched word to this son matching result;

Treating apparatus is used for the matching result that obtains is merged processing, obtains this and searches the matching result of word in CAM.

7. system according to claim 6 is characterized in that, said read apparatus obtains each son through following mode and searches the pairing SRAM of word and go up each memory address this son is searched the matching result of word, comprising:

An all corresponding length is equal to the bit vector of CAM search depth on each memory address of SRAM; Wherein each of bit vector representes that successively a CAM effectively enters the mouth; If a certain place value of bit vector equals 1; Exist with son on the equivalent locations among the expression CAM and search the identical data of word, search is accomplished, and matees successfully; If all positions of bit vector all equal 0, explain not exist among the CAM and search the identical data of word that search is accomplished, the coupling failure with son.

8. system according to claim 7 is characterized in that:

Said treating apparatus, be used for to N the bit vector that obtains carry out by turn with operation, obtain this and search the matching result of word in CAM.

9. system according to claim 7 is characterized in that, said system also comprises:

With operating means, link to each other with said treating apparatus, the matching result that obtains is reduced computing or operation, obtain the search matched result of CAM, if the result is 1, expression is mated successfully; If the result is 0, the failure of expression coupling.

10. system according to claim 7 is characterized in that, said system also comprises:

Preferential code translator links to each other with said treating apparatus, is used for the matching result that obtains is carried out preferential decoded operation, obtains an occurrence, and this occurrence is searched the address of word in CAM as this.

Images