An evaluation of directory protocols for medium-scale shared-memory multiprocessors

ABSTRACT

This paper considers alternative directory protocols for providing cache coherence in shared-memory multiprocessors with 32 to 128 processors, where the state requirements of DirN may be considered too large. We consider DiriB, i=1,2,4, DirN, Tristate (also called superset), Coarse Vector, and three new protocols. The new protocols—Gray-hardward, Gray-software, Home—are optimizations of Tristate that use gray coding to favor near-neighbor sharing. Our results are the first to compare all these protocols with complete applications (and the first evaluation of Tristate with a non-synthetic workload). Results for three applications—ocean (one-dimensional sharing), appbt (three-dimensional sharing), and barnes (dynamic sharing)—for 128 processors on the Wisconsin Wind Tunnel show that (a)Diri B sends 15 to 43 times as many invalidation messages as DirN, (b) Gray-software sends 1.0 to 4.7 times as many messages as DirN, making it better than Tristate, Gray-hardware, and Home, and (c) the choice between DiriB, Coarse Vector, and Gray-software depends on whether one wants to optimize for few sharers (DiriB), many sharers (Coarse Vector), or hedge one's bets betweem both alternatives (Gray-software).

REFERENCES

• 1: 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
• 2: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 3: David Bailey, John Barton, Thomas Lasinski, and Horst Simon. The NAS Parallel Benchmarks. Report RNR-91-002 Revision 2, Ames Research Center, August 1991.
• 4: Said Bettayeb , Zevi Miller , I. Hal Sudborough, Embedding grids into hypercubes, Journal of Computer and System Sciences, v.45 n.3, p.340-366, Dec. 1992 [doi>10.1016/0022-0000(92)90030-M]
• 5: 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
• 6: D. L. Chaiken, CACHE COHERENCE PROTOCOLS FOR LARGE-SCALE MULTIPROCESSORS, Massachusetts Institute of Technology, Cambridge, MA, 1990
• 7: Mee-Yee Chan. Dilation-2 Embeddings of Grids Into Hypercubes. In Proceedings of the 1988 International Conference on Parallel Processing (Vol. III), pages 295-298, 1988.
• 8: M. Y. Chan, Embedding of d-dimensional grids into optimal hypercubes, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.52-57, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72941]
• 9: Anoop Gupta, Wolf-Dietrich Weber, and Todd Mowry. Reducing Memory and Traffic Requirements for Scalable Directory-Based Cache Coherence Schemes. In Proceedings of the 1990 International Conference on Parallel Processmg (Vol. I Archztecture), pages 312-321, 1990.
• 10: Davib B. Gustavson, The Scalable Coherent Interface and Related Standards Projects, IEEE Micro, v.12 n.1, p.10-22, January 1992 [doi>10.1109/40.124376]
• 11: 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
• 12: Kendall Square Research. Kendall Square Research Technical Summary, 1992.
• 13: W. Michael, A scalable coherent cache system with a dynamic pointing scheme, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.358-367, November 16-20, 1992, Minneapolis, Minnesota, United States
• 14: Brian W. O'Krafka , A. Richard Newton, An empirical evaluation of two memory-efficient directory methods, Proceedings of the 17th annual international symposium on Computer Architecture, p.138-147, May 28-31, 1990, Seattle, Washington, United States
• 15: Steven K. Reinhardt , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , David A. Wood, The Wisconsin Wind Tunnel: virtual prototyping of parallel computers, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.48-60, May 10-14, 1993, Santa Clara, California, United States
• 16: 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]
• 17: 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

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Measurement, Performance, Theory

Keywords:
cache coherence, directory protocols, gray code, multiprocessors, shared-memory