Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-03-18
2002-12-24
Coleman, Eric (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S234000
Reexamination Certificate
active
06499101
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to the field of instruction execution in computers, and more particularly to an apparatus and method for predicting the outcome of branch instructions in a pipeline microprocessor.
2. Description of the Related Art
An application program for execution on a microprocessor consists of a structured series of macro instructions that are stored in sequential locations in memory. A current instruction pointer within the microprocessor points to the address of the instruction currently being executed and a next instruction pointer within the microprocessor points to the address of the next instruction for execution. During each clock cycle, the length of the current instruction is added to the contents of the current instruction pointer to form a pointer to a next sequential instruction in memory. The pointer to the next sequential instruction is provided to logic that updates the next instruction pointer. If the logic determines that the next sequential instruction is indeed required for execution, then the next instruction pointer is updated with the pointer to the next sequential instruction in memory. Thus, macro instructions are fetched from memory in sequence for execution by the microprocessor.
Obviously, because a microprocessor is designed to execute instructions from memory in the sequence that they are stored, it follows that a program configured to execute macro instructions sequentially from memory is one which will run efficiently on the microprocessor. For this reason, most application programs are designed to minimize the number of instances where macro instructions are executed out of sequence. These out-of-sequence instances are known as jumps, or branches.
A program branch presents a problem because most conventional microprocessors do not simply execute one instruction at a time. Rather, a present day microprocessor consists of a number of pipeline stages, each stage performing a specific function. Instructions, inputs, and results from one stage to the next are passed in synchronization with a pipeline clock. Hence, several instructions may be executing in different stages of the microprocessor pipeline within the same clock cycle. As a result, when logic within a given stage determines that a program branch is to occur, then previous stages of the pipeline, that is, stages that are executing instructions following in sequence, must be cast out to begin execution of sequential macro instructions beginning with the instruction directed by the branch, or the branch target instruction. This casting out of previous pipeline stages is known as flushing and refilling the pipeline.
A conditional branch is a branch that may or may not occur, depending upon an evaluation of some specified condition. And, this evaluation is typically performed in later stages of the microprocessor pipeline. To preclude wasting many clock cycles associated with flushing and refilling the pipeline, present day microprocessors also provide logic in an early pipeline stage that predicts whether a conditional branch will occur or not. If it is predicted that a conditional branch will occur, then only those instructions prior to the early pipeline stage must be flushed, including those in the instruction buffer. Even so, this is a drastic improvement; correctly predicted branches are executed in roughly two clock cycles. But an incorrect prediction takes many more cycles to execute than if no branch prediction mechanism had been provided in the first place. The accuracy of branch predictions in a pipeline processor therefore significantly impacts the processor's performance, for better or worse.
Yet, present day branch prediction techniques chiefly predict the outcome of a given conditional branch instruction in an application program based upon outcomes obtained when the conditional branch instruction was previously executed within the same instance of the application program. Historical branch prediction, or dynamic branch prediction, is effective because conditional branch instructions tend to exhibit repetitive outcome patterns when executed within an application program.
The historical outcome data is stored in a branch history table that is accessed using the address of a conditional branch instruction-a unique identifier for the instruction. A corresponding entry in the branch history table contains the historical outcome data associated with the conditional branch instruction. A dynamic prediction of the outcome of the conditional branch instruction is made based upon the contents of the corresponding entry in the branch history table.
Yet, because most present day microprocessors have address ranges on the order of gigabytes, it is not practical for a branch history table to be as large as the microprocessor's address range. Because of this, smaller branch history tables are provided, on the order of kilobytes, and only low order bits of a conditional branch instruction's address are used as an index into the table. But this presents another problem: because low order address bits are used to index the branch history table, two or more conditional branch instructions can index the same entry. This is known as aliasing. As such, the outcome of a more recently executed conditional branch instruction will replace the outcome of a formerly executed conditional branch instruction that is aliased to the same table entry. If the former conditional branch instruction is encountered again, its historical outcome information is unavailable to be used for a dynamic prediction.
Because dynamic predictions are sometimes not available, an alternative prediction is made for the outcome of a conditional branch instruction, usually based solely upon some static attribute of the instruction, such as the relative direction of a branch target instruction as compared to the address of the conditional branch instruction. This alternative prediction is called a static prediction because it is not based upon a changing execution environment within an application program. The static branch prediction is most often used as a fallback in lieu of a dynamic prediction. Hence, when a dynamic prediction is unavailable, the static prediction is used.
The present inventors have observed that the outcomes of some conditional branch instructions, when observed on pipeline microprocessor executing today's predominant desktop computer application programs, exhibit a bias toward one outcome or the other, totally as a function of static indicators such as the type of conditional test performed, regardless of historical outcome data associated with the instructions. These instructions are called biased outcome conditional branch instructions. And, it has also been observed that the entries in a branch history table associated with other conditional branch instructions that exhibit no such bias, are at times negatively impacted as a result of updates occurring from biased outcome instructions which are aliased to the same entries.
Thus, the accuracy of branch predictions is degraded on the whole in a microprocessor that allows the outcomes of biased conditional branch instructions to impact the historical outcome data for conditional branch instructions that do not exhibit a static bias.
Therefore, what is needed is an apparatus for predicting the outcomes of branch instructions that is more accurate than has heretofore been provided.
In addition, what is needed is a branch prediction mechanism in a microprocessor that favorably utilizes static indicators of a conditional branch instruction to predict its outcome.
Furthermore, what is needed is an apparatus in a microprocessor for predicting branches that eliminates the effects of outcomes of biased outcome conditional branch instructions on data regarding historical outcomes for unbiased outcome conditional branch instructions.
Moreover, what is needed is a method in a microprocessor for mandating that the microprocessor use a static branch prediction over a dynamic pr
Henry G. Glenn
Parks Terry
Coleman Eric
Huffman James W.
Huffman Richard K.
I.P. First L.L.C.
LandOfFree
Static branch prediction mechanism for 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 Static branch prediction mechanism for conditional branch..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Static branch prediction mechanism for conditional branch... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2988478