System and method for maintaining prefetch stride continuity through the use of prefetch bits

Abstract

A processor includes a cache that has a lines to store data. The processor also includes prefetch bits each of which is associated with one of the cache lines. The processor further includes a prefetch manager that calculates prefetch data as if a cache miss occurred whenever a cache request results in a cache hit to a cache line that is associated with a prefetch bit that is set. In a further embodiment, the prefetch manager prefetches data into the cache based on the distance between cache misses for an instruction.

What is claimed is:  
     
         1 . A processor comprising: 
 a cache having plurality of lines to store data;    a plurality of prefetch bits each associated with one of the cache lines; and    a prefetcher to calculate prefetch data as though a cache miss occurred if a cache request results in a cache hit to a line that is associated with a set prefetch bit.    
     
     
         2 . The processor of  claim 1 , wherein the prefetch data includes miss distance information for instructions.  
     
     
         3 . The processor of  claim 1 , wherein the prefetch bits are stored in the cache.  
     
     
         4 . The processor of  claim 1 , wherein the prefetch manager has logic to reset a prefetch bit associated with a cache line whenever a cache request results in a cache hit to the cache line and the prefetch bit was set.  
     
     
         5 . The processor of  claim 1  further comprising logic to store recency of use information for the plurality of cache lines which logic uses information from the prefetch bits to determine the recency of use information.  
     
     
         6 . A cache comprising: 
 a data array having plurality of lines to store data; and    a plurality of prefetch bits each associated with one of the data array lines to indicate that data stored in the associated line was prefetched into the cache.    
     
     
         7 . The cache of  claim 6 , wherein the cache contains logic to reset a prefetch bit in response to a read from the data array line associated with the prefetch bit.  
     
     
         8 . The cache of  claim 6 , wherein the cache further comprises a least recently used (LRU) array, and wherein said plurality of prefetch bits are located in the LRU array.  
     
     
         9 . The cache of  claim 6 , wherein the cache has logic to store recency of use information associated with each data array line, and wherein said logic stores information indicating that a data array line has a status of least recently used whenever the data array line is updated with data that was prefetched into the cache.  
     
     
         10 . The cache of  claim 9 , wherein said logic stores information indicating that the data array line last read has a status of most recently used unless the data array line is associated with a prefetch bit that indicates data being stored in this data array line was prefetched into the cache.  
     
     
         11 . A processor comprising: 
 a cache;    an instruction decoder to decode instructions and to cause cache requests to be sent for data to be used by the instructions decoded;    a cache manager to generate a cache miss response for a cache request if data requested is stored in the cache and the cache manager determines that the data was prefetched into the cache; and    a cache prefetcher to receive cache miss responses from the cache manager and to prefetch data into the cache based on the distance between cache misses for an instruction.    
     
     
         12 . The processor of  claim 11 , wherein the processor further includes a plurality of prefetch bits that store information used by the prefetch manager to determine if data was prefetched into the cache.  
     
     
         13 . The processor of  claim 12 , wherein the cache contains a Read request buffer, and wherein the plurality of prefetch bits are attached to the Read request buffer.  
     
     
         14 . The processor of  claim 12 , wherein the processor contains logic to reset the prefetch bit associated with prefetched data in response to the first hit to the prefetched data, and wherein the cache manager will determine that data was not prefetched if the prefetch bit associated with said data is reset.  
     
     
         15 . The processor of  claim 11 , wherein the cache contains bits to store information about the status of each line in the cache, and wherein the cache contains logic to update the status of a cache line to least recently used whenever prefetched data is stored in the cache line and to update the status of said cache line to most recently used whenever the prefetched data is read a second time after the data is prefetched into the cache.  
     
     
         16 . A method of maintaining the continuity of prefetch information, the method comprising: 
 decoding an instruction a first time;    sending a first request to a cache for data to be used by said instruction;    determining that the data requested in the first request is stored in a line in a cache;    determining that a prefetch bit associated with said cache line indicates that the cache line stores data that was prefetched into the cache; and    calculating prefetch information for said instruction, wherein the prefetch information is calculated based on the first request having resulted in a cache miss.    
     
     
         17 . The method of  claim 16 , wherein the method further comprises resetting the prefetch bit associated with the cache line.  
     
     
         18 . The method of  claim 16 , wherein the calculation of prefetch information for an instruction comprises calculating miss distance information for the instruction.  
     
     
         19 . The method of  claim 16 , further comprising: 
 decoding a second instruction which is to use said data;    sending a second request to the cache for said data;    determining that the data requested in the second request is stored in a line in the cache;    determining that the prefetch bit associated with said cache line indicates that the cache line stores data that was not prefetched into the cache;    calculating prefetch information for the instruction, wherein the prefetch information is calculated based on the second request having resulted in a cache hit; and    updating the status information corresponding to the cache line to indicate that the cache line was most recently used.    
     
     
         20 . A processor comprising: 
 a cache having a plurality of cache lines;    a means for prefetching data into one of the cache lines; and    a means for indicating that a cache line contains prefetched data.    
     
     
         21 . The processor of  claim 20 , further comprising a means for determining that a virtual miss has occurred in response to a request for data sent to the cache whenever the data is stored in a cache line and the means for indicating indicates that the cache lines contains prefetched data.  
     
     
         22 . The processor of  claim 20 , wherein the means for prefetching updates a prefetch table to indicate that a miss response was received whenever a response was received for an actual miss or a virtual miss.  
     
     
         23 . The processor of  claim 20  further comprising a means for preventing the calculation of a miss distance of zero for instructions that have a miss distance that is greater than zero but less than the size of a cache line.  
     
     
         24 . The processor of  claim 20 , wherein the means for indicating that a cache line contains prefetched data stores a data structure that is used to determine whether a cache line contains prefetched data, and wherein the processor further comprising a means for reducing cache pollution that uses the same data structure as said means for indicating.