Data cache region prefetcher

Abstract

A data cache region prefetcher creates a region when a data cache miss occurs. Each region includes a predetermined range of data lines proximate to each data cache miss and is tagged with an associated instruction pointer register (RIP). The data cache region prefetcher compares subsequent memory requests against the predetermined range of data lines for each of the existing regions. For each match, the data cache region prefetcher sets an access bit and attempts to identify a pseudo-random access pattern based on the set access bits. The data cache region prefetcher increments or decrements appropriate counters to track how often the pseudo-random access pattern occurs. If the pseudo-random access pattern occurs frequently, then the next time a memory request is processed with the same RIP and pattern, the data cache region prefetcher prefetches the data lines in accordance with the pseudo-random access pattern for that RIP.

What is claimed is: 
     
         1 . A data cache region prefetcher, comprising:
 a line entry data table including a plurality of line entries,   wherein each line entry includes a region defined by a predetermined number of access bits, and an access bit for a given line entry is set if a cache line is requested within the region; and   a region history table configured to receive evictions from the line entry data table,   wherein the data cache region prefetcher is configured to determine an access pattern from certain access bits in an evictable line entry and exclude line entries having predetermined access patterns from eviction to the region history table.   
     
     
         2 . The data cache region prefetcher of  claim 1 , wherein the data cache region prefetcher is configured to evict the line entries having pseudo-random access patterns to the region history table. 
     
     
         3 . The data cache region prefetcher of  claim 1 , wherein the region history table is indexed using at least an instruction pointer register (RIP). 
     
     
         4 . The data cache region prefetcher of  claim 3 , wherein the region history table is further indexed using an offset to support multiple pseudo-random access patterns, for the same RIP, depending on whether an initial access to a region is at a beginning, end or middle of a cache line. 
     
     
         5 . The data cache region prefetcher of  claim 1 , wherein:
 the region history table includes a plurality of region history entries,   each region history entry including the predetermined number of access bits,   each region history entry including counters for certain access bits in the predetermined number of access bits, and   the counters are incremented or decremented depending on whether the access bit is set for the evictable line entry.   
     
     
         6 . The data cache region prefetcher of  claim 1 , further comprising:
 a region prefetch generator configured to receive prefetch requests from the region history table on a condition that counters associated with specific access bits in a specific region history entry in the region history table have reached a threshold.   
     
     
         7 . The data cache region prefetcher of  claim 1 , wherein the data cache region prefetcher is configured to block other prefetchers from processing streams that are pending with the data cache region prefetcher. 
     
     
         8 . The data cache region prefetcher of  claim 1 , wherein each line entry further includes second access bits which are set when a subsequent cache line request is within one access bit of a home bit in the predetermined number of access bits and which are used to determine the predetermined access patterns that are excluded from eviction to the region history table. 
     
     
         9 . A processing system, comprising:
 a stream prefetcher; and   a data cache region prefetcher including:
 a line entry data table having a plurality of line entries; and 
 a region history table which receives evictions from the line entry data table, 
 wherein each line entry includes a region defined by a predetermined number of access bits, and an access bit for a given line entry is set if a cache line is requested within the region; and 
   the data cache region prefetcher is configured to:
 determine an access pattern from certain access bits in an evictable line entry and exclude line entries having predetermined access patterns from eviction to the region history table; and 
 block the stream prefetcher from processing streams that are pending with the data cache region prefetcher. 
   
     
     
         10 . The system of  claim 9 , wherein the data cache region prefetcher is further configured to evict line entries having pseudo-random access patterns to the region history table. 
     
     
         11 . The system of  claim 9 , wherein the region history table is indexed using at least an instruction pointer register (RIP). 
     
     
         12 . The system of  claim 11 , wherein the region history table is further indexed using an offset to support multiple pseudo-random access patterns, for the same RIP, depending on whether an initial access to a region is at a beginning, end or middle of a cache line. 
     
     
         13 . The system of  claim 9 , wherein:
 the region history table including a plurality of region history entries,   each region history entry including the predetermined number of access bits,   each region history entry including counters for certain access bits in the predetermined number of access bits, and   the counters are incremented or decremented depending on whether there is a bit set in the respective access bit.   
     
     
         14 . The system of  claim 9 , further comprising:
 a region prefetch generator configured to receive prefetch requests from the region history table on a condition that counters associated with specific access bits in a specific region history entry in the region history table have reached a threshold.   
     
     
         15 . The system of  claim 9 , wherein each line entry further includes second access bits which are set when a subsequent cache line request is within one access bit of a home bit in the predetermined number of access bits and which are used to determine the predetermined access patterns that are excluded from eviction to the region history table. 
     
     
         16 . A method for data cache region prefetching, the method comprising:
 receiving a cache line request at a line entry table, the line entry table including a plurality of line entries, wherein each line entry includes a region defined by a predetermined number of access bits;   setting an access bit for a given line entry if the cache line request is within the region;   determining an access pattern from certain access bits in an evictable line entry;   excluding line entries having predetermined access patterns from eviction to a region history table; and   evicting line entries having pseudo-random access patterns to a region history table.   
     
     
         17 . The method of  claim 16 , further comprising:
 indexing the region history table using at least an instruction pointer register (RIP).   
     
     
         18 . The method of  claim 17 , further comprising:
 indexing the region history table using the RIP and an offset to support multiple pseudo-random access patterns for the same RIP, depending on whether an initial access to a region is at a beginning, end or middle of a cache line.   
     
     
         19 . The method of  claim 16 , wherein the region history table includes a plurality of region history entries, each history line entry including counters for certain access bits in the predetermined number of access bits, the method further comprising:
 incrementing or decrementing the counters depending on whether respective access bits are set.   
     
     
         20 . The method of  claim 16 , further comprising:
 sending prefetch requests to a region prefetch generator on a condition that counters associated with specific access bits in a specific region history entry in the region history table meet or exceed a threshold.   
     
     
         21 . The method of  claim 16 , further comprising:
 blocking other prefetchers from processing streams that are pending with the data cache region prefetcher.   
     
     
         22 . The method of  claim 16 , wherein each line entry further includes second access bits, the method further comprising:
 setting the second access bits when a subsequent cache line request is within one access bit of a home bit in the predetermined number of access bits; and   using the set second access bits to determine the predetermined access patterns that are excluded from eviction to the region history table.