|
|
|
| Table 4.8 A static branch prediction strategy. |
| | Instruction Class | Instruction | Guessed Successful (S) | Guessed Unsuccessful (U) | | Unconditional branch | BR | Always* | Never | | Branch on Condition | BC
BCR | Never
Never | Always
Always | | Loop Control | BCT | Always | Never | | Call/Return | BAL
BALR | Always*
Always* | Never
Never | | *These are called ''known successful" branches. We ignore the case when the target is specified as the successor in-line instruction. |
|
|
| Table 4.9 Static branch prediction success rates (scientific environment). | | Instruction Class | Branch Instr % | | % Correct Guess | | BR unconditional | (72.5)(.20)=14.5 | | 14.5 | | BC conditional | (72.5)(.80)=58 | | (58)(.46)=27 | | Loop | (9.8) | | 9.8´.91=9 | | Call/Return | (17.7) | | 17.7 | | | | 68.2% |
|
|
|
|
|
|
related to the timely fetch of instructions, since the delay for a taken branch depends on the time required to fetch the branch target. |
|
|
|
|
|
|
|
|
Beyond the trivial fixed prediction, there are two classes of strategies for guessing whether or not a branch will be taken: a static strategy, which is based upon the type of branch instruction, and a dynamic strategy, which is based upon the recent history of branch activity. |
|
|
|
|
|
|
|
|
Even perfect prediction does not eliminate branch delay. Perfect prediction simply converts the delay for conditional branch into that for unconditional branch (branch taken). |
|
|
|
|
|
|
|
|
One static strategy is to make an early prediction of the outcome of the branch based on the particular branch opcode. When a branch is decoded, a guess is made on the outcome of the branch, and if it is determined that the branch will be successful, the pipeline fetches the target instruction stream and begins decoding from it. A simple approach using R/M instructions is shown in Table 4.8. |
|
|
|
|
|
|
|
|
The general effectiveness of a strategy described in Table 4.8 can be determined using R/M data from Tables 3.43.10. |
|
|
|
|
|
|
|
|
For a scientific environment, 26 out of 100 HLL operations are branches (Table 3.4). The branch frequency varies by architecture from 13% to 22%. In Table 4.9 we compute the success rate of the Table 4.8 static prediction strategy using Table 3.10. |
|
|
|
|
|
|
|
|
If we had used the Table 3.10 data to guess the most likely outcome, we would guess that conditional branches went to target (i.e., S). This "all S" strategy would have improved our prediction rate to about 72%. However, |
|
|
|
|
|