【正文】 Adapted from Patterson, Katz and Culler 169。 UCB Dynamic Branch Prediction ?Performance = ?(accuracy, cost of misprediction) ?Branch History Table (BHT): Lower bits of PC address index table of 1bit values ? Says whether or not branch taken last time ( TTaken, N ) ?No full address check (saves HW, but may be wrong) ?Problem: in a loop, 1bit BHT will cause 2 mispredictions (avg is 9 iterations before exit): ? End of loop case, when it exits instead of looping as before ?First time through loop on next time through code, when it predicts exit instead of looping ?Only % accuracy if 9 iterations per loop on average . . . TTT T N N T TT . . . Copyright 2020 UCB amp。 Man Kaufmann ECE668 .12 Adapted from Patterson, Katz and Culler 169。 UCB % of predictions from local predictor in Tournament Prediction Scheme 98% 100% 94% 90% 55% 76% 72% 63% 37% 69% 0% 20% 40% 60% 80% 100% nasa7 matrix300 tomcatv doduc spice fpppp gcc espresso eqntott li Copyright 2020 UCB amp。 continue execution with no stalls No Yes Yes Yes No No ID IF EX for the 5stage MIPS Copyright 2020 UCB amp。 BlueRISC Copyright 2020 UCB amp。 Compiletime Copyright 2020 CAM amp。 Man Kaufmann ECE668 .22 Adapted from Patterson, Katz and Culler 169。 Man Kaufmann ECE668 .16 Adapted from Patterson, Katz and Culler 169。 Man Kaufmann ECE668 .10 Adapted from Patterson, Katz and Culler 169。 UCB Static Branch Prediction ?Simplest: Predict taken ? average misprediction rate = untaken branch frequency, which for the SPEC programs is 34% ? Unfortunately, the correct prediction rate ranges from not very accurate (41%) to highly accurate (91%) ?Predict on the basis of branch direction? ? choosing backwardgoing branches to be taken (loop) ? forwardgoing branches to be not taken (if) ? SPEC programs, however, most forwardgoing branches are taken = predict taken is better ?Predict branches on the basis of profile information collected from earlier runs ? Misprediction varies from 5% to 22% Copyright 2020 UCB amp。 Man Kaufmann ECE668 .5 Adapted from Patterson, Katz and Culler 169。 UCB Reevaluating Correlation ? Several SPEC benchmarks have less than a dozen branches responsible for 90% of taken branches: program branch % static = 90% press 14% 236 13 eqntott 25% 494 5 gcc 15% 9531 2020 mpeg 10% 5598 532 real gcc 13% 17361 3214 ? Real programs + OS more like gcc ? Small benefits of correlation beyond benchmarks? ? Mispredict because either: ? Wrong guess for that branch ? Got branch history of wrong branch when indexing the table ? For SPEC92, 4096 about as good as infinite table ? Misprediction mostly due to wrong prediction ? Can we improve using global history? Copyright 2020 UCB amp。 Man Kaufmann ECE668 .18 Adapted from Patterson, Katz and Culler 169。 Man Kaufmann