Decoupled store completion/silent deterministic replay: enabling scalable data memory for CPR/CFP processors

ABSTRACT

CPR/CFP (Checkpoint Processing and Recovery/Continual Flow Pipeline) support an adaptive instruction window that scales to tolerate last-level cache misses. CPR/CFP scale the register file by aggressively reclaiming the destination registers of many in-flight instructions. However, an analogous mechanism does not exist for stores and loads. As the window expands, CPR/CFP processors must track all in-flight stores and loads to support forwarding and detect memory ordering violations.

The previously-described SVW (Store Vulnerability Window) and SQIP (Store Queue Index Prediction) schemes provide scalable, non-associative load and store queues, respectively. However, they don't work smoothly in a CPR/CFP context. SVW/SQIP rely on the ability to dynamically stall some loads until a specific older store writes to the cache. Enforcing this serialization in CPR/CFP is expensive if the load and store are in the same checkpoint.

We introduce two complementary procedures that implement this serialization efficiently. Decoupled Store Completion (DSC) allows stores to write to the cache before the enclosing checkpoint completes execution. Silent Deterministic Replay (SDR) supports mis-speculation recovery in the presence of DSC by replaying loads older than completed stores using values from the load queue. The combination of DSC and SDR enables an SVW/SQIP based CPR/CFP memory system that outperforms previous designs while occupying less area.

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: Colin Blundell , Milo M.K. Martin , Thomas F. Wenisch, InvisiFence: performance-transparent memory ordering in conventional multiprocessors, Proceedings of the 36th annual international symposium on Computer architecture, June 20-24, 2009, Austin, TX, USA
• 3: 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
• 4: Luis Ceze , Karin Strauss , James Tuck , Jose Renau , Josep Torrellas, CAVA: Hiding L2 Misses with Checkpoint-Assisted Value Prediction, IEEE Computer Architecture Letters, v.3 n.1, p.7, January 2004 [doi>10.1109/L-CA.2004.3]
• 5: Luis Ceze , James Tuck , Pablo Montesinos , Josep Torrellas, BulkSC: bulk enforcement of sequential consistency, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 6: 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
• 7: Chris Gniady , Babak Falsafi , T. N. Vijaykumar, Is SC + ILP = RC?, Proceedings of the 26th annual international symposium on Computer architecture, p.162-171, May 01-04, 1999, Atlanta, Georgia, United States
• 8: A. Hilton, S. Nagarakatte, and A. Roth. iCFP: Tolerating All-Level Cache Misses in In-Order Pipelines. In Proc. 15th Intl. Symp. on High Performance Computer Architecture, pages 431--442, Feb. 2009.
• 9: José F. Martínez , Jose Renau , Michael C. Huang , Milos Prvulovic , Josep Torrellas, Cherry: checkpointed early resource recycling in out-of-order microprocessors, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 10: P. Michaud. A PPM-like, Tag-Based Branch Predictor. Journal of Instruction Level Parallelism, 7(1):1--10, Apr. 2005.
• 11: Onur Mutlu , Jared Stark , Chris Wilkerson , Yale N. Patt, Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.129, February 08-12, 2003
• 12: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging, Proceedings of the 32nd annual international symposium on Computer Architecture, p.284-295, June 04-08, 2005
• 13: Miquel Pericas , Adrian Cristal , Francisco J. Cazorla , Ruben Gonzalez , Daniel A. Jimenez , Mateo Valero, A Flexible Heterogeneous Multi-Core Architecture, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.13-24, September 15-19, 2007 [doi>10.1109/PACT.2007.5]
• 14: M. Pericas, R. Gonzalez, D. Jimenez, and M. Valero. A Decoupled KILO-Instruction Processor. In Proc. 12th Intl. Symp. on High Performance Computer Architecture, pages 53--64, Feb. 2006.
• 15: Parthasarathy Ranganathan , Vijay S. Pai , Sarita V. Adve, Using speculative retirement and larger instruction windows to narrow the performance gap between memory consistency models, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.199-210, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258512]
• 16: 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
• 17: A. Roth. Store Vulnerability Window (SVW): A Filter and Potential Replacement for Load Re-Execution. Journal of Instruction Level Parallelism, 8, 2006. (http://www.jilp.org/vol8/).
• 18: Amir Roth, Physical Register Reference Counting, IEEE Computer Architecture Letters, v.7 n.1, p.9-12, January 2008 [doi>10.1109/L-CA.2007.15]
• 19: Elham Safi , Patrick Akl , Andreas Moshovos , Andreas Veneris , Aggeliki Arapoyianni, On the latency, energy and area of checkpointed, superscalar register alias tables, Proceedings of the 2007 international symposium on Low power electronics and design, August 27-29, 2007, Portland, OR, USA [doi>10.1145/1283780.1283863]
• 20: Simha Sethumadhavan , Franziska Roesner , Joel S. Emer , Doug Burger , Stephen W. Keckler, Late-binding: enabling unordered load-store queues, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 21: 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]
• 22: 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]
• 23: 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
• 24: 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]
• 25: D. Tarjan, S. Thoziyoor, and N. Jouppi. CACTI 4.0. Technical Report HPL-2006-86, Hewlett-Packard Labs Technical Report, Jun. 2006.
• 26: Christoph von Praun , Harold W. Cain , Jong-Deok Choi , Kyung Dong Ryu, Conditional Memory Ordering, Proceedings of the 33rd annual international symposium on Computer Architecture, p.41-52, June 17-21, 2006
• 27: Thomas F. Wenisch , Anastasia Ailamaki , Babak Falsafi , Andreas Moshovos, Mechanisms for store-wait-free multiprocessors, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 28: Adi Yoaz , Mattan Erez , Ronny Ronen , Stephan Jourdan, Speculation techniques for improving load related instruction scheduling, Proceedings of the 26th annual international symposium on Computer architecture, p.42-53, May 01-04, 1999, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: Pipeline processors**

General Terms:
Design, Performance

Keywords:
checkpoint processors, load-store queues