Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-05-01
2004-02-17
Verbrugge, Kevin (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S134000, C711S128000
Reexamination Certificate
active
06694408
ABSTRACT:
BACKGROUND INFORMATION
1. Field of the Invention
The invention relates to cache memories, and particularly to a replacement algorithm in a cache memory architecture.
2. Description of Related Art
In a cache memory design, one of the challenges is to maintain data integrity in a cache with an intelligent, efficient, and cost-effective replacement algorithm. Functions of a cache memory are typically divided into an instruction cache section for storing instructions and/or a data cache section for storing data close to an execution unit. A cache request to a cache memory causes a TagHit or a TagMiss condition. A TagHit, where a TagHit signal is asserted, indicates that the requested data exist in the cache. A TagMiss, where a TagHit signal is deasserted, indicates that the requested data is not present in cache, at which time a processor may make a request to a system or secondary memory to locate the requested data.
An associativity with a TagHit or TagMiss condition needs to be known for future use. If there is a TagMiss condition, one associativity is selected for replacement. The replacement selection is made by a replacement algorithm, which is a subset of the external control logic. The external control logic supports the functionalities for detecting associativity with TagHit, enabling only one associativity at a time, selecting an associativity to be replaced, and enabling all associativities at the same time to find the associativity with a TagHit condition.
One conventional solution designs associativity selection or replacement algorithm for cache for a specific number of associativities. When the number of associativities increases or decreases, the replacement algorithm is modified to support a new configuration. Another conventional approach adds the required logic for an n-set associativity but uses only a portion of logic for a subset of associativities. Such implementation is inefficient.
Associativity selection for cache accesses requires one signal per associativity to detect if the current access is a Tag Hit. This signal is asserted if the requested data currently exist in cache. A Valid signal is used to flag if the cache line is valid or not valid. A Lock signal is used to flag if the cache line is locked or not lock. If the replacement algorithm implemented is Not the Most Recently Used (NMRU), the Most Recently Used (MRU) signal is needed.
In a conventional replacement selection block, a replacement algorithm, miss queue and control logic are implemented external to a cache memory array. The conventional replacement algorithm block selects one associativity if there is not any TagHit signal asserted. The miss queue block maintains or stores the associativity selected by the conventional replacement algorithm to be used when the data is send by a system memory. The control logic is used to enable or start read and write operations to the cache memory based on information from the replacement algorithm and the instruction pipe unit or fetch unit. A shortcoming of this conventional replacement selection circuit is the high number of handshake signals that are required between a cache memory.
Another shortcoming in conventional associativity selection for cache requires one signal per associativity for detecting if a current access is a TagHit. If the access results in a TagHit, then that signifies that data currently exists in cache However, if the access is a Miss condition or the associativity needs to be refilled, then one signal per associativity is required to select the specific associativity to be accessed. Thus, in traditional implementations, two routing paths per associativity are used to detect TagHit conditions and for replacement/refill selection. The complexity of signal routing increases as the number of associativities increases.
Accordingly, it is desirable to have a scalable replacement algorithm for associativity selection in a cache memory to increase the cache access time while reducing signal routing complexity.
SUMMARY OF THE INVENTION
The invention provides a system and method for executing a replacement selection algorithm embedded in each associativity of a cache memory architecture. Each associativity in a cache has an internal control logic that governs the process for replacing a cache line when a certain condition occurs, such as a presence or absence of a TagHit. A designated set of control signals is used in associativity control logic for corresponding to external control logic. An associativity control logic within associativity provides an internal capability to determine whether a TagHit condition occurs as well as volunteering the associativity for replacement. The preferred replacement algorithm is implemented using an approximation to Not the Most Recently Used Associativity (NMRU).
Advantageously, the number of signals for communicating between a cache and an external control logic are the same. If the number of associativities increases in a cache, the control logic within associativity or the external control logic does not need to be modified to accommodate for the changes in the number of associativities. Therefore, the replacement selection provides a flexible modular approach while avoiding changes in associativity control logic or in an external control logic. Additionally, the fixed number of signals in an associativity control logic reduces the routing complexity between an associativity and an external control logic in manufacturing of an integrated circuit chip.
REFERENCES:
patent: 6490654 (2002-12-01), Wickeraad et al.
patent: 6516384 (2003-02-01), Clark et al.
patent: 2002/0010839 (2002-01-01), Tirumala et al.
Gupta Mayank
Pak Edward T.
Villagomez Javier
IP Strategy Group, P.C.
Verbrugge Kevin
LandOfFree
Scalable replacement method and system in a cache 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 Scalable replacement method and system in a cache memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable replacement method and system in a cache memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3348746