Explore BrainMass

Branch Hazard

One type of pipeline hazard that can occur is a branch hazard.

a. Describe what a branch hazard is, and what causes a branch hazard.

b. Give a relevant example using the MIPS instruction set architecture. Compare and contrast how the code will proceed it the branch is taken, vs if the branch is not taken, and explain how this affects the pipeline.

c. Fully describe at least TWO of the techniques, OTHER than stalling, that can be used (in an attempt) to overcome branch hazards.

Solution Preview

a. A branch hazard occurs because the PC must begin fetch and decode of the next n instructions, where n is the number of cycles until the branch has been evaluated. If the branch were evaluated and forwarded in the 3rd cycle, there are two additional instruction issues that could be erroneous and have to be nullified, wasting clock cycles.

b. Assuming the simple 5 stage MIPS pipeline, and that the branch can be evaluated in the decode stage:

Loop: LD R1,R3(R5) ; Load the n*8th value in the array pointed at by R5
LD R2,R3(R6) ; Load the n*8th value in the array pointed at by R6
DADDU R4,R1,R4 ; Add R1 to R4
DADDU R4,R2,R4 ; Add R2 to R4
SUBI R3,R3,#8 ; Decrement the array counter
BNE R3,Loop ; If the end of the arrays has not been reached, do it again.
SD R4,0(R5) ; Store the data in the address pointed to by R5

If SD were to begin executing and not be nullified, the value of the 0th element of the array pointed to by R5 would be incorrect. If the SD were nullified, as will be the case, it is still a ...

Solution Summary

This solution discusses branch hazards in depth.