Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-12-02
2001-05-08
Pan, Daniel H. (Department: 2171)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S239000, C712S001000, C717S152000
Reexamination Certificate
active
06230261
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to the field of microprocessors, and more particularly to a method and apparatus for performing branch prediction based on branch instruction test type.
2. Description of the Related Art
Computer instructions are typically stored in successive addressable locations within a memory. When processed by a Central Processing Unit (CPU), the instructions are fetched from consecutive memory locations and executed. Each time an instruction is fetched from memory, a program counter within the CPU is incremented so that it contains the address of the next instruction in the sequence. This is the next sequential instruction pointer, or NSIP. Fetching of an instruction, incrementing of the program counter, and execution of the instruction continues linearly through memory until a program control instruction is encountered.
A program control instruction, when executed, changes the address in the program counter and causes the flow of control to be altered. In other words, program control instructions specify conditions for altering the contents of the program counter. The change in the value of the program counter as a result of the execution of a program control instruction causes a break in the sequence of instruction execution. This is an important feature in digital computers, as it provides control over the flow of program execution and a capability for branching to different portions of a program. Examples of program control instructions include Jump, Test and Jump conditionally, Call, and Return.
A Jump instruction causes the CPU to unconditionally change the contents of the program counter to a specific value, i.e., to the target address for the instruction where the program is to continue execution. A Test and Jump conditionally causes the CPU to test the contents of a status register, or possibly compare two values, and either continue sequential execution or jump to a new address, called the target address, based on the outcome of the test or comparison. A Call instruction causes the CPU to unconditionally jump to a new target address, but also saves the value of the program counter to allow the CPU to return to the program location it is leaving. A Return instruction causes the CPU to retrieve the value of the program counter that was saved by the last Call instruction, and return program flow back to the retrieved instruction address.
In early microprocessors, execution of program control instructions did not impose significant processing delays because such microprocessors were designed to execute only one instruction at a time. If the instruction being executed was a program control instruction, by the end of execution the microprocessor would know whether it should branch, and if it was supposed to branch, it would know the target address of the branch. Thus, whether the next instruction was sequential, or the result of a branch, it would be fetched and executed.
Modern microprocessors are not so simple. Rather, it is common for modern microprocessors to operate on several instructions at the same time, within different blocks or pipeline stages of the microprocessor. As instructions are fetched, they are introduced into one end of the pipeline. They proceed through pipeline stages within a microprocessor until they complete execution. In such pipelined microprocessors it is often not known whether a branch instruction will alter program flow until it reaches a late stage in the pipeline. But, by this time, the microprocessor has already fetched other instructions and is executing them in earlier stages of the pipeline. If a branch causes a change in program flow, all of the instructions in the pipeline that followed the branch must be thrown out. In addition, the instruction specified by the target address of the branch instruction must be fetched. Throwing out the intermediate instructions, and fetching the instruction at the target address creates processing delays in such microprocessors.
To alleviate this delay problem, many pipelined microprocessors use branch prediction mechanisms in an early stage of the pipeline that predict the outcome of branch instructions, and then fetch subsequent instructions according to the branch prediction. Branch prediction schemes are commonly classified as either static or dynamic branch prediction schemes. With a static branch predictor, the prediction remains the same for a given branch instruction throughout the entire execution of the program in which the branch instruction is contained. That is, if the static branch predictor predicts a given branch will be taken the first time the branch instruction is executed, the static branch predictor will predict the branch will be taken every time the branch instruction is executed throughout the execution of the program. Thus, the prediction made by a static branch predictor does not depend upon the dynamic behavior of the branch instruction.
In contrast, dynamic branch predictors keep a history of the outcome of branch instructions as a program executes and make predictions based upon the history. Thus, one time a given branch instruction executes the dynamic branch predictor may predict the branch will be taken. But the next time the branch instruction executes, the dynamic branch predictor may predict the branch will not be taken, particularly if the branch was not taken the previous time.
Static branch prediction is typically performed in one of two ways. The first type of static branch prediction is commonly referred to as software branch prediction. “Software branch-prediction predicts branches statically by annotating the program with prediction information (such as setting a bit in a branch instruction to indicate the outcome of the branch) and relies on the fact that the outcome of a branch usually favors one possible outcome over the other. The favored outcome is determined by measuring an instruction trace or by making a reasonable guess based on program context (for example, loop branches are likely to be taken more often than not).”
Superscalar Microprocessor Design,
Mike Johnson, 1991, Prentice-Hall, Inc., p. 63.
For example, many software branch prediction schemes rely on a profiling compiler. First the target program is compiled without branch prediction or with default branch prediction. It is then executed one or more times and statistics are gathered about the outcome history of the various branches in the program. Then the program is recompiled using the statistics gathered. During the recompile, the compiler sets a bit in the branch instructions to indicate what the outcome of the branch is most likely to be. When the re-compiled program executes, the microprocessor uses the bit to predict branch outcomes. This type of scheme may only be employed on microprocessors that include hardware for examining the bit set by the profiling compiler.
Another static branch prediction scheme that has been employed is referred to as the BTFNT (Backwards Taken, Forward Not Taken) static branch prediction scheme. See “A System Level Perspective on Branch Architecture Performance”, by Brad Calder, Dirk Grunwald and Joel Emer, from Proceedings of MICRO-28, Nov. 29-Dec. 1, 1995 at Ann Arbor, Mich., pp. 202-203. BTNFT branch prediction is premised upon the observation that historically approximately 80-90% of backward jumps are taken. This observation recognizes the presence of loops that are common in many programs. In this scheme, the static branch predictor examines the branch instruction and determines whether the direction of the target address of the branch is backward or forward relative to the location of branch instruction itself. For example, if the branch instruction is at address 0x34710 and the target address of the branch instruction is 0x34704, then the BTFNT scheme predicts the branch will be taken. If the target address is 0x34718, then the BTFNT scheme predicts the branch will not be taken.
Some branch instructions employ a signed displacement that is added to the processor's
Henry G. Glenn
Parks Terry
Chen Te Yu
Davis E. Alan
Huffman James W.
I. P. First, L.L.C.
Pan Daniel H.
LandOfFree
Method and apparatus for predicting conditional branch... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for predicting conditional branch..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for predicting conditional branch... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2515703