Boosting the performance of hybrid snooping cache protocols

ABSTRACT

Previous studies of bus-based shared-memory multiprocessors have shown hybrid write-invalidate/write-update snooping protocols to be incapable of providing consistent performance improvements over write-invalidate protocols. In this paper, we analyze the deficiencies of hybrid snooping protocols under release consistency, and show how these deficiencies can be dramatically reduced by using write caches and read snarfing.Our performance evaluation is based on program-driven simulation and a set of five scientific applications with different sharing behaviors including migratory sharing as well us producer-consumer sharing. We show that a hybrid protocol, extended with write caches as well as read snarfing, manages to reduce the number of coherence misses by between 83% and 95% as compared to a write-invalidate protocol for all five applications in this study. In addition, the number of bus transactions is reduced by between 36% and 60% for four of the applications and by 9% for the fifth application. Because of the small implementation cost of the hybrid protocol and the two extensions, we believe that this combination is an effective approach to boost the performance of bus-based multiprocessors.

REFERENCES

• 1: C. Anderson , J.-L. Baer, Two techniques for improving performance on bus-based multiprocessors, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.264, January 22-25, 1995
• 2: J. K. Archibald, A cache coherence approach for large multiprocessor systems, Proceedings of the 2nd international conference on Supercomputing, p.337-345, June 1988, St. Malo, France [doi>10.1145/55364.55397]
• 3: Brorsson, M., Dahlgren, E, Nilsson, H., and Stenstrrm, P. "The CacheMire Test Bench -- A Flexible and Effective Approach for Simulation of Multiprocessors," in Proc. of the 26th Annual Simulation Symposium, pp. 41-49, 1993.
• 4: Fredrik Dahlgren , Per Stenström, Using write caches to improve performance of cache coherence protocols in shared-memory multiprocessors, Journal of Parallel and Distributed Computing, v.26 n.2, p.193-210, April 15, 1995 [doi>10.1006/jpdc.1995.1059]
• 5: DEC, "DECChip 21064 - A RISC Microproces,~~or Preliminary Data Sheet," Digital Equipment Corporation, Maynard, Massachusetts, 1993.
• 6: S. J. Eggers , R. H. Katz, A characterization of sharing in parallel programs and its application to coherency protocol evaluation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.373-382, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 7: S. J. Eggers , R. H. Katz, Evaluating the performance of four snooping cache coherency protocols, Proceedings of the 16th annual international symposium on Computer architecture, p.2-15, April 1989, Jerusalem, Israel
• 8: Galles, M. and Williams, E. "Performance optimizations, Implementation, and Verification of the SGI Challenge Multiprooessor," in Proc. of the 27th Hawaii Int. Conference on System Sciences, Vol. 1, pp.134-143, 1994.
• 9: 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
• 10: J. R. Goodman , P. J. Woest, The Wisconsin multicube: a new large-scale cache-coherent multiprocessor, Proceedings of the 15th Annual International Symposium on Computer architecture, p.422-431, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 11: Norman P. Jouppi, Cache write policies and performance, Proceedings of the 20th annual international symposium on Computer architecture, p.191-201, May 16-19, 1993, San Diego, California, United States
• 12: Karlin, M.R., Manasse, M.S., Rudolph, L., and Sleator, D.D. "Competitive Snoopy Caching," in Proc. oJ the 27th Annual Symposium on Foundations oj Computer Science, pp.244-254, 1986.
• 13: 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
• 14: Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
• 15: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 16: Thacker, C.P., Conroy, L.C., and Stewart, L.C. "The Alpha Demonstration Unit: A High-Performance Multiprocessor for Software and Chip Development," in Digital Technical Journal, 4(4):51-65, 1992.
• 17: Charles P. Thacker , Lawrence C. Stewart, Firefly: a multiprocessor workstation, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.164-172, October 1987, Palo Alto, California, United States
• 18: Jack E. Veenstra , Robert J. Fowler, The Prospects for On-Line Hybrid Coherency Protocols on Bus-Based Multiprocessors, University of Rochester, Rochester, NY, 1994

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance