Memory dependence prediction using store sets

ABSTRACT

For maximum performance, an out-of-order processor must issue load instructions as early as possible, while avoiding memory-order violations with prior store instructions that write to the same memory location. One approach is to use memory dependence prediction to identify the stores upon which a load depends, and communicate that information to the instruction scheduler. We designate the set of stores upon which each load has depended as the load's "store set". The processor can discover and use a load's store set to accurately predict the earliest time the load can safely execute. We show that store sets accurately predict memory dependencies in the context of large instruction window, superscalar machines, and allow for near-optimal performance compared to an instruction scheduler with perfect knowledge of memory dependencies. In addition, we explore the implementation aspects of store sets, and describe a low cost implementation that achieves nearly optimal performance.

REFERENCES

• 1: Daniel Leibholz , Rahul Razdan, The Alpha 21264: A 500 MHz Out-of-Order Execution Microprocessor, Proceedings of the 42nd IEEE International Computer Conference, p.28, February 23-26, 1997
• 2: K. Ycagcr. The MIPS R10000 Supcrscalar Microprocessor. Hot Chips VII, 1995.
• 3: 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
• 4: Intel Corporation. Pentium(R) Pro Developer's Manual. McGraw-Hill, June 1997.
• 5: 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
• 6: J. Hesson, J. LeBlanc, 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.
• 7: 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
• 8: 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
• 9: S. McFarling. Combining Branch Predictors. WRL Technical Note TN-36, June I993.
• 10: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 11: S.Steely, D. Sager, D. Fite. Memory Reference Tagging US Patent 5,619,662 Filed Aug. 1994, Issued Apr. 1997.
• 12: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Design, Performance