Complete course notes

Page 1

Branch Prediction Techniques Conditional branches in 5-stage MIPS pipeline: • Branch Outcome (BO) and Branch Target Address (BTA) ready at the end of the EX stage (3rd stage) • Conditional branches solved when PC is updated at the end of the ME stage (4th stage) Control Hazard: attempt to decide which is the next instruction to fetch before the branch condition is evaluated • Arise from the pipelining of conditional branches and other instructions changing the PC • Reduce the performance from the ideal speedup gained by the pipelining since they can make it necessary to stall the pipeline • To feed the pipeline we need to fetch a new instruction at each clock cycle, but the branch decision (to change or not change the PC) is taken during the ME stage • If a branch changes the PC to its target address, it is a Taken (T) branch • If a branch falls through, it is Not Taken (NT) Conservative Assumption Conservative Assumption: stall the pipeline until the branch decision is taken and then fetch the correct instruction • Without forwarding: 3 clock cycles stall • With forwarding: 2 clock cycles stall We can assume branch NT and flush the next 3 instructions in the pipeline only if the branch will be taken. We cannot assume the branch T because we don’t know the BTA PC Early Evaluation Add HW resources to: • Compare registers to derive the BO • Compute the BTA • Update PC during ID stage NO FORWARDING FORWARDING LOAD FOLLOWED BY BRANCH 2 stalls before ID stage of branch to enable forwarding ME→ID + 1 stall after the branch for branch resolution ALU FOLLOWED BY BRANCH 1 stall before ID stage of branch to enable the forwarding EX→ID +1 stall after the branch for branch resolution Static Branch Prediction Techniques Actions for a branch are fixed for each branch during the…