System and method for prefetching data into a cache based on miss distance

#Embodiments of the present invention relate to prefetching data from a memory. In particular, the present invention relates to methods and apparatus for prefetching data from a memory for use by a processor.

#Instructions executed by a processor often use data that may be stored in a memory device such as a Random Access Memory (RAM). For example, a processor may execute a LOAD instruction to load a register with data that is stored at a particular memory address. In many systems, because the access time for the system memory is relatively slow, frequently used data elements are copied from the system memory into a faster memory device called a cache and, if possible, the processor uses the copy of the data element in the cache when it needs to access (i.e., read to or write from) that data element. If the memory location that is accessed by an instruction has not been copied into a cache, then the access to the memory location by the instruction is said to cause a “cache miss” because the data needed could not be obtained from the cache. Computer systems operate more efficiently if the number of cache misses is minimized.

#One way to decrease the time spent waiting to access a RAM is to “prefetch” data from the RAM memory before it is needed and, thus, before the cache miss occurs. Many processors have an instruction cycle in which instructions to be executed are obtained from memory in one step (i.e., an instruction fetch) and executed in another step. If the instruction to be executed accesses a memory location (e.g., a memory LOAD), then the data at that location must be fetched into the appropriate section of the processor from a cache or, if a cache miss, from a system memory. A cache prefetcher attempts to anticipate which data addresses will be accessed by instructions in the future and prefetches the data to be accessed from the memory before the data is needed. This prefetched data may be stored in a cache or buffer for later use.

#FIG. 1 is a partial block diagram of a computer system having a prefetcher according to an embodiment of the present invention.

#FIG. 2 is a partial block diagram of a series of addresses in a memory and a cache according to an embodiment of the present invention.

#FIG. 3 is a partial block diagram of a critical miss prefetch table according to an embodiment of the present invention.

#Embodiments of the present invention relate to a prefetcher which prefetches data for an instruction based on the distance between cache misses caused by the instruction. In an embodiment, the prefetcher builds a prefetch table that records the distance between consecutive cache misses for instructions. This distance is the stride for the cache misses and may be referred to as a “miss distance” for the instruction. If the miss distance for an instruction occurs in a pattern, then misses occurring according to this pattern may be referred to as “critical cache misses.” After an instruction causes a “current cache miss”, the prefetcher of this embodiment may request prefetching of the data located at the miss distance away from the address of the data that caused the current cache miss. This data will then be available for future use. The miss distance may be stored in a critical cache miss prefetch table.

#A critical cache miss management policy such as described enables the use of a smaller table size than in previous prefetchers while maintaining to a large extent the performance advantages of previous prefetching mechanisms. The critical cache miss prefetcher achieves these efficient results because it does not store strides and addresses for LOAD instructions that do not generally cause misses. In addition, the prefetcher does not need to check for a cache miss for data that generally does not cause a cache miss even thought it is within the stride.

#Embodiments of the invention obtain further performance improvements by filtering out misses that are not part of a miss pattern. Such misses may be referred to as “cold misses” or “noise misses.” In an embodiment, the address that caused a miss for an instruction is not even recorded unless at least two misses are detected for that instruction. In a further embodiment, prefetching is not performed for an instruction until the miss distance is confirmed. In a still further embodiment, the miss distance stored in the critical miss prefetch table is not recalculated for an instruction unless two consecutive misses occur at a distance different than the miss distance. A more detailed description of these and other embodiments is provided below.