Abstract:
A microprocessor includes first and second cache memories occupying distinct hierarchy levels, the second backing the first. A prefetcher monitors load operations and maintains a recent history of the load operations from a cache line and determines whether the recent history indicates a clear direction. The prefetcher prefetches one or more cache lines into the first cache memory when the recent history indicates a clear direction and otherwise prefetches the one or more cache lines into the second cache memory. The prefetcher also determines whether the recent history indicates the load operations are large and, other things being equal, prefetches a greater number of cache lines when large than small. The prefetcher also determines whether the recent history indicates the load operations are received on consecutive clock cycles and, other things being equal, prefetches a greater number of cache lines when on consecutive clock cycles than not.

Description:
CROSS REFERENCE TO RELATED APPLICATION(S) 
       [0001]    This application claims priority based on U.S. Provisional Application Ser. No. 61/328,530, filed Apr. 27, 2010, entitled MULTI-MODAL DATA PREFETCHER, which is hereby incorporated by reference in its entirety. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The present invention relates in general to the field of microprocessors, and particularly to data prefetching therein. 
       BACKGROUND OF THE INVENTION 
       [0003]    The Intel® Core™ microarchitecture implements a hardware prefetcher (which has been referred to as the Data Cache Unit Prefetcher) which prefetches into the level-1 data (L1D) cache. Upon recognizing a pattern of loads within a cache line, the Data Cache Unit Prefetcher prefetches the next sequential cache line into the L1D cache. If each successive load was to a lower address than each previous address, the previous sequential cache line is prefetched. 
       BRIEF SUMMARY OF INVENTION 
       [0004]    In one aspect the present invention provides a microprocessor. The microprocessor includes first and second cache memories occupying distinct levels within a cache memory hierarchy of the microprocessor, wherein the second cache memory backs the first cache memory within the cache memory hierarchy. The microprocessor also includes a load unit configured to receive memory load operations. The microprocessor includes a data prefetcher coupled to the first and second cache memories. The data prefetcher is configured to monitor the load operations and maintain a recent history of the load operations from a cache line. The data prefetcher is also configured to determine whether the recent history indicates a clear direction of the load operations from the cache line. The data prefetcher is also configured to prefetch one or more cache lines into the first cache memory when the recent history indicates a clear direction and to prefetch the one or more cache lines into the second cache memory when the recent history does not indicate a clear direction. 
         [0005]    In another aspect, the present invention provides a method for prefetching data into a hierarchy of cache memories of a microprocessor, wherein the hierarchy includes first and second cache memories that occupy distinct levels within the hierarchy, wherein the second cache memory backs the first cache memory. The method includes monitoring memory load operations received by a load unit of the microprocessor and maintaining a recent history of the load operations from a cache line. The method also includes determining whether the recent history indicates a clear direction of the load operations from the cache line. The method also includes prefetching one or more cache lines into the first cache memory when the recent history indicates a clear direction and prefetching the one or more cache lines into the second cache memory when the recent history does not indicate a clear direction. 
         [0006]    In yet another aspect, the present invention provides a computer program product encoded in at least one computer readable medium for use with a computing device, the computer program product comprising computer readable program code embodied in said medium for specifying a microprocessor. The computer readable program code includes first program code for specifying first and second cache memories occupying distinct levels within a cache memory hierarchy of the microprocessor, wherein the second cache memory backs the first cache memory within the cache memory hierarchy. The computer readable program code also includes second program code for specifying a load unit, configured to receive memory load operations. The computer readable program code also includes third program code for specifying a data prefetcher, coupled to the first and second cache memories. The data prefetcher is configured to monitor the load operations and maintain a recent history of the load operations from a cache line. The data prefetcher is also configured to determine whether the recent history indicates a clear direction of the load operations from the cache line. The data prefetcher is also configured to prefetch one or more cache lines into the first cache memory when the recent history indicates a clear direction and to prefetch the one or more cache lines into the second cache memory when the recent history does not indicate a clear direction. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]      FIG. 1  is a block diagram illustrating a microprocessor having a data prefetcher according to the present invention. 
           [0008]      FIG. 2  is a flowchart illustrating operation of the microprocessor of  FIG. 1 . 
           [0009]      FIG. 3  is a block diagram illustrating a microprocessor having a data prefetcher according to an alternate embodiment of the present invention. 
           [0010]      FIG. 4  is a flowchart illustrating operation of the prefetcher of the alternate embodiment of  FIG. 3  to perform the operation at block  204  of  FIG. 2 . 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0011]    The present disclosure describes a prefetcher with additional prefetching modes over the scheme described above regarding the Intel Data Cache Unit Prefetcher. First, the prefetcher takes into account whether there is a clear load direction and if not, having less confidence, prefetches into the L2 cache rather than the L1D cache. Second, the prefetcher looks at how close together in time the loads to the same cache line occur. If they are relatively close together (e.g., on consecutive clock cycles), the prefetcher prefetches more cache lines than it otherwise would. Third, the prefetcher looks at the size of the loads. If they are relatively large, then the prefetcher prefetches more cache lines than it otherwise would. 
         [0012]    Referring now to  FIG. 1 , a block diagram illustrating a microprocessor  100  having a data prefetcher  136  according to the present invention is shown. The microprocessor  100  includes an instruction cache  102 , coupled to an instruction translator  112 , coupled to a register alias table (RAT)  116 , coupled to reservation stations  118 , coupled to a load unit  122 . The reservation stations  118  issue instructions to the load unit  122  (or other execution units, not shown) for execution potentially out of program order. A retire unit (not shown) includes a reorder buffer that enforces retirement of instructions in program order. The load unit  122  reads data from a level-1 data (L1D) cache  132 . A level-2 (L2) cache  134  backs the L1D cache  132  and the instruction cache  102 . The L2 cache  134  reads and writes system memory via a bus interface unit  126  that interfaces the microprocessor  100  to a bus, such as a local bus or memory bus. The microprocessor  100  also includes a data prefetcher  136 , or prefetch unit  136 , that prefetches data from system memory into the L2 cache  134  and L1D cache  132  as described in detail herein. 
         [0013]    The prefetcher  136  includes control logic  146 , which is coupled to control a history queue  142 , a cache line counter  162 , a clock cycle counter  148 , and a most recent previous clock cycle register  164 . The history queue  142  is a queue of entries  144 . Each queue entry  144  includes an address field  152 , a size field  154 , a consecutive field  156 , and a direction field  158 . The address field  152  stores the load address of the load operation for which the respective queue entry  144  was allocated. The size field  154  stores the size (number of bytes) of the load operation. The consecutive indicator  156  indicates whether the load operation was received by the prefetcher  136  on a consecutive clock cycle to the clock cycle in which the most recent previous load operation was received by the prefetcher  136 . The direction indicator  158  indicates the direction of the load relative to the most recent previous load. 
         [0014]    The cache line counter  162  counts the total number of loads to the current cache line since the prefetcher  136  began tracking accesses to the current cache line, as described below with respect to block  204  of  FIG. 2 . The clock cycle counter  148  increments each clock cycle of the microprocessor  100 . Thus, the value of the clock cycle counter  148  sampled by the control logic  146  when a load operation is received at block  204  may be used as an indicator of the clock cycle in which a new load was received relative to other contemporary loads and, more particularly, to determine whether two load operations were received on consecutive clock cycles in order to populate the consecutive indicator  156  of a queue entry  144 . The use of the clock cycle counter  148  and most recent previous clock cycle  164  register are described further below with respect to  FIG. 2 . 
         [0015]    Referring now to  FIG. 2 , a flowchart illustrating operation of the microprocessor  100  of  FIG. 1  is shown. Flow begins at block  202 . 
         [0016]    At block  202 , a new load operation arrives at the L1D cache  132  from the load unit  122 . The load operation specifies a load address specifying the location in memory from which to fetch the load data and the size of the data, e.g., 1, 2, 4, 8 or 16 bytes. Flow proceeds to block  204 . 
         [0017]    At block  204 , the prefetcher  136  snoops the L1D cache  132  to detect the new load operation and its relevant information. In response, the prefetcher  136  allocates an entry  144  in the history queue  142  and populates the entry  144 . In particular, the control logic  146  populates the address field  152  with the load address and populates the size field  154  with the load data size. Additionally, the control logic  146  reads the current value of the clock cycle counter  148  and the current value of the most recent previous clock cycle register  164  and compares them. If the current value of the clock cycle counter  148  is one more than the current value of the most recent previous clock cycle register  164 , the control logic  146  sets the value of the consecutive indicator  156  to indicate consecutive cycles; otherwise, the control logic  146  clears the value of the consecutive indicator  156  to indicate non-consecutive cycles. In an alternate embodiment, the control logic  146  sets the value of the consecutive indicator  156  to indicate consecutive cycles if the current value of the clock cycle counter  148  is N more than the current value of the most recent previous clock cycle register  164 , where N is a predetermined value; otherwise, the control logic  146  clears the consecutive indicator  156 . In one embodiment, N is two; however, the predetermined value is a design choice that may be made based on various factors, such as the size of the L1D cache  132  and/or L2 cache  134 . In one embodiment, the predetermined value is programmable via a model specific register (MSR) of the microprocessor  100 . After reading the value of the most recent previous clock cycle register  164 , the control logic  146  updates it with the value read from the clock cycle counter  148 . Additionally, the control logic  146  compares the load address with the address field  152  of the most recent previous load operation in the history queue  142  and populates the direction field  158  to indicate the direction of the new load operation relative to the most recent previous load operation. Additionally, the control logic  146  marks the entry valid by setting a valid bit (not shown) of the entry  144 . Additionally, the control logic  146  increments the cache line counter  162 . Furthermore, prior to allocating and populating and validating the allocated entry  144  and incrementing the cache line counter  162 , the control logic  146  determines whether the load address of the new load operation specifies a location within the same cache line as the other load operations in the history queue  142 ; if not, the control logic  146  invalidates all the entries  144  in the history queue  142  to begin accumulating history for the new current cache line implicated by the new load operation and clears the cache line counter  162 . Flow proceeds to block  206 . 
         [0018]    At block  206 , the prefetcher  136  recognizes a load access pattern within the current cache line implicated by the new load operation. In one embodiment, the prefetcher  136  recognizes a load access pattern within the current cache line when the value of the cache line counter  162  that was incremented at block  204  is greater than or equal to a predetermined value P. In one embodiment, P is four; however, the predetermined value is a design choice that may be made based on various factors, such as the size of the L1D cache  132  and/or L2 cache  134 . In one embodiment, the predetermined value is programmable via a model specific register (MSR) of the microprocessor  100 . Other methods for detecting a load access pattern within the current cache line may also be employed. Flow proceeds to decision block  208 . 
         [0019]    At block  208 , the prefetcher  136  determines whether there is a clear direction in the load access pattern. In one embodiment, the prefetcher  136  detects a clear direction if the direction indicators  158  of the valid queue entries  144  of the last at least D load operations indicate that they were in the same direction, where D is a predetermined value. In one embodiment, the predetermined value is three; however, the predetermined value is a design choice that may be made based on various factors, such as the size of the L1D cache  132  and/or L2 cache  134 . In one embodiment, the predetermined value is programmable via a model specific register (MSR) of the microprocessor  100 . An alternate embodiment is described below with respect to FIG.  3  in which the clear direction determination is made by another method. If the prefetcher  136  detects a clear direction, flow proceeds to decision block  218 ; otherwise, flow proceeds to decision block  212 . 
         [0020]    At decision block  212 , the prefetcher  136  determines whether the load operations to the current cache line are large. In one embodiment, the prefetcher  136  considers the load operations large if the size fields  154  of valid queue entries  144  indicate that all the loads are at least size Y, where Y is a predetermined value. In one embodiment, the predetermined value of Y is eight bytes; however, the predetermined value is a design choice that may be made based on various factors, such as the size of the L1D cache  132  and/or L2 cache  134 . In one embodiment, the predetermined value is programmable via a model specific register (MSR) of the microprocessor  100 . In an alternate embodiment, the prefetcher  136  considers the load operations large if a majority of the loads are at least size Y, which is determined by comparing two counters that keep track of the number of large and non-large loads, respectively, and which are updated at block  204 . If the loads are large, flow proceeds to block  214 ; otherwise, flow proceeds to block  216 . 
         [0021]    At block  214 , the prefetcher  136  prefetches the next two sequential cache lines into the L2 cache  134 . The prefetcher  136  prefetches into the L2 cache  134  rather than the L1D cache  132  if it determined at decision block  208  that there is no clear direction, because there is a lower confidence level that the prefetched data will actually be needed, therefore the prefetcher  136  is less willing to displace potentially useful data in the L1D cache  132 . Flow ends at block  214 . 
         [0022]    At block  216 , the prefetcher  136  prefetches only the next sequential cache line into the L2 cache  134 . Flow ends at block  216 . 
         [0023]    At decision block  218 , the prefetcher  136  determines whether the load operations to the current cache line are being received on consecutive clock cycles. Loads received on consecutive clock cycles implies that the program is walking through memory very quickly, so the prefetcher  136  needs to prefetch further ahead than it otherwise would in order to stay ahead of the program, i.e., in order to have future cache lines in the L1D cache  132  by the time the program needs them. In one embodiment, the prefetcher  136  considers the load operations as being received on consecutive clock cycles if the consecutive indicators  156  of the valid queue entries  144  of the most recent at least C loads from the current cache line are set, where C is a predetermined value. In one embodiment, the predetermined value of C is three; however, the predetermined value is a design choice that may be made based on various factors, such as the size of the L1D cache  132  and/or L2 cache  134 . In one embodiment, the predetermined value is programmable via a model specific register (MSR) of the microprocessor  100 . If the loads are on consecutive clock cycles, flow proceeds to decision block  232 ; otherwise, flow proceeds to decision block  222 . 
         [0024]    At decision block  222 , the prefetcher  136  determines whether the load operations to the current cache line are large, similar to the manner described above with respect to decision block  212 . If the loads are large, flow proceeds to block  224 ; otherwise, flow proceeds to block  226 . 
         [0025]    At block  224 , the prefetcher  136  prefetches the next two cache lines in the clear direction determined at block  208  into the L1D cache  132 . The prefetcher  136  prefetches into the L1D cache  132  rather than the L2 cache  134  if it determined at decision block  208  that there is a clear direction, because there is a higher confidence level that the prefetched data will actually be needed, therefore the prefetcher  136  is more willing to displace potentially useful data in the L1D cache  132 . Flow ends at block  224 . 
         [0026]    At block  226 , the prefetcher  136  prefetches only the next cache line in the clear direction determined at block  208  into the L1D cache  132 . Flow ends at block  226 . 
         [0027]    At decision block  232 , the prefetcher  136  determines whether the load operations to the current cache line are large, similar to the manner described above with respect to decision block  212 . If the loads are large, flow proceeds to block  234 ; otherwise, flow proceeds to block  236 . 
         [0028]    At block  234 , the prefetcher  136  prefetches the next three cache lines in the clear direction determined at block  208  into the L1D cache  132 . Flow ends at block  234 . 
         [0029]    At block  236 , the prefetcher  136  prefetches the next two cache lines in the clear direction determined at block  208  into the L1D cache  132 . Flow ends at block  236 . 
         [0030]    Referring now to  FIG. 3 , a block diagram illustrating a microprocessor  100  having a data prefetcher  136  according to an alternate embodiment of the present invention is shown. The prefetcher  136  of  FIG. 3  is similar to the prefetcher  136  of  FIG. 1  and operates similar to the manner described in the flowchart of  FIG. 2  with the following differences. The prefetcher  136  of  FIG. 3  updates the history information at block  204  and makes the clear direction decision at decision block  208  of  FIG. 2  differently as described below. The queue entries  144  of the history queue  142  of the embodiment of  FIG. 3  do not include a direction field  158 . Additionally, the prefetcher  136  includes a min pointer register  304  and a max pointer register  306  that the control logic  146  maintains to point to the lowest and highest address offset, respectively, within the current cache line that has been accessed since the prefetcher  136  began tracking accesses to the current cache line. The prefetcher  136  also includes a min change counter  308  and a max change counter  312  that count the number of changes to the min pointer  304  and the max pointer  306 , respectively, since the prefetcher  136  began tracking accesses to the current cache line. The operation of the prefetcher  136  at block  204  of  FIG. 2  according to the alternate embodiment of  FIG. 3  is as follows. The control logic  146  determines whether there is a clear direction by determining whether the difference between the min change counter  308  and the max change counter  312  is greater than a predetermined value. In one embodiment, the predetermined value is one; however, the predetermined value is a design choice that may be made based on various factors, such as the size of the L1D cache  132  and/or L2 cache  134 . In one embodiment, the predetermined value is programmable via a model specific register (MSR) of the microprocessor  100 . If the min change counter  308  is greater than the max change counter  312  by the predetermined amount, then the clear direction is downward; if the max change counter  312  is greater than the min change counter  308  by the predetermined amount, then the clear direction is upward; otherwise, there is no clear direction. Furthermore, if the load address of the new load operation does not specify a location within the same cache line as the other load operations in the history queue  142 , the control logic  146  clears the max change counter  312  and the min change counter  308 . 
         [0031]    Referring now to  FIG. 4 , a flowchart illustrating operation of the prefetcher  136  of the alternate embodiment of  FIG. 3  to perform the operation at block  204  of  FIG. 2  is shown. Flow begins at decision block  404 . 
         [0032]    At decision block  404 , the control logic  146  determines whether the new load address—more specifically, the new load address offset within the current cache line—is greater than the max pointer  306  value. If so, flow proceeds to block  406 ; otherwise, flow proceeds to decision block  408 . 
         [0033]    At block  406 , the control logic  146  updates the max pointer  306  with the new load address offset and increments the max change counter  312 . Flow ends at block  406 . 
         [0034]    At decision block  408 , the control logic  146  determines whether the new load address offset within the current cache line is less than the min pointer  304  value. If so, flow proceeds to block  412 ; otherwise, flow ends. 
         [0035]    At block  412 , the control logic  146  updates the min pointer  304  with the new load address offset and increments the min change counter  308 . Flow ends at block  412 . 
         [0036]    Although embodiments have been described above with respect to load operations, other embodiments are contemplated that perform similar prefetching with respect to store operations. 
         [0037]    While various embodiments of the present invention have been described herein, it should be understood that they have been presented by way of example, and not limitation. It will be apparent to persons skilled in the relevant computer arts that various changes in form and detail can be made therein without departing from the scope of the invention. For example, software can enable, for example, the function, fabrication, modeling, simulation, description and/or testing of the apparatus and methods described herein. This can be accomplished through the use of general programming languages (e.g., C, C++), hardware description languages (HDL) including Verilog HDL, VHDL, and so on, or other available programs. Such software can be disposed in any known computer usable medium such as magnetic tape, semiconductor, magnetic disk, or optical disc (e.g., CD-ROM, DVD-ROM, etc.), a network, wire line, or other communications medium. Embodiments of the apparatus and method described herein may be included in a semiconductor intellectual property core, such as a microprocessor core (e.g., embodied in HDL) and transformed to hardware in the production of integrated circuits. Additionally, the apparatus and methods described herein may be embodied as a combination of hardware and software. Thus, the present invention should not be limited by any of the exemplary embodiments described herein, but should be defined only in accordance with the following claims and their equivalents. Specifically, the present invention may be implemented within a microprocessor device which may be used in a general purpose computer. Finally, 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 scope of the invention as defined by the appended claims.