High-Level Architecture Independence via Parallel Graph Reduction

Project Summary


Title:	High-Level Architecture Independence via Parallel Graph Reduction
Investigator:	Hans-Wolfgang Loidl
Grant no.:	APART fellowship 624
Institution:	Dept of Computing and Elec Eng, Heriot-Watt University
Duration:	1/8/1999 - 31/7/2002
Funding Body:	Austrian Academy of Sciences

The long-term aim of my research is to make the computational power of multi-processor systems available to non-specialists in parallel programming. The specific goal of my fellowship is to develop a system for high-level parallel computation, demonstrating reasonable performance across a range of parallel architectures with no or minimal program changes. To achieve these I focus on the development of systems for parallel computation using a minimal parallel extension of the standard functional language Haskell, GpH. The language is implemented on a parallel graph reduction machine, GUM, that abstracts over most architecture-dependent aspects of the execution.

Austrian Academy of Sciences

State of the Project

Implementation

The current version of GpH is part of the CVS repository for the Glasgow Haskell Compiler (GHC) and can be checked out from there. Go to the GHC web page to find out details how to do this. We have used this version in a couple of measurements performed on our Beowulf machine (see the GpH papers page). We are currently working on performance comparisons of our system with two related parallel functional languages: Eden and PMLS.

Programming Language

We have recently extended evaluation strategies, our programming technique for controlling parallelism in GpH, to incorporate mechanisms for data clustering. We use Haskell type classes and manual program transformation to increase the task granularity and the data locality of parallel computations. Details are discussed in our clustering paper listed below.

Applications

In cooperation with Wolfgang Schreiner from RISC-Linz I am working on GpH/Maple, a system combining GpH as parallel coordination language with the Maple computer algebra system. This combination enables the user to implement symbolic applications in GpH and call arbitrary Maple functions from within GpH. At the moment we have a sequential prototype ready, and we have implemented three simple symbolic applications in GpH. Details of this strand of research can be found on the GpH/Maple web page.

Downloading GpH

You have two options in downloading GpH:

Check out the most recent version of GHC from the GHC CVS repository. See the CVS cheat sheet on a quick intro how to use the CVS repository.
Download a source bundle for GUM from the GpH web page.

In both cases, the README.GUM file explains how to install GHC and GUM from these sources and how to compile and execute parallel programs.

Documentation

User's Guide

To get you started with using GpH check the Gentle Introduction to GPH. This document provides a general introduction to the language, gives a step-by-step introduction with some simple parallel programs, and gives some practical information on installation, execution, and visualisation.

Implementor's Guide

