Advanced search
1 file | 285.87 KB

Speculative Return Address Stack management revisited

Author
Organization
Abstract
Branch prediction feeds a speculative execution processor core with instructions. Branch mispredictions are inevitable and have negative effects on performance and energy consumption. With the advent of highly accurate conditional branch predictors, nonconditional branch instructions are gaining importance. In this article, we address the prediction of procedure returns. On modern processors, procedure returns are predicted through a return address stack (RAS). The overwhelming majority of the return mispredictions are due to RAS overflows and/or overwriting the top entries of the RAS on a mispredicted path. These sources of misprediction were addressed by previously proposed speculative return address stacks [Jourdan et al. 1996; Skadron et al. 1998]. However, the remaining misprediction rate of these RAS designs is still significant when compared to state-of-the-art conditional predictors. We present two low-cost corruption detectors for RAS predictors. They detect RAS overflows and wrong path corruption with 100% coverage. As a consequence, when such a corruption is detected, another source can be used for predicting the return. On processors featuring a branch target buffer (BTB), this BTB can be used as a free backup predictor for predicting returns when corruption is detected. Our experiments show that our proposal can be used to improve the behavior of all previously proposed speculative RASs. For instance, without any specific management of the speculative states on the RAS, an 8-entry BTB-backed up RAS achieves the same performance level as a state-of-the-art, but complex, 64-entry self-checkpointing RAS [Jourdan et al. 1996]. Therefore, our proposal can be used either to improve the performance of the processor or to reduce its hardware complexity.
Keywords
Experimentation, Performance, Algorithms, Return address prediction, corruption detection, back-up predictor

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 285.87 KB

Citation

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

Chicago
Vandierendonck, Hans, and Andre Seznec. 2008. “Speculative Return Address Stack Management Revisited.” Acm Transactions on Architecture and Code Optimization 5 (3): 15:1–15:20.
APA
Vandierendonck, H., & Seznec, A. (2008). Speculative Return Address Stack management revisited. ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION, 5(3), 15:1–15:20.
Vancouver
1.
Vandierendonck H, Seznec A. Speculative Return Address Stack management revisited. ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION. New York, NY, USA: Assoc. Computing Machinery; 2008;5(3):15:1–15:20.
MLA
Vandierendonck, Hans, and Andre Seznec. “Speculative Return Address Stack Management Revisited.” ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION 5.3 (2008): 15:1–15:20. Print.
@article{675105,
  abstract     = {Branch prediction feeds a speculative execution processor core with instructions. Branch mispredictions are inevitable and have negative effects on performance and energy consumption. With the advent of highly accurate conditional branch predictors, nonconditional branch instructions are gaining importance.
In this article, we address the prediction of procedure returns. On modern processors, procedure returns are predicted through a return address stack (RAS). The overwhelming majority of the return mispredictions are due to RAS overflows and/or overwriting the top entries of the RAS on a mispredicted path. These sources of misprediction were addressed by previously proposed speculative return address stacks [Jourdan et al. 1996; Skadron et al. 1998]. However, the remaining misprediction rate of these RAS designs is still significant when compared to state-of-the-art conditional predictors.
We present two low-cost corruption detectors for RAS predictors. They detect RAS overflows and wrong path corruption with 100% coverage. As a consequence, when such a corruption is detected, another source can be used for predicting the return. On processors featuring a branch target buffer (BTB), this BTB can be used as a free backup predictor for predicting returns when corruption is detected.
Our experiments show that our proposal can be used to improve the behavior of all previously proposed speculative RASs. For instance, without any specific management of the speculative states on the RAS, an 8-entry BTB-backed up RAS achieves the same performance level as a state-of-the-art, but complex, 64-entry self-checkpointing RAS [Jourdan et al. 1996]. Therefore, our proposal can be used either to improve the performance of the processor or to reduce its hardware complexity.},
  author       = {Vandierendonck, Hans and Seznec, Andre},
  issn         = {1544-3566},
  journal      = {ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION},
  keywords     = {Experimentation,Performance,Algorithms,Return address prediction,corruption detection,back-up predictor},
  language     = {eng},
  number       = {3},
  pages        = {15:1--15:20},
  publisher    = {Assoc. Computing Machinery},
  title        = {Speculative Return Address Stack management revisited},
  url          = {http://dx.doi.org/10.1145/1455650.1455654},
  volume       = {5},
  year         = {2008},
}

Altmetric
View in Altmetric
Web of Science
Times cited: