【正文】 UCB Pitfall: Sometimes dumber is better ? Alpha 21264 uses tournament predictor (29 Kbits) ? Earlier 21164 uses a simple 2bit predictor with 2K entries (or a total of 4 Kbits) ? SPEC95 benchmarks, 21264 outperforms ? 21264 avg. mispredictions per 1000 instructions ?21164 avg. mispredictions per 1000 instructions ? Reversed for transaction processing (TP) ! ? 21264 avg. 17 mispredictions per 1000 instructions ?21164 avg. 15 mispredictions per 1000 instructions ? TP code much larger amp。 Add hints to be used at runtime ? Also, predict statically ? Branch folding 187。 UCB ?Avoid branch prediction by turning branches into conditionally executed instructions: if (x) then A = B op C else NOP ?If false, then neither store result nor cause interference ?Expanded ISA of Alpha, MIPS, PowerPC, SPARC have conditional move。 UCB Branch Target “Cache” ? Branch Target cache Only predicted taken branches ? “Cache” Content Addressable Memory (CAM) or Associative Memory (see figure) ? Use a big Branch History Table amp。 UCB 94% 96% 98% 98% 97% 100% 70% 82% 77% 82% 84% 99% 88% 86% 88% 86% 95% 99% 0% 20% 40% 60% 80% 100% gcc espresso li fpppp doduc tomcatv Profilebased 2bit counter Tournament Accuracy of Branch Prediction ? Profile: branch profile from last execution (static in that is encoded in instruction, but profile) fig Copyright 2020 UCB amp。 ith bit is 1 = ith prior branch taken。 Man Kaufmann ECE668 .13 Adapted from Patterson, Katz and Culler 169。 Man Kaufmann ECE668 .9 Adapted from Patterson, Katz and Culler 169。 UCB ?Better Solution: 2bit scheme: ?Red: stop, not taken ?Green: go, taken 2bit Branch Prediction Scheme 1 T T N Predict Taken Predict Not Taken Predict Taken Predict Not Taken T N T N N T* T*N N* N*T (Jim Smith, 1981) Copyright 2020 UCB amp。 Computer Engineering Computer Architecture ECE 668 Dynamic Branch Prediction Copyright 2020 UCB amp。 Man Kaufmann ECE668 .2 Adapted from Patterson, Katz and Culler 169。 Man Kaufmann ECE668 .6 Adapted from Patterson, Katz and Culler 169。 UCB Further Comparison ?Alternating taken / nottaken ?Your worstcase prediction scenario ?Both schemes achieve 8095% accuracy with only a small difference in behavior T T N T N T N N T* T*N N* N*T T T N T N T N N T* T*N N* N*T 1 2 Copyright 2020 UCB amp。 UCB Gselect and Gshare predictors ? Keep a global register (GR) with oute of k branches ? Use that in conjunction with PC to index into a table containing 2bit predictor ? Gselect – concatenate ? Gshare – XOR (better) Copyright 2020 CAM / P HTg l o b a l b r a n c h h i s t o r yr e g i s t e r ( G B H R )/d e c o d e2p r e d i c t :t a k e n /n o t t a