3.3.2 GpH -- Glasgow Parallel Haskell
Report by: Phil Trinder
The Team:
Phil Trinder, Kevin Hammond, Hans-Wolfgang Loidl, Alvaro Rebon Portillo, Andre Rauber du Bois, Mustafa Aswad, Abyd Al Zain.
Status:
Steaming Ahead!
GpH aims to provide low-pain parallelism, i.e. acceptable
performance with minimal programming effort. It does so by
introducing a single new primitive combinator: par x y that
returns y but may create a thread to evaluate x
depending on machine load. Evaluation strategies are
higher-order polymorphic functions that abstract over par and
seq to provide high level constructs to coordinate
parallelism, e.g. parList s applies strategy s to
every element of a list.
The project has been running since 1994 initially at Glasgow and
subsequently at Heriot-Watt and St Andrews Universities. Recent work
covers language, system and applications aspects, and consistently
emphasises the architecture independence (cf.
http://www.cee.hw.ac.uk/~dsg/gph/arch-indep.html) of our
approach. A robust version of GpH (GUM-4.06) is available for
RedHat-based Linux machines (binary snapshot
ftp://ftp.macs.hw.ac.uk/pub/gph/gum-4.06-snap-i386-unknown-linux.tar;
installation instructions
ftp://ftp.macs.hw.ac.uk/pub/gph/README.GUM). Versions for Sun
shared-memory machines, Debian, and an alpha-release based on GHC
5.02 are available on request <gph@cee.hw.ac.uk>.
Language:
We have recently produced a truly parallel
implementation of a referentially transparent bottom-avoiding choice
operator (
http://www.cee.hw.ac.uk/~dsg/gph/papers/drafts/flops-submitted.ps.gz)
and used it to explore a new class of parallel algorithms in GpH,
namely branch-and-bound. It reveals an interesting relationship
between non-strict and speculative parallel evaluation.
System:
We are developing the GUM implementation of GpH in
the following ways. We are investigating the challenges posed by
porting GUM to a computational GRID. To improve the architecture
independent performance of GpH we have added new features to its
implementation (GUM). The load balancing (
http://www.cee.hw.ac.uk/~dsg/gph/papers/drafts/sfp01-gum.ps.gz)
in GUM has been made more flexible by implementing low- and
high-watermarks on the spark pools, which represent potential
parallelism. Thread migration is being implemented as a technique of
avoiding gross load imbalance in applications with a small amount of
parallelism. For a better control of data locality in GpH
programs we are currently exploring language constructs with
explicit placement parameters as well as abstractions over these
basic constructs. We have improved the distributed shared memory
performance
(http://www.cee.hw.ac.uk/~dsg/gph/papers/ps/dsm02.ps.gz) of
GUM, in particular global address management and the graph packing,
enabling the user to optimise the parallel execution for execution
time or heap space.
An implementation of a time and space static analysis is nearing
completion. Although the current analysis is for a strict language,
the intention is to use the result of the analysis to select
appropriate computations for parallel evaluation.
Applications:
We have produced detailed comparisons of three
parallel functional languages : GpH (
http://www.cee.hw.ac.uk/~dsg/gph/), Eden (
http://www.mathematik.uni-marburg.de/~loogen/eden.html), PMLS
( http://www.cee.hw.ac.uk/Research/funct_prog.html),
discussing language and implementation differences (
http://www.cee.hw.ac.uk/~dsg/gph/papers/drafts/hosc-submitted.ps.gz).
Detailed performance results of several parallel programs on a
Beowulf cluster are given. A survey of parallel and distributed
Haskells (
http://www.cee.hw.ac.uk/~dsg/gph/papers/ps/jfp01.ps.gz)
has just appeared in the JFP special issue.
We are investigating the architecture independence of GpH by
developing a significant application (genetic alignment) for a
variety of parallel architectures: a Beowulf cluster, a SunServer
SMP. We have also published careful measurements of the Naira
parallel Haskell compiler.
3.3.2.1 Further reading:
http://www.cee.hw.ac.uk/~dsg/gph/