Patent Publication Number: US-2003233530-A1

Title: Enhanced instruction prefetch engine

Description:
BACKGROUND  
       [0001] 1. Field of the Invention  
       [0002] This invention relates generally to information processing systems, and more specifically to an information processing system comprising an instruction prefetch engine for prefetching instructions from slow memory to reduce or eliminate execution delays associated with memory latencies particularly when branch instructions are executed.  
       [0003] 2. Description of the Related Art  
       [0004] Improving processor performance is a continuing goal in the information processing industry. As we get closer to the limits of Moore&#39;s Law architectural approaches to speeding up processor speed become more desirable. One such approach is prefetching of instructions from a slow memory or storage device to a faster memory to improve system performance. It is also known in processor instruction execution, to predict the outcome of a branch instruction so that the instructions following the branch may be prefetched in parallel with the execution of the currently executing instructions. Prefetching is effective because processor speeds presently are faster than memory speeds. If the prefetch engine guesses (or predicts) the wrong branch, additional cycles will be required to fetch the required instructions on the correct branch. Therefore, there is a performance penalty when the branch prediction is incorrect. There is thus a need for a strategy that minimizes or eliminates these branch prediction performance penalties.  
       SUMMARY OF THE INVENTION  
       [0005] Briefly according to the invention, a method for prefetching instructions from a slower memory for storing them in a faster memory comprises the following: prefetching the instructions from a slower memory; recognizing an opcode corresponding to an unconditional branch instruction; continuing to prefetch at a target address of the unconditional branch instruction, responsive to recognizing the opcode corresponding to the unconditional branch instruction; recognizing an opcode corresponding to a conditional branch instruction; prefetching along each of the possible branches for the conditional branch instruction, responsive to recognizing the opcode corresponding to the conditional branch instruction; selecting a branch for execution from the possible branches of the conditional branch; and canceling prefetching of other possible branches not selected. 
     
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
     [0006]FIG. 1 is a block diagram of a known information-processing system wherein the invention can be advantageously used.  
     [0007]FIG. 2 is a block diagram illustrating the operation of an instruction prefetch system according to the prior art.  
     [0008]FIG. 3 shows the system of FIG. 1 modified to operate according to an embodiment of the invention.  
     [0009]FIG. 4 illustrates the system operation when the execution unit gets to the conditional branch and takes one path or the other according to an embodiment of the invention.  
     [0010]FIG. 5 illustrates the system operation when the prefetch engine encounters a conditional branch when it is already prefetching along multiple paths, according to an embodiment of the invention.  
     [0011]FIG. 6 illustrates system operation when the execution unit reaches a conditional branch and takes one of the branches.  
     [0012]FIG. 7 is a flow chart illustrating the operation of an instruction prefetch system according to an embodiment of the invention. 
    
    
     DETAILED DESCRIPTION  
     [0013] Referring to FIG. 1, there is shown a known information processing system  10  that can be modified to operate in accordance with an embodiment of the invention. The system  10  comprises a system processor  12 , a system memory  16  (e.g., DRAM, or dynamic random-access memory), a read-only memory or ROM  15 , and an I/O (input/output) subsystem  20 , all coupled by means of a system bus  22 . The processor includes an execution engine  13 , a prefetch engine  14  that prefetches (or copies) instructions stored in the slower memory  16  and stores them in a faster memory (instruction cache  18 ) so that the execution engine  13  of the processor  12  does not have to wait for instructions to be fetched from the slower memory  16 . The instructions copied into the instruction cache  18  may constitute an entire computer program or a portion thereof. The copied instructions  19  are a subset of the instructions  17  in DRAM  16 . Although the instruction prefetch engine  14  and the instruction cache are shown as part of the processor  12 , it is also possible to use another processing device or an external cache to implement the functionality discussed herein. Moreover the implementation of this functionality may be realized by using various combinations of software and hardware with close or equivalent performance. For example the invention may be implemented with a conventional processor executing instructions stored in a machine readable medium such as a CD ROM.  
     [0014] Referring to FIG. 2, when the prefetch engine  14  recognizes an operation code, or opcode (the part of a machine instruction that instructs the computer what to do, such as input, add or branch), corresponding to an unconditional branch instruction it continues to prefetch instructions at the target address of the unconditional branch instruction. The prefetch engine  14  creates a copy of the unconditional branch  24  in the faster cache  18  The execution engine  13  can then proceed to execute the instructions from the copy in the cache  18 . Cache  18  may also be used to temporarily store other instructions.  
     [0015] Referring to FIG. 3, the prefetch engine  14  reads instructions from the system memory  16  and when it recognizes an opcode corresponding to a conditional branch instruction  26  it prefetches instructions along each of the possible instruction branches and stores a copy of the branches in cache  18 .  
     [0016] Referring to FIG. 4, when the execution engine  13  gets to the conditional branch  26  and “takes” (i.e., executes the instructions along) one branch  28  or the other then according to an aspect of the invention, the prefetch engine  14  cancels prefetching on the branch  30  (or branches) not taken.  
     [0017] Referring to FIG. 5, depending on the “depth” of the instruction prefetch and the code being prefetched, the instruction prefetch engine  14  may encounter a conditional branch when it is already prefetching instructions along two (or more) branches. In this case the prefetched instructions would form a tree  32  and the instruction prefetch engine  14  would fetch instructions along each branch of the tree  32 . There will be a point of diminishing returns and it is probably not necessary to build an instruction prefetch engine that can simultaneously prefetch instructions along each of 1024 different branches, for example. But it may be useful to allow for the possibility of prefetching on up to 8 or 16 branches, for example. Thus it may be advantageous to maintain an array of 8 or 16 prefetch queues that get reused when old branches are canceled and new conditional branch instructions are encountered.  
     [0018] Referring to FIG. 6, when the execution unit  13  reaches a conditional branch and takes one of the branches, the prefetch engine cancels prefetching on the subtree for the branch not taken.  
     [0019] Since the prefetch engine may fetch instructions along multiple branches and since this could lead to memory contention problems and since it is not desired to unnecessarily slow down the execution of instructions that are making memory accesses, it is advantageous to have a priority scheme in which the processor&#39;s execution unit has a higher priority than the instruction prefetch unit in accessing memory.  
     [0020] The following pseudocode illustrates a possible implementation of the invention. Initially the prefetch engine is fetching along a single “live” “branch” 
                                  Do forever                         For each live branch in the instruction branch tree                         If there is room in the prefetch queue for this branch                         Fetch instruction for this branch from this branch&#39;s           “next address”           If the instruction is not a branch or a conditional           branch                         Increment this branch&#39;s “next address”                         Elseif the instruction is an unconditional branch                         Set “next address” for this branch = target           address of the unconditional branch                         Elseif the instruction is a conditional branch                         Increment this branch&#39;s “next address”           Create a new branch for the target address           Of the instruction                         }                         }                         }                 }       Create new branch (for some target address)       {                         If there are no unused prefetch queues                         Queue the create // it will be dequeued when another           branch is canceled                         Else {                         Allocate a new branch           In the parent branch, note the id of this new branch           // so when the parent branch is canceled, this branch can           //be canceled too           Set this branch&#39;s next address to the target address                         }                 }                  
 
     [0021] Referring to FIG. 7, there is shown a flow chart  100  illustrating at a high level, the operation of an instruction prefetch system according to an embodiment of the invention. The method comprises the following steps. In step  102 , the prefetch engine determines whether a given branch is active. If it is, the prefetch engine prefetches an instruction for this branch in step  104 . If not the prefetch engine doesn&#39;t do any prefetching for this branch. After the instruction is prefetched in step  104 , a check is made in step  106  to determine if the instruction is a branch instruction. If not, the next address for this branch is incremented in step  108  and control returns to step  102  as shown. If the check in step  106  determines that the instruction is a branch instruction, a check is made in step  110  to determine if the branch instruction is an unconditional branch instruction or a conditional branch instruction. If step  110  determines that the instruction is an unconditional branch instruction, the next address for this branch is, in step  112 , set equal to the target address of the branch instruction and control returns to step  102 . If, on the other hand, the check in step  110  determines that the instruction is a conditional branch instruction, then the prefetch engine will pursue multiple paths by incrementing the next address for the current branch in step  114  and creating a new branch (or branches) for the target address (or addresses) of the branch instruction in step  116 .  
     [0022] Other implementations are contemplated within the scope of the following claims.