Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-08-10
2002-04-23
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S137000, C711S122000, C711S134000, C711S159000
Reexamination Certificate
active
06378042
ABSTRACT:
BACKGROUND
A. Technical Field
The present invention relates generally to associative memories, and in particular to cache organizations for associative memories.
B. Background of the Invention
An associative memory semiconductor device is a device such as a content addressable memory (CAM. CAM is a well-known device that permits the contents of the memory to be searched and matched instead of having to specify a memory location address in order to retrieve data from the memory. Associative memory can be used to accelerate any application requiring fast searching of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. Associative memory provides a performance advantage over conventional memory devices with conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired information against the entire list of entries simultaneously, giving an order-of-magnitude reduction in search time associative memory devices are often used to store a routing table for high speed switching systems. These systems need to rapidly search the routing table to look for a matching destination address so that a data packet may be routed to the appropriate destination address.
Future generations of communications switches require multi-level switching (routing) policy tables with hundreds of thousands of entries and speeds achievable only with associative memory. However, such routing policy tables may need only a few thousand data base entries at any given time instead of more than half a million of data base entries. Next generation products will probably require associative memory in the 4 to 128 Mbit range. Associative memories this size, however, require hundreds of millions of transistors, far too many to incorporate in a single chip in the next several generations of semiconductor processes. Therefore, caching associative memories will be required for future generations of communications Integrated Circuits.
Conventional cache memory systems are well known in the art. A typical cache memory subsystem consists of Tag Random Access Memory and Data RAM. Both TagRAM and DataRAM are in the form of a high-speed static random access memory (SRAM), which provides faster access time than the dynamic random access memory (DRAM). Conventional well-known random access memory device CAM) is an integrated circuit that temporarily stores data in an array of memory cells. In the RAM device, each stored piece of data may be accessed independently of any other piece of data. The data in a RAM is stored at a particular location called an address. Accordingly, indicating the address at which the data is located may access any piece of data in the RAM.
Conventional algorithms are known for determining which data needs to be replaced in a conventional RAM cache system. Two of the most widely used algorithms are Least Recently Used (LRU), or Least Frequently Used (LFU). In the RAM caching system only one match can be found in a given time. Since only one entry can be replaced at a time, these algorithms can be easily implemented in the RAM caching system. A search on an associative memory, however, may result in several matches in response to the search input. Consequently, the existing algorithms need to be substantially modified in order to deal with multiple matches.
Accordingly, it is desirable to provide a caching associative memory device that in combination with a conventional external associative memory or algorithmic search engine is capable of searching a big volume of data, thereby overcoming the problems of conventional associative memory devices. Furthermore, it is desirable to provide a system that is capable of determining which entries need to be replaced in such a caching associative memory device when no matching data is found.
SUMMARY OF THE INVENTION
The present invention is a system and a method for operating an associative memory cache device in a computer system. The system comprises a search client configured to search for data in an associative memory cache, an associative memory cache element coupled to the search client for generating a matching signal, and a main associative memory element coupled to the associative memory cache element configured to search for data not found in the associative memory cache element.
In one aspect, the present invention is a multi-level system for operating an associative memory cache device, comprising a search client configured to search for data in an associative memory, a multi-level associative memory cache coupled to the search client in a multilevel hierarchy for searching for data, and an associative memory element coupled to the multi-level associative memory cache for generating a matching signal.
In another aspect, the present invention is a method for operating an associative memory cache device. The method comprises receiving a search request for data, returning a matching signal and overlapping higher priority signals responsive to finding the data in the associative memory cache.
In yet another aspect, the present invention is a method for operating an associative memory cache device. The method comprises receiving a search request for data to the associative memory cache element, issuing the search request for the data to the associative memory element responsive to not finding the data in the associative memory cache element, determining which data needs to be replaced in the associative memory cache element, and replacing the data in the associative memory cache element with new data.
In another aspect, the present invention is a method for operating a multilevel associative memory cache device. The method comprises searching a first level associative memory element; providing a search result if matching data is found in the level
1
associative memory cache element; searching a second level associative memory or other associative memory cache element if a match was not found; providing a search result if matching data is found in the level
2
associative memory cache element; searching a higher level associative memory cache elements and a top level associative memory until a match is found; providing a search result from the higher level associative memory cache elements and the top level associative memory; and replacing entries in the multiple cache levels based on either a LRU of LFU algorithm.
These and other features and advantages of the present invention may be better understood by considering the following detailed description of preferred embodiments of the invention. In the course of this description, reference will be frequently made to the attached drawings.
REFERENCES:
patent: 3911401 (1975-10-01), Lee
patent: 4980823 (1990-12-01), Liu
patent: 5265232 (1993-11-01), Gannon et al.
patent: 5701426 (1997-12-01), Ryan
patent: 5761706 (1998-06-01), Kessler et al.
patent: 5822757 (1998-10-01), Chi
patent: 5970509 (1999-10-01), Green
patent: 5996071 (1999-11-01), White et al.
patent: 6065091 (2000-05-01), Green
patent: 6161144 (2000-12-01), Michels et al.
patent: 6195735 (2001-02-01), Krueger et al.
patent: 6292871 (2001-09-01), Fuente
patent: WO 99/26139 (1999-05-01), None
“Cache Data Update to MRU”, IBM Technical Disclosure Bulletin, vol. 29, No. 10. Mar. 1987, p. 4282.
“The Nth Chance Algorithm for Virtual Memory”, IBM Technical Disclosure Bulletin, vol. 29, No. 9, Feb. 1987, pp. 4187-4188.
Croft Walter E.
Henderson Alex E.
Fast-Chip, Inc.
Fenwick & West LLP
Peugh B. R.
LandOfFree
Caching associative memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Caching associative memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Caching associative memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2842151