LCM: memory system support for parallel language implementation

ABSTRACT

Higher-level parallel programming languages can be difficult to implement efficiently on parallel machines. This paper shows how a flexible, compiler-controlled memory system can help achieve good performance for language constructs that previously appeared too costly to be practical.

Our compiler-controlled memory system is called Loosely Coherent Memory (LCM). It is an example of a larger class of Reconcilable Shared Memory (RSM) systems, which generalize the replication and merge policies of cache-coherent shared-memory. RSM protocols differ in the action taken by a processor in response to a request for a location and the way in which a processor reconciles multiple outstanding copies of a location. LCM memory becomes temporarily inconsistent to implement the semantics of C** parallel functions efficiently. RSM provides a compiler with control over memory-system policies, which it can use to implement a language's semantics, improve performance, or detect errors. We illustrate the first two points with LCM and our compiler for the data-parallel language C**.

References

1. 1.Sarita V. Adve and Mark D. Hill. A Unified Formalization of Four Shared-Memory Models. IEEE Transactions on Parallel and Distributed Systems, 4(6):613-624, 1993.
2. 2.Anant Agaxwal, Richard Simoni, Mark Horowitz, and John Hennessy. An Evaluation of Directory Schemes for Cache Coherence. In Proceedings of the 15th Annual International Symposium on Computer Architecture, pages 280-289, 1988.
3. 3.Zahira Ammarguellat and W.L. Harrison III. Automatic Recognition of Induction Variables and Recurrence Relations by Abstract Interpretation. In Proceedings o.f the SIGPLAN '90 Conference on Programming Language Design and Implementation (PLDI), pages 283-295, June 1990.
4. 4.Andrew W. Appel, John R. Ellis, and Kai Li. Realtime Concurrent Collection on Stock Multiprocessors. In Proceedings o/ the SIGPLAN '88 Conference on Programming Language Design and Implementation (PLDI), pages 11-20, June 1988.
5. 5.Andrew W. Appel and Kai Li. Virtual Memory Primitives for User Programs. In Proceedings of the Fourth International Con/erence on Architectural Support/or Programming Languages and Operating Systems (ASPLOS IV), pages 96-107, April 1991.
6. 6.Monica Beltrametti, Kenneth Bobey, and John R. Zorbas. The Control Mechanism for the Myrias Parallel Computer System. Computer Architecture News, 16(4):21-30, September 1988.
7. 7.John K. Bennett, John B. Carter, and Willy Zwanepoel. Munin: Distributed Shared Memory Based on Type- Specific Memory Coherence. In Second A CM SIGPLAN Symposium on Principles ~4 Practice of Parallel Programming (PPOPP), pages 168-176, February 1990.
8. 8.Guy E. Blelloch. NESL: A Nested Data-Parallel Language (Version 2.6). Technical Report CMU-CS-93-129, Department of Computer Science, Carnegie Mellon University, April 1993.
9. 9.William J. Bolosky and Michael L. Scott. False Sharing and its Effect on Shared Memory Performance. In Proceedings of the Fourth Symposium on Experiences with D~stributed and Multiprocessor Systems (SEDMS), September 1993.
10. 10.John B. Carter, John K. Bennett, and Willy Zwanepoel. Implementation and Performance of Munin. In Proceedings of the Thirteenth A CM Symposium on Operating System Principles (SOSP), pages 152-164, October 1991.
11. 11.David Chaiken, John Kubiatowicz, and Anant Agarwal. LimitLESS Directories: A Scalable Cache Coherence Scheme. In Proceedings o/the Fourth International Conference on Architectural Support/or Programming Languages and Operating Systems (ASPLOS IV), pages 224- 234, April 1991.
12. 12.Siddhartha Chatterjee, Guy E. Blelloch, and Allan L. Fischer. Size and Access Inference for Data-Parallel Programs. In Proceedings of the $IGPLAN '91 Conference on Programming Language Design and Implementation (PLDI), pages 130-144, June 1991.
13. 13.Alan L. Cox, Sandhya Dwarkadas, Pete Keleher, Honghui Lu, Ramakrishnan Rajamony, and Willy Zwaenepoel. Software Versus Hardware Shared-Memory implementation: A Case Study. in Proceedings of the 21st Annual International Symposium on Computer Architecture, pages 106-117, April 1994.
14. 14.Babak Falsafi, Alvin Lebeck, Steven Reinhardt, Ioannis Schoinas, Mark D. Hill, James Larus, Anne Rogers, and David Wood. Application-Specific Protocols for User- Level Shared Memory. In Proceedings of Supercomputing 9J, November 1994. To appear.
15. 15.Michael J. Feeley and Henry M. Levy. Distributed Shared Memory with Versioned Objects. In OOPSLA '93: Ob3ect-Oriented Programming Systems, Languages and Applications Conference Proceedings, pages 247-262, October 1992.
16. 16.PhiIlip J. Hatcher, Michael J. Quinn, Anthony J. Lapadula, Bradley K. Seevers, Ray J. Anderson, and Robert R. Jones. Data-Parallel Programming on MIMD Computers. IEEE Transactions on Parallel and Distributed Systems, 2(3):377-383, July 1991.
17. 17.High Performance Fortran Forum. High Performance Fortran Language Specification. Version 1.0, May 1993.
18. 18.Mark D. Hill, James R. Larus, Steven K. Reinhardt, and David A. Wood. Cooperative Shared Memory: Software and Hardware for Scalable Multiprocessors. ACM Transactions on Computer Systems, 11(4):300-318, November 1993. Earlier version appeared in ASPLOS V, Oct. 1992.
19. 19.David Kranz, Kirk Johnson, Anant Agarwal, John Kubiatowicz, and Beng-Hong Lira. Integrating Message-Passing and Shared-Memory: Early Experience. In Fifth A CM SIGPLAN Symposium on Principles ~ Practice of Parallel Programming (PPOPP), pages 54-63, May 1993.
20. 20.Jeffrey Kuskin et al. The Stanford FLASH Multiproces~ sor. In Proceedings o.f the 21st Annual International Symposium on Computer Architecture, pages 302-313, April 1994.
21. 21.James R. Larus. C**: a Large-Grain, Object-Oriented, Data-Parallel Programming Language. In Utpal Banerjee, David Gelernter, Alexandru Nicolau, and David Padua, editors, Languages And Compilers for Parallel Computing (5th International Workshop), pages 326-341, New Haven, August 1992. Springer-Verlag.
22. 22.James 1~. Larus. Compiling for Shared-Memory and Message-Passing Computers. A CM Letters on Programming Languages and Systems, 2(1-4):165-180, March- December 1994.
23. 23.Daniel Lenoski, James Laudon, Kourosh Gharachorloo, Anoop Gupta, and John Hennessy. The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor. In Proceedings of the 17th Annual International Symposium on Computer Architecture, pages 148-159, June 1990.
24. 24.Kai Li and Paul Hudak. Memory Coherence in Shared Virtual Memory Systems. A CM Transactions on Computer Systems, 7(4):321-359, November 1989.
25. 25.Robert H.B. Netzer and Barton P. Miller. Improving the Accuracy of Data Race Detection. In Third A CM SIG- PLAN Symposium on Principles ~4 Practice of PavaUel Programming (PPOPP), pages 133-144, April 1991.
26. 26.Steven K. Reinhardt, James R. Larus, and David A. Wood. Tempest and Typhoon: User-Level Shared Memory. In Proceedings of the 21st Annual Internatwnal Symposium on Computer Architecture, pages 325-337, April 1994.
27. 27.John R. Rose and Guy L. Steele Jr. C*: An Extended C Language for Data Parallel Programming. In Proceedings of the Second International Conference on Supercornputrag, pages 2-16, Santa Clara, California, May 1987.
28. 28.Gary W. Sabot. The Paralation Model: Architecture- Independent Parallel Programming. MIT Press, 1988.
29. 29.Joel H. Saltz, Ravi Mirchandaney, and Kay Crowley. Run- Time Parallelization and Scheduling of Loops. IEEE Transactions on Computers, 40(5):603-612, May 1991.
30. 30.Ioannis Schoinas, Babak Falsafi, Alvin R. Lebeck, Steven K. Reinhardt, James R. Larus, and David A. Wood. Fine-grain Access Control for Distributed Shared Memory. In Proceedings of the Sixth International Conference on Architectural Support 7'or Programming Languages and Operating Systems (ASPLOS l/l), October 1994. To appear.
31. 31.Guy L. Steele Jr. Making Asynchronous Parallelism Safe for the World. In Conference Record of the Seventeenth Annual A CM Symposium on Principles of Programming Languages, pages 218-231, January 1990.
32. 32.David A. Wood, Satish Chandra, Babak FaIsafi, Mark D. Hill, James R. Larus, Alvin R. Lebeck, James C. Lewis, Shubhendu S. Mukherjee, Subbarao Patacharla, and Steven K. Reinhardt. Mechanisms for Cooperative Shared Memory. In Proceedings of the 20th Annual International Symposmm on Computer Architecture, pages 156-168, May 1993.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Evaluation

    • Metrics

• Information systems

  • Information storage systems

    • Storage management

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language types

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

        • Memory management