BulkSC: bulk enforcement of sequential consistency

ABSTRACT

While Sequential Consistency (SC) is the most intuitive memory consistency model and the one most programmers likely assume, current multiprocessors do not support it. Instead, they support more relaxed models that deliver high performance. SC implementations are considered either too slow or -- when they can match the performance of relaxed models -- too difficult to implement.

In this paper, we propose Bulk Enforcement of SC (BulkSC), anovel way of providing SC that is simple to implement and offers performance comparable to Release Consistency (RC). The idea is to dynamically group sets of consecutive instructions into chunks that appear to execute atomically and in isolation. The hardware enforces SC at the coarse grain of chunks which, to the program, appears as providing SC at the individual memory access level. BulkSC keeps the implementation simple by largely decoupling memory consistency enforcement from processor structures. Moreover, it delivers high performance by enabling full memory access reordering and overlapping within chunks and across chunks. We describe a complete system architecture that supports BulkSC and show that it delivers performance comparable to RC.

REFERENCES

• 1: S. V. Adve and K. Gharachorloo, "Shared Memory Consistency Models: A Tutorial," Western Reseach Laboratory-Compaq. Research Report 95/7, September 1995.
• 2: Sarita V. Adve , Mark D. Hill, Weak ordering—a new definition, Proceedings of the 17th annual international symposium on Computer Architecture, p.2-14, May 28-31, 1990, Seattle, Washington, United States
• 3: 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
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: Milo Martin , Colin Blundell , E. Lewis, Subtleties of Transactional Memory Atomicity Semantics, IEEE Computer Architecture Letters, v.5 n.2, p.17, July 2006 [doi>10.1109/L-CA.2006.18]
• 6: 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
• 7: Luis Ceze , Karin Strauss , James Tuck , Josep Torrellas , Jose Renau, CAVA: Using checkpoint-assisted value prediction to hide L2 misses, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.2, p.182-208, June 2006 [doi>10.1145/1138035.1138038]
• 8: Luis Ceze , James Tuck , Josep Torrellas , Calin Cascaval, Bulk Disambiguation of Speculative Threads in Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.227-238, June 17-21, 2006
• 9: H. Chafi, J. Casper, B. D. Carlstrom, A. McDonald, C. Cao Minh, W. Baek, C. Kozyrakis, and K. Olukotun, "A Scalable, Non-blocking Approach to Transactional Memory," in Inter. Symp. on High Performance Computer Architecture, February 2007.
• 10: Adrian Cristal , Daniel Ortega , Josep Llosa , Mateo Valero, Out-of-Order Commit Processors, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.48, February 14-18, 2004 [doi>10.1109/HPCA.2004.10008]
• 11: M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
• 12: K. Gharachorloo, A. Gupta, and J. L. Hennessy, "Two Techniques to Enhance the Performance of Memory Consistency Models.," in Inter. Conf. on Parallel Processing, August 1991.
• 13: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 14: Chris Gniady , Babak Falsafi, Speculative Sequential Consistency with Little Custom Storage, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.179-188, September 22-25, 2002
• 15: 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
• 16: A. Gupta, W. Weber, and T. Mowry, "Reducing Memory and Traffic Requirements for Scalable Directory-Based Cache Coherence Schemes," in Inter. Conference on Parallel Processing, August 1990.
• 17: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 18: Mark D. Hill, Multiprocessors Should Support Simple Memory-Consistency Models, Computer, v.31 n.8, p.28-34, August 1998 [doi>10.1109/2.707614]
• 19: Meyrem Kyrman , Nevin Kyrman , Jose F. Martynez, Cherry-MP: Correctly Integrating Checkpointed Early Resource Recycling in Chip Multiprocessors, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.245-256, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.15]
• 20: Nevin Kirman , Meyrem Kirman , Mainak Chaudhuri , Jose F. Martinez, Checkpointed Early Load Retirement, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.16-27, February 12-16, 2005 [doi>10.1109/HPCA.2005.9]
• 21: L. Lamport, "How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs," IEEE Tran. on Comp., July 1979.
• 22: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
• 23: 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
• 24: 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
• 25: Vijay S. Pai , Parthasarathy Ranganathan , Sarita V. Adve , Tracy Harton, An evaluation of memory consistency models for shared-memory systems with ILP processors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.12-23, October 01-04, 1996, Cambridge, Massachusetts, United States
• 26: Mark S. Papamarcos , Janak H. Patel, A low-overhead coherence solution for multiprocessors with private cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.348-354, January 1984
• 27: 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]
• 28: J. Renau, B. Fraguela, J. Tuck, W. Liu, M. Prvulovic, L. Ceze, S. Sarangi, P. Sack, K. Strauss, and P. Montesinos, "SESC Simulator," January 2005. http://sesc.sourceforge.net.
• 29: 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
• 30: 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
• 31: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Design, Performance

Keywords:
bulk, chip multiprocessors, memory consistency models, programmability, sequential consistency