Steven Anderson
Abstract
Monolithic approaches to functional language arrays, such as Haskell array comprehensions, define elements all at once, at the time the array is created, instead of incrementally. Although monolithic arrays are elegant, a naive implementation can be very inefficient. For example, if a compiler does not know whether an element has zero or many definitions, it must compile runtime tests. If a compiler does not know inter-element data dependencies, it must resort to pessimistic strategies such as compiling elements as thunks, or making unnecessary copies when updating an array.
Subscript analysis, originally developed for imperative language vectorizing and parallelizing compilers, can be adapted to provide a functional language compiler with the information needed for efficient compilation of monolithic arrays. Our contribution is to develop the number-theoretic basis of subscript analysis with assumptions appropriate to functional arrays, detail the kinds of dependence information subscript analysis can uncover, and apply that dependence information to sequential efficient compilation of functional arrays.
- 1 D.J.Kuck Abu-Sufah, W. and D.H.Lawrie. On the performance enhancement of paging systems through program analysis and transformation. IEEE Trans. Computers, C-30(5):341-355, 1981.]]Google Scholar
Digital Library
- 2 R. Allen and K. Kennedy. Automatic translation of Fortran programs to vector form. A CM TOP~AS, 9(4):491-542, 1987.]] Google ScholarDigital Library
- 3 S. Anderson. Non-strict arrays in a strict context. Research report, Yale University, Department of Computer Science, January.]]Google Scholar
- 4 V. Balasundaram. Interactive Parallelization of Numerical Scientific Programs. PhD thesis, Computer Science Department, Rice University, 1989.]] Google ScholarDigital Library
- 5 A. Bloss. Update analysis and efficient compilation of functional aggregates. In FPCA, pages 26-38, 1989.]] Google ScholarDigital Library
- 6 M. Burke and R. Cytron. Interprocedural dependence analysis and parallelization. In A CM SIGPLAN, pages 162-175, 1986.]] Google ScholarDigital Library
- 7 D.A.Padua B.Leazure D.J. Kuck, R.H.Kuhn and M.J.Wolfe. Dependence graphs and compiler optimizetion. in A CM POPL, pages 207-217, 1981.]] Google Scholar
- 8 J. Guzmalt and P.Hudak. Single-threaded polymorphic lambda calculus. In A CM Conf. on Logic in Computer Science, 1990.]]Google Scholar
- 9 P. Hudak. Alfl reference manual and programmer's guide. Research Report YALEU/DCS/RR-322, Second Edition, Yale University, October 1984.]]Google Scholar
- 10 P. Hudak. Arrays, non-determinism, side-effects, and parallelism: A functional perspective. In Proceedings of the Santa Fe Graph Reduction Workshop, pages 312- 327. Los Alamos/MCC, Springer-Verlag LNCS 279, October 1986.]] Google ScholarDigital Library
- 11 P. Hudak. A semantic model of reference counting. In A CM Conf. Lisp and Functional Programming, pages 351-363, 1986.]] Google ScholarDigital Library
- 12 P. Hudak. A semantic model of reference counting and its abstraction (detailed summary). In Proceedings 1986 A CM Conference on LISP and Functional Programming, pages 351-363. ACM, August 1986.]] Google ScholarDigital Library
- 13 P. Hudak and S. Anderson. HaskeU solutions to the language session problems at the 1988 Salishan high-speed computing conference. Technical Report YALEU/DCS/RR-627, Yale University, Department of Computer Science, January 1988.]]Google Scholar
- 14 P. Hudak and P. Wadler (editors). Report on the functional programming language hazkell. Technical Report YALEU/DCS/RR666, Yale University, Department of Computer Science, November 1988.]]Google Scholar
- 15 V. Hudak and P. Wadler (editors). Report on the programming language haskell, a non-strict purely functional language (version 1.0), October 1989. to appear in SIGPLAN Notices.]] Google ScholarDigital Library
- 16 K. Iverson. A Programming Language. Wiley, New York, 1962.]] Google ScholarDigital Library
- 17 R.M. Keller. Fel programmer's guide. AMPS TR 7, University of Utah, March 1982.]]Google Scholar
- 18 J.R. Mcgraw. The VAL language: description and analysis. TOPLAS, 4(1):44-82, January 1982.]] Google ScholarDigital Library
- 19 R.S. Nikhil, K. Pingali, and Arvind. Id Nouveau. Computation Structures Group Memo 265, Massachusetts Institute of Technology, Laboratory for Computer Science, July 1986.]]Google Scholar
- 20 Jr. Steele, Guy L. and W. Daniel Hillis. Connection machine lisp: Fine-grained parallel symbolic proceasing. In Proceedings 1986 A CM Conference on Lisp and Functional Programming, pages 279-297, Cambridge, Massachusetts, August 1986. ACM SIG- PLAN/SIGACT/SIGART.]] Google ScholarDigital Library
- 21 D.J.Kuck U. Banerjee, S.C.Chen and R.A.Towle. Time and parallel processor bounds for Fortran-like loops. IEEE Trans. Computers, C-28(9):660-670, September 1979.]]Google ScholarDigital Library
- 22 P. Wadler. A new array operation for functional Innguages. In LNCS 295: Proc. Graph Reduction Workshop, Santa Fe. Springer-Verlag, 1986.]] Google ScholarDigital Library
- 23 P. Wadler. List comprehensions. In S.L. Peyton Jones, editor, Implementation of Functional Pro. gramming Languages. Prentice-Hall, 1987.]]Google Scholar
- 24 P. Wadler. Deforestation. in LNCS 300: European Symposium on Programming. Springer-Verlag, 1988.]]Google Scholar
- 25 Michael J. Wolfe. Optimizing Supercompilers for Supercomputers. PhD thesis, University of illinois, 1982.]] Google ScholarDigital Library
Index Terms
- Compilation of Haskell array comprehensions for scientific computing
Recommendations
Compilation of Haskell array comprehensions for scientific computing
PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementationMonolithic approaches to functional language arrays, such as Haskell array comprehensions, define elements all at once, at the time the array is created, instead of incrementally. Although monolithic arrays are elegant, a naive implementation can be ...
Automatic SIMD vectorization for Haskell
ICFP '13: Proceedings of the 18th ACM SIGPLAN international conference on Functional programmingExpressing algorithms using immutable arrays greatly simplifies the challenges of automatic SIMD vectorization, since several important classes of dependency violations cannot occur. The Haskell programming language provides libraries for programming ...
Automatic SIMD vectorization for Haskell
ICFP '13Expressing algorithms using immutable arrays greatly simplifies the challenges of automatic SIMD vectorization, since several important classes of dependency violations cannot occur. The Haskell programming language provides libraries for programming ...
Comments