Parallel destructive updating in strict functional languages

ABSTRACT

In our recent paper, we gave an efficient interprocedural update analysis algorithm for strict functional languages with flat arrays and sequential evaluation. In this paper, we show that the same algorithm extends to a parallel functional language with additional constructs for partitioning and combining arrays. Even with parallel evaluation, the complexity of the analysis remains polynomial. The analysis has been implemented and the results show that several numerical algorithms such as direct and iterative methods for solving linear equations, LU, Cholesky, and QR factorizations, multigrid methods for solving partial differential equations, and non-numeric algorithms such as sorting can be implemented functionally with all updates made destructive. We describe a new array construct to specify a collection of updates on an array and show that problems like histogram, inverse permutation, and polynomial multiplication have efficient parallel functional solutions. Monolithic array operators can be considered as a special case of this new construct.

REFERENCES

• 1: Arvind , Rishiyur S. Nikhil , Keshav Pingali, I-structures: Data structures for parallel computing, Proceedings of the Workshop on Graph Reduction, p.336-369, September 29-October 01, 1986
• 2: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• 3: Adrienne Gael Bloss, Path analysis and the optimization of nonstrict functional languages, 1989
• 4: Adrienne Bloss, Update analysis and the efficient implementation of functional aggregates, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.26-38, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99373]
• 5: David C. Cann, Compilation techniques for high-performance applicative computation, 1989
• 6: David Cann, Retire Fortran?: a debate rekindled, Communications of the ACM, v.35 n.8, p.81-89, Aug. 1992 [doi>10.1145/135226.135231]
• 7: 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]
• 8: M. Draghicescu , S. Purushothaman, A compositional analysis of evaluation-order and its application, Proceedings of the 1990 ACM conference on LISP and functional programming, p.242-250, June 27-29, 1990, Nice, France [doi>10.1145/91556.91658]
• 9: Pascal Fradet, Syntactic detection of single-threading using continuations, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.241-258, June 1991, Cambridge, Massachusetts, United States
• 10: G. H. Golub. Matrix Computations. The Johns Hopkins University Press, 1988.
• 11: Gene Golub , James M. Ortega, Scientific computing: an introduction with parallel computing, Academic Press Professional, Inc., San Diego, CA, 1993
• 12: Carsten K. Gomard , Peter Sestoft, Globalization and live variables, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.166-177, June 17-19, 1991, New Haven, Connecticut, United States
• 13: K. Gopinath, Copy elimination in single assignment languages, Stanford University, Stanford, CA, 1988
• 14: K. Gopinath , J. L. Hennessy, Copy elimination in functional languages, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.303-314, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75304]
• 15: Juan Carlos Guzman, On expressing the mutation of state in a functional programming language, Yale University, New Haven, CT, 1993
• 16: J. Guzm~n and P. Hud~k. Singlo-three~ded polymorphic lambda calculus. In IEEE Symposium on Logic in Computer Science, 1990.
• 17: Paul Hudak, Arrays, non-determinism, side-effects, and parallelism: A functional perspective, Proc. of a workshop on Graph reduction, p.312-327, September 1987, Santa Fe, New Mexico, United States
• 18: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• 19: P. Hudak. Mutable abstract datatypes or how to have your state and munge it too. Technical report, Department of Computer Science, Yale University, 1993.
• 20: R. Nikhil. Id (version 90.0) reference manual. Technical Report CSG Memo 284-1, MIT, 545 Technology Square, Cambridge, MA 02139, August 1990.
• 21: A. V. S. Sastry, Efficient array update analysis of strict functional languages, University of Oregon, Eugene, OR, 1994
• 22: A. V. S. Sastry , William Clinger , Zena Ariola, Order-of-evaluation analysis for destructive updates in strict functional languages with flat aggregates, Proceedings of the conference on Functional programming languages and computer architecture, p.266-275, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165222]
• 23: David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
• 24: P. Sestoft. Replacing function parameters with global variables. Master's thesis, DIKU, University of Copenhagen, Oct. 1988.
• 25: Peter Sestoft, Replacing function parameters by global variables, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.39-53, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99374]
• 26: Guy L. Steele, Jr. , W. Daniel Hillis, Connection Machine Lisp: fine-grained parallel symbolic processing, Proceedings of the 1986 ACM conference on LISP and functional programming, p.279-297, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319870]
• 27: Vipin Swarup , Uday S. Reddy , Evan Ireland, Assignments for applicative languages, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.192-214, June 1991, Cambridge, Massachusetts, United States
• 28: Philip Wadler, A new array operation, Proc. of a workshop on Graph reduction, p.328-335, September 1987, Santa Fe, New Mexico, United States
• 29: Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]
• 30: P. Wadler. Linear types can change the world! In M. Broy and C. B. Jones, editors, Programming Concepts and Methods. North Holland, 1990. Presented at IFiP TC2 Working Conference on Programming Concepts and Methods, Sea of Galilee, Israel, April 1990.

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.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Design, Experimentation, Languages, Performance