Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2002-12-30
2004-10-26
Nguyen, Van Thu (Department: 2824)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S189020, C365S194000
Reexamination Certificate
active
06809944
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to Content Addressable Memories (CAMs) and a method and apparatus for automatically providing a Next Free Address (NFA) for a write operation.
BACKGROUND OF THE INVENTION
In the following detailed description, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those of ordinary skill in the art to make and use the invention, and it is to be understood that structural, logical or procedural changes may be made to the specific embodiments disclosed without departing from the spirit and scope of the present invention.
A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data input to the device or in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory search on a RAM, the user supplies the address and gets back the data stored in that address (location).
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address, or the data can be written into a first empty memory location (also known as the NFA or Next Free Address). Once information is stored in a memory location, it is found doing a memory search by comparing every bit in any memory location with every bit of data in a comparand register circuit. When the content stored in the CAM memory location does not match the data placed in the comparand register, the local match detect circuit associated with the CAM memory location returns a no-match indication. When the content stored in the CAM memory location matches the data placed in the comparand register, the local match detect circuit associated with the CAM memory location returns a match indication. If one or more of the local match detect circuits return a match indication then the CAM device outputs a match indication. If no local match detect circuits return a match indication then the CAM device outputs a no-match indication. In addition, if a match is found then the CAM returns the identification of the address location in which the matching data is stored (or one of the address locations in which matching data was stored if more than one memory location contained matching data). Thus, with a CAM, the user supplies the data and gets back an indication of an address where a matching data is stored in the memory.
Data written into CAMs is often written to the first memory location that does not already contain valid data. This memory location is referred to as the Next Free Address (NFA), as mentioned previously. Since determining the NFA can be time-consuming, a CAM device which expedites the determination of an NFA is desired.
BRIEF SUMMARY OF THE INVENTION
In one aspect, the invention provides a content addressable memory, comprising a plurality of memory storage locations where each location has an associated indicator for indicating that the memory storage location is available for data storage, and an associated match line for indicating if a search word matches a word stored in the memory storage location. The invention also provides a first selector circuit for selecting one of the indicator and match line associated with each of the plurality of memory storage locations and applying it to a priority encoder; a next free address register coupled to the output of the priority encoder; and a match results register also coupled to the output of the priority encoder; where either the next free address register or the match results register is enabled to receive an address corresponding to the output of the priority encoder depending on the first selector circuit.
The invention also provides a priority encoder having a plurality of inputs and operable in a first mode where the first selection circuit respectively couples the match lines to the plurality of inputs to indicate a highest priority match on the match lines and in a second mode where the first selection circuit respectively couples the indicators to the plurality of inputs to indicate a highest priority storage location or NFA available for data storage.
REFERENCES:
patent: 6108747 (2000-08-01), Kaganoi
patent: 6693814 (2004-02-01), McKenzie et al.
patent: 6697275 (2004-02-01), Sywyk et al.
patent: 6718433 (2004-04-01), Pereira
Regev Alon
Regev Zvi
Dickstein , Shapiro, Morin & Oshinsky, LLP
Micro)n Technology, Inc.
Nguyen Hien
Nguyen Van Thu
LandOfFree
CAM with automatic next free address pointer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with CAM with automatic next free address pointer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CAM with automatic next free address pointer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3272724