Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2002-05-31
2004-08-03
Nelms, David (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S185250, C365S189011, C365S189070
Reexamination Certificate
active
06771525
ABSTRACT:
The present invention relates To a Content Addressable Memory (CAM), and more specifically to a method and circuit for searching a CAM with variable width search data, wherein the width of the search data may be changed on each search instruction.
BACKGROUND OF THE INVENTION
A CAM is a memory device, which allows a processor within a computer, to perform a parallel search through the CAM's stored data in order to retrieve the address of any matching stored data if such data is found. The search and stored data can be either binary (comprising logic “1” or “0” state) or ternary (logic “1”, “0” or “don't care” states) data.
A CAM is usually subdivided in banks of CAM cell arrays. A CAM array comprises a plurality of CAM cells arranged in rows and columns with row of the cell being connected to an associated match line and cells being connected to associated search lines. The cells are also coupled to wordlines and bitlines for retrieving information out of and for storing information in the CAM.
During a search operation, search data often referred to as a search key of a particular width is placed on the search lines. The search key on the search data lines is compared with stored data in all CAM cell locations simultaneously and a match (also referred to as a “hit”) or mismatch result (also referred to as a “miss”) is provided to match lines coupled to each CAM cell. If the search key matches the information stored in a particular row in the CAM, the associated match line will indicate a hit or match condition. If the search key and the stored data are different, the associated match line will indicate a miss or mismatch condition. All match line outputs are processed by a multiple match resolver (MMR) and priority encoder (PE) block that will provide as an output signal the highest priority match address where the match information is located.
Conventional CAM's are mode configurable to perform search operations on data words having specific word widths for example, 144 bit or 288 bit search modes. Typically in such CAM's, a configuration register stores the operating mode of the device and fields within the register specify the word width. Data will be written into the CAM according to the word width setting in the mode register and search instructions issued to the CAM will therefore search the stored data based on the word width specified in the configuration register. In order to charge the word width the mode register must first be updated and then the new search is performed. Thus, variable word width searching “on-the-fly” is not supportable by such conventional CAM's. Thus, although pre-set word-width CAM's 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.
Some conventional approaches have been proposed for searching words which are wider than default word widths stored in a CAM, for example in U.S. Pat. No. 6,252,789 to Pereira et al. Such approaches however require extra width expansion circuitry associated with each CAM row for handling situations when search data words that are wider than the default stored word width. Furthermore, such width expansion circuitry are interconnected and a match result is not provided to a priority encoder until the last word in a multiword data chain has been compared to the contents of the data stored in the CAM. This approach therefore is only effective in exact match multiple word searches.
Thus, there is still a need for a CAM that is capable of performing variable word width searching with search data widths that can be changed on-the-fly, and while storage of data words makes efficient use of the CAM.
SUMMARY OF THE INVENTION
In accordance with this invention there is provided a content addressable memory (CAM) for performing search operations using variable width search data, the CAM comprising:
a) a plurality of arrays of CAM cells, each coupled to a respective sub-search data bus, the sub-search buses being confined to form a main search data bus, to which is applied the search data;
b) selector circuits receiving match line signals from respective CAM arrays, the match line signals being indicative of the results of a search and comparison formed in the associated CAM array, the selector circuit being responsive to a mode selection signal for selecting one or more of the match line output signals to be switched to a priority encoder and multiple match resolver (PE-MMR) wherein a first mode or all match line output signals are switched to the PE-MMR and in a second mode groups of match line output signals from selected arrays are switched to the PE-MMR, whereby wide width data searching is performed by simultaneously evaluating match line outputs from the plurality of arrays.
An advantage of the invention is the ability to perform variable word width searches (72, 144 and 288 bit wide words for example) with the ability to change the searchable word width mode on-the-fly; i.e. on each new search instruction issued to the CAM device.
In accordance with another aspect of the invention, there is provided a method for performing variable word width searching in a content addressable memory comprises selectively combining match line latch outputs from two adjacent CAM memory arrays and providing the selectively combined match line outputs to a multiple match resolver/priority encoder in response to a variable word width control signal. If a 72 bit mode search is performed, the priority encoder will simultaneously receive and process four separate match line latch outputs match line locations in adjacent arrays. If a 144 bit mode search is performed, then a combination of two match line latch outputs are provided from two adjacent arrays to the priority encoder. If a 288 bit mode search is performed, a combination of four match line latch outputs is provided to the priority encoder.
REFERENCES:
patent: 6081441 (2000-06-01), Ikeda
patent: 6252789 (2001-06-01), Pereira et al.
patent: 6373738 (2002-04-01), Towler et al.
patent: 6535410 (2003-03-01), Yanagawa
MOSAID Technologies Incorporated
Nelms David
Pillay Kevin
Tran Long
LandOfFree
Method and apparatus for performing variable word width... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing variable word width..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing variable word width... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3352214