Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-12-02
2001-06-12
Pan, Daniel H. (Department: 2171)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S224000, C712S023000
Reexamination Certificate
active
06247122
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 by combining static and dynamic branch predictors.
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. Hennessy and Patterson define pipelining as, “an implementation technique whereby multiple instructions are overlapped in execution.”
Computer Architecture: A Ouantitative Approach,
2
nd
edition, by John L. Hennessy and David A. Patterson, Morgan Kaufmann Publishers, San Francisco, Calif., 1996. The authors go on to provide the following excellent illustration of pipelining:
A pipeline is like an assembly line. In an automobile assembly line, there are many steps, each contributing something to the construction of the car. Each step operates in parallel with the other steps, though on a different car. In a computer pipeline, each step in the pipeline completes a part of an instruction. Like the assembly line, different steps are completing different parts of the different instructions in parallel. Each of these steps is called a pipe stage or a pipe segment. The stages are connected one to the next to form a pipe—instructions enter at one end, progress through the stages, and exit at the other end, just as cars would in an assembly line.
Thus, 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.
A popular branch prediction scheme uses a branch history table (BHT), or prediction history table (PHT) to make predictions about conditional branch instruction outcomes. One simple BHT is an array of single bits. Each bit stores the last outcome of a branch instruction. For example, the bit stores a 1 if the branch was taken the last time it was executed and a 0 if the branch was not taken the last time it was executed.
The array is indexed by the address of the branch instruction. To make a prediction for a branch instruction, a branch predictor takes the address of the branch instruction and outputs the bit from the array entry selected by the address. Thus, the prediction for a given execution of a branch instruction is the outcome of the previous execution of the branch instruction. After the branch instruction executes (i.e., once the microprocessor resolves whether the branch is taken or not) the bit indexed by the branch instruction address is updated with the actual branch instruction outcome. A branch prediction mechanism such as a branch history table is commonly referred to as a dynamic branch prediction mechanism because it keeps a history of the outcome of branch instructions as a program executes and makes predictions based upon the history.
Many computer systems today have memory address ranges on the order of gigabytes. It is not practical for the BHT to be as large as the memory space of the system in which the microprocessor operates. Common BHT sizes are 1KB to 4KB. Therefore, only a portion of the address branch instruction is used to index into the BHT. Typically, the lower address bits are used as the index. Consequently, sometimes two or more branch instructions will index into the same location in the BHT. This phenomenon is commonly referred to as aliasing. This is a similar phenomenon that occurs in caches. However, most BHT's do not have cache tags and sets. Therefore, the outcome of the newer branch will replace the outcome of the older branch. This may be detrimental if the older branch executes next, rather than the newer branch.
The aliasing phenomenon is also referred to as PHT interference, since the outcome of one branch is interfering with the subsequent prediction of another completely unrelated branch. See Eric Spangle, Robert S. Chappell, Mitch Alsup, Yale N. Patt, “The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference”, Proceedings of the 24th International Symposium on Computer Architecture, Denver, June 1997, which is hereby incorporated by reference.
Spangle defines interference as “a branch accessing a PHT entry that was previously updated by a different branch.” He notes that interference may be positive, negative or
Henry G. Glenn
Parks Terry
Chen Ye Ya
Davis E. Alan
Huffman James W.
IP-First L.L.C.
Pan Daniel H.
LandOfFree
Method and apparatus for performing branch prediction... 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 performing branch prediction..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing branch prediction... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2467500