21-07-2014, 11:42 AM
UNIVERSITY OF MASSACHUSETTS
UNIVERSITY OF MASSACHUSETTS.ppt (Size: 780 KB / Downloads: 11)
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 backward-going branches to be taken (loop)
forward-going branches to be not taken (if)
SPEC programs, however, most forward-going 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%
Eight Branch Prediction Schemes
1-bit Branch-Prediction
2-bit Branch-Prediction
Correlating Branch Prediction
Gshare
Tournament Branch Predictor
Branch Target Buffer
Conditionally Executed Instructions
Return Address Predictors
Tournament Predictors
Motivation for correlating branch predictors: 2-bit local predictor failed on important branches; by adding global information, performance improved
Tournament predictors: use two predictors, 1 based on global information and 1 based on local information, and combine with a selector
Hopes to select right predictor for right branch (or right context of branch)
Special Case: Return Addresses
Register Indirect branch - hard to predict address
SPEC89 85% such branches for procedure return
Since stack discipline for procedures, save return address in small buffer that acts like a stack: 8 to 16 entries has small miss rate