Performance evaluation of hybrid hardware and software distributed shared memory protocols

ABSTRACT

Hardware distributed shared memory (DSM) systems efficiently support fine grain sharing of data by maintaining coherence at the level of individual cache lines and providing automatic replication in processor caches. Software DSM systems, on the other hand, amortize high communication costs by maintaining coherence at coarser granularities and replicating data at the level of local main memories. Even though software DSM systems have traditionally been targeted towards loosely coupled environments, some of the techniques are potentially useful in the context of tightly coupled multiprocessors. In particular, communicating data at a coarse grain can sometimes be more efficient than transferring the data as individual cache lines. Furthermore, replication in local memories can accommodate applications with larger working sets as compared to replication in processor caches only. Therefore, combining the two techniques in a hybrid protocol can potentially exploit the benefits of each approach. This paper proposes one such hybrid protocol and evaluates its performance in the context of the FLASH multiprocessor architecture. The hybrid system allows the programmer to optionally identify regions of data shared at a coarse granularity. Coherence for such data is maintained at the grain of the entire region using a software-DSM-style protocol. We evaluate the performance gains of this approach through a detailed simulation study of several parallel applications. Our preliminary results show that the hybrid protocol can eliminate a substantial fraction of remote cache misses through bulk transfer of coarse grain data regions and replication of such data in local memories. The performance gains over hardware cache coherence are modest at low network latencies, but increase substantially at higher network latencies and processor speeds. Finally, we show that similar to cache-only memory architectures, the hybrid protocol is insensitive to data placement issues.

REFERENCES

• 1: Sarita V. Adve , Mark D. Hill, Weak ordering—a new definition, Proceedings of the 17th annual international symposium on Computer Architecture, p.2-14, May 28-31, 1990, Seattle, Washington, United States
• 2: Anant Agarwal , Beng-Hong Lim , David Kranz , John Kubiatowicz, APRIL: a processor architecture for multiprocessing, Proceedings of the 17th annual international symposium on Computer Architecture, p.104-114, May 28-31, 1990, Seattle, Washington, United States
• 3: 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]
• 4: Jean-Loup Baer and Tien-Fu Chen, An effective on-chip preloading scheme to reduce data access penalty. Technical Report 91-03-07, University of Washington, March 1991.
• 5: B. Bershad and M. Zekauskas. Midway: Shared memory parallel programming with entry consistency for distributed memory multiprocessors. Technical Report CMU-CS-91-170~ Camegie-MeUon University, September 1991.
• 6: Brian Bershad, Matthew Zekauskas, and Wayne Sawdon. The Midway distributed shared memory system. In Proceedings of COMP- CON'93, pages 528-537, February 1993.
• 7: John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
• 8: 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
• 9: Rohit Chandra, Anoop Gupta, and John L. Hennessy. Integrating concurrency and data abstraction in the COOL programming language. IEEE Computer, August 1994. To appear.
• 10: J. Chase , F. Amador , E. Lazowska , H. Levy , R. Littlefield, The Amber system: parallel programming on a network of multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.147-158, November 1989
• 11: Czarek Dubnicki , Thomas J. LeBlanc, Adjustable block size coherent caches, Proceedings of the 19th annual international symposium on Computer architecture, p.170-180, May 19-21, 1992, Queensland, Australia
• 12: M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
• 13: Sandhya Dwarkadas , Peter Keleher , Alan L. Cox , Willy Zwaenepoel, Evaluation of release consistent software distributed shared memory on emerging network technology, Proceedings of the 20th annual international symposium on Computer architecture, p.144-155, May 16-19, 1993, San Diego, California, United States
• 14: S. J. Eggers , R. H. Katz, The effect of sharing on the cache and bus performance of parallel programs, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.257-270, April 03-06, 1989, Boston, Massachusetts, United States
• 15: Michael J. Feeley , Henry M. Levy, Distributed shared memory with versioned objects, conference proceedings on Object-oriented programming systems, languages, and applications, p.247-262, October 18-22, 1992, Vancouver, British Columbia, Canada
• 16: 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
• 17: 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
• 18: Stephen R. Goldschmidt , John L. Hennessy, The accuracy of trace-driven simulations of multiprocessors, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.146-157, May 10-14, 1993, Santa Clara, California, United States
• 19: Erik Hagersten , Anders Landin , Seif Haridi, DDM: A Cache-Only Memory Architecture, Computer, v.25 n.9, p.44-54, September 1992 [doi>10.1109/2.156381]
• 20: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• 21: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 22: David Kranz , Kirk Johnson , Anant Agarwal , John Kubiatowicz , Beng-Hong Lim, Integrating message-passing and shared-memory: early experience, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.54-63, May 19-22, 1993, San Diego, California, United States
• 23: John Kubiatowicz , Anant Agarwal, Anatomy of a message in the Alewife multiprocessor, Proceedings of the 7th international conference on Supercomputing, p.195-206, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165970]
• 24: 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
• 25: Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690--691, September 1979.
• 26: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, Proceedings of the 17th annual international symposium on Computer Architecture, p.148-159, May 28-31, 1990, Seattle, Washington, United States
• 27: 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]
• 28: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 29: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 30: Todd Mowry , Anoop Gupta, Tolerating latency through software-controlled prefetching in shared-memory multiprocessors, Journal of Parallel and Distributed Computing, v.12 n.2, p.87-106, June 1991 [doi>10.1016/0743-7315(91)90014-Z]
• 31: R. S. Nikhil , G. M. Papadopoulos , Arvind, T: a multithreaded massively parallel architecture, Proceedings of the 19th annual international symposium on Computer architecture, p.156-167, May 19-21, 1992, Queensland, Australia
• 32: Kendall Square Research. KSR1 Technical Summary. Waltham, MA, 1992.
• 33: Martin Rinard. The Design and Implementation of Jade, a high-level Portable Parallel Programming Language. PhD thesis, Department of Computer Science, Stanford University. In preparation.
• 34: Martin C. Rinard , Daniel J. Scales , Monica S. Lam, Jade: A High-Level, Machine-Independent Language for Parallel Programming, Computer, v.26 n.6, p.28-38, June 1993 [doi>10.1109/2.214440]
• 35: Edward Rothberg , Anoop Gupta, Techniques for improving the performance of sparse matrix factorization on multiprocessor workstations, Proceedings of the 1990 conference on Supercomputing, p.232-241, October 1990, New York, New York, United States
• 36: Edward Rothberg and Anoop Gupta. An efficient block-oriented approach to parallel sparse cholesky factorization. Technical Report CSL-TR-92-533, Computer Systems Lab, Stanford University, July 1992.
• 37: Harjinder S. Sandhu , Benjamin Gamsa , Songnian Zhou, The shared regions approach to software cache coherence on multiprocessors, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.229-238, May 19-22, 1993, San Diego, California, United States
• 38: 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]
• 39: Per Stenström , Truman Joe , Anoop Gupta, Comparative performance evaluation of cache-coherent NUMA and COMA architectures, Proceedings of the 19th annual international symposium on Computer architecture, p.80-91, May 19-21, 1992, Queensland, Australia
• 40: Josep Torrellas, Monica Lam, and John Hennessy. Shared data placement optimizat~ons to reduce multiprocessor cache miss rates. In Proceedings of the 1990 International Conference on Parallel Processing, pages II: 266-270, August 1990.
• 41: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization

  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Design, Measurement, Performance, Theory