Analyzing stores and references in a parallel symbolic language

ABSTRACT

We describe an analysis of a parallel language in which processes communicate via first-class mutable shared locations. The sequential core of the language defines a higher-order strict functional language with list data structures. The parallel extensions permit processes and shared locations to be dynamically created; synchronization among processes occurs exclusively via shared locations.The analysis is defined by an abstract interpretation on this language. The interpretation is efficient and useful, facilitating a number of important optimizations related to synchronization, processor/thread mapping, and storage management.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: Paul S. Barth , Rishiyur S. Nikhil , Arvind Nikhil, M-structures: extending a parallel, non-strict, functional language with state, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.538-568, June 1991, Cambridge, Massachusetts, United States
• 3: Adrienne Bloss , P. Hudak , J. Young, An optimising compiler for a modern functional language, The Computer Journal, v.32 n.2, p.152-161, April 1989 [doi>10.1093/comjnl/32.2.152]
• 4: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• 5: Jyh-Herng Chow, June 1993. Personal Communication.
• 6: Jyh-Herng Chow , William Ludwell Harrison, III, Compile-time analysis of parallel programs that share memory, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143194]
• 7: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• 8: Eric C. Cooper and J. Gregory Morrisett. Adding Threads to Standard ML. Technical Report CMU-CS- 90-186, School of Computer Science, Carnegie Mellon University, December 1990.
• 9: Patrick. Cousot. Semantic Foundations of Program Analysis. In Program Flow Analysis: Theory and Foundation, pages 303-342. Prentice-Hall, 1981.
• 10: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 11: Saumya K. Debray, Static inference of modes and data dependencies in logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.418-450, July 1989 [doi>10.1145/65979.65983]
• 12: Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
• 13: Richard P. Gabriel , John McCarthy, Queue-based multi-processing LISP, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.25-44, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802019]
• 14: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 15: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 16: W. Horwat , A. A. Chien , W. J. Dally, Experience with CST: programming and implementation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.101-109, June 19-23, 1989, Portland, Oregon, United States
• 17: Paul Hudak , Jonathan Young, Collecting interpretations of expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.269-290, April 1991 [doi>10.1145/103135.103139]
• 18: Williams Ludwell Harrison III. The Interprocedurai Analysis and Automatic Parallelization of Scheme Programs. Lisp and Symbolic Computation: an International Journal, 2(3/4):179-396, 1989.
• 19: Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, June 1990
• 20: Suresh Jagannathan , Jim Philbin, A foundation for an efficient multi-threaded scheme system, Proceedings of the 1992 ACM conference on LISP and functional programming, p.345-357, June 22-24, 1992, San Francisco, California, United States
• 21: Monica S. Lam , Martin C. Rinard, Coarse-grain parallel programming in Jade, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.94-105, April 21-24, 1991, Williamsburg, Virginia, United States
• 22: J. M. Lucassen , D. K. Gifford, Polymorphic effect systems, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.47-57, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73564]
• 23: John Mellor-Crummey, On-the-fly detection of data races for programs with nested fork-join parallelism, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.24-33, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125861]
• 24: Nicolas Mercouroff, An Algorithm for Analyzing Communicating Processes, Proceedings of the 7th International Conference on Mathematical Foundations of Programming Semantics, p.312-325, March 25-28, 1991
• 25: J. Gregory Morrisett , Andrew Tolmach, Procs and locks: a portable multiprocessing platform for standard ML of New Jersey, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.198-207, May 19-22, 1993, San Diego, California, United States
• 26: Jonathan A. Rees , Norman I. Adams IV, T: a dialect of Lisp or LAMBDA: The ultimate software tool, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.114-122, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802142]
• 27: John H. Reif , Scott A. Smolka, Data flow analysis of distributed communicating processes, International Journal of Parallel Programming, v.19 n.1, p.1-30, Feb. 1990 [doi>10.1007/BF01407862]
• 28: John H. Reppy, CML: A higher concurrent language, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.293-305, June 24-28, 1991, Toronto, Ontario, Canada
• 29: E. Shapiro, Concurrent prolog: collected papers, MIT Press, Cambridge, MA, 1987
• 30: Olin Shivers. Data-flow Analysis and Type Recovery in Scheme. In Topics in Advanced Language Implementation. MIT Press, 1990.
• 31: Olin Shivers, The semantics of Scheme control-flow analysis, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-198, June 17-19, 1991, New Haven, Connecticut, United States
• 32: Guy L. Steele, Jr., Making asynchronous parallelism safe for the world, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.218-231, December 1989, San Francisco, California, United States [doi>10.1145/96709.96731]
• 33: Stephen Weeks , Suresh Jagannathan , James Philbin, A concurrent abstract interpreter, Lisp and Symbolic Computation, v.7 n.2-3, p.173-193, June 1994 [doi>10.1007/BF01018693]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: T

General Terms:
Algorithms, Languages, Theory, Verification