Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-05-04
2003-05-06
Portka, Gary J (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S128000, C711S134000
Reexamination Certificate
active
06560677
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer systems, and more particularly to cache memory systems.
BACKGROUND OF THE INVENTION
Cache memory has long been used in computing systems to decrease the memory access time for a Central Processing Unit (CPU) by reducing the number of accesses to a main memory. With respect to the main memory, the cache memory is typically a high speed, low capacity memory in which active portions of program instructions and/or data are stored. The cache memory is typically faster than a main memory by a factor of 5 to 10 and typically approaches the speed of the CPU itself. By keeping some of the most frequently accessed instructions and/or data in the cache memory, the average memory access time may approach the access time of the cache memory and thereby improve the overall performance of the computing system.
In particular, improved performance of the computing system may be achieved by presuming that the computer program exhibits a behavior known as “locality of reference.” The locality of reference phenomenon recognizes that most computer program instruction processing proceeds in loops and subroutines which tends to limit memory references made by the computer program to a localized area of memory. Similarly, memory references to data may tend to be localized, because table lookup routines or other iterative routines may repeatedly refer to memory addresses within a relatively small range of memory addresses. Accordingly, although the cache memory may have small capacity, a large fraction of the data or instructions requested may be located in the cache memory and thereby improve the performance of the computing system. Data and/or instructions which exhibit locality of reference behavior are sometimes referred to as normal entries.
In operation, the CPU requests data or instructions for processing. If the requested data or instructions are stored in the cache memory (a cache hit), the requested data or instructions are provided to the CPU according to the speed of the cache memory. If, however, the requested data or instruction is not stored in the cache memory (a cache miss), a block of words (including the requested data or instruction) is accessed in the main memory and provided to the CPU according to the speed of the main memory. In addition, the block of words accessed in the main memory is copied into the cache memory so that future requests to the same words will be serviced by the cache memory. Accordingly, existing entries within the cache may be replaced by the block of words retrieved from the main memory. For example, when a cache miss results in a block of words being retrieved from main memory, a correspondingly sized portion of the cache may be replaced (overwritten) by the block of words retrieved from the main memory. The cache entries selected for replacement are sometimes referred to as “victims.”
It is known to use replacement schemes, such as a Least Recently Used (LRU) or a round-robin scheme, to select the victims in the cache when a block is copied from main memory into the cache. For example, it is known to use an LRU scheme when replacing normal entries in the cache with data and/or instructions from main memory that exhibit the same locality of reference behavior (i. e., normal). Such cache systems are discussed in U.S. Pat. No. 5,809,527 entitled “Outboard File Cache System” to Cooper et al. which is incorporated herein by reference.
On the other hand, some data and/or instructions such as global variables or address pointers, are used by the CPU on an ongoing basis. Such data and/or instructions may be requested by the CPU despite the operational behavior exhibited by the computer program. For example, a program that otherwise exhibits locality of reference behavior may use an address pointer to a particular interrupt routine irrespective of the instructions the computer program is executing when an interrupt is received. Accordingly, some data and/or instructions stored in the cache can be locked so that they cannot be replaced, thereby improving the likelihood that the requested data and/or instructions are stored in the cache.
Although some types of data and instructions stored in the cache exhibit locality of reference behavior (e.g., normal entries) other types of entries may not. For example, the CPU may move video data from the main memory to a video frame buffer only once and subsequently may not request the same data again once the move is complete. Such data and/or instructions in the cache are referred to as “transient.” In such situations, the locality of reference presumption, may degrade the performance of the cache memory by replacing normal entries (which may be subsequently requested) with transient entries. Consequently, subsequent requests for the normal entries which were replaced with the transient entries may result in cache misses, thereby reducing the performance of the cache. Accordingly, it is known to use separate cache memories to store transient and normal data and/or instructions. In view of the above, there exists a need to improve cache memories wherein different types of data and/or instructions (such as locked, normal, and transient) are processed in cache memory systems.
SUMMARY OF THE INVENTION
In view of the above, it is an object of the present invention to allow improvement in the performance of cache memories.
It is another object of the present invention to allow more efficient use of cache memories.
These and other objects of the present invention may be provided by designating normal, transient, and locked subsets of the ways of a cache memory. On a cache miss, entries from the main memory are copied into the normal or the transient subset of the ways of the cache memory. The subset to which the entry is copied is selected based on the program behavior associated with the entry copied from main memory. For example, if an entry in main memory has an attribute associated with it that indicates that the entry exhibits normal program behavior, the normal subset is selected. If the entry in main memory has an attribute associated with it that indicates that the entry exhibits transient program behavior, the transient subset is selected. In one embodiment, the attribute associated with the entry is held in a memory management page table. In an alternate embodiment, a particular instruction (such as a load transient or load normal instruction) in the instruction set of the CPU is used.
Designating the normal subset for normal entries and the transient subset for transient entries may allow both types of entries to be processed while reducing the likelihood that interaction between the normal and transient entries may adversely affect the performance of the cache. For example, if transient entries are allowed to overwrite normal entries the cache performance with respect to the normal entries may be reduced.
In a further aspect of the present invention, the designations of the normal, transient, and locked subsets are programmable. The designated subsets may, therefore, be altered to meet to changing processing requirements. For example, the designations of the subsets may be changed to designate a greater portion of the cache for normal entries.
In another aspect of the present invention, at least one way included in the transient subset is included in the normal subset. Accordingly, entries designated as normal or transient may be copied into the common ways of the subsets.
REFERENCES:
patent: 4513367 (1985-04-01), Chan et al.
patent: 4977498 (1990-12-01), Rastegar et al.
patent: 5025366 (1991-06-01), Baror
patent: 5367653 (1994-11-01), Coyle et al.
patent: 5493667 (1996-02-01), Huck et al.
patent: 5519846 (1996-05-01), Swenson
patent: 5553262 (1996-09-01), Ishida et al.
patent: 5555393 (1996-09-01), Tanaka et al.
patent: 5584014 (1996-12-01), Nayfeh et al.
patent: 5627992 (1997-05-01), Baror
patent: 5732242 (1998-03-01), Mowry
patent: 5809527 (1998-09-01), Cooper et al.
patent: 6185657 (2001-02-01), Moyer
patent: 6202129 (2001-03-01), Palanca et al.
patent: 60
Bridges Jeffrey Todd
Sartorius Thomas Andrew
Flynn John D.
Myers Bigel Sibley & Sajovec P.A.
Portka Gary J
LandOfFree
Methods, cache memories, systems and computer program... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods, cache memories, systems and computer program..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, cache memories, systems and computer program... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3064614