pH : Parallel Haskell

A formal definition of the pHlanguage itself is available as CSG Memo #369. It defines pH in terms of Haskell. Some modifications have been added to the type system, including constructor classes; these are in line with existing Haskell implementations. The original pH manifesto is available in html format as well.

The pH language is is a parallel, eagerly-evaluated variant of Haskellwith syntactic provisions for loops, barriers, and I- and M- structure storage. The eager evaluation model of pH is similar to that of Id; the current version of the pH compiler shares a back end with the Id compiler, producing code for the Monsoon dataflow machine. The front end of the pH compiler is a modification of hbcc, an ordinary Haskell compiler developed by Lennart Augustsson. Optimizations have been added to parallelize list generation and traversal, while existing optimizations have been weakened somewhat so that they behave properly in the presence of side effects. The pH Prelude is largely identical to the Haskell Prelude, permitting many programs to compile without modification in either Haskell or pH. Functions which deal with infinite data structures (such as enumFrom) have been eliminated, and the error behavior of other functions (such as array) have been modified slightly. In addition, pH provides Prelude code for parallel list operations, I-structures, and M-structures. A variation on State Transformers will permit state-manipulating programs written in a subset of pH to be run under Haskell simply by incorporating additional code. It is hoped that by retaining much of the Haskell language, pH will allow direct parallelization of existing Haskell programs, and permit better comparisons between lazy and eager evaluation models.

There are two documents describing list traversal optimization. This material should be useful to functional programmers of every stripe, and not just implementors of eager languages. The documents are Jan-Willem Maessen's M.Eng. thesis, "Eliminating Intermediate Lists in pH Using Local Transformations" (with an accompanying abstract), and a shorter, more recent, technical memo "Simplifying Parallel List Traversal" which describes the current implementation of traversal optimization as a rewriting of the program structure. This paper, and the list traversal optimization itself, is being rewritten in response to the recent "Warm Fusion" work at Glasgow, which expands upon the original work (foldr/build optimization) which inspired the research at CSG.

