Tomasulo Algorithm eliminates name dependencies (WAW and WAR) Control dependencies still a problemIn long pipelines, branches may take many cycles before they reach the execute stages IF ID ALU WB MEM beq x y beq x beq squashed becomes a no-op NT T # a 2-bit predictor 0 0 0 1 prediction is taken 1 0 1 1 prediction is not taken 10 lowest bits of PC 0 1023 address of branches (PC) If everything is 0 in the table at the beginning, so it's predicted not taken.
Then, when that branch is run again, the table entry is updated to 01.
When the branch is run again, and it is taken, it is updated to 11.
This can be shown as:
NT → NT → T
This branch predictor is known as a local branch predictor.
# IF ID ALU WB MEM You are watching if the branch is taken/not taken 0 0 0 0 0 1 6-bit shift register 0 0 0 0 1 0 0 0 0 1 0 1 Watches if branches are taken or not and updates the shift register This register gets taken, and treated as a number. This time, you use the 6-bit GHR to index into a table a 2-bit predictor 0 0 0 1 prediction is taken 1 0 1 1 prediction is not taken 0 63 Global History Register (GHR) (On diagram, arrows show how to update the table based on actual branch outcomes)
# PC prediction Local BP GHR prediction Correlating Predictor PC which predictor Selector 0 0 0 1 local 1 0 1 1 correlating local correct correlating incorrect Update decrement selector local incorrect correlating correct increment selector local correct correlating correct leave it alone local incorrect correlating incorrect leave it alone