Using prediction to accelerate coherence protocols

ABSTRACT

Most large shared-memory multiprocessors use directory protocols to keep per-processor caches coherent. Some memory references in such systems, however, suffer long latencies for misses to remotely-cached blocks. To ameliorate this latency, researchers have augmented standard coherence protocols with optimizations for specific sharing patterns, such as read-modify-write, producer-consumer, and migratory sharing. This paper seeks to replace these directed solutions with general prediction logic that monitors coherence activity and triggers appropriate coherence actions.This paper takes the first step toward using general prediction to accelerate coherence protocols by developing and evaluating the Cosmos coherence message predictor. Cosmos predicts the source and type of the next coherence message for a cache block using logic that is an extension of Yeh and Patt's two-level PAp branch predictor. For five scientific applications running on 16 processors, Cosmos has prediction accuracies of 62% to 93%. Cosmos' high prediction accuracy is a result of predictable coherence message signatures that arise from stable sharing patterns of cache blocks.

REFERENCES

• 1: Hazim Abdel-Shafi , Jonathan Hall , Sarita V. Adve , Vikram S. Adve, An Evaluation of Fine-Grain Producer-Initiated Communication in Cache-Coherent Multiprocessors, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.204, February 01-05, 1997
• 2: 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]
• 3: A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 4: Cristiana Amza , Alan L. Cox , Willy Zwaenepoel , Sandhya Dwarkadas, Software DSM Protocols that Adapt between Single Writer and Multiple Writer, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.261, February 01-05, 1997
• 5: Jean-Loup Baer , Tien-Fu Chen, An effective on-chip preloading scheme to reduce data access penalty, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.176-186, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125932]
• 6: David Bailey, John Barton, Thomas Lasinski, and Horst Simon. The NAS Parallel Benchmarks. Technical Report RNR-91-002 Revision 2, Ames Research Center, August 1991.
• 7: John K. Bennett , John B. Carter , Willy Zwaenepoel, Adaptive software cache management for distributed shared memory architectures, Proceedings of the 17th annual international symposium on Computer Architecture, p.125-134, May 28-31, 1990, Seattle, Washington, United States
• 8: B.R. Brooks, R.E. Bruccoleri, B.D. Olafson. D.J. States, S'Swamintathan' and M. Karplus. Charmm: A program for macromolecular energy, minimization, and dynamics calculation. Journal of Computational Chemistry, 4(187), 1983.
• 9: Doug Burger and Sanjay Mehta. Parallelizing Appbt for a Shared- Memory Multiprocessor. Technical Report 1286, Computer Sciences Department, University of Wisconsin-Madison, September 1995.
• 10: David Chaiken , John Kubiatowicz , Anant Agarwal, LimitLESS directories: A scalable cache coherence scheme, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.224-234, April 08-11, 1991, Santa Clara, California, United States
• 11: Satish Chandra , Brad Richards , James R. Larus, Teapot: language support for writing memory coherence protocols, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.237-248, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 12: 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
• 13: Anoop Gupta , Wolf-Dietrich Weber, Cache Invalidation Patterns in Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.41 n.7, p.794-810, July 1992 [doi>10.1109/12.256449]
• 14: Mark D. Hill , James R. Larus , Steven K. Reinhardt , David A. Wood, Cooperative shared memory: software and hardware for scalable multiprocessor, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.262-273, October 12-15, 1992, Boston, Massachusetts, United States
• 15: Tor E. Jeremiassen , Susan J. Eggers, Reducing false sharing on shared memory multiprocessors through compile time data transformations, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.179-188, July 19-21, 1995, Santa Barbara, California, United States
• 16: Teresa L. Johnson , Wen-mei W. Hwu, Run-time adaptive cache hierarchy management via reference analysis, Proceedings of the 24th annual international symposium on Computer architecture, p.315-326, June 01-04, 1997, Denver, Colorado, United States
• 17: Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel D. Sleator. Competitive Snoopy Caching. Algorithmica, 3:79-119, 1988.
• 18: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 19: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 20: 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
• 21: Daniel Lenoski, James Laudon, Kourosh Gharachorloo, Anoop Gupta, John Hennessy, Mark Horowitz, and Monica Lam. Design of the Stanford DASH Multiprocessor. Technical Report CSL-TR-89- 403, Computer System Laboratory, Stanford University, December 1989.
• 22: Tom Lovett , Russell Clapp, STiNG: a CC-NUMA computer system for the commercial marketplace, Proceedings of the 23rd annual international symposium on Computer architecture, p.308-317, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 23: Todd Carl Mowry, Tolerating latency through software-controlled data prefetching, Stanford University, Stanford, CA, 1995
• 24: Shubhendu S. Mukherjee , Babak Falsafi , Mark D. Hill , David A. Wood, Coherent network interfaces for fine-grain communication, Proceedings of the 23rd annual international symposium on Computer architecture, p.247-258, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 25: Shubhendu S. Mukherjee , Mark D. Hill, An evaluation of directory protocols for medium-scale shared-memory multiprocessors, Proceedings of the 8th international conference on Supercomputing, p.64-74, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181271]
• 26: Shubhendu S. Mukherjee, Steven K. Reinhardt, Babak Falsafi. Mike Litzkow, Steve Huss-Lederman, Mark D. Hill, James R. Larus, and David A. Wood. Wisconsin Wind Tunnel II: A Fast and Portable Parallel Architecture Simulator. In Workshop on Performance Analysis and Its Impact on Design (PAID), June 1997.
• 27: Shubhendu S. Mukherjee , Shamik D. Sharma , Mark D. Hill , James R. Larus , Anne Rogers , Joel Saltz, Efficient support for irregular applications on distributed-memory machines, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.68-79, July 19-21, 1995, Santa Barbara, California, United States
• 28: Håkan Grahn , Per Stenström, Evaluation of a competitive-update cache coherence protocol with migratory data detection, Journal of Parallel and Distributed Computing, v.39 n.2, p.168-180, Dec. 15, 1996 [doi>10.1006/jpdc.1996.0164]
• 29: 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
• 30: 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
• 31: Jonas Skeppstedt , Per Stenström, Simple compiler algorithms to reduce ownership overhead in cache coherence protocols, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.286-296, October 05-07, 1994, San Jose, California, United States
• 32: Jonas Skeppstedt , Per Stenström, A compiler algorithm that reduces read latency in ownership-based cache coherence protocols, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.69-78, June 27-29, 1995, Limassol, Cyprus
• 33: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 34: IEEE Computer Society. IEEE Standard for Scalable Coherent Interface (SCI), 1992.
• 35: 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
• 36: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 37: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 38: David A. Wood , Satish Chandra , Babak Falsafi , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , Shubhendu S. Mukherjee , Subbarao Palacharla , Steven K. Reinhardt, Mechanisms for cooperative shared memory, Proceedings of the 20th annual international symposium on Computer architecture, p.156-167, May 16-19, 1993, San Diego, California, United States
• 39: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization

General Terms:
Performance