Static Parallelization of Functional Programs: Elimination of Higher-Order Functions & Optimized Inlining
Functional programs have long been recognized as attractive subjects of an implicit static parallelization because functional programming excludes artificial dependences, which would restrict parallelism. One central concept which makes functional program
- PDF / 151,927 Bytes
- 5 Pages / 431 x 666 pts Page_size
- 61 Downloads / 178 Views
tract. Functional programs have long been recognized as attractive subjects of an implicit static parallelization because functional programming excludes artificial dependences, which would restrict parallelism. One central concept which makes functional programming a powerful paradigm is the higher-order function, which can have functions appearing in its arguments or result. We present an automatic method of eliminating higher-order functions, which is based on earlier work by Bell, Bellegarde and Hook [2]. The number of auxiliary functions added in the process is subsequently minimized by inlining transformations. Keywords: functional programming, Haskell, higher-order function, inlining, parallelization, skeletons.
1
Introduction
We report on first experiences with a new compiler for a functional language, called HDC, which supports the use of skeletons, i.e., higher-order functions which have customized parallel implementations, collected in a skeleton library. The overall idea is to equip HDC with implicit, high-quality parallelism through these skeleton implementations. The compiler consists of quite a number of phases; we concentrate on two here. One performs higher-order elimination (HOE), the other inlining. More complete information on the compiler is available elsewhere [6]. The following section sketches the different phases of our parallelizing compiler. Section 3 describes the HOE algorithm proposed in the literature and our modifications to it. Section 4 comments on the quality of the generated first-order program. Section 5 concludes.
2
The HDC Compiler
The HDC compiler [6, 9] translates a subset of Haskell [3] into an imperative language – at present, C with MPI calls. The main difference to Haskell is that HDC P. Amestoy et al. (Eds.): Euro-Par’99, LNCS 1685, pp. 930–934, 1999. c Springer-Verlag Berlin Heidelberg 1999
Static Parallelization of Functional Programs
931
is strict, in order to facilitate a compile-time parallelization. (However, invisibly to the programmer, strictness is partly eliminated by inlining transformations.) The compiler is based on the principle of compilation by transformation, which has already been used successfully in the Glasgow Haskell compiler GHC [10], and consists of the following phases [6]: scanning/parsing, using the tool happy desugaring list comprehension simplification lambda lifting, let elimination [8] simplification of list comprehensions type checking monomorphization elimination of functional arguments (HOE) elimination of mutual recursion (optional) case elimination generation of intermediate DAG code tuple elimination optimization cycle (optional) – inline expansion – rule-based DAG optimizations – size inference [5] 14. abstract code generation 15. automatic parallelization (optional) 16. code generation 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
3
Higher-Order Elimination (HOE)
The program subject to HOE must be well-typed according to the HindleyMilner rules. It must also be closed, i.e., all functions cited must be available to the HOE
Data Loading...
