Branch Prediction

Branch Prediction

• Branch prediction is a key hardware technique used in modern processors to increase Instruction‒Level Parallelism (ILP) by reducing the performance loss caused by control hazards. Control hazards occur when the flow of execution changes due to branch instructions (e.g., if‒else, loops, function calls). Since the target of a branch may not be known until its execution stage, the processor might have to stall, wasting cycles. Branch prediction solves this problem by guessing the outcome of the branch before it is resolved.

• Prediction techniques can be used to check whether a branch will be valid or not valid. These techniques reduce the branch penalty.

• The common prediction techniques are :

■ Predict never taken

■ Predict always taken

■ Predict by opcode

■ Taken/Not taken switch

■ Branch history table

• In the first two approaches if prediction is wrong a page fault or protection violation error occurs. The processor then halts prefetching and fetches the instruction from the desired address.

• In the third prediction technique, the prediction decision is based on the opcode of the branch instruction. The processor assumes that the branch will be taken from certain branch opcodes and not for others.

• The fourth and fifth prediction techniques are dynamic; they depend on the execution history of the previously executed conditional branch instruction.

Branch prediction strategies

• There are two types of branch prediction strategies :

■ Static branch strategy.

■ Dynamic branch strategy.

Static branch strategy: In this strategy branch can be predicted based on branch code types statically. This means that the probability of branch with respect to a particular branch instruction type is used to predict the branch. This branch strategy may not produce accurate results every time.

Dynamic branch strategy: This strategy uses recent branch history during program execution to predict whether or not the branch will be taken next time when it occurs. It uses recent branch information to predict the next branch. The recent branch information includes branch prediction statistics such as:

T : Branch taken

N : Not taken

NN : Last two branches not taken

NT : Not branch taken and previous takes

TT : Both last two branch taken

TN : Last branch taken and previous not taken

• The recent branch information is stored in the buffer called Branch Target Buffer (BTB).

• Along with above information branch target buffer also stores the address of branch target.

• Fig. 3.12.4 shows the organization of branch target buffer.

• Fig. 3.12.5 shows a typical state diagram used in dynamic branch prediction.

• This state diagram allows the backtracking of last two instructions in a given program. The branch target buffer entry contains the backtracking information which guides the prediction.

• The prediction information is updated upon completion of the current branch.

• To make branch overhead zero, the branch target buffer is extended to store the target instruction itself and a few of its successor instructions. This allows processing of conditional branches with zero delay.

Example: 1

The following sequence of instructions are executed in the basic 5‒stage pipelined processor :

lw$1, 40($6)

add $6, $2, $2

sw $6, 50($1)

Indicate dependence and their type. Assuming there is no forwarding in this pipelined processor, indicate hazards and add NOP instructions to eliminate them.

Solution:

a) I1: 1w $1, 40($6): Raw dependency on $1 from I1 to I3

I2: add $6, $2, $2: Raw dependency on $6 from I2 to I3

I3: sw $6,50 ($1) : WAR dependancy on $6 from I1 to I2 and I3

b) In the basic five‒stage pipeline WAR dependency does not cause any hazards. Assuming there is no forwarding in this pipelined processor RAW dependencies cause hazards – if register read happens in the second half of the clock cycle and the register write happens in the first half. The code that eliminates these hazards by inserting nop instruction is:

1w $1, 40($6)

add $6, $2, $2

nop; delay 13 to avoid RAW hazard on $1 from I1

sw $6,50($1)

Example: 2

A processor has five individual stages, namely, IF, ID, EX, MEM and WB and their latencies are 250 ps, 350 ps, 150 ps, 300 ps, and 200 ps respectively. The frequency of the instructions executed by the processor are as follows; ALU: 40%, Branch 25 % load: 20% and store 15%. What is the clock cycle time in a pipelined and non‒pipelined processor? If you can split one stage of the pipelined datapath into two new stages, each with half the latency of the original stage, which stage would you split and what is the new clock cycle time of the processor? Assuming there are no stalls or hazards, what is the utilization of the data memory? Assuming there are no stalls or hazards, what is the utilization of the write register port of the "Registers" unit?

Solution:

a) Clock cycle time in a pipelined processor = 350 ps

Clock cycle time in non‒pipelined processor

= 250 ps + 350 ps + 150 ps + 300 ps + 200 ps = 1250 ps

b) We have to split one stage of the pipelined datapath which has a maximum latency

i.e. ID.

After splitting ID stage with latencies ID1 = 175 ps and ID2 = 175 ps we have new clock cycle time of the processor equal to 300 ps

c) Assuming there are no stalls or hazards, the utilization of the data memory

= 20% to 15% = 35 %

d) Assuming there are no stalls or hazards, the utilization of the write ‒ register port of the register unit = 40% +25% = 65%

Review Question

1.What is branch prediction?