Speculation techniques for improving load related instruction scheduling

ABSTRACT

State of the art microprocessors achieve high performance by executing multiple instructions per cycle. In an out-of-order engine, the instruction scheduler is responsible for dispatching instructions to execution units based on dependencies, latencies, and resource availability. Most existing instruction schedulers are doing a less than optimal job of scheduling memory accesses and instructions dependent on them, for the following reasons:• Memory dependencies cannot be resolved prior to execution, so loads are not advanced ahead of preceding stores.• The dynamic latencies of load instructions are unknown, so scheduling dependent instructions is based on either optimistic load-use delay (may cause re-scheduling and re-execution) or pessimistic delay (creating unnecessary delays).• Memory pipelines are more expensive than other execution units, and as such, are a scarce resource. Currently, an increase in the memory execution bandwidth is usually achieved through multi-banked caches where bank conflicts limit efficiency.In this paper we present three techniques to address these scheduler limitations. One is to improve the scheduling of load instructions by using a simple memory disambiguation mechanism. The second is to improve the scheduling of load dependent instructions by employing a Data Cache Hit-Miss Predictor to predict the dynamic load latencies. And the third is to improve the efficiency of load scheduling in a multi-banked cache through Cache-Bank Prediction.

REFERENCES

• Aust97: Gary S. Tyson , Todd M. Austin, Improving the accuracy and performance of memory communication through renaming, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.218-227, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• Beke99: Michael Bekerman , Stephan Jourdan , Ronny Ronen , Gilad Kirshenboim , Lihu Rappoport , Adi Yoaz , Uri Weiser, Correlated load-address predictors, Proceedings of the 26th annual international symposium on Computer architecture, p.54-63, May 01-04, 1999, Atlanta, Georgia, United States
• Chry98: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• Digi97: Digital Equipment Corporation, Maynard MA- "21164 Alpha Microprocessor Hardware Reference Manual"- Digital Equipment Corporation, 1997.
• Fran96: Manoj Franklin , Gurindar S. Sohi, ARB: A Hardware Mechanism for Dynamic Reordering of Memory References, IEEE Transactions on Computers, v.45 n.5, p.552-571, May 1996 [doi>10.1109/12.509907]
• Gall94: David M. Gallagher , William Y. Chen , Scott A. Mahlke , John C. Gyllenhaal , Wen-mei W. Hwu, Dynamic memory disambiguation using the memory conflict buffer, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.183-193, October 05-07, 1994, San Jose, California, United States
• Hess95: J. Hesson, J. LeBlanc and S. Ciavaglia- "'Apparatus to Dynamically Control the Out-Of-Order Execution of Load-Store Instructions"- US. Patent 5,615,350 Filed Dec. 1995, Issued Mar. 1997.
• Huan94: A. S. Huang , G. Slavenburg , J. P. Shen, Speculative disambiguation: a compilation technique for dynamic memory disambiguation, Proceedings of the 21ST annual international symposium on Computer architecture, p.200-210, April 18-21, 1994, Chicago, Illinois, United States
• Hunt95: D. Hunt, Advanced performance features of the 64-bit PA-8000, Proceedings of the 40th IEEE Computer Society International Conference, p.123, March 05-09, 1995
• Inte96: Intel Corporation- "Pentium~ Pro Family Developers Manual "- lnteI Corporation, 1996
• Jour98: S. Jourdan, R. Ronen, M. Bekerman, B. Shomar, and A. Yoaz- "A Novel Renaming Scheme to Exploit Value Temporal Locality through Physical Register Reuse and Unification"- MICRO-31, Dec. 1998.
• Kess98: R.E. Kessler- "The Alpha 21264 Microprocessor: Out-of-Order Execution at 600 MHz"- HOT-CHIPS 10, Aug. 1998,
• Mcfa93: S. McFarling- "'Combining Branch Predictors"- WRL Technical Note TN-36, June 1993.
• Mich97: Pierre Michaud , André Seznec , Richard Uhlig, Trading conflict and capacity aliasing in conditional branch predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.292-303, June 01-04, 1997, Denver, Colorado, United States
• Mosh97: Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
• Mosh97b: Andreas Moshovos , Gurindar S. Sohi, Streamlining inter-operation memory communication via data dependence prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.235-245, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• Mowr97: Todd C. Mowry , Chi-Keung Luk, Predicting data cache misses in non-numeric applications through correlation profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.314-320, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• Nico89: Alexandru Nicolau, Run-time disambiguation: coping with statically unpredictable dependencies, IEEE Transactions on Computers, v.38 n.5, p.633-678, May 1989
• Patt95: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• Pinte96: Shlomit S. Pinter , Adi Yoaz, Tango: a hardware-based data prefetching technique for superscalar processors, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.214-225, December 02-04, 1996, Paris, France
• Rive97: Jude A. Rivers , Gary S. Tyson , Edward S. Davidson , Todd M. Austin, On high-bandwidth data cache design for multi-issue processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.46-56, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• Simo95: M. Simone , A. Essen , A. Ike , A. Krishnamoorthy , T. Maruyama , N. Patkar , M. Ramaswami , M. Shebanow , V. Thirumalaiswamy , D. Tovey, Implementation trade-offs in using a restricted data flow architecture in a high performance RISC microprocessor, Proceedings of the 22nd annual international symposium on Computer architecture, p.151-162, June 22-24, 1995, S. Margherita Ligure, Italy
• Tuls95: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• Weis94: Shlomo Weiss , James E. Smith, IBM Power and PowerPC, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• Wils96: Kenneth M. Wilson , Kunle Olukotun , Mendel Rosenblum, Increasing cache port efficiency for dynamic superscalar microprocessors, Proceedings of the 23rd annual international symposium on Computer architecture, p.147-157, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• Yeh97: Yeh and Patt- ''Two-Level Adaptive Training Branch Prediction" - ISCA-24, June 1997.

INDEX TERMS

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

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Design, Management, Measurement, Performance