Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-01-09
2004-06-29
Moazzami, Nasser (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06757780
ABSTRACT:
FIELD AND BACKGROUND OF THE INVENTION
The present invention relates to the field of Content Addressable Memory (CAM) and, more particularly, to a system for, and method of, implementing a RAM-Based Binary CAM and a RAM-Based Range Content Addressable Memory (RCAM).
Conventional memory arrays such as Random Access Memories (RAMs) store and retrieve data units indexed by their address.
Content Addressable Memories (CAMs) are associative memories that contain Key Entries and Associated Data Entries that uniquely correspond to the Key Entries. A CAM stores the key entries and the associated data entries at any available location and retrieves the Associated Data for any key that is submitted to be searched in the CAM.
A Binary CAM stores an ordered list of single integer key entries and a corresponding list of their associated data. An RCAM stores instead a list of key entries that represent range boundaries and a list of associated data that correspond uniquely to these ranges. A key search in a Binary CAM results in an exact match, whereas a key search in an RCAM matches an entire range. The RCAM also stores a list of associated boundary type entries that determine the validity of the corresponding ranges. This list can be stored in conjunction with the list of associated data or in a separate array.
A successful approach to utilizing RAM-based technology on a binary CAM is provided in my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00458, which is incorporated by reference for all purposes as if fully set forth herein. A method and apparatus are disclosed therein for the high-rate arrangement, storage and extraction of data in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns, each of the key entries in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond to these key entries are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array and a match signal, “True” or “False”, is also output with the retrieved associated data entry to indicate whether the associated data is valid or not. The key entries in the two-dimensional array are arranged, each entry in a separate cell, in rows or columns, in a subsequent ascending or descending order. The entries are arranged in the array so that at least a portion of the array is filled without blanks with valid entries. The arrays of the key entries and their associated data are kept in perfect sequence by Insert and Remove algorithms.
The main innovations introduced by this technology include:
Surrounding the RAM structure with search logic in the RAM periphery: The number of comparator units is proportional to the RAM periphery length rather than to the RAM area. This results in dramatic savings in the amount of comparator logic, while keeping the memory cell extremely efficient in density and speed. The CAM implementation overhead is typically less than 15%. Therefore, the CAM density obtained with this method is asymptotically close to the comparable size in RAM technology.
Fast Search Algorithm: The surrounding logic in conjunction with the RAM structure performs searches with the same throughput as a comparable RAM, and twice the latency. (Theoretically, single clock latency may be accomplished, but pipelining may yield a better throughput and a similar latency if measured on absolute time scale (nano-seconds).
Continuous “Housekeeping” Procedure: Unlike CAMs of the prior art, these CAM devices keep the “house in order”. That is, the deletion of keys does not leave “holes” in the list, which would otherwise require “housekeeping” operations on the managing processor section. Similarly, the addition of new keys keeps the list in a perfect sequence. This “housekeeping” procedure takes longer than the search, but is much faster than required by the system. The overhead associated with the Key List update is significantly shorter when compared with the time taken by the processor to do the housekeeping. This superior performance is due to the efficient RAM and Insert/Remove hardware architecture, which execute very time-efficient algorithms.
In my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00595, which is incorporated by reference for all purposes as if fully set forth herein, a method and apparatus are disclosed for arranging and storing a set of key entries and a corresponding set of associated data entries in storage areas within a memory device. Each location in the first storage area is assigned a unique index and is associated with the corresponding location to second storage area with the same index. Each key entry represents a range of consecutive values and is denoted herein as Range Key Entry. The range may be represented by its lower or upper boundary.
When a key is submitted for search and is found to belong to a range represented by a range key entry, the associated data entry with the same index is extracted from the memory as valid data and a Match signal is issued. If no range is found to contain the submitted key, no valid associated data is retrieved and a No-Match signal is issued.
A successful approach to utilizing RAM-based technology on an RCAM in a similar way that on a binary CAM is provided in my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/01025, which is incorporated by reference for all purposes as if fully set forth herein. A method and apparatus are disclosed therein for the high-rate arrangement, storage of ranges of integers and extraction of data associated with these ranges in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns, each of the key entries (representing range boundaries) in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond uniquely to these ranges are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found within an integer range, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array.
The RCAM includes a third two-dimensional array, consisting of associated boundary type entries that also correspond uniquely to these ranges and are stored under the same pair of indices; these entries determine the validity of the corresponding ranges. A match signal, “True” or “False”, is output accordingly with the retrieved associated data entry to indicate whether the matched range and the associated data are valid or not. The array of associated boundary type entries can be stored in conjunction with that of associated data entries or separately.
The key entries in the two-dimensional array are arranged, each entry in a separate cell, in rows or columns, in a subsequent ascending or descending order. The entries are arranged in the array so that at least a portion of the array is filled without blanks with valid entries.
In many cases, the relatively slow speed of the Insert and Remove operations hampers the performance of the system. It would, therefore, be highly advantageous to have a system for, and a method of significantly improving the speed of the Insert and Remove algorithms, while maintaining the arrays of the key entries and their associated data in perfect sequence.
SUMMARY OF THE INVENTION
The present invention relates to a device for binary CAMs and for RCAMs having multiple module content addressable memories, and a method of utilizing the device.
According t
Friedman Mark M.
Hywire Ltd.
Moazzami Nasser
LandOfFree
Multiple module content addressable memories does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple module content addressable memories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple module content addressable memories will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3339844