Advanced search
1 file | 1.29 MB

Linear branch entropy : characterizing and optimizing branch behavior in a micro-architecture independent way

(2017) IEEE TRANSACTIONS ON COMPUTERS. 66(3). p.458-472
Author
Organization
Abstract
In this paper, we propose linear branch entropy, a new metric for characterizing branch behavior. Linear branch entropy is independent of the configuration of a specific branch predictor, but is highly correlated with the branch misprediction rate of any predictor. In particular, we empirically derive a linear relationship between linear branch entropy and branch misprediction rate, which enables predicting miss rates for a range of branch predictors using a single branch entropy profile. Linear branch entropy is more accurate than previously proposed branch classification models, such as taken rate and transition rate. In addition, linear branch entropy provides insight for both analyzing an application's inherent branch behavior as well as for understanding a branch predictor's performance for easy-to-predict versus hard-to-predict branches. We present several case studies, ranging from comparing state-of-the-art branch predictors to compiler optimizations. More in particular, we find that the winner of the latest branch predictor competition outperforms the runners-up on easy-to-predict branches, but performs worse on hard-to-predict branches. We also show that using linear branch entropy to guide if-conversion in compilers leads to better performance compared to standard if-conversion heuristics.
Keywords
Experimentation, measurement, performance

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 1.29 MB

Citation

Please use this url to cite or link to this publication:

Chicago
De Pestel, Sander, Stijn Eyerman, and Lieven Eeckhout. 2017. “Linear Branch Entropy : Characterizing and Optimizing Branch Behavior in a Micro-architecture Independent Way.” Ieee Transactions on Computers 66 (3): 458–472.
APA
De Pestel, S., Eyerman, S., & Eeckhout, L. (2017). Linear branch entropy : characterizing and optimizing branch behavior in a micro-architecture independent way. IEEE TRANSACTIONS ON COMPUTERS, 66(3), 458–472.
Vancouver
1.
De Pestel S, Eyerman S, Eeckhout L. Linear branch entropy : characterizing and optimizing branch behavior in a micro-architecture independent way. IEEE TRANSACTIONS ON COMPUTERS. Los alamitos: Ieee Computer Soc; 2017;66(3):458–72.
MLA
De Pestel, Sander, Stijn Eyerman, and Lieven Eeckhout. “Linear Branch Entropy : Characterizing and Optimizing Branch Behavior in a Micro-architecture Independent Way.” IEEE TRANSACTIONS ON COMPUTERS 66.3 (2017): 458–472. Print.
@article{8542503,
  abstract     = {In this paper, we propose linear branch entropy, a new metric for characterizing branch behavior. Linear branch entropy is independent of the configuration of a specific branch predictor, but is highly correlated with the branch misprediction rate of any predictor. In particular, we empirically derive a linear relationship between linear branch entropy and branch misprediction rate, which enables predicting miss rates for a range of branch predictors using a single branch entropy profile. Linear branch entropy is more accurate than previously proposed branch classification models, such as taken rate and transition rate. In addition, linear branch entropy provides insight for both analyzing an application's inherent branch behavior as well as for understanding a branch predictor's performance for easy-to-predict versus hard-to-predict branches. We present several case studies, ranging from comparing state-of-the-art branch predictors to compiler optimizations. More in particular, we find that the winner of the latest branch predictor competition outperforms the runners-up on easy-to-predict branches, but performs worse on hard-to-predict branches. We also show that using linear branch entropy to guide if-conversion in compilers leads to better performance compared to standard if-conversion heuristics.},
  author       = {De Pestel, Sander and Eyerman, Stijn and Eeckhout, Lieven},
  issn         = {0018-9340},
  journal      = {IEEE TRANSACTIONS ON COMPUTERS},
  keywords     = {Experimentation,measurement,performance},
  language     = {eng},
  number       = {3},
  pages        = {458--472},
  publisher    = {Ieee Computer Soc},
  title        = {Linear branch entropy : characterizing and optimizing branch behavior in a micro-architecture independent way},
  url          = {http://dx.doi.org/10.1109/TC.2016.2601323},
  volume       = {66},
  year         = {2017},
}

Altmetric
View in Altmetric
Web of Science
Times cited: