Speculative return address stack management revisited

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.

REFERENCES

• 1: Branch Behavior of a Commercial OLTP Workload on Intel IA32 Processors, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.242, September 16-18, 2002
• 2: Alper Buyuktosunoglu , Tejas Karkhanis , David H. Albonesi , Pradip Bose, Energy efficient co-adaptive instruction fetch and issue, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 3: Calder, B., Grunwald, D., and Zorn, B. 1994. Quantifying behavioral differences between C and C++ programs. Journal of Programming Languages 2, 4, 313--351.
• 4: Desmet, V., Sazeides, Y., Kourouyiannis, C., and De Bosschere, K. 2005. Correct alignment of a return-address-stack after call and return mispredictions. In Workshop on Duplicating, Deconstructing and Debunking. 25--33.
• 5: Karel Driesen , Urs Hölzle, The cascaded predictor: economical and adaptive branch target prediction, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.249-258, November 1998, Dallas, Texas, United States
• 6: Dirk Grunwald , Artur Klauser , Srilatha Manne , Andrew Pleszkun, Confidence estimation for speculation control, Proceedings of the 25th annual international symposium on Computer architecture, p.122-131, June 27-July 02, 1998, Barcelona, Spain
• 7: Gwennap, L. 1996. Digital 21264 sets new standard. Microprocessor Report 10, 14 (Oct.), 1--6.
• 8: S. Hily , A. Seznec, Branch Prediction and Simultaneous Multithreading, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.169, October 20-23, 1996
• 9: Erik Jacobsen , Eric Rotenberg , J. E. Smith, Assigning confidence to conditional branch predictions, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.142-152, December 02-04, 1996, Paris, France
• 10: Daniel A. Jimenez, Piecewise Linear Branch Prediction, Proceedings of the 32nd annual international symposium on Computer Architecture, p.382-393, June 04-08, 2005
• 11: Stephan Jourdan , Tse-Hao Hsing , Jared Stark , Yale N. Patt, The Effects of Mispredicted-Path Execution on Branch Prediction Structures, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.58, October 20-23, 1996
• 12: David R. Kaeli , Philip G. Emma, Branch history table prediction of moving target branches due to subroutine returns, Proceedings of the 18th annual international symposium on Computer architecture, p.34-42, May 27-30, 1991, Toronto, Ontario, Canada
• 13: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 14: Kun Luo , Manoj Franklin , Shubhendu S. Mukherjee , André Seznec, Boosting SMT Performance by Speculation Control, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.2, April 23-27, 2001
• 15: Srilatha Manne , Artur Klauser , Dirk Grunwald, Pipeline gating: speculation control for energy reduction, Proceedings of the 25th annual international symposium on Computer architecture, p.132-141, June 27-July 02, 1998, Barcelona, Spain
• 16: McGregor, J., Karig, D., Shi, Z., and Lee, R. 2003. A processor architecture defense against buffer overflow attacks. In Proceedings of the International Conference on Information Technology: Research and Education. 243--250.
• 17: Cameron McNairy , Don Soltis, Itanium 2 Processor Microarchitecture, IEEE Micro, v.23 n.2, p.44-55, March 2003 [doi>10.1109/MM.2003.1196114]
• 18: Andre Seznec, Analysis of the O-GEometric History Length Branch Predictor, Proceedings of the 32nd annual international symposium on Computer Architecture, p.394-405, June 04-08, 2005
• 19: André Seznec , Stephen Felix , Venkata Krishnan , Yiannakis Sazeides, Design tradeoffs for the Alpha EV8 conditional branch predictor, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 20: Seznec, A. and Michaud, P. 2006. A case for (partially) TAgged GEometric history length branch prediction. Journal of Instruction-Level Parallelism 8, 1 (Feb.), 1--23.
• 21: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 22: Kevin Skadron , Pritpal S. Ahuja , Margaret Martonosi , Douglas W. Clark, Improving prediction for procedure returns with return-address-stack repair mechanisms, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.259-271, November 1998, Dallas, Texas, United States
• 23: Song, P. 1997. UltraSPARC-3 aims at MP servers. Microprocessor Report.
• 24: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 25: Webb, C. F. 1988. Subroutine call/return stack. IBM Tech. Disc. Bulletin 30, 11 (Apr.), 221--225.
• 26: Xu, J., Kalbarczyk, Z., Patel, S., and Iyer, R. 2002. Architecture support for defending against buffer overflow attacks. In Proceedings of the 5th Workshop on Evaluating and Architecting System Dependability.
• 27: Dong Ye , David Kaeli, A reliable return address stack: microarchitectural features to defeat stack smashing, ACM SIGARCH Computer Architecture News, v.33 n.1, March 2005 [doi>10.1145/1055626.1055637]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Return address prediction, back-up predictor, corruption detection