Substituting associative load queue with simple hash tables in out-of-order microprocessors

ABSTRACT

Buffering more in-flight instructions in an out-of-order microprocessor is a straightforward and effective method to help tolerate the long latencies generally associated with off-chip memory accesses. One of the main challenges of buffering a large number of instructions, however, is the implementation of a scalable and efficient mechanism to detect memory access order violations as a result of out-of-order scheduling of load and store instructions. Traditional CAM-based associative queues can be very slow and energy consuming. In this paper, instead of using the traditional age-based load queue to record load addresses, we explicitly record age information in address-indexed hash tables to achieve the same functionality of detecting premature loads. This alternative design eliminates associative searches and significantly reduces the energy consumption of the load queue. With simple techniques to reduce the number of false positives, performance degradation is kept at a minimum.

REFERENCES

• 1: Haitham Akkary , Ravi Rajwar , Srikanth T. Srinivasan, Checkpoint Processing and Recovery: Towards Scalable Large Instruction Window Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.423, December 03-05, 2003
• 2: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 3: D. Burger and T. Austin. The SimpleScalar Tool Set, Version 2.0. Technical report 1342, Computer Sciences Department, University of Wisconsin-Madison, June 1997.
• 4: Harold W. Cain , Mikko H. Lipasti, Memory Ordering: A Value-Based Approach, Proceedings of the 31st annual international symposium on Computer architecture, p.90, June 19-23, 2004, München, Germany
• 5: F. Castro, D. Chaver, L. Pinuel, M. Prieto, M. Huang, and F. Tirado. A Power-Efficient and Scalable Load-Store Queue Design. In International Workshop on Power And Timing Modeling, Optimization and Simulation. September 2005. Lecture Notes in Computer Science Vol. 2236(8):1--9.
• 6: Fernando Castro , Daniel Chaver , Luis Pinuel , Manuel Prieto , Francisco Tirado , Michael Huang, Load-Store Queue Management: an Energy-Efficient Design Based on a State-Filtering Mechanism., Proceedings of the 2005 International Conference on Computer Design, p.617-624, October 02-05, 2005 [doi>10.1109/ICCD.2005.70]
• 7: Compaq Computer Corporation. Alpha 21264/EV6 Microprocessor Hardware Reference Manual, September 2000. Order number: DS-0027B-TE.
• 8: Amit Gandhi , Haitham Akkary , Ravi Rajwar , Srikanth T. Srinivasan , Konrad Lai, Scalable Load and Store Processing in Latency Tolerant Processors, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.446-457, June 04-08, 2005
• 9: Alok Garg , M. Wasiur Rashid , Michael Huang, Slackened Memory Dependence Enforcement: Combining Opportunistic Forwarding with Decoupled Verification, Proceedings of the 33rd annual international symposium on Computer Architecture, p.142-154, June 17-21, 2006
• 10: R. Huang, A. Garg, and M. Huang. Software-Hardware Cooperative Memory Disambiguation. In International Symposium on High-Performance Computer Architecture. February 2006.
• 11: Il Park , Chong Liang Ooi , T. N. Vijaykumar, Reducing Design Complexity of the Load/Store Queue, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.411, December 03-05, 2003
• 12: Amir Roth, Store Vulnerability Window (SVW): Re-Execution Filtering for Enhanced Load Optimization, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.458-468, June 04-08, 2005
• 13: Simha Sethumadhavan , Rajagopalan Desikan , Doug Burger , Charles R. Moore , Stephen W. Keckler, Scalable Hardware Memory Disambiguation for High ILP Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.399, December 03-05, 2003
• 14: Tingting Sha , Milo M. K. Martin , Amir Roth, Scalable Store-Load Forwarding via Store Queue Index Prediction, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.159-170, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.29]
• 15: Sam S. Stone , Kevin M. Woley , Matthew I. Frank, Address-Indexed Memory Disambiguation and Store-to-Load Forwarding, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.171-182, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.10]
• 16: J. Tendler, J. Dodson, J. Fields, H. Le, and B. Sinharoy. POWER4 System Microarchitecture. IBM Journal of Research and Development, Vol. 46(1):5--25, January 2002.
• 17: E. F. Torres , P. Ibanez , V. Vinals , J. M. Llaberia, Store Buffer Design in First-Level Multibanked Data Caches, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.469-480, June 04-08, 2005

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General

General Terms:
Design, Experimentation, Measurement

Keywords:
LSQ, hash table, memory disambiguation, scalability