Abstract:
An apparatus in a microprocessor for selectively retiring a prefetched cache line is disclosed. The microprocessor includes a prefetch buffer that stores a cache line prefetched from a system memory coupled to the microprocessor. The microprocessor includes a cache memory, comprising an array of storage elements for storing cache lines. The array is indexed by an index input. The microprocessor includes a counter that counts a number of accesses to a replacement candidate line in the cache. The replacement candidate line is stored in a storage element of the array indexed by an index portion of an address of the prefetched cache line stored in the prefetch buffer. The microprocessor also includes control logic that selectively replaces the replacement candidate cache line in the cache memory with the prefetched cache line from the prefetch buffer based on the number of accesses to the replacement candidate line.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application is a divisional of application Ser. No. 11/198,988, filed Aug. 8, 2005, which is a continuation of application Ser. No. 10/420,357, filed Apr. 21, 2003, which claims priority based on Provisional Application No. 60/390,054, filed Jun. 18, 2002. 
     
    
     BACKGROUND OF THE INVENTION  
     Field of the Invention  
       [0002]     This invention relates in general to the field of cache memories, and particularly to cache line prefetching.  
         [0003]     Modern computer systems include a microprocessor and a system memory for storing instructions to be executed by the microprocessor and data to be processed by the instructions. The time required to read data from the system memory is typically very large relative to the time the microprocessor spends executing one or more instructions to process the data—in some cases one or two orders of magnitude. Consequently, the processor may sit idle while the data is loaded from the system memory, which is very inefficient and degrades system performance.  
         [0004]     To alleviate this problem, microprocessors include a cache memory. A cache memory is a memory within the processor smaller than the system memory that stores a subset of the system memory data. When the processor executes an instruction that references data, the processor first checks to see if the data is present in the cache, commonly referred to as a “cache hit,” from a previous load of the data. If the load hits in the cache, then the instruction can be executed immediately. Otherwise, if the load “misses” the cache, the instruction must wait while the data is fetched from the system memory into the processor.  
         [0005]     Microprocessor designers have recognized that software programs frequently access data and instructions sequentially. Hence, if a load misses in the cache, it is highly likely that the data at the memory addresses following the load miss address will be requested by the program in the near future. Consequently, a microprocessor may speculatively begin loading the next chunk of data after the missing data into the cache, even though the program has not yet requested the next data, in anticipation of a future need for the next chunk of data. This is commonly referred to as a prefetch.  
         [0006]     The chunk of data prefetched is commonly the size of a cache line. Caches store data in cache lines. Common cache line sizes are 32 bytes or 64 bytes. A cache line is the smallest unit of data that can be transferred between the cache and the system memory. That is, when a microprocessor wants to read a cacheable piece of data missing in the cache, it reads from memory the entire cache line containing the missing piece of data and stores the entire cache line in the cache. Similarly, when a new cache line needs to be written to the cache that causes a modified cache line to be replaced, the microprocessor writes the entire replaced line to memory.  
         [0007]     The conventional approach is to treat the prefetched cache line as an ordinary line fill. An ordinary line fill is a fetch of a cache line from system memory because an instruction accessed data in the cache line. With an ordinary line fill, the fetched cache line is unconditionally written, or retired, into the cache. A disadvantage of unconditionally retiring a speculatively prefetched cache line into the cache is that it potentially replaces a line in the cache that is currently being used or likely to be used in the near future, thereby potentially adversely affecting cache efficiency. A solution to this problem is needed in order to improve cache efficiency.  
       SUMMARY OF THE INVENTION  
       [0008]     The present invention distinguishes a prefetched cache line from an ordinary cache line fill and selectively retires the prefetched cache line into the cache based upon contemporaneous accesses to the line in the cache that is the candidate for being replaced by the prefetched line. Accordingly, in attainment of the aforementioned object, it is a feature of the present invention to provide an apparatus in a microprocessor for selectively retiring a prefetched cache line into a cache memory of the microprocessor. The apparatus includes a prefetch buffer that stores the prefetched cache line, and a counter, coupled to the prefetch buffer. The counter stores a count of accesses to a replacement candidate line in the cache. The apparatus also includes control logic, coupled to the counter, which selectively retires the prefetched cache line to the cache based on the count in the counter.  
         [0009]     In another aspect, it is a feature of the present invention to provide a method for selectively retiring a prefetched cache line from a prefetch buffer into a cache memory of a microprocessor. The method includes prefetching a cache line into the prefetch buffer. The method also includes counting a number of accesses to a replacement candidate line in the cache, after the prefetching. The method also includes receiving a request to prefetch another cache line into the prefetch buffer subsequent to the prefetching. The method also includes selectively retiring the prefetched cache line from the prefetch buffer by replacing the replacement candidate cache line in the cache memory with the prefetched cache line based on the counting, in response to the receiving the subsequent prefetch request.  
         [0010]     In another aspect, it is a feature of the present invention to provide a microprocessor that includes a prefetch buffer that stores a cache line prefetched from a system memory coupled to the microprocessor. The microprocessor includes a cache memory, comprising an array of storage elements for storing cache lines. The array is indexed by an index input. The microprocessor includes a counter that counts a number of accesses to a replacement candidate line in the cache. The replacement candidate line is stored in a storage element of the array indexed by an index portion of an address of the prefetched cache line stored in the prefetch buffer. The microprocessor also includes control logic that selectively replaces the replacement candidate cache line in the cache memory with the prefetched cache line from the prefetch buffer based on the number of accesses to the replacement candidate line.  
         [0011]     In another aspect, it is a feature of the present invention to provide a computer program product embodied on a computer-readable storage medium for use with a computing device including a computer-readable storage medium having computer-readable program code embodied in the medium for providing a microprocessor. The program code includes first program code for providing a prefetch buffer, for storing a cache line prefetched from a system memory coupled to the microprocessor. The program code also includes second program code for providing a cache memory, comprising an array of storage elements for storing cache lines. The array is indexed by an index input. The program code also includes third program code for providing a counter, configured to count a number of accesses to a replacement candidate line in the cache. The replacement candidate line is stored in a storage element of the array indexed by an index portion of an address of the prefetched cache line stored in the prefetch buffer. The program code also includes fourth program code for providing control logic, coupled to the cache memory and the prefetch buffer and the counter, configured to selectively replace the replacement candidate cache line in the cache memory with the prefetched cache line from the prefetch buffer based on the number of accesses to the replacement candidate line.  
         [0012]     An advantage of the present invention is that by adding a small amount of additional hardware we are able to potentially improve cache efficiency by decreasing the likelihood of detrimentally replacing a cache line that is more likely to be accessed in the near future than the prefetched line.  
         [0013]     Other features and advantages of the present invention will become apparent upon study of the remaining portions of the specification and drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]      FIG. 1  is a block diagram of a microprocessor with an apparatus for selectively retiring prefetched cache lines according to the present invention.  
         [0015]      FIG. 2  is a flowchart illustrating operation of the microprocessor of  FIG. 1  to selectively retire a prefetched cache line from the prefetch buffer into the cache according to the present invention.  
         [0016]      FIG. 3  is a block diagram of a microprocessor with an apparatus for selectively retiring prefetched cache lines according to an alternate embodiment of the present invention.  
         [0017]      FIG. 4  is a flowchart illustrating operation of the microprocessor of  FIG. 3  to selectively retire a prefetched cache line from the prefetch buffer into the cache according to an alternate embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0018]     Referring now to  FIG. 1 , a block diagram of a microprocessor  100  with an apparatus for selectively retiring prefetched cache lines according to the present invention is shown. Microprocessor  100  includes a plurality of stages coupled together to form a pipeline. One or more of the pipeline stages includes an address generator for generating a memory access operation address, referred to in  FIG. 1  as load/store address  132 . The load/store address  132  specifies the address of a load or store operation. A load operation reads data from memory into microprocessor  100 , and a store operation writes data from microprocessor  100  to memory. In one embodiment, load/store address  132  is a physical memory address.  
         [0019]     Microprocessor  100  also includes a cache memory  104 , or cache  104 . In one embodiment, cache  104  comprises a 64 KB 4-way set associative cache memory. In one embodiment, cache  104  is a level-1 data cache; however, the present invention is not limited to use with a data cache, but may be employed with an instruction cache or with a unified data/instruction cache. Additionally, the present invention is not limited to application with a level-1 cache, but may be employed with caches at any level of the cache hierarchy.  
         [0020]     Cache  104  stores address tags and status of each cache line stored therein. The tags comprise an upper portion of the memory address of cache lines stored in cache  104 . In one embodiment, the status comprises MESI (Modified/Exclusive/Shared/Invalid) protocol state information. Cache  104  receives load/store address  132 . A lower portion of load/store address  132  is used to index into cache  104  to select a set, or row, of ways. Cache  104  compares the upper portion of load/store address  132  with the address tags of each way in the selected set so a determination may be made of whether load/store address  132  hits in the cache, i.e., whether load/store address  132  matches any tags present in cache  104  and has a valid status. Cache  104  outputs status information  134 , which includes the MESI state of each way of the selected set, and an indication of whether any of the tags in the selected set match load/store address  132 . If load/store address  132  is for a load operation causing a hit in cache  104 , the hitting cache line data is provided to the stage of the microprocessor  100  pipeline requesting the cache line data.  
         [0021]     Microprocessor  100  also includes control logic  102 , coupled to cache  104 . Control logic  102  receives status  134  from cache  104  and load/store address  132 . Control logic  102  responsively generates control signals to control the operation of cache  104 . Operation of control logic  102  will be described in more detail below.  
         [0022]     Microprocessor  100  also includes a prefetch line buffer  106 , coupled to cache  104 . Prefetch buffer  106  receives a prefetched cache line  136  from a bus interface unit, which fetches data from a system memory into microprocessor  100  over a processor bus. As described below, if load/store address  132  misses in cache  104 , control logic  102  causes a cache line following the cache line implicated by load/store address  132 , i.e., prefetched cache line  136 , to be prefetched from system memory into prefetch buffer  106 . Advantageously, control logic  102  selectively retires the prefetched cache line  136  into cache  104  based on contemporaneous accesses to the prefetched cache line  136 , as described below.  
         [0023]     Prefetch buffer  106  provides the prefetched cache line  136  to cache  104 . Additionally, prefetch buffer  106  provides the prefetched cache line  136  to one or more stages of the microprocessor  100  pipeline requesting data in the prefetched cache line  136 . In this regard, prefetch line buffer  106  may be viewed as an extension of cache  104 . That is, if control logic  102  determines that a load operation specifies a load/store address  132  that misses in cache  104  but hits in prefetch buffer  106 , control logic  102  may provide data from the prefetched cache line  136  to a microprocessor  100  pipeline stage.  
         [0024]     Microprocessor  100  also includes a prefetch address register (PAR)  108 , coupled to control logic  102 . PAR  108  stores the address of the prefetched cache line  136  stored in prefetch buffer  106 , referred to as prefetch address  138 . When control logic  102  causes the prefetched cache line  136  to be prefetched into prefetch buffer  106 , control logic  102  updates PAR  108  with the prefetched cache line address  138 . Additionally, control logic  102  compares PAR  108  with load/store address  132  to detect subsequent accesses to the prefetched cache line  136 .  
         [0025]     Microprocessor  100  also includes a prefetch buffer access count (PBAC) register  116 , coupled to control logic  102 . PBAC register  116  stores the number of accesses to the prefetched cache line  136  in prefetch buffer  106 , referred to as PBAC  128 . Control logic  102  increments PBAC register  116  when control logic  102  detects an access to the prefetched cache line  136 . In one embodiment, an access includes a read of the prefetched cache line  136 . However, other embodiments are contemplated in which accesses to the prefetched cache line  136  also include writes and/or snoop operations. Control logic  102  clears PBAC register  116  when a new prefetched cache line  136  is prefetched into prefetch buffer  106 .  
         [0026]     Microprocessor  100  also includes a plurality of candidate way access count (CWAC) registers  112 , coupled to control logic  102 . The embodiment of  FIG. 1  includes four CWAC registers  112 , denoted CWAC 0   112 A, CWAC 1   112 B, CWAC 2   112 C, and CWAC 3   112 D, corresponding to each of the four ways in 4-way set associative cache  104 . Each of the CWAC registers  112  stores the number of accesses to the corresponding way of the candidate set. The candidate set is the set of ways in cache  104  selected by prefetch address  138 . Control logic  102  increments one of the CWAC registers  112  when control logic  102  detects an access to the corresponding way of the selected set in cache  104 . Control logic  102  clears the CWAC registers  112  when a new prefetched cache line  136  is prefetched into prefetch buffer  106 .  
         [0027]     Microprocessor  100  also includes minimum selection logic  114 , coupled to CWAC registers  112 . Minimum selection logic  114  receives the CWAC from each of the CWAC registers  112  and outputs the smallest value received from the CWAC registers  112 , denoted min_AC  122 . In addition, minimum selection logic  114  outputs to control logic  102  min_way signal  126 , which specifies the way number having the smallest value received from the CWAC registers  112 .  
         [0028]     Microprocessor  100  also includes a comparator  118 , coupled to minimum selection logic  114  and PBAC register  116 . Comparator  118  compares min_AC  122  and PBAC  128 , and generates a true value on result output  124  if PBAC  128  is greater than min_AC  122 , and generates a false value otherwise. In another embodiment, comparator  118  compares min_AC  122  and PBAC  128 , and generates a true value on result output  124  if PBAC  128  is greater than or equal to min_AC  122 , and generates a false value otherwise. Result  124  is provided to control logic  102 .  
         [0029]     Referring now to  FIG. 2 , a flowchart illustrating operation of microprocessor  100  of  FIG. 1  to selectively retire a prefetched cache line from prefetch buffer  106  into cache  104  is shown. Flow begins at decision block  202 .  
         [0030]     At decision block  202 , control logic  102  determines whether load/store address  132  misses in cache  104  by examining status signals  134  of  FIG. 1 . If so, flow proceeds from decision block  202  to block  204 ; otherwise, flow returns to decision block  202 .  
         [0031]     At block  204 , after initiating a fetch of the missing cache line from memory into cache  104 , control logic  102  instructs the bus interface unit to prefetch the next cache line after the cache line implicated by missing load/store address  132  into prefetch buffer  106  of  FIG. 1 . Before prefetching the next cache line into prefetch buffer  106 , control logic  102  verifies that the next cache line is also missing in cache  104 . When the prefetched cache line  136  has been prefetched into prefetch buffer  106 , control logic  102  updates prefetch address register  108  with prefetch address  138  of  FIG. 1 , i.e., the address of the next cache line. Flow proceeds from block  204  to decision block  206 .  
         [0032]     At decision block  206 , control logic  102  queries cache  104  with prefetch address  138  and determines whether any of the ways in the candidate set is invalid by examining status information  134  of  FIG. 1 . If so, flow proceeds from decision block  206  to block  208 ; otherwise, flow proceeds to block  212 .  
         [0033]     At block  208 , control logic  102  retires the prefetched cache line  136  into the invalid way of the candidate set of cache  104 . Flow returns from block  208  to decision block  202 .  
         [0034]     At block  212 , control logic  102  clears to zero PBAC register  116  and CWAC registers  112  of  FIG. 1 . Flow proceeds from block  212  to decision block  214 .  
         [0035]     At decision block  214 , as load/store operations access cache  104 , control logic  102  determines whether any of the operations have invalidated any of the ways in the candidate set. For example, a way in the candidate set may be invalidated by an invalidating snoop access. If any of the ways in the candidate set have been invalidated, flow proceeds from decision block  214  to block  208 ; otherwise, flow proceeds to decision block  216 .  
         [0036]     At decision block  216 , control logic  102  determines whether a new prefetch request has been made. That is, control logic  102  determines whether a new load/store address  132  has missed in cache  104  causing prefetch buffer  106  to be needed for prefetching a new cache line. If so, flow proceeds from decision block  216  to decision block  218 ; otherwise, flow proceeds to decision block  224 .  
         [0037]     At decision block  218 , control logic  102  determines whether PBAC  128  is greater than min_AC  122  by examining result signal  124  of  FIG. 1 . If so, flow proceeds from decision block  218  to block  222 . Otherwise, flow proceeds to block  204  such that the prefetched cache line  136  stored in prefetch buffer  106  is not retired into cache  104 , but instead is discarded, i.e., subsequently overwritten by the new prefetched cache line.  
         [0038]     At block  222 , control logic  102  retires the prefetched cache line  136  into the way of the candidate set of cache  104  specified by min way signal  126 . Flow proceeds from block  222  to block  204 .  
         [0039]     At decision block  224 , control logic  102  determines whether a way in the candidate set has been accessed by examining status information  134 . In one embodiment, a way is accessed if load/store address  132  hits in cache  104 , i.e., if the way has valid status and the tag of the way matches the tag portion of load/store address  132 . If the candidate set has been accessed, flow proceeds from decision block  224  to block  226 ; otherwise flow proceeds to decision block  228 .  
         [0040]     At block  226 , control logic  102  increments the CWAC register  112  corresponding to the accessed way determined at decision block  224 . For example, if way  2  is accessed, then control logic  102  increments CWAC 2   112 C. Flow proceeds from block  226  to decision block  228 .  
         [0041]     At decision block  228 , control logic  102  determines whether the prefetched cache line  136  has been accessed by comparing prefetch address  138  with load/store address  132 . If so, flow proceeds from decision block  228  to block  232 ; otherwise flow proceeds to decision block  214 .  
         [0042]     At block  232 , control logic  102  increments PBAC register  116 . Flow proceeds from block  232  to decision block  214 .  
         [0043]     The pseudocode shown in Table 1 below also describes the operation of microprocessor  100  described in  FIG. 2 .  
                                                                       TABLE 1                                       if ( anyWayInCandidateSetlnvalid ) {            retirePrefetchedLineToCache( );           } else {            PBAC = CWAC[0] = CWAC[1] = CWAC[2] = CWAC[3] = 0;            while (noNewPrefetchRequested &amp;&amp;            noWaylnCandidateSetInvalidated ) {             if ( candidateSetAccessed )              CWAC[accessed Way]++;             if ( PrefetchedLineAccessed )              PBAC++;            }            if (newPrefetchRequested ) {             if ( PBAC &gt; min_AC )              RetirePrefetchedLineToCache( );                  else   /* throw away prefetched cache line */                   OverwritePrefetchBufferWithNewPrefetchData( );                 } else {   /* way in candidate set was invalidated */                  RetirePrefetchedLineToCache( );            }           }                      
 
         [0044]     As may be observed from  FIGS. 1 and 2 , the present invention advantageously selectively retires the prefetched cache line  136  into cache  104 , based on the number of times the prefetched cache line  136  is accessed relative to the number of times the ways of the candidate set is accessed, rather than indiscriminately retiring the prefetched cache line  136  into cache  104 .  
         [0045]     Referring now to  FIG. 3 , a block diagram of a microprocessor  300  with an apparatus for selectively retiring prefetched cache lines according to an alternate embodiment of the present invention is shown.  
         [0046]     Microprocessor  300  includes a cache  104 , prefetch buffer  106 , prefetch address register (PAR)  108 , load/store address  132 , status information  134 , prefetched cache line  136 , and prefetch address  138  similar to like-numbered items of  FIG. 1 .  
         [0047]     Microprocessor  300  also includes control logic  302  similar to control logic  102  of  FIG. 1  and similarly coupled to cache  104  and prefetch buffer  106 ; however, control logic  302  of  FIG. 3  operates to selectively retire prefetched cache line  136  into cache  104  based on values stored in a candidate line access counter (CLAC) register  314 , an access threshold register (ATR)  316 , and a candidate way register (CWR)  318 , all coupled to control logic  302 .  
         [0048]     CWR  318  stores a value specifying the candidate way, which is the way of the candidate set to be selectively replaced by prefetched cache line  136 . In one embodiment, initially, control logic  302  populates CWR  318  with the least-recently-used way of the candidate set determined from status information  134 . If the candidate way is replaced before a new prefetch is requested, control logic  302  updates CWR  318  with the new least-recently-used way.  
         [0049]     CLAC  314  stores a count of the number of times the candidate line, or candidate way, specified in CWR  318  has been accessed since prefetched cache line  136  was prefetched into prefetch buffer  106 .  
         [0050]     ATR  316  stores a threshold value used by control logic  302  to compare with the value stored in CLAC  314  to selectively retire the prefetched cache line  136 , as described below. In one embodiment, the value stored in ATR  316  is predetermined. In one embodiment, the value stored in ATR  316  is programmable.  
         [0051]     Referring now to  FIG. 4 , a flowchart illustrating operation of microprocessor  300  of  FIG. 3  to selectively retire a prefetched cache line from prefetch buffer  106  into cache  104  is shown. Flow begins at decision block  402 .  
         [0052]     At block  402 , control logic  302  determines whether load/store address  132  misses in cache  104  by examining status signals  134  of  FIG. 3 . If so, flow proceeds from decision block  402  to block  404 ; otherwise, flow returns to decision block  402 .  
         [0053]     At block  404 , after initiating a fetch of the missing cache line from memory into cache  104 , control logic  302  populates CWR  318  with a value specifying the least-recently-used way of the candidate line. Furthermore, control logic  302  instructs the bus interface unit to prefetch the next cache line after the cache line implicated by missing load/store address  132  into prefetch buffer  106  of  FIG. 1 . Before prefetching the next cache line into prefetch buffer  106 , control logic  102  verifies that the next cache line is also missing in cache  104 . Additionally, control logic  302  populates prefetch address register  108  with the address of the next cache line after the missing cache line. Flow proceeds from block  404  to decision block  406 .  
         [0054]     At decision block  406 , control logic  302  queries cache  104  with prefetch address  138  and determines whether any of the ways in the candidate set is invalid by examining status information  134  of  FIG. 3 . If so, flow proceeds from decision block  406  to block  408 ; otherwise, flow proceeds to block  412 .  
         [0055]     At block  408 , control logic  302  retires the prefetched cache line  136  into the candidate way of cache  104  specified in CWR  318 . Flow returns from block  408  to decision block  402 .  
         [0056]     At block  412 , control logic  302  clears to zero CLAC  314  of  FIG. 3 . Flow proceeds from block  412  to decision block  414 .  
         [0057]     At decision block  414 , as load/store operations access cache  104 , control logic  302  determines whether any of the operations have invalidated the candidate way. If so, flow proceeds from decision block  414  to block  408 ; otherwise, flow proceeds to decision block  416 .  
         [0058]     At decision block  416 , control logic  302  determines whether a new prefetch request has been made. If so, flow proceeds from decision block  416  to decision block  418 ; otherwise, flow proceeds to decision block  424 .  
         [0059]     At decision block  418 , control logic  302  determines whether the value stored in CLAC  314  is greater than the value stored in ATR  316  of  FIG. 3 . If so, flow proceeds from decision block  418  to block  422 . Otherwise, flow proceeds to block  404  such that the prefetched cache line  136  stored in prefetch buffer  106  is not retired into cache  104 , but instead is discarded, i.e., subsequently overwritten by the new prefetched cache line.  
         [0060]     At block  422 , control logic  302  retires the prefetched cache line  136  into the candidate way of cache  104  specified by CWR  318 . Flow proceeds from block  422  to block  404 .  
         [0061]     At decision block  424 , control logic  302  determines whether the candidate way has been accessed by examining status information  134 . In one embodiment, the candidate way is accessed if the candidate way has valid status and the tag of the way matches the tag portion of load/store address  132 . If so, flow proceeds from decision block  424  to block  426 ; otherwise flow proceeds to decision block  428 .  
         [0062]     At block  426 , control logic  302  increments the CLAC  314 . Flow proceeds from block  426  to decision block  428 .  
         [0063]     At decision block  428 , control logic  302  determines whether the candidate way has been replaced by a store operation. If so, flow proceeds from decision block  428  to block  432 ; otherwise flow proceeds to decision block  414 .  
         [0064]     At block  432 , control logic  302  updates CWR  318  with the new least-recently-used way in the candidate set and clears to zero CLAC  314 . Flow proceeds from block  432  to decision block  414 .  
         [0065]     The pseudocode shown in Table 2 below also describes the operation of microprocessor  300  described in  FIG. 4 .  
                                               TABLE 2                           if ( Cache[PrefetchIndex][CandidateWay].Valid == 0 ) {        RetirePrefetchToCache( );       } else {        CandidateLineAccessCount = 0;        while ( ! NewPrefetchRequest &amp;&amp; ! CandidateLineInvalidated ) {         if ( CandidateLineAccessed ) {          CandidateLineAccessCount++;              } else if (CandidateLineInvalidated ) {   /* e.g., by external snoop */               RetirePrefetchToCache( );              } else if (CandidateLineReplaced ) {   /* i.e., with valid miss           data */               UpdateCandidateWayRegister( );          CandidateLineAccessCount = 0;         }        }        if ( ( CandidateLineAccessCount &lt; AccessThreshold ) &amp;&amp;           ( ! CandidateLinelnvalidated))        {         RetirePrefetchToCache( );        } else {         OverWritePrefetchBufferWithNewPrefetchData( );         /* i.e., flush old prefetch data */        }       }                  
 
         [0066]     Although the present invention and its objects, features, and advantages have been described in detail, other embodiments are encompassed by the invention. For example, the present invention is suitable for use with a data cache or an instruction cache or a combined instruction/data cache. Furthermore, although an embodiment has been described in which accesses to the prefetched cache line and replacement candidate lines are tracked after the prefetched line is fetched into the prefetch buffer, other contemporaneous accesses may be tracked and used as a basis for selectively retiring the prefetched cache line, such as including accesses to candidate lines and/or the prefetched line between the time the need to prefetch is identified and the time the prefetched line arrives in the prefetch buffer. Additionally, reads, writes, snoops, and various access combinations thereof may be tracked for use in selectively retiring the prefetched cache line. That is, various heuristics may be embodied to determine whether the prefetched cache line or a replacement candidate line in the cache has a higher probability of being accessed in the future, which is more advantageous than the conventional method of unconditionally retiring the prefetched cache line into the cache. Finally, although the invention has been described with respect to prefetches generated by a miss of the cache, the invention is adaptable to use with any type of prefetch, such as a prefetch generated by a prefetch program instruction.  
         [0067]     In addition to implementations of the invention using hardware, the invention can be implemented in computer readable code (e.g., computer readable program code, data, etc.) embodied in a computer usable (e.g., readable) medium. The computer code causes the enablement of the functions or fabrication or both of the invention disclosed herein. For example, this can be accomplished through the use of general programming languages (e.g., C, C++, JAVA, and the like); GDSII databases; hardware description languages (HDL) including Verilog HDL, VHDL, Altera HDL (AHDL), and so on; or other programming and/or circuit (i.e., schematic) capture tools available in the art. The computer code can be disposed in any known computer usable (e.g., readable) medium including semiconductor memory, magnetic disk, optical disk (e.g., CD-ROM, DVD-ROM, and the like), and as a computer data signal embodied in a computer usable (e.g., readable) transmission medium (e.g., carrier wave or any other medium including digital, optical or analog-based medium). As such, the computer code can be transmitted over communication networks, including Internets and intranets. It is understood that the invention can be embodied in computer code (e.g., as part of an IP (intellectual property) core, such as a microprocessor core, or as a system-level design, such as a System on Chip (SOC)) and transformed to hardware as part of the production of integrated circuits. Also, the invention may be embodied as a combination of hardware and computer code.  
         [0068]     Those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiments as a basis for designing or modifying other structures for carrying out the same purposes of the present invention without departing from the spirit and scope of the invention as defined by the appended claims.