Late-binding: enabling unordered load-store queues

ABSTRACT

Conventional load/store queues (LSQs) are an impediment to both power-efficient execution in superscalar processors and scaling tolarge-window designs. In this paper, we propose techniques to improve the area and power efficiency of LSQs by allocating entries when instructions issue ("late binding"), rather than when they are dispatched. This approach enables lower occupancy and thus smaller LSQs. Efficient implementations of late-binding LSQs, however, require the entries in the LSQ to be unordered with respect to age. In this paper, we show how to provide full LSQ functionality in an unordered design with only small additional complexity and negligible performance losses. We show that late-binding, unordered LSQs work well for small-window superscalar processors, but can also be scaled effectively to large, kilo-window processors by breaking the LSQs into address-interleaved banks. To handle the increased overflows, we apply classic network flow control techniques to the processor micronetworks, enabling low-overhead recovery mechanisms from bank overflows. We evaluate three such mechanisms: instruction replay, skid buffers, an dvirtual-channel buffering in the on-chip memory network. We show that for an 80-instruction window, the LSQ can be reduced to 32 entries. For a 1024-instruction window, the unordered, late-binding LSQ works well with four banks of 48 entries each. By applying a Bloom filter as well, this design achieves full hardware memory disambiguation for a 1,024 instruction window while requiring low average power per load and store access of 8 and 12 CAM entries, respectively.

REFERENCES

• 1: 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
• 2: Fernando Castro , Luis Pinuel , Daniel Chaver , Manuel Prieto , Michael Huang , Francisco Tirado, DMDC: Delayed Memory Dependence Checking through Age-Based Filtering, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.297-308, December 09-13, 2006 [doi>10.1109/MICRO.2006.21]
• 3: 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]
• 4: Samantika Subramaniam , Gabriel H. Loh, Fire-and-Forget: Load/Store Scheduling with No Store Queue at All, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.273-284, December 09-13, 2006 [doi>10.1109/MICRO.2006.26]
• 5: 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
• 6: 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
• 7: Alper Buyuktosunoglu , David H. Albonesi , Pradip Bose , Peter W. Cook , Stanley E. Schuster, Tradeoffs in power-efficient issue queue design, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566454]
• 8: Amir Roth. High Bandwidth Load Store Unit for Single- and Multi-Threaded Processors. Technical Report MS-CIS-04-09, Dept. of Computer and Information Sciences, University of Pennsylvania, 2004.
• 9: Rajeev Balasubramonian , Sandhya Dwarkadas, Dynamic management of microarchitecture resources in future microprocessors, The University of Rochester, 2003
• 10: L. Baugh and C. Zilles. Decomposing the load-store queue by function for power reduction and scalability. In P=ac² Conference, IBM Research, 2004.
• 11: Eric Borch , Srilatha Manne , Joel Emer , Eric Tune, Loose Loops Sink Chips, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.299, February 02-06, 2002
• 12: Doug Burger , Stephen W. Keckler , Kathryn S. McKinley , Mike Dahlin , Lizy K. John , Calvin Lin , Charles R. Moore , James Burrill , Robert G. McDonald , William Yoder , the TRIPS Team, Scaling to the End of Silicon with EDGE Architectures, Computer, v.37 n.7, p.44-55, July 2004 [doi>10.1109/MC.2004.65]
• 13: 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
• 14: Adrian Cristal , Oliverio J. Santana , Francisco Cazorla , Marco Galluzzi , Tanausu Ramirez , Miquel Pericas , Mateo Valero, Kilo-Instruction Processors: Overcoming the Memory Wall, IEEE Micro, v.25 n.3, p.48-57, May 2005 [doi>10.1109/MM.2005.53]
• 15: Rajagopalan Desikan , Doug Burger , Stephen W. Keckler, Measuring Experimental Error in Microprocessor Simulation, Proceedings of the 28th annual international symposium on Computer architecture, p.266-277, June 30-July 04, 2001, Göteborg, Sweden [doi>10.1145/379240.565338]
• 16: Elham Safi , Andreas Moshovos , Andreas Veneris, L-CBF: a low-power, fast counting bloom filter architecture, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165634]
• 17: 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 ]
• 18: Aamer Jaleel , Bruce Jacob, Using Virtual Load/Store Queues (VLSQs) to Reduce the Negative Effects of Reordered Memory Instructions, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.191-200, February 12-16, 2005 [doi>10.1109/HPCA.2005.42]
• 19: Teresa Monreal , Antonio González , Mateo Valero , José González , Victor Viñals, Delaying physical register allocation through virtual-physical registers, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.186-192, November 16-18, 1999, Haifa, Israel
• 20: 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
• 21: Karthikeyan Sankaralingam , Ramadass Nagarajan , Robert McDonald , Rajagopalan Desikan , Saurabh Drolia , M. S. Govindan , Paul Gratz , Divya Gulati , Heather Hanson , Changkyu Kim , Haiming Liu , Nitya Ranganathan , Simha Sethumadhavan , Sadia Sharif , Premkishore Shivakumar , Stephen W. Keckler , Doug Burger, Distributed Microarchitectural Protocols in the TRIPS Prototype Processor, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.480-491, December 09-13, 2006 [doi>10.1109/MICRO.2006.19]
• 22: 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
• 23: Simha Sethumadhavan and Robert McDonald and Rajagopalan Desikan and Doug Burger and Stephen W. Keckler. Design and Implementation of the TRIPS Primary Memory System. In ICCD, 2006.
• 24: Srikanth T. Srinivasan , Ravi Rajwar , Haitham Akkary , Amit Gandhi , Mike Upton, Continual flow pipelines, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 25: Stefan Bieschewski , Joan-Manuel Parcerisa , Antonio Gonzalez, Memory Bank Predictors, Proceedings of the 2005 International Conference on Computer Design, p.666-670, October 02-05, 2005 [doi>10.1109/ICCD.2005.73]
• 26: J. M. Tendler, J. S. Dodson, J. J. S. Fields, H. Le, and B. Sinharoy. POWER4 system microarchitecture. IBM Journal of Research and Development, 26(1):5--26, January 2001.
• 27: 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]
• 28: Tingting Sha , Milo M. K. Martin , Amir Roth, NoSQ: Store-Load Communication without a Store Queue, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.285-296, December 09-13, 2006 [doi>10.1109/MICRO.2006.39]
• 29: Hang-Sheng Wang , Xinping Zhu , Li-Shiuan Peh , Sharad Malik, Orion: a power-performance simulator for interconnection networks, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 30: Victor V. Zyuban , Peter M. Kogge, Inherently lower-power high-performance superscalar architectures, University of Notre Dame, Notre Dame, IN, 2000

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: Single-instruction-stream, single-data-stream processors (SISD)**

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Design, Performance

Keywords:
late binding, memory disambiguation, network flow control