《高性能处理器体系结构》课件PPT5 推测执行-分支预测技术2.ppt

CS of USTC AN Hong CS258 S99 Lecture on  High Performance Processor Architecture (CS05162) Dynamic Prediction(1)：利用单个分支自身历史（基于模式的预测） Dynamic Prediction ：Use run-time information to make prediction example: Branch Prediction Buffer(1-位预测器) Dynamic Prediction： 1-bit BHT Branch History Table Lower bits of PC address index table of 1-bit values Says whether or not branch taken last time No address check Problem: in a loop, 1-bit BHT will cause two mispredictions : 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 Dynamic Prediction：1-bit BHT （Branch Prediction Buffer） Pros: Small. 1 bit per entry can fit lots of entries Always returns a prediction Cons: aliasing between branches one bit of state mispredicts many branches for (I =0; I10; I++) { a = a + 1; } Two mispredictions per loop invocation Dynamic Prediction(2)：Bimodal Branch Prediction Scheme（2bits BHT, 2-位饱和预测器） Solution: 2-bit predictor where change prediction only if get misprediction twice: Use extra state to reduce mispredictions at loop ends Red: stop, not taken Green: go, taken Adds hysteresis to decision making process Bimodal Branch Prediction Scheme Strategy: Based on the direction the branch went the last few times it was executed. Based on a little self-history pattern Based on a counter Works well: when each branch is strongly biased in a particular direction. For scientific/engineering applications where program execution is dominated by inner-loops. Bimodal Branch Prediction Scheme 例1：…NNNTNNN… 1-位预测器，出现2次预测错 2-位预测器，出现1次预测错 例2：TNTNTN…., 初始状态为01的2-位预测器，出现100%预测错 BHT方法准确度 Mispredict because either: Wrong guess for that branch Got branch history of wrong branch when index the table 4096 entry table programs vary from 1% misprediction (nasa7, tomcatv) to 18% (eqntott), with spice at 9% and gcc at 12% 4096 about as good as infinite table (in Alpha 21164) 2-bit已经足够, n-bit (n2)与2-bit效果