Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-05-25
2001-09-18
Bragdon, Reginald G. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S137000, C711S128000
Reexamination Certificate
active
06292871
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to cache memory systems and provides apparatus and methods for facilitating access by a processor to data stored in a memory.
BACKGROUND OF THE INVENTION
In processing systems such as computers, the data to be utilized by a processor is stored in a main memory and control logic manages the transfer of data between the memory and the processor in response to requests issued by the processor. The data stored in the main memory generally includes both instructions to be executed by the processor and data to be operated on by the processor. For simplicity, both instructions and true data are referred to collectively herein as “data” unless the context otherwise requires. The time taken by a main memory access is relatively long in relation to operating speeds of modern processors. To address this, a cache memory with a shorter access time is generally interposed between the main memory and the processor, and the control logic manages the storage of data retrieved from the main memory in the cache and the supply of data from the cache to the processor. The cache is organized into multiple “lines”, each line providing storage for a block, or line, of data from the main memory which may be many bytes in length. When the processor issues a request for data in a line N, the control logic determines whether that line is stored in the cache. If so, ie. if there is a cache hit, the data is retrieved from the cache. If not, ie. if there is a cache miss, the data must be retrieved from the main memory and the processor is stalled while this operation takes place. Since a cache access is much faster than a main memory access, it is clearly desirable to manage the system so as to achieve a high ratio of cache hits to cache misses. Increasing the size of the cache makes this task easier, but cache memory is expensive in comparison to the slower, main memory. It is therefore important to use cache memory space as efficiently as possible.
In conventional cache memory systems, a line of data retrieved from the memory following a cache miss is stored in the cache, overwriting a previously stored line which is selected for eviction by the control logic in accordance with a priority system. The priority system indicates the relative priority of lines of data stored in the cache, with low priority lines being selected for eviction before higher priority lines. The control logic implements the priority system by maintaining priority data indicative of the current priorities of the stored lines various priority systems are known, though the generally favoured technique is a Least Recently Used system where the control logic maintains data indicating relatively how recently lines stored in the cache have been accessed by the processor. The least recently used (LRU) line is selected for eviction first when space is required for a new line, and this line then becomes the most recently used (MRU) line when it is read out to the processor. Whatever the priority system employed, it is desirable to utilize the cache memory space so as to reduce processor stall time due to main memory accesses as far as possible.
In practice, the effectiveness of current cache memory systems is dependent on the nature of the processing application. For example, real time multithreaded applications, such as in a storage controller environment, have an execution profile which is unfriendly to the operation of a conventional cache. Execution of instructions in these environments is driven by external events, such as a new host I/O arriving or a disk I/O completing, and these events tend to occur in a random order. Each event calls for a particular sequence of instructions to be executed a single time. These instructions are not then executed again until the next time that event occurs. The lack of repetition means that a cache will not be effective unless an event repeats within the lifetime of lines stored in the cache. If the set of all events is large, and the code that is executed for each event is mostly unique, then the full set of code will exceed the available cache memory space. Thus, an instruction will only be executed once before it is evicted from the cache and replaced with another instruction for another event. This means that the cache is not effective in improving the instruction throughput of the processor.
One way to improve efficiency of a cache memory system is to attempt to anticipate processor requests and retrieve lines of data from the memory in advance. This technique is known as prefetching. U.S. Pat. No. 5,566,324 discloses such a memory system in which, in the event of a main cache miss, a current line is retrieved from memory and the sequentially next line is retrieved and stored in a prefetch cache. If the prefetched line is requested next by the processor, this line is then loaded to the main cache and supplied to the processor, so that a main memory access is avoided. U.S. Pat. No. 4,980,823 discloses another prefetching system which, rather than using a separate prefetch store as in U.S. Pat. No. 5,566,324, prefetches lines directly into an LRU location of the cache. Known prefetching systems can improve performance to some extent in applications where data lines are called sequentially by the processor. However, in many applications the processing requirements are more complex and the effectiveness of current prefetching systems is limited. The applications described above in relation to a storage controller provide an example. While the use of known prefetching systems in this environment will save some processor stall time for main memory accesses, ie. for the sequentially called lines within a particular section of code, this does not significantly improve the overall efficiency of the memory system.
DISCLOSURE OF THE INVENTION
According to one aspect of the present invention there is provided a cache memory system for facilitating access by a processor to lines of data stored in a memory, the system comprising: a cache for storing lines of data for access by the processor; a prefetch store for storing lines of data to be transferred to the cache; and a memory controller for receiving processor requests for access to lines of data and retrieving lines of data from the memory, the memory controller maintaining priority data indicative of the relative priority of lines of data stored in the cache. The memory controller is configured to respond to receipt of a processor request for access to data in a line N such that: in the case of a cache hit, the memory controller controls supply of that data from the cache to the processor; in the case of a cache miss when line N is not stored in the prefetch store, the memory controller retrieves line N from the memory, and controls storage of the line in the cache and supply of the data to the processor, the priority data for line N being set to a high relative priority; in the case of a cache miss when line N is stored in the prefetch store, the memory controller transfers line N from the prefetch store to the cache and controls supply of the data to the processor, the priority data for line N being set to a low relative priority, and for both a cache hit and a cache miss, the memory controller prefetches the sequentially next line N+1 from the memory to the prefetch store.
Thus, in embodiments of the present invention, prefetching is performed on both a cache hit and a cache miss, and prefetched data lines which are then requested and supplied to the processor are stored in the cache with a lower priority than lines retrieved directly from the main memory. As a result, lines which generally cannot be prefetched successfully are retained in the cache in favour of lines which can be prefetched successfully. Those lines which are called out of sequence, eg. the branch targets for the working set of a piece of code, will therefore tend to be retained in the cache. Because prefetching is performed for cache hits as well as cache misses, a line which can be prefetched successfully is general
August Casey P.
Bragdon Reginald G.
International Business Machines - Corporation
LandOfFree
Loading accessed data from a prefetch buffer to a least... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Loading accessed data from a prefetch buffer to a least..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Loading accessed data from a prefetch buffer to a least... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546708