Application-specific protocols for user-level shared memory

ABSTRACT

Recent distributed shared memory (DSM) systems and proposed shared-memory machines have implemented some or all of their cache coherence protocols in software. One way to exploit the flexibility of this software is to tailor a coherence protocol to match an application's communication patterns and memory semantics. This paper presents evidence that this approach can lead to large performance improvements. It shows that application-specific protocols substantially improved the performance of three application programs--appbt, em3d, and barnes--over carefully tuned transparent shared memory implementations. The speed-ups were obtained on Blizzard, a fine-grained DSM system running on a 32-node Thinking Machines CM-5.

REFERENCES

• 1: 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.
• 2: 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
• 3: 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
• 4: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 5: Matthew I. Frank and Mary K. Vernon. A Hybrid Shared Memory/Message Passing Parallel Machine. In Proceedings of the 1993 International Conference on Parallel Processing (Vol. I Architecture), pages 232-236, August 1993.
• 6: Dana S. Henry , Christopher F. Joerg, A tightly-coupled processor-network interface, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.111-122, October 12-15, 1992, Boston, Massachusetts, United States
• 7: 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]
• 8: W. Daniel Hillis , Lewis W. Tucker, The CM-5 Connection Machine: a scalable supercomputer, Communications of the ACM, v.36 n.11, p.31-40, Nov. 1993 [doi>10.1145/163359.163361]
• 9: Kendall Square Research. Kendall Square Research Technical Summary, 1992.
• 10: 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
• 11: 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
• 12: James R. Larus, Compiling for shared-memory and message-passing computers, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.165-180, March–Dec. 1993 [doi>10.1145/176454.176514]
• 13: James R. Larus , Thomas Ball, Rewriting executable files to measure program behavior, Software—Practice & Experience, v.24 n.2, p.197-218, Feb. 1994 [doi>10.1002/spe.4380240204]
• 14: James R. Larus , Brad Richards , Guhan Viswanathan, LCM: memory system support for parallel language implementation, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.208-218, October 05-07, 1994, San Jose, California, United States
• 15: 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]
• 16: 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]
• 17: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 18: 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
• 19: Steven K. Reinhardt , Babak Falsafi , David A. Wood, Kernel Support for the Wisconsin Wind Tunnel, USENIX Microkernels and Other Kernel Architectures Symposium, p.73-90, September 20-23, 1993
• 20: 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
• 21: 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
• 22: Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.297-306, October 05-07, 1994, San Jose, California, United States
• 23: 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]
• 24: Daniel Stodolsky , J. Bradley Chen , Brian N. Bershad, Fast Interrupt Priority Management in Operating System Kernels, USENIX Microkernels and Other Kernel Architectures Symposium, p.105-110, September 20-23, 1993
• 25: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 26: 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
• 27: William A Wulf. Compilers and Computer Architecture. IEEE Computer, 14(7):41-47, July 1981.