Fast parallel implementation of lazy languages—the EQUALS experience

ABSTRACT

This paper describes EQUALS, a fast parallel implementation of a lazy functional language on a commercially available shared-memory parallel machine, the Sequent Symmetry. In contrast to previous implementations, we detect parallelism automatically by propagating exhaustive (normal form) demand. Another important difference between EQUALS and previous implementations is the use of reference counting for memory management instead of garbage collection. Our implementation shows that reference counting leads to very good scalability, low memory requirements and improved locality. We compare our results with sequntial SML/NJ as well as parallel (v, G-machine and GAML implementations.

REFERENCES

• AEL88: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• Aug84: L. Augustsson, A compiler for lazy M~, LFP,1984.
• Aug89: L. Augustsson and T. Johnsson, Parallel graph reduction with the (u, G) machzne, FPCA, t989.
• Dar81: John Darlington , Mike Reeve, ALICE a multi-processor reduction machine for the parallel evaluation CF applicative languages, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.65-76, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806764]
• Geo89: Lal George, An abstract machine for parallel graph reduction, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.214-229, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99387]
• Gol88a: B. Goldberg, Buckwheat: Graph reduction on shared-memory multiprocessor, LFP, t988.
• Gol88b: Benjamin F. Goldberg, Multiprocessor execution of functional programs, 1988
• Joh84: Thomas Johnsson, Efficient compilation of lazy evaluation, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.58-69, June 17-22, 1984, Montreal, Canada
• HL79: G. Huet and J.J. Levy, Computatzons ~n hot, ambiguous hnear term rewriting systems, Tech Rep. No. 359, 1979, IRIA, ke Chesney, France, 1979.
• Lav88: Alain Laville, Implementation of Lazy Pattern Matching Algorithms, Proceedings of the 2nd European Symposium on Programming, p.298-316, March 21-24, 1988
• Mar91: Luc Maranget, GAML: a parallel implementation of Lazy ML, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.102-123, June 1991, Cambridge, Massachusetts, United States
• MKH90: Eric Mohr , David A. Kranz , Robert H. Halstead, Jr., Lazy task creation: a technique for increasing the granularity of parallel programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.185-197, June 27-29, 1990, Nice, France [doi>10.1145/91556.91631]
• PS90: Laurence Puel , Ascander Suarez, Compiling pattern matching by term decomposition, Proceedings of the 1990 ACM conference on LISP and functional programming, p.273-281, June 27-29, 1990, Nice, France [doi>10.1145/91556.91670]
• PJ87: S.L. Peyton Jones, GRIP: A parallel graph reduction machine, FPCA, 1987.
• SPR90: R. C. Sekar , Shaunak Pawagi , I. V. Ramarkrishnan, Small domains spell fast strictness analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.169-183, December 1989, San Francisco, California, United States [doi>10.1145/96709.96727]
• SRR92: R. C. Sekar , R. Ramesh , I. V. Ramakrishnan, Adaptive Pattern Matching, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.247-260, July 13-17, 1992
• Seq87: Sequent Computer Systems, Sequent guide to parallel programming, 1987.
• WW87: Paul Watson , Ian Watson, Evaluating functional programs on the FLAGSHIP machine, Proc. of a conference on Functional programming languages and computer architecture, p.80-97, October 1987, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Languages, Performance