TY - GEN
T1 - Probabilistic counter updates for predictor hysteresis and stratification
AU - Riley, Nicholas
AU - Zilles, Craig
PY - 2006/9/26
Y1 - 2006/9/26
N2 - Hardware counters are a fundamental building block of modern high-performance processors. This paper explores two applications of probabilistic counter updates, in which the output of a pseudo-random number generator decides whether to perform a counter increment or decrement. First, we discuss a probabilistic implementation of counter hysteresis, whereby previously proposed branch confidence and criticality predictors can be reduced in size by factors of 2 and 3, respectively, with negligible impact on performance. Second, we build a frequency stratifier by making increment and decrement probabilities functions of the current counter value. The stratifier enables a 4-bit counter to classify an instruction's Likelihood of Criticality with sufficient accuracy to closely approximate the performance of an unbounded precision classifier. Because probabilistic updates are both simple and effective, we believe these ideas hold great promise for immediate use by industry, perhaps enabling the use of structures such as branch confidence predictors which may have previously been viewed as too expensive given their functionality.
AB - Hardware counters are a fundamental building block of modern high-performance processors. This paper explores two applications of probabilistic counter updates, in which the output of a pseudo-random number generator decides whether to perform a counter increment or decrement. First, we discuss a probabilistic implementation of counter hysteresis, whereby previously proposed branch confidence and criticality predictors can be reduced in size by factors of 2 and 3, respectively, with negligible impact on performance. Second, we build a frequency stratifier by making increment and decrement probabilities functions of the current counter value. The stratifier enables a 4-bit counter to classify an instruction's Likelihood of Criticality with sufficient accuracy to closely approximate the performance of an unbounded precision classifier. Because probabilistic updates are both simple and effective, we believe these ideas hold great promise for immediate use by industry, perhaps enabling the use of structures such as branch confidence predictors which may have previously been viewed as too expensive given their functionality.
UR - http://www.scopus.com/inward/record.url?scp=33748867908&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748867908&partnerID=8YFLogxK
U2 - 10.1109/HPCA.2006.1598118
DO - 10.1109/HPCA.2006.1598118
M3 - Conference contribution
AN - SCOPUS:33748867908
SN - 0780393686
SN - 9780780393684
T3 - Proceedings - International Symposium on High-Performance Computer Architecture
SP - 111
EP - 121
BT - Proceedings - Twelfth International Symposium on High-Performance Computer Architecture, 2006
T2 - Twelfth International Symposium on High-Performance Computer Architecture, 2006
Y2 - 11 February 2006 through 15 February 2006
ER -