Mechanisms for store-wait-free multiprocessors

ABSTRACT

Store misses cause significant delays in shared-memory multiprocessors because of limited store buffering and ordering constraints required for proper synchronization. Today, programmers must choose from a spectrum of memory consistency models that reduce store stalls at the cost of increased programming complexity. Prior research suggests that the performance gap among consistency models can be closed through speculation--enforcing order only when dynamically necessary. Unfortunately, past designs either provide insufficient buffering, replace all stores with read-modify-write operations, and/or recover from ordering violations via impractical fine-grained rollback mechanisms.

We propose two mechanisms that, together, enable store-wait-free implementations of any memory consistency model. To eliminate buffer-capacity-related stalls, we propose the scalable store buffer, which places private/speculative values directly into the L1 cache, thereby eliminating the non-scalable associative search of conventional store buffers. To eliminate ordering-related stalls, we propose atomic sequence ordering, which enforces ordering constraints over coarse-grain access sequences while relaxing order among individual accesses. Using cycle-accurate full-system simulation of scientific and commercial applications, we demonstrate that these mechanisms allow the simplified programming of strict ordering while outperforming conventional implementations on average by 32% (sequential consistency), 22% (SPARC total store order) and 9% (SPARC relaxed memory order).

REFERENCES

• 1: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 2: 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
• 3: R. Bhargava , L. K. John, Issues in the design of store buffers in dynamically scheduled processors, Proceedings of the 2000 IEEE International Symposium on Performance Analysis of Systems and Software, p.76-87, April 24-25, 2000
• 4: 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]
• 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: Yuan Chou , Brian Fahs , Santosh Abraham, Microarchitecture Optimizations for Exploiting Memory-Level Parallelism, Proceedings of the 31st annual international symposium on Computer architecture, p.76, June 19-23, 2004, München, Germany
• 7: Yuan Chou , Lawrence Spracklen , Santosh G. Abraham, Store Memory-Level Parallelism Optimizations for Commercial Applications, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.183-196, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.31]
• 8: Oguz Ergin , Deniz Balkan , Dmitry Ponomarev , Kanad Ghose, Increasing Processor Performance Through Early Register Release, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.480-487, October 11-13, 2004
• 9: A. Gandhi, H. Akkary, R. Rajwar, S. T. Srinivasan, and K. Lai. Scalable load and store processing in latency tolerant processors. Proc. of the 38th Int'l Symposium on Microarchitecture, Dec. 2005.
• 10: K. Gharachorloo, A. Gupta, and J. Hennessy. Two techniques to enhance the performance of memory consistency models. Proc. of the Int'l Conference on Parallel Processing, Aug. 1991.
• 11: Kourosh Gharachorloo , Anoop Gupta , John Hennessy, Performance evaluation of memory consistency models for shared-memory multiprocessors, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.245-257, April 08-11, 1991, Santa Clara, California, United States
• 12: 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
• 13: 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
• 14: Lance Hammond , Mark Willey , Kunle Olukotun, Data speculation support for a chip multiprocessor, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.58-69, October 02-07, 1998, San Jose, California, United States
• 15: M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. Technical Report 92/07, Digital Equipment Corporation, Cambridge Research Laboratory, Dec. 1992.
• 16: 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]
• 17: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 18: L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690--691, Sep. 1979.
• 19: J. Larus and R. Rajwar. Transactional Memory. Morgan Claypool Publishers, 2006.
• 20: 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
• 21: José F. Martínez , Josep Torrellas, Speculative synchronization: applying thread-level speculation to explicitly parallel applications, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 22: 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
• 23: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 24: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 25: Parthasarathy Ranganathan , Kourosh Gharachorloo , Sarita V. Adve , Luiz André Barroso, Performance of database workloads on shared-memory systems with out-of-order processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.307-318, October 02-07, 1998, San Jose, California, United States
• 26: Parthasarathy Ranganathan , Vijay S. Pai , Hazim Abdel-Shafi , Sarita V. Adve, The interaction of software prefetching with ILP processors in shared-memory systems, Proceedings of the 24th annual international symposium on Computer architecture, p.144-156, June 01-04, 1997, Denver, Colorado, United States
• 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: 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
• 29: 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]
• 30: Minglong Shao , Anastassia Ailamaki , Babak Falsafi, DBmbench: fast and accurate database workload representation on modern microarchitecture, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.254-267, October 17-20, 2005, Toranto, Ontario, Canada
• 31: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 32: J. Greggory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, A scalable approach to thread-level speculation, Proceedings of the 27th annual international symposium on Computer architecture, p.1-12, June 2000, Vancouver, British Columbia, Canada
• 33: Per Stenström , Mats Brorsson , Lars Sandberg, An adaptive cache coherence protocol optimized for migratory sharing, Proceedings of the 20th annual international symposium on Computer architecture, p.109-118, May 16-19, 1993, San Diego, California, United States
• 34: 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]
• 35: 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
• 36: 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
• 37: Thomas F. Wenisch , Roland E. Wunderlich , Michael Ferdman , Anastassia Ailamaki , Babak Falsafi , James C. Hoe, SimFlex: Statistical Sampling of Computer System Simulation, IEEE Micro, v.26 n.4, p.18-31, July 2006 [doi>10.1109/MM.2006.79]
• 38: Roland E. Wunderlich , Thomas F. Wenisch , Babak Falsafi , James C. Hoe, SMARTS: accelerating microarchitecture simulation via rigorous statistical sampling, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design, Performance

Keywords:
memory consistency models, store buffer design