Abstract:
In a first aspect of the present invention, a method for prefetching instructions in a superscalar processor is disclosed. The method comprises the steps of fetching a set of instructions along a predicted path and prefetching a predetermined number of instructions if a low confidence branch is fetched and storing the predetermined number of instructions in a prefetch buffer. In a second aspect of the present invention, a system for prefetching instructions in a superscalar processor is disclosed. The system comprises a cache for fetching a set of instructions along a predicted path, a prefetching mechanism coupled to the cache for prefetching a predetermined number of instructions if a low confidence branch is fetched and a prefetch buffer coupled to the prefetching mechanism for storing the predetermined number of instructions. Through the use of the method and system in accordance with the present invention, existing prefetching algorithms are improved with minimal additional hardware cost.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates generally to superscalar processors and more particularly to a method and system for prefetching instructions in such a processor.  
         BACKGROUND OF THE INVENTION  
         [0002]    Instruction prefetching has been analyzed in great details over the years. Many of the proposed approaches require the keeping of a large table that indicates what cache line to prefetch when a particular address is being fetched. In highly speculative superscalar processors, instructions are prefetched from a path predicted by a branch prediction algorithm.  
           [0003]    To reduce memory access time, a memory subsystem is usually organized within the processor with multiple cache levels. In the memory hierarchy, the first level cache is the fastest but it is also the smallest in size. For instruction accesses, most microprocessors have a dedicated first level cache, called an instruction cache (IL1 cache). During execution, the IL1 cache is usually accessed at every cycle with a very short access time (1 cycle in most processors).  
           [0004]    Furthermore, optimization tools such as Feedback Directed Program Restructuring, (FDPR) restructures programs so that the most frequent paths of execution are laid out in the memory in sequential cache lines. This gives rise to the successful use of a simple instruction prefetching algorithm called Next Sequential Address (NSA). In this algorithm on an IL1 miss, the demand line is fetched with high priority and the next one (or more) sequential lines are “prefetched” with lower priority. Also, on a hit in the prefetch buffer, the next sequential line is prefetched. To prevent pollution of the IL1 cache with prefetched lines (since the prefetched lines may not be actually needed), the prefetched lines are stored in a separate area, called the “prefetch buffer”. Furthermore, to reduce memory traffic, before sending a prefetch request to the memory subsystem below IL1, the IL1 cache directory and the prefetch buffer is checked to see if the cache line already exists.  
           [0005]    Since the IL1 cache is usually small (often no more than 64 KB), significant IL1 cache misses occur for most workloads. On a IL1 cache miss, the execution pipeline is usually dry and the line is brought in from a lower level of the memory hierarchy with a much longer access time (for example, if the line is found in a lower level cache, the access time may be about 10 cycles). Consequently, IL1 cache misses are undesirable due to cache miss latency or the amount of time required to bring the line in from a lower level of the memory hierarchy.  
           [0006]    Accordingly, what is needed is an improved method and system for prefetching instructions in a superscalar processor. The method and system should be simple, cost effective and capable of being easily adapted to current technology. The present invention addresses such a need.  
         SUMMARY OF THE INVENTION  
         [0007]    In a first aspect of the present invention, a method for prefetching instructions in a superscalar processor is disclosed. The method comprises the steps of fetching a set of instructions along a predicted path and prefetching a predetermined number of instructions if a low confidence branch is fetched and storing the predetermined number of instructions in a prefetch buffer.  
           [0008]    In a second aspect of the present invention, a system for prefetching instructions in a superscalar processor is disclosed. The system comprises a cache for fetching a set of instructions along a predicted path, a prefetching mechanism coupled to the cache for prefetching a predetermined number of instructions if a low confidence branch is fetched and a prefetch buffer coupled to the prefetching mechanism for storing the predetermined number of instructions.  
           [0009]    Through the use of the method and system in accordance with the present invention, existing prefetching algorithms are improved with minimal additional hardware cost. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]    [0010]FIG. 1 is a high level block diagram of an illustrative embodiment of a processor for processing instructions and data in accordance with the present invention.  
         [0011]    [0011]FIG. 2 is a simple block diagram of the prefetching mechanism of the present invention.  
         [0012]    [0012]FIG. 3 is a flowchart of the method in accordance with the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0013]    The present invention relates to an improved method and system for prefetching instructions in a superscalar processor. The following description is presented to enable one of ordinary skill in the art to make and use the invention and is provided in the context of a patent application and its requirements. Various modifications to the preferred embodiment and the generic principles and features described herein will be readily apparent to those skilled in the art. Thus, the present invention is not intended to be limited to the embodiment shown but is to be accorded the widest scope consistent with he principles and features described herein.  
         [0014]    The present invention is present in the context of a preferred embodiment. The preferred embodiment of the present invention is a method and system for prefetching instructions in a superscalar processor. The method and system in accordance with the present invention prefetches instructions from the branches that are “difficult to predict” by a branch prediction algorithm. Most importantly, the method and system in accordance with the present invention prefetches cache lines that are needed after the misprediction of a difficult to predict branch. Accordingly, when a difficult to predict branch mispredicts, the needed cache lines are retrieved from the prefetch buffer, thus avoiding cache miss latency.  
         [0015]    Please refer now to FIG. 1. FIG. 1 is a high level block diagram of an illustrative embodiment of a processor, generally designated  10 , for processing instructions and data in accordance with the present invention. Processor  10  comprises a single integrated circuit superscalar processor, which, as discussed further below, includes various execution units, registers, buffers, memories, and other functional units that are all formed by integrated circuitry. As illustrated in FIG. 1, processor  10  may be coupled to other devices, such as a system memory  12  and a second processor  13 , by an interconnect fabric  14  to form a larger data processing system such as computer system.  
         [0016]    Processor  10  has an on-chip multi-level cache hierarchy including a unified level two (L2) cache  16  and bifurcated level one (L1) instruction (I) and data (D) caches  18  and  20 , respectively. As is well known to those skilled in the art, caches  16 ,  18  and  20  provide low latency access to cache lines corresponding to memory locations in system memory  12 .  
         [0017]    Instructions are fetched for processing from L1 I-cache  18  in response to the effective address (EA) residing in instruction fetch address register (IFAR)  30 . During each cycle, a new instruction fetch address may be loaded into IFAR  30  from one of three sources: branch prediction unit (BPU)  36 , which provides speculative path addresses resulting from the prediction of conditional branch instructions, group completion table (GCT)  38 , in completion unit (CU)  118  which provides non-speculative path addresses, and branch execution unit (BEU)  92 , which provides non-speculative addresses resulting from the resolution of incorrectly predicted conditional branch instructions. If hit/miss logic  22  determines, after translation of the EA contained in IFAR  30  by effective-to-real address translation (ERAT)  32  and lookup of the real address (RA) in I-cache directory  34 , that the cache line of instructions corresponding to the EA in IFAR  30  does not reside in L1 I-cache  18 , then hit/miss logic  22  provides the RA to L2 cache  16  as a request address via I-cache request bus  24 . Such request addresses may also be generated by prefetch logic within L2 cache  16  based upon recent access patterns. In response to a request address, L2 cache  16  outputs a cache line of instructions, which are loaded into prefetch buffer (PB)  28  and L1 I-cache reload bus  26 , possibly after passing through optional predecode logic  144 .  
         [0018]    Once the cache line specified by the EA in IFAR  30  resides in L1 cache  18 , L1 I-cache  18  outputs the cache line to both branch prediction unit (BPU)  36  and to instruction fetch buffer (IFB)  40 . BPU  36  scans the cache line of instructions for branch instructions and predicts the outcome of conditional branch instructions, if any. Following a branch prediction, BPU  36  furnishes a speculative instruction fetch address to IFAR  30 , as discussed above, and passes the prediction to branch instruction queue  64  so that the accuracy of the prediction can be determined when the conditional branch instruction is subsequently resolved by branch execution unit  92 .  
         [0019]    IFB  40  temporarily buffers the cache line of instructions received from L1 I-cache  18  until the cache line of instructions can be translated by instruction translation unit (ITU)  42 . In the illustrated embodiment of processor  10 , ITU  42  translates instructions from user instruction set architecture (UISA) instructions into a possibly different number of internal ISA (IISA) instructions that are directly executable by the execution units of processor  10 . Such translation may be performed, for example, by reference to microcode stored in a read-only memory (ROM) template. In at least some embodiments, the UISA-to-IISA translation results in a different number of IISA instructions than UISA instructions and/or IISA instructions of different lengths than corresponding UISA instructions. The resultant IISA instructions are then assigned by group completion table  38  to an instruction group, the members of which are permitted to be dispatched and executed out-of-order with respect to one another. Group completion table  38  tracks each instruction group for which execution has yet to be completed by at least one associated EA, which is preferably the EA of the oldest instruction in the instruction group.  
         [0020]    Following UISA-to-IISA instruction translation, instructions are dispatched to one of latches  44 ,  46 ,  48  and  50 , possibly out-of-order, based upon instruction types. That is, branch instructions and other condition register (CR) modifying instructions are dispatched to latch  44 , fixed-point and load-store instructions are dispatched to either of latches  46  and  48 , and floating-point instructions are dispatched to latch  50 . Each instruction requiring a rename register for temporarily storing execution results is then assigned one or more rename registers by the appropriate one of CR mapper  52 , link and count (LC) register mapper  54 , exception register (XER) mapper  56 , general-purpose register (GPR) mapper  58 , and floating-point register (FPR) mapper  60 .  
         [0021]    The dispatched instructions are then temporarily placed in an appropriate one of CR issue queue (CRIQ)  62 , branch issue queue (BIQ)  64 , fixed-point issue queues (FXIQs)  66  and  68 , and floating-point issue queues (FPIQs)  70  and  72 . From issue queues  62 ,  64 ,  66 ,  68 ,  70  and  72 , instructions can be issued opportunistically to the execution units of processor  10  for execution as long as data dependencies and antidependencies are observed. The instructions, however, are maintained in issue queues  62 - 72  until execution of the instructions is complete and the result data, if any, are written back, in case any of the instructions needs to be reissued.  
         [0022]    As illustrated, the execution units of processor  10  include a CR unit (CRU)  90  for executing CR-modifying instructions, a branch execution unit (BEU)  92  for executing branch instructions, two fixed-point units (FXUs)  94  and  100  for executing fixed-point instructions, two load-store units (LSUs)  96  and  98  for executing load and store instructions, and two floating-point units (FPUs)  102  and  104  for executing floating-point instructions. Each of execution units  90 - 104  is preferably implemented as an execution pipeline having a number of pipeline stages.  
         [0023]    During execution within one of execution units  90 - 104 , an instruction receives operands, if any, from one or more architected and/or rename registers within a register file coupled to the execution unit. When executing CR-modifying or CR-dependent instructions, CRU  90  and BEU  92  access the CR register file  80 , which in a preferred embodiment contains a CR and a number of CR rename registers that each comprise a number of distinct fields formed of one or more bits. Among these fields are LT, GT, and EQ fields that respectively indicate if a value (typically the result or operand of an instruction) is less than zero, greater zero, or equal to zero. Link and count register (LCR) register file  82  contains a count register (CTR), a link register (LR) and rename registers of each, by which BEU  92  may also resolve conditional branches to obtain a path address. General-purpose register files (GPRs)  84  and  86 , which are synchronized, duplicate register files, store fixed-point and integer values accessed and produced by FXUs  94  and  100  and LSUs  96  and  98 . Floating-point register file (FPR)  88 , which like GPRs  84  and  86  may also be implemented as duplicate sets of synchronized registers, contains floating-point values that result from the execution of floating-point instructions by FPUs  102  and  104  and floating-point load instructions by LSUs  96  and  98 .  
         [0024]    After an execution unit finishes execution of an instruction, the execution unit writes the result to the designated destination as specified by the instruction, removes the instruction from the issue queue, notifies CU  118 , which schedules completion of instructions in program order. To complete an instruction executed by one of CRU  90 , FXUs  94  and  100  or FPUs  102  and  104 , CU  118  signals the execution unit, which writes back the result data, if any, from the assigned rename register(s) to one or more architected registers within the appropriate register file. Once all instructions within its instruction group have completed, it is removed from GCT  38 . Other types of instructions, however, are completed differently.  
         [0025]    When BEU  92  resolves a conditional branch instruction and determines the path address of the execution path that should be taken, the path address is compared against the speculative path address predicted by BPU  36 . If the path addresses match, no further processing is required. If, however, the calculated path address does not match the predicted path address, BEU  92  supplies the correct path address to IFAR  30 . In either event, the branch instruction can then be removed from BIQ  64 , and when all other instructions within the same instruction group have completed, from GCT  38 .  
         [0026]    Following execution of a load instruction, the effective address computed by executing the load instruction is translated to a real address by a data ERAT (not illustrated) and then provided to L1 D-cache  20  as a request address. At this point, the load instruction is removed from FXIQ  66  or  68  and placed in load reorder queue (LRQ)  114  until the indicated load is performed. If the request address misses in L1 D-cache  20 , the request address is placed in load miss queue (LMQ)  116 , from which the requested data is retrieved from L2 cache  16 , and failing that, from another processor  13  or from system memory  12 . LRQ  114  snoops exclusive access requests (e.g., read-with-intent-to-modify), flushes or kills on interconnect fabric  14  against loads in flight, and if a hit occurs, cancels and reissues the load instruction.  
         [0027]    Store instructions are similarly completed utilizing a store queue (STQ)  110  into which effective addresses for stores are loaded following execution of the store instructions. From STQ  110 , data can be stored into either or both of L1 D-cache  20  and L2 cache  16 .  
         [0028]    As previously mentioned, the method and system in accordance with the present invention prefetches instructions from the branches that are “difficult to predict” by a branch prediction algorithm. Most importantly, the method and system in accordance with the present invention prefetches cache lines that are needed after the misprediction of a difficult to predict branch. Accordingly, when a difficult to predict branch mispredicts, the needed cache lines are retrieved from the prefetch buffer, thus avoiding cache miss latency.  
         [0029]    For a better understanding of the present invention, please refer now to FIG. 2. FIG. 2 is an illustration of the prefetch mechanism of a superscalar processing system in accordance with the present invention. It should be noted that elements shown in FIG. 2 that are common with FIG. 1 have the same reference numerals. Depicted in the illustration is the L2 Cache  16 , the I-Cache  18 , the Instruction Prefetch Buffer  28 , the Instruction Fetch Address Register (IFAR)  30 , a local branch history table (LBHT)  35 , a global branch history table (GBHT)  45 , a branch selector mechanism  55 , and Prefetch Request Determination Logic  65 . Each branch history table  35 ,  45  implements a branch prediction algorithm and are located in the branch prediction unit  36 . The mechanism also includes a confidence detection mechanism. The confidence detection mechanism includes a branch detection block  67  and an unconditional branch detection block  69  which are coupled to the ICache  18 . Each of the blocks  67  and  69  provide masks to a detection of the first low confidence branch in the predicted path block  77 . Block  77  in turn provides a signal to the prefetch request determination block  65 . The prefetch request determination block  65  also receives signals from a link stack block  73 , latches  71  and the ICache  18 . The latches  71  receive data from IFAR  30 . The output of the prefetch determination request logic  65  is a prefetch address and the number of cache lines to prefetch.  
         [0030]    The operation of these branch prediction mechanisms are described in more detail in U.S. patent application Ser. No. ______, entitled “Circuit System and Method for Performing Branch Prediction by Selectively Accessing Bimodal and Fetch Based Branch Industry Tables” filed on Nov. 3, 1999, and assigned to the assignee of this application and incorporated by reference herein. Each of the arrays of LBHT  35  and GBHT  45  require 2K lines at a time (that is, they need 11-bits to index). In a preferred embodiment, each of the lines includes 8-bits. Eight instructions at a time come out of the ICache  18 , each of which could be a conditional branch (in which case, we have predictions for each one of them). 8-bits from GSEL  55  determine which branch predictions out of the two methods should be used. If the GSEL  55  outcome is 11110000, then first four predictions are taken from GBHT  45  and the last four predictions are taken from the LBHT  35 . If GBHT  45  outcome is 11100000 and the LBHT  35  outcome is 00001001, then the “Combined branch prediction” is 11101001. These are the 8-bits shown as “Branch Prediction (8 b)” in the figure.  
         [0031]    Also included in the branch prediction unit  36  is the branch selector mechanism  55 . The IFAR  30  is used to index the I-Cache  18  and the Prefetch Buffer  28  and also helps in indexing the branch history tables  35 ,  45  and the branch selector mechanism  55 . The Prefetch Request Determination Logic  65  implements the requests to prefetch and store instructions based on the branch predictions.  
         [0032]    When instructions come out of the I-Cache  18  they are decoded to determine which one, if any, are conditional branches. In the case of a conditional branch, if the condition is true, the branch is a branch with a taken prediction. If the condition is not true, the branch is a branch with not-taken prediction. A taken prediction indicates that the instruction fetch should occur from the target of the branch. A not-taken prediction means that the next sequential instructions will be fetched.  
         [0033]    A typical branch prediction algorithm uses the two branch prediction algorithms employed by the two branch history tables  35 ,  45  to formulate a combined branch prediction  75 . The branch selector mechanism  55  determines which elementary branch prediction algorithm should be used to make the final prediction for a particular branch. For a majority of the branches, the two branch prediction algorithms agree. However, trace-based analysis shows that the branches for which the two prediction algorithms disagree are the “difficult to predict” branches. These branches will be referred to here as “low confidence” branches.  
         [0034]    In accordance with the prefetching algorithm of the present invention, a predetermined number of cache lines are prefetched and stored in the prefetch buffer  28  when a “low confidence” branch is fetched. By storing a predetermined number of cache lines in the prefetch buffer  28  when a “low confidence” branch is fetched, cache miss latency that occurs immediately following a branch misprediction is avoided since the cache lines that are needed after a branch misprediction, are already stored in the prefetch buffer  28 .  
         [0035]    A detection of the first “low confidence” branch is provided by the predicted path block  77 . IFAR bits 59:61 indicates where in the sector the actual instructions start. When the “conditional branch mask” signal is ANDed with the “branch prediction” signal and then OR the result with the “unconditional branch mask” signal, an 8-bit vector is provided. If there is a 1 in this vector at or after the “actual instructions” start, then we have a taken branch in the predicted path and no other instructions after the position where the first 1 appeared are in the predicted path. For example, if IFAR (59:61)=001, then actual instructions start at position 2. If the “conditional branch mask” is 00100010, and the branch prediction is 00000111, then we have two conditional branches (in position 3 rd  and 7 th ) and the branch in 3 rd  position is predicted not-taken and in the 7 th  position is predicted taken. If the “unconditional branch mask” is 00000001, then we have the final result after the AND and OR operation as 00000011. So the actual instructions (in the predicted path starts at position 1 and ends at position 7). So the vector representing the “actual instructions” is 01111110 (that is, instructions at position 1 through 7 are in the predicted path). The next problem is to determine if there is any conditional branch instructions among the actual instructions that is predicted with “low confidence”.  
         [0036]    Two 8-bit vectors come out of the LBHT  35  and GBHT  45  arrays, including branch predictions for two different methods. If the vectors differ in any of the positions, then a conditional branch in that position (if any) is considered to be predicted with “low confidence”. In the above example, the vectors from LBHT  35 , GBHT  45  and GSEL  55  arrays are: 00100111, 00000111 and 00111111. This makes the final “branch prediction” to be 00000111 (as mentioned before). Since the local and global predictions for the conditional branch in the third position differs, this branch is predicted to be “not-taken” with low confidence.  
         [0037]    The information that there is a “low confidence” branch in the predicted path and its position is sent to the block “Prefetch request determination logic”.  
         [0038]    To better understand the prefetching algorithm in accordance with the present invention, please refer to FIG. 3. FIG. 3 is a flowchart of the prefetching algorithm in accordance with the present invention. First, a set of instructions along a predicted path is fetched, via step  200 . Preferably, the path is selected by the branch selector mechanism based on a combined branch prediction by the two branch history tables. Next, a predetermined number of instructions are prefetched if a “low confidence” branch is fetched in step  200 , via step  202 . Preferably, the Prefetch Request Determination Logic implements step  202 . Also, the predetermined number of instructions can be  1 ,  2 , etc. Finally, the prefetched instructions are stored in a prefetch buffer, via step  204 .  
         [0039]    Preferably the predetermined number of instructions are prefetched in step  202  based on the following conditions:  
         [0040]    1) If there is no cache miss and a “low confidence” branch is fetched with taken prediction, then prefetch the predetermined number of sequential lines from the not-taken path.  
         [0041]    2) If there is no cache miss and a “low confidence” branch is fetched with not-taken prediction, then prefetch the predetermined number of sequential cache lines from the taken path.  
         [0042]    3) If there is a cache miss and a “low confidence” branch is fetched from the missed cache line (after the miss has been serviced), then prefetch a predetermined number of cache lines from the not-taken path and a predetermined number of sequential cache lines from the taken path.  
         [0043]    4) If no “low-confidence” branch has been fetched, a traditional prefetching algorithm is used, such as if there is a cache miss for a given cache line, then a predetermined member of next sequential cache lines are prefetched (i.e. an NSA algorithm).  
         [0044]    In accordance with the present invention, when the “low confidence” branch is executed, if it turns out to be mispredicted, then the instructions from the actual path of execution will be found in the prefetch buffer based on the prefetching algorithm. These instructions are then forwarded down the pipeline, thus avoiding a cache miss penalty.  
         [0045]    Although the present invention has been described in accordance with the embodiments shown, one of ordinary skill in the art will readily recognize that there could be variations to the embodiments and those variations would be within the spirit and scope of the present invention. Accordingly, many modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the appended claims.