Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-11-30
2004-03-16
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06708250
ABSTRACT:
The present invention relates generally to the field of content addressable memories (CAMs) and more particularly to a circuit and method for searching a CAM with search data having variable word widths.
BACKGROUND OF THE INVENTION
A content addressable memory (CAM) is a memory device in which data is accessed and modified based on the content of the stored data, rather than the location where the data is stored. In general, a typical CAM search operation involves receiving a search data word and comparing the search data word with all entries in the CAM to determine whether there exists a single match, a multiple match or a mismatch between the search data word and entries in the CAM. Each storage location in a row of a CAM is connected to a matchline that indicates a match or mismatch result of the comparison between the stored data word and the search word. All match lines indicating a match condition are typically processed by a priority encoder to determine a highest priority match address which is provided as an output of the CAM.
Each data word and match line combination has a unique N-bit address within the CAM. Accordingly, for any search cycle there may be up to 2
N
match lines activated. As mentioned, the CAM typically includes a priority encoder for generating the N-bit address corresponding to the highest priority active match line. This N-bit address may be used for network applications such as Internet Protocol (IP) routing table lookup, compression and decompression as well as fully associative cache memory implementations in microprocessor systems.
Ternary CAMs are widely used in networking applications due to their ability to store logic “1”, logic “0” as well as “don't care” states. CAMs are commonly available in data widths that are 72-bits and 144-bits and more recently 288-bits wide. Typically in networking applications, the 72-bit storage mode is used to store medium access controller (MAC) addresses for Layer 2 bridging tables, while Layer 3 Internet Protocol (IP) routing tables are stored using the 144-bit mode. Each IP routing table entry consists of a source address, source port, destination addresses, destination port and some kind of QOS (Quality of Service) or TOS (Type of Service) field. In CAMs supporting both data widths, both types of tables can be maintained thereby reducing system cost allowing a common CAM resource to be used for the two functions.
When search data widths are known beforehand such variable width CAMs are useful, however in applications such as URL (Uniform Resource Locator) lookup, search data widths are typically very long and are of undetermined length. The current variable data width CAMs are still limited to discrete predetermined widths and thus the use of CAMs for this purpose has gained little support.
As mentioned above, it would be useful to store URLs in a CAM to accelerate network traffic associated with frequently accessed world wide web pages and deal effectively with web page caching. If a very-wide CAM (hundreds to thousands of bits wide) is implemented that could handle most URL lengths, there would be a large amount of wasted storage space when storing typical or short URLs. In such a circumstance, utilizing the same CAM for bridging or routing entries would become wasteful.
Thus, although variable pre-set word-width CAMs do exist, there is still a need for a CAM that supports arbitrary word width searches and which is capable of switching between one or more types of searching “on-the-fly”. Furthermore, different word-width entries should be stored in CAM words having arbitrary boundaries so that the entire CAM can be utilized without unused or wasted gaps between entries.
One example of a system for searching words which are wider than default word widths stored in a CAM is presented in U.S. Pat. No. 6,252,789 to Pereira et al. Pereira describes circuitry that allows a data word chain wider than the width of a CAM row to be stored and searched in one or more rows of the CAM. As a result, wider word searches can be performed with a CAM organized physically into multiple smaller words.
In Pereira, a sequence of one or more data words is stored in one or more rows of CAM cells. Each row has an associated match line and width expansion logic circuit. The width expansion circuits are interconnected and each have a carry input, a canny output and a match line output for determining how to provide match results to the priority encoder and to each other. Control signals generated by an instruction decoder are provided to each width expansion logic circuit for determining when to provide a first, subsequent and last word in the data word chain for comparison with data stored in the CAM. If a search data word having a default word width is provided, the match output signal in each width expansion logic circuit is provided to the priority encoder and the carry output signal is held in an inactive state. If the search data word provided to the CAM is the first word of a multiword chain however, each match line output signal is set to indicate a mismatch, i.e. it is suppressed, and each carry output signal is propagated to the next width expansion circuit. If the search data word provided to the CAM is subsequent word of a multiword chain, each match line output signal indicates a mismatch and each carry output signal is generated by the logical combination of the carry input signal and the intermediate match line result and is similarly propagated to the next width expansion circuit. If the search data word provided to the CAM is the last word of a multiword chain, each match line output signal indicates a match if the logical combination of the carry input signal and the intermediate match line result are both activated. As a result, a match result is not provided to the priority encoder until the last word in a multiword data chain has been compared to the contents of the CAM. This approachtherefore is only effective in exact match multiple word searches. As a result, a disadvantage of this approach is that intermediatesearch results are unavailable. For example in case a closest match occurred before the last word of tee multiword search data was provided, that closest match result would effectively be masked.
Thus, there is still a need for a CAM that is capable of searching variable width data words and wherein storage of data words makes efficient use of the CAM.
SUMMARY OF THE INVENTION
A content addressable memory (CAM) for generating intermediate search results in a search on a stored data word sequence, the CAM comprises a plurality of rows of CAM cells each for storing a data word in the data word sequence; a plurality of match lines each coupled to a corresponding row of CAM cells, each for generating a corresponding match line signal; a priority encoder coupled to the match line for generating a match address in response to a match line signal; and a plurality of logic circuits, each coupled to corresponding match lines for selectively coupling The match line signal to the priority encoder in response to an instruction signal, the instruction signal for instructing the CAM to generate a match address output on a new search or on a continuation of a previous search, such that portions of the data word sequence occurring at any intermediate location within the sequence provides match results in response to input search data which are equivalent to portions of the stored data word sequence.
REFERENCES:
patent: 3984821 (1976-10-01), Locke
patent: 4254476 (1981-03-01), Burrows
patent: 4296475 (1981-10-01), Nederlof et al.
patent: 4366551 (1982-12-01), Holtz
patent: 4831586 (1989-05-01), Nakagawa et al.
patent: 6252789 (2001-06-01), Pereira et al.
patent: 6253280 (2001-06-01), Voelkel
patent: 2317387 (2001-03-01), None
Chace Christian P.
Mosaid Technologies Incorporated
Pillay Kevin
Renault Ogilvy
Sparks Donald
LandOfFree
Circuit and method for performing variable width searches in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit and method for performing variable width searches in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit and method for performing variable width searches in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3266619