Assume that 20 percent of the dynamic count of the instructi

Assume that 20 percent of the dynamic count of the instructions executed for a program
are branch instructions. Assume further that 75 percent of branches are actually taken. The
program is executed in two different processors that have the same clock rate. One uses
static branch prediction with the assume-not-taken approach. The other uses dynamic
branch prediction based on the states in Figure 6.12a. The branch target buffer is used in
the manner described in Section 6.6.4.
(a) With no pipeline stalls due to other causes, what must be the minimum prediction
accuracy for the processor using dynamic branch prediction to perform at least as well as
the processor using static branch prediction?
(b) If the dynamic prediction accuracy is actually 90 percent, what is the speedup relative
to using static prediction

Solution

Two-way branching is usually implemented with a conditional jump instruction. A conditional jump can either be \"not taken\" and continue execution with the first branch of code which follows immediately after the conditional jump, or it can be \"taken\" and jump to a different place in program memory where the second branch of code is stored. It is not known for certain whether a conditional jump will be taken or not taken until the condition has been calculated and the conditional jump has passed the execution stage in the instruction pipeline
Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline. The branch predictor attempts to avoid this waste of time by trying to guess whether the conditional jump is most likely to be taken or not taken. The branch that is guessed to be the most likely is then fetched and speculatively executed. If it is later detected that the guess was wrong then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay.

The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. As a result, making a pipeline longer increases the need for a more advanced branch predictor.

b.Ans

A more complex form of static prediction assumes that backward branches will be taken, and forward-pointing branches will not be taken. A backward branch is one that has a target address that is lower than its own address. This technique can help with prediction accuracy of loops, which are usually backward-pointing branches, and are taken more often than not taken.

Some processors allow branch prediction hints to be inserted into the code to tell whether the static prediction should be taken or not taken. The Intel Pentium 4 accepts branch prediction hints while this feature is abandoned in later processors.[2]

Static prediction is used as a fall-back technique in some processors with dynamic branch prediction when there isn\'t any information for dynamic predictors to use. Both the Motorola MPC7450 (G4e) and the Intel Pentium 4 use this technique as a fall-back

A local branch predictor has a separate history buffer for each conditional jump instruction. It may use a two-level adaptive predictor. The history buffer is separate for each conditional jump instruction, while the pattern history table may be separate as well or it may be shared between all conditional jumps.

The Intel Pentium MMX, Pentium II and Pentium III have local branch predictors with a local 4-bit history and a local pattern history table with 16 entries for each conditional jump.

On the SPEC\'89 benchmarks, very large local predictors saturate at 97.1% correct.