Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-09-22
2002-04-23
Kim, Matthew M. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000, C711S159000
Reexamination Certificate
active
06378044
ABSTRACT:
TECHNICAL FIELD
The present claimed invention relates to the field of cache architecture. More specifically, the present claimed invention relates to replacement of cache contents in a set associative cache environment.
BACKGROUND ART
Modern computer systems typically have a main memory (e.g., random access memory, or RAM) for storing data (e.g., program instructions and operands) therein to facilitate program execution. In addition, cache memory is usually also included in modern computer systems. Cache memory is high speed memory for storing data which is frequently accessed, and data can be stored therein and retrieved therefrom very efficiently. Main memory is thus configured to store frequently used data into cache memory in order to optimize the performance of computer systems. However, main memory is generally much larger than cache memory in a computer system. Therefore, the computer system needs to have a mechanism for determining what data within cache memory is to be replaced when new, uncached data is read from main memory for caching and there is no more space available in cache memory.
Generally, within a set associative cache environment, the cache memory is divided into multiple sets (e.g., 4 sets, or four-way), where each set acts as an independent cache for the entire address space of main memory. Data in a given location in main memory (e.g., a particular 4-byte word in main memory) can be stored in one, and only one, corresponding location in each one of the cache sets. Since main memory is larger than any of the individual cache sets, several locations in main memory would map to a particular location in each of the cache sets. Thus, when that specific location in each cache set is already occupied by valid data, and new, uncached data from a location in main memory which also maps to the same specific location needs to be cached, a decision must be made as to which cache set's old yet valid data is to be cast out and replaced by the new, uncached data just read from main memory.
Some prior art approaches to cache replacement are geared towards cache environments which include multiple cache sets. However, these prior art cache replacement approaches do not take into consideration the fact that the individual cache sets in a set associative cache environment can be configured to cache instructions (code), operands (data), or both. Thus, such prior art approaches cannot be applied to select which among the multiple cache sets is to be used for storing the newly read uncached data based on the type of data read. In other words, such prior art approaches fail to provide a cache replacement mechanism which accounts for the existence of code-only, data-only, and code-data cache sets in any given configuration within a set associative cache environment. Thus, a method and system for cache replacement in a set associative cache environment having configurable cache sets is needed.
Additionally, a method and system for cache replacement suitable for use in a set associative cache environment must not require complete revamping of existing computer systems. That is, in implementing a viable method and system for cache replacement in a set associative cache environment, components that are well known in the art and are compatible with existing computer systems need to be used so that the cost of realizing the method and system for cache replacement is low. In so doing, the need to incur costly expenditures for retrofitting existing computer systems or for building custom components is eliminated.
Thus, a need exists for a method and system for cache replacement. A further need exists for a method and system which meets the above listed need wherein the method and system operates in a set associative cache environment having configurable cache sets. Still another need exists for a method and system which meets both of the above cited needs and wherein the method and system is conducive to use with existing computer systems.
DISCLOSURE OF THE INVENTION
The present invention provides a method and system for cache replacement, and which operates in a set associative cache environment having configurable cache sets. The present invention accomplishes the above achievements with a method and system which performs cache replacement in a pseudo-random manner and which is conducive to use with existing computer systems.
Specifically, in one embodiment, the present invention identifies a cache location corresponding to uncached data received from main memory and determines a data type for the uncached data. The present invention then examines the cache location in at least one of the configurable cache sets which is configured for the data type of the uncached data. Provided that the cache location of at least one of the configurable cache sets is not occupied by valid data and that the same configurable cache set is configured for the data type of the uncached data, the present invention stores the uncached data into that configurable cache set at the cache location without displacing valid data therein. Provided that the cache location of each of the configurable cache sets which is configured for the data type of the uncached data is occupied by valid yet old data, the present invention replaces the old data stored in one of the configurable cache sets at the cache location with the uncached data. In so doing, this embodiment of the present invention provides a method for cache replacement among configurable cache sets.
In another embodiment, the present invention includes the above recited steps and further the present invention examines a counter for the data type of the uncached data, the counter being incremented based on configurations of the first and second configurable cache sets, such that a value of the counter does not exceed a number of the first and second configurable cache sets which is configured for the data type of the uncached data. The present invention then replaces the old data stored in one of the first and second configurable cache sets at the cache location with the uncached data, where the particular configurable cache set for storing the uncached data is selected based on the value of the counter.
The present invention also describes in detail the system for performing the steps of the above described method.
These and other advantages of the present invention will no doubt become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.
REFERENCES:
patent: 4802086 (1989-01-01), Gay et al.
patent: 5537571 (1996-07-01), Deville
patent: 5553262 (1996-09-01), Ishida et al.
patent: 5729712 (1998-03-01), Whittaker
patent: 5737749 (1998-04-01), Patel et al.
patent: 5737752 (1998-04-01), Hilditch
patent: 5943687 (1999-08-01), Liedberg
patent: 6023747 (2000-02-01), Dodson
patent: 6049849 (2000-04-01), Arimilli et al.
patent: 6065099 (2000-05-01), Clark et al.
patent: 6073224 (2000-06-01), Watkins
patent: 6128703 (2000-10-01), Bourekas et al.
patent: 6141731 (2000-10-01), Beardsley et al.
patent: 6145057 (2000-11-01), Arimilli et al.
patent: 6154813 (2000-11-01), Martin et al.
patent: 0 325422 (1989-07-01), None
patent: 2311880 (1997-10-01), None
Jirgal James J.
Luce Roger W.
Kim Matthew M.
Tzeng Fred F.
VLSI Technology Inc.
Wagner , Murabito & Hao LLP
LandOfFree
Method and system for cache replacement among configurable... 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 system for cache replacement among configurable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for cache replacement among configurable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2854269