Coherence decoupling: making use of incoherence

ABSTRACT

This paper explores a new technique called coherence decoupling, which breaks a traditional cache coherence protocol into two protocols: a Speculative Cache Lookup (SCL) protocol and a safe, backing coherence protocol. The SCL protocol produces a speculative load value, typically from an invalid cache line, permitting the processor to compute with incoherent data. In parallel, the coherence protocol obtains the necessary coherence permissions and the correct value. Eventually, the speculative use of the incoherent data can be verified against the coherent data. Thus, coherence decoupling can greatly reduce --- if not eliminate --- the effects of false sharing. Furthermore, coherence decoupling can also reduce latencies incurred by true sharing. SCL protocols reduce those latencies by speculatively writing updates into invalid lines, thereby increasing the accuracy of speculation, without complicating the simple, underlying coherence protocol that guarantees correctness.The performance benefits of coherence decoupling are evaluated using a full-system simulator and a mix of commercial and scientific benchmarks. Our results show that 40% to 90% of all coherence misses can be speculated correctly, and therefore their latencies partially or fully hidden. This capability results in performance improvements ranging from 3% to over 16%, in most cases where the latencies of coherence misses have an effect on performance.

REFERENCES

• 1: Alaa R. Alameldeen , David A. Wood, Variability in Architectural Simulations of Multi-Threaded Workloads, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.7, February 08-12, 2003
• 2: Craig Anderson , Anna R. Karlin, Two Adaptive Hybrid Cache Coherency Protocols, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.303, February 03-07, 1996
• 3: Alan L. Cox , Robert J. Fowler, Adaptive cache coherency for detecting migratory shared data, Proceedings of the 20th annual international symposium on Computer architecture, p.98-108, May 16-19, 1993, San Diego, California, United States
• 4: Fredrik Dahlgren, Boosting the performance of hybrid snooping cache protocols, Proceedings of the 22nd annual international symposium on Computer architecture, p.60-69, June 22-24, 1995, S. Margherita Ligure, Italy
• 5: F. Dahlgren , M. Dubois , P. Stenström, Combined performance gains of simple cache protocol extensions, Proceedings of the 21ST annual international symposium on Computer architecture, p.187-197, April 18-21, 1994, Chicago, Illinois, United States
• 6: Michel Dubois , Jonas Skeppstedt , Livio Ricciulli , Krishnan Ramamurthy , Per Stenström, The detection and elimination of useless misses in multiprocessors, Proceedings of the 20th annual international symposium on Computer architecture, p.88-97, May 16-19, 1993, San Diego, California, United States
• 7: Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , Ioannis Schoinas , Mark D. Hill , James R. Larus , Anne Rogers , David A. Wood, Application-specific protocols for user-level shared memory, Proceedings of the 1994 conference on Supercomputing, p.380-389, December 1994, Washington, D.C., United States
• 8: 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]
• 9: 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
• 10: Phillip B. Gibbons , Michael Merritt , Kourosh Gharachorloo, Proving sequential consistency of high-performance shared memories (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.292-303, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113406]
• 11: P. N. Glaskowsky. IBM Raises Curtain on Power5. Microprocessor Report, Oct. 14 2003.
• 12: 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
• 13: S. Gopal , T. Vijaykumar , J. Smith , G. Sohi, Speculative Versioning Cache, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.195, January 31-February 04, 1998
• 14: Mark D. Hill , James R. Larus , Steven K. Reinhardt , David A. Wood, Cooperative shared memory: software and hardware for scalable multiprocessors, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.300-318, Nov. 1993 [doi>10.1145/161541.161544]
• 15: IEEE. IEEE Standard for Scalable Coherent Interface (SCI), 1992. IEEE 1596--1992.
• 16: T. Karkhanis and J. Smith. A day in the life of a cache miss. In Proceedings of 2nd Annual Workshop On Memory Performance Issues, May 2002.
• 17: Stefanos Kaxiras , James R. Goodman, Improving CC-NUMA Performance Using Instruction-Based Prediction, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.161, January 09-12, 1999
• 18: S. Kaxiras and C. Young. Coherence communication prediction in shared-memory multiprocessors. In Proceedings of the 6th Int. Symp. on High Performance Computer Architecture, pages 156--167, Feb. 2000.
• 19: J. Kuskin , D. Ofelt , M. Heinrich , J. Heinlein , R. Simoni , K. Gharachorloo , J. Chapin , D. Nakahira , J. Baxter , M. Horowitz , A. Gupta , M. Rosenblum , J. Hennessy, The Stanford FLASH multiprocessor, Proceedings of the 21ST annual international symposium on Computer architecture, p.302-313, April 18-21, 1994, Chicago, Illinois, United States
• 20: An-Chow Lai , Babak Falsafi, Memory sharing predictor: the key to a speculative coherent DSM, Proceedings of the 26th annual international symposium on Computer architecture, p.172-183, May 01-04, 1999, Atlanta, Georgia, United States
• 21: An-Chow Lai , Babak Falsafi, Selective, accurate, and timely self-invalidation using last-touch prediction, Proceedings of the 27th annual international symposium on Computer architecture, p.139-148, June 2000, Vancouver, British Columbia, Canada
• 22: Alvin R. Lebeck , David A. Wood, Dynamic self-invalidation: reducing coherence overhead in shared-memory multiprocessors, Proceedings of the 22nd annual international symposium on Computer architecture, p.48-59, June 22-24, 1995, S. Margherita Ligure, Italy
• 23: 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]
• 24: Kevin M. Lepak , Mikko H. Lipasti, Silent stores for free, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.22-31, December 2000, Monterey, California, United States [doi>10.1145/360128.360133]
• 25: Kevin M. Lepak , Mikko H. Lipasti, Temporally silent stores, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 26: Milo M. K. Martin , Pacia J. Harper , Daniel J. Sorin , Mark D. Hill , David A. Wood, Using destination-set prediction to improve the latency/bandwidth tradeoff in shared-memory multiprocessors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 27: Milo M. K. Martin , Mark D. Hill , David A. Wood, Token coherence: decoupling performance and correctness, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 28: Milo M. K. Martin , Daniel J. Sorin , Harold W. Cain , Mark D. Hill , Mikko H. Lipasti, Correctly implementing value prediction in microprocessors that support multithreading or multiprocessing, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 29: 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
• 30: Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
• 31: Farnaz Mounes-Toussi , David J. Lilja, The Potential of Compile-Time Analysis to Adapt the Cache Coherence Enforcement Strategy to the Data Sharing Characteristics, IEEE Transactions on Parallel and Distributed Systems, v.6 n.5, p.470-481, May 1995 [doi>10.1109/71.382316]
• 32: Shubhendu S. Mukherjee , Mark D. Hill, Using prediction to accelerate coherence protocols, Proceedings of the 25th annual international symposium on Computer architecture, p.179-190, June 27-July 02, 1998, Barcelona, Spain
• 33: 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
• 34: Y. N. Patt , W. M. Hwu , M. Shebanow, HPS, a new microarchitecture: rationale and introduction, Proceedings of the 18th annual workshop on Microprogramming, p.103-108, December 03-06, 1985, Pacific Grove, California, United States
• 35: 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
• 36: 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
• 37: Alain Raynaud , Zheng Zhang , Josep Torrellas, Distance-Adaptive Update Protocols for Scalable Shared-Memory Multiprocessors, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.323, February 03-07, 1996
• 38: S. K. Reinhardt , J. R. Larus , D. A. Wood, Tempest and typhoon: user-level shared memory, Proceedings of the 21ST annual international symposium on Computer architecture, p.325-336, April 18-21, 1994, Chicago, Illinois, United States
• 39: Karthikeyan Sankaralingam , Ramadass Nagarajan , Haiming Liu , Changkyu Kim , Jaehyuk Huh , Doug Burger , Stephen W. Keckler , Charles R. Moore, Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 40: Gurindar S. Sohi, Instruction Issue Logic for High-Performance, Interruptible, Multiple Functional Unit, Pipelined Computers, IEEE Transactions on Computers, v.39 n.3, p.349-359, March 1990 [doi>10.1109/12.48865]
• 41: 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
• 42: 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
• 43: Q. Yang , G. Thangadurai , L. M. Bhuyan, Design of an Adaptive Cache Coherence Protocol for Large Scale Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.281-293, May 1992 [doi>10.1109/71.139202]
• 44: 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)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
coherence decoupling, coherence misses, false sharing, speculative cache lookup