Can We Do Better?: Last-time and 2BC predictors exploit "last-time"predictability Realization 1: A branch's outcome can becorrelated with other branches' outcomes-Globalbranchcorrelation Realization 2: A branch's outcome can becorrelated with past outcomes of the same branch(other than the outcome of the branch "last-time'it was executed)- Local branch correlationComputerArchitecture26
Computer Architecture Can We Do Better? • Last-time and 2BC predictors exploit “last-time” predictability • Realization 1: A branch’s outcome can be correlated with other branches’ outcomes – Global branch correlation • Realization 2: A branch’s outcome can be correlated with past outcomes of the same branch (other than the outcome of the branch “last-time” it was executed) – Local branch correlation 26
Global Branch Correlation (T)Recently executed branch outcomes in theexecution path is correlated with the outcome ofthe next branchif(condi)if(condlANDcond2): If first branch not taken, second also not takenbranch Y:if (condl)a =2:branch X:if (a==0): If first branch taken, second definitely not takenComputerArchitecture27
Computer Architecture Global Branch Correlation (I) • Recently executed branch outcomes in the execution path is correlated with the outcome of the next branch • If first branch not taken, second also not taken • If first branch taken, second definitely not taken 27
Global Branch Correlation (II)branchY:if(condl)branchZ:if(cond2)branchX:if(condlANDcond2） If Y and Z both taken, then X also taken. If Y or Z not taken, then X also not takenComputerArchitecture28
Computer Architecture Global Branch Correlation (II) • If Y and Z both taken, then X also taken • If Y or Z not taken, then X also not taken 28
Global Branch Correlation (IIl)· Eqntott, SPEC 1992if (aa==2);; B1aa=0;if (bb==2); B2bb=0;; B3if (aa!=bb) 1If B1 is not taken (i.e.aa==0@B3)and B2 is not taken (i.e. bb=0@B3)thenB3iscertainlytakenComputerArchitecture29
Computer Architecture Global Branch Correlation (III) • Eqntoe, SPEC 1992 if (aa==2) ;; B1 aa=0; if (bb==2) ;; B2 bb=0; if (aa!=bb) { ;; B3 . } If B1 is not taken (i.e. aa==0@B3) and B2 is not taken (i.e. bb=0@B3) then B3 is certainly taken 29
Capturing Global Branch Correlationldea:Associatebranchoutcomeswith"globalT/NThistoryof all branchesMakeapredictionbasedontheoutcomeofthebranchthelast time the sameglobal branch history was encounteredImplementation:-Keeptrackofthe“globalT/NThistory"ofallbranchesinaregisterGlobal History Register (GHR)-UseGHRtoindexintoatableof thatrecordedtheoutcomethatwasseenforthatGHRvalueintherecentpastPatternHistoryTable(tableof2-bitcounters)Globalhistory/branchpredictorUses two levels of history (GHR + history at that GHR)ComputerArchitecture30
Computer Architecture Capturing Global Branch Correlation • Idea: Associate branch outcomes with “global T/NT history” of all branches • Make a predicLon based on the outcome of the branch the last Lme the same global branch history was encountered • ImplementaLon: – Keep track of the “global T/NT history” of all branches in a register à Global History Register (GHR) – Use GHR to index into a table of that recorded the outcome that was seen for that GHR value in the recent past à Paeern History Table (table of 2-bit counters) • Global history/branch predictor • Uses two levels of history (GHR + history at that GHR) 30