Generating multithreaded code from parallel haskell for symmetric multiprocessors

This dissertation presents pHc , a new compiler for Parallel Haskell (pH) with complete support for the entire language. pH blends the powerful features of a high-level, higher-order language with implicitly parallel, non-strict semantics. The result is a language that is easy to use but tough to compile. The principal contribution of this work is a new code-generation algorithm that works directly on λ*, a terse intermediate representation based on the λ-calculus. All the power of the original language is preserved in λ*, and in addition, the new representation makes it easy to express the important concept of threads, groups of expressions that can execute sequentially, at a high-level. Code generation proceeds in two steps. First, the compiler turns λ* programs into multithreaded code for the Shared-Memory Threaded (SMT) machine, an abstract symmetric multiprocessor (SMP). The SMT machine simplifies the code-generator, by providing special mechanisms for parallelism, and improves its portability, by isolating it from any particular SMP. Unlike previous compilers for similar languages, the SMT code generated by pHc makes use of suspensive threads for better use of sequential processors. Second, the compiler transforms SMT instructions into executable code. In keeping with the goals of simplicity and portability, the final product is emitted as a C program, with some extensions for compiler-controlled multithreading. This code is linked with a Run-Time System (RTS) that provides two facilities: a work-stealing scheduler and a memory manager with garbage-collection. To evaluate the performance of the code, we generated instrumented programs. Using a small but varied set of benchmarks, we measured the components of run-time, the instruction mix, the scalability of code up to eight processors, and as a comparison, the single-processor performance against two of the latest Haskell compilers. We found encouraging speedups up to four processors, but rarely beyond. Moreover, we found substantial overhead in single-processor performance. These results are consistent with our emphasis on completeness and correctness first and on performance second. We conclude with some suggestions for future work that will remedy some of the shortcomings discovered in the evaluation. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)