If you are a fearless runtime-system hacker and want to extend the existing GUM system, take a look at the Stg Survival Sheet (sort-of a very drafty Implementor's Guide).

Papers

This a list of recent papers published in the frame of the APART 624 project. Earlier papers (before March 1998) can be found on my publications page.

Drafts

NB: The papers in this subsection are still in draft stage and not formally published, yet.

M. Lange, H-W. Loidl.
"Parallel and Symbolic Model Checking for Fixpoint Logic with Chop".
In PDMC'04 --- Intl. Workshop on Parallel and Distributed Techniques in Verification, London, U.K, September 2004. Submitted.
A. Rauber Du Bois, P. Trinder, H-W. Loidl.
"mHaskell: Mobile Computation in a Purely Functional Language".
In Haskell Workshop, Snowbird, Utah, September, 2004. Submitted.

Journal papers

H-W. Loidl, F. Rubio Diez, N.R. Scaife, K. Hammond, U. Klusik, R. Loogen, G.J. Michaelson, S. Horiguchi, R. Pena Mari, S.M. Priebe, A.J. Rebon Portillo, and P.W. Trinder.
"Comparing Parallel Functional Languages: Programming and Performance".
Higher-order and Symbolic Computation, 16(3):203-251, 2003.
ps.gz
H-W. Loidl, P.W. Trinder, and C. Butz.
"Tuning Task Granularity and Data Locality of Data Parallel GPH Programs".
Parallel Processing Letters, 11(4):471--486, December 2001. Selected papers from HLPP2001 - International Workshop on High-level Parallel Programming and Applications, Universite d'Orleans, France, March 26-27, 2001.
ps.gz
P.W. Trinder, H-W. Loidl, and R.F. Pointon.
"Parallel and Distributed Haskells".
Journal of Functional Programming, 12(4&5):469-510, July 2002. Special Issue on Haskell.
ps.gz
H-W. Loidl, P.W. Trinder, K. Hammond, S.B. Junaidu, R.G. Morgan, and S.L. Peyton Jones.
"Engineering Parallel Symbolic Programs in GPH."
Concurrency - Practice and Experience, 11:701-752, 1999.
ps.gz

Conference Papers

A. Rauber Du Bois, P. Trinder, H-W. Loidl.
"Towards Mobility Skeletons".
In CMPP'04 --- Intl. Workshop on Constructive Methods for Parallel Programming, Stirling, Scotland, UK, July 2004.
ps.gz
A. Rauber Du Bois, R. Pointon, H-W. Loidl, P. Trinder
"A Declarative Parallel Bottom-Avoiding Choice"
In SBAC-PAD 2002 - Symposium on Computer Architecture and High Performance Computing, Vitoria, Brazil, October 28-30, 2002.
ps.gz
H-W. Loidl.
"The Virtual Shared Memory Performance of a Parallel Graph Reducer"
In CCGrid 2002 - International Symposium on Cluster Computing and the Grid (DSM 2002: International Workshop on Distributed Shared Memory on Clusters), pp. 311-318, May 21 - 24, 2002, Berlin, Germany. IEEE Press.
ps.gz
R.F. Pointon, S.M. Priebe, H-W. Loidl, R. Loogen, P.W. Trinder.
"Functional vs Object-Oriented Distributed Languages". In EUROCAST'01 --- International Conference on Computer Aided Systems Theory, Formal Methods and Tools for Computer Science, Palmas de Gran Canaria, Spain, February 19-23, 2001. LNCS 2178, pp. 101-116. Springer-Verlag.
ps.gz
P.W. Trinder, H-W. Loidl, E. Barry Jr., K. Hammond, U. Klusik, S.L. Peyton Jones, and A.J. Rebon Portillo.
"The Multi-Architecture Performance of the Parallel Functional Language GPH".
In Euro-Par 2000 --- Parallel Processing, LNCS 1900, pp. 739-743. Springer-Verlag, August 2000.
ps.gz

Workshop Papers

A. Rauber Du Bois, P.W. Trinder, and H-W. Loidl.
"Implementing Mobile Haskell"
TFP 2003: Fourth Symposium on Trends in Functional Programming, September 11th-12th 2003, Edinburgh, Scotland. Intellect 2004.
ps.gz
Andre Rauber Du Bois, Phil Trinder, and Hans-Wolfgang Loidl.
"Mobile Computation in Haskell"
Accepted for WFLP'03: 12th Int'l Workshop on Functional and (Constraint) Logic Programming, Valencia, Spain, June 12-13. ps.gz
A. Rauber Du Bois, H-W. Loidl, P. Trinder.
"Thread Migration in a Parallel Graph Reducer".
IFL'02 International Workshop on the Implementation of Functional Languages Madrid, Spain, September 16-18, 2002. LNCS 2670, pp. 199-214. Springer-Verlag.
ps.gz
A.J. Rebon Portillo, K. Hammond, H-W. Loidl, P. Vasconcelos.
"Cost Analysis using Automatic Size and Time Inference".
IFL'02 International Workshop on the Implementation of Functional Languages Madrid, Spain, September 16-18, 2002. LNCS 2670, pp. 232-247. Springer-Verlag.
ps.gz
H-W. Loidl.
"Load Balancing in a Parallel Graph Reducer".
In SFP'01 --- Scottish Functional Programming Workshop, University of Stirling, Scotland, August 22-24, 2001. Trends in Functional Programming, vol. 3, pp. 63-74, Intellect.
ps.gz
H-W. Loidl, U. Klusik, K. Hammond, R. Loogen, and P.W. Trinder.
"GpH and Eden: Comparing Two Parallel Functional Languages on a Beowulf Cluster".
In SFP'00 --- Scottish Functional Programming Workshop, University of St Andrews, Scotland, July 26-28, 2000. Trends in Functional Programming, vol. 2, pp. 39-52, Intellect, December 2000.
ps.gz
P.W. Trinder, R.F. Pointon, and H-W. Loidl.
"Towards Runtime System Level Fault Tolerance for a Distributed Functional Language".
In SFP'00 --- Scottish Functional Programming Workshop, University of St Andrews, Scotland, July 26-28, 2000. Trends in Functional Programming, vol. 2, pp. 103-114, Intellect, December 2000.
ps.gz
R.F. Pointon, P.W. Trinder, and H-W. Loidl.
"The Design and Implementation of GdH: a Distributed Functional Language".
In IFL'00 --- International Workshop on the Implementation of Functional Languages, RWTH Aachen, Germany, September 4-7, 2000. LNCS 2011, pp. 53-70, Springer-Verlag, January 2001.
ps.gz

People

Hans-Wolfgang Loidl (primary investigator)
Phil Trinder
Robert Pointon
Andre Rauber Du Bois