There is also a series of CSG Memos which discuss various aspects of the semantics of pH and various ways to translate barriers into control flow. These include Normalizing Strategies for Multithreaded Interpretation and Compilation of Non-Strict Languages by Shail Aditya, Semantics of Barriers in a Non-Strict, Implicitly-Parallel Language by Shail Aidtya, Arvind, and Joseph Stoy (the FPCA '95 paper), and most recently Semantics of pH: A parallel dialect of Haskell, by Shail Aidtya, Arvind, Lennart Augustsson, Jan-Willem Maessen, and Rishiyur S. Nikhil., a revised version of the paper presented at the 1995 Haskell Workshop.

Goals

Background

• We have experience compiling the functional language Id for dataflow machines.
• We would like to focus our attention on compilation techniques for parallel execution on stock architectures.
• Since the invention of Id, many advances have been made in the design of functional languages

Benfits to Modifying Haskell

• Advanced type system (classes for overloading, records, higher-order types)
• Existing, stable compiler front ends
• Body of research on optimizations, analyses, etc.
• Constant improvements in all of the above (active research)
• Understood by many
• Large corpus of code (subsumes most Id code)

The pH Language

• Includes all Haskell syntax, and the same type inference system (an extension of Hindley-Milner type inference).
• Adds I- and M-structures, which work as in Id.
• Uses type classes (existing mechanism) to typecheck imperative functions.
• Adds new syntax for while and for loops.
• Permits the use of barriers as in Id, which force execution to wait until immediately preceding side effects are complete.

Compilation Techniques

• Id programs can be transliterated into pH.
• Front end written elsewhere (Lennart Augustsson, Chalmers)
• A largely language-independent optimization phase parallelizes list and array comprehensions (which would otherwise be sequential).
• Front end can connect to old Id compiler, thus producing code for Monsoon (and in principle Berkeley's TAM/TL0, etc.).
• New back end will produce multithreaded code for PowerPC platforms; this is the main focus of our compiler research at the moment.

Compiler Issues Currently being Investigated

• Algorithms for partitioning code into threads preserve some of the dataflow legacy. We are exploring:
  • How we want our programs to work semantically;
  • How to achieve those semantics in an actual implementation;
  • How this corresponds with what we already know about partitioning functional programs into threads.
• There are several reasons one might use a non-strict or lazy functional language; we need to decide which are important:
  • Expressive Power: It's easier to write programs without side effects if we permit non-strict data dependencies. A recent paper by Schauser suggests that only a limited form of non-strictness is needed in this case.
  • Parallelism: Non-strictness by its very nature frees the compiler from concerns about execution order. Thus, independent computations can always be run in parallel, dramatically increasing the available parallelism in a program. However, it is not always clear how to determine when this parallelism can most usefully be exploited.
  • Equational Reasoning: Non-strict languages are naturally modeled by the lambda calculus. Many optimizations can be expressed as rules for rewriting lambda terms, meaning that they are simpler to understand and thus to verify. Unfortunately, much of the equational behavior is lost when side effects and barriers are added to the language, and this makes reasoning and optimization much more difficult.
• We would like to experiment with different semantics of the underlying language:
  • There needs to be a common framework for these semantics, so optimizations don't need to be re-written with each experiment
  • We want to try very strict versions of pH---for example, "strict except for data structures".
  • At the other extreme, a few provisions for laziness could simplify problems with efficiency.

State of Implementation

Current Work

• Library issues and implementation, along with high-level code optimizations based on algebraic programming and types are being investigates by Jan-Willem Maessen.
• Optimizing code at all levels - Much work has been done on this subject in Id by Joanna Kulik. This ought to be directly applicable to pH, assuming we retain a compatible (graph-like) world view.
• Partitioning code into threads - This is the focus of work at CSG by Satyan Coorg. The idea is to partition eager code into strict partitions. These partitions are gauranteed to run - to completion (without blocking) - exactly when all of their input is available. The partitioning phase is thus a bridge between conventional functional (or dataflow) compilation and multithreaded architectures
• A graph-like virtual machine - Much of the work performed by an Id or pH program is analogous to the "graph building" performed by lazy compiled graph-reduction systems such as the G-machine. This observation is leading us to examine graph-like views of pH execution. Shail Aditya has been at the vanguard of this work, and there are several variations on this theme now written up; the most recent is available as CSG Memo #374
• *RISC - multithreaded generic back end: *RISC is a hopefully fairly architecture-independent description of multithreaded code, with an instruction set loosely based on that of the PowerPC. The goal is to generate code for any RISC-based machine, but initially PowerPC-based workstations and SMP's, and the *T-NG machine. The back end efforts are thus closely tied to the *T-NG project.

Built compiler and libraries (I think):
  http://web.mit.edu/~jmaessen/Public/phc-compiler.tar.gz

Compiler source only:
  http://web.mit.edu/~jmaessen/Public/phc-front-end.tar.gz

Full release (recommended, as who knows what the binaries are linked
against):
  http://web.mit.edu/~jmaessen/Public/phc.tar.gz

It works on UltraSPARC SMP's (anything with 64-bit compare and swap),
and the uniprocessor version works on arbitrary SPARC boxes.  Hackers
will have to find the right define flag to set uniprocessor vs
multiprocessor.  Requires a haskell compiler with the hbc libraries
(such as hbc, or a determined hacker's installation of ghc) to build
the compiler itself from source, but this is otherwise the most
portable component.  Any use of the compiler requires GCC 2.7.3; later
non-2.8 versions of gcc may also work, but haven't been tested.

Support-wise you're pretty much on your own.

Haskell dialect: A lot of the syntax in the pH book doesn't exist
directly in this implementation.  The parser doesn't accept records
with named fields, and qualified names can't be used to refer to
imports.  There's no special syntax for I- and M-structure constructs;
look in ICell.hs, MCell.hs, and PHArray.hs in the libraries to see
what exists.  For barriers, the notation uses nested "seq" and "par"
constructs: 

let seq par a = f x
            b = g x
        c = a + b
in  c

This executes f x and g x in parallel, then when they have terminated
sums them and returns the sum.  Note the use of indentation to
indicate the extent of the "seq" and "par" sub-blocks.

Licensing: The license prevents redistribution.  It should be open
  source.  I want to open it up, but that requires getting actual
  written permission from Lennart and Arvind.  Lennart is in favor
  near as I can tell, but he never replies to my mail when I get
  specific so it's been stuck.