*** Superseded by Data Parallel Haskell ***

The Nepal Project
Compilation of Nested Data Parallelism

In the Nepal1 project, we investigate techniques for the high-performance implementation of nested data parallel languages. Our focus is on translation and optimisation schemes that can be formalised as source-to-source transformations as well as in high-performance runtime systems for the compiled code. We recently managed to generalise our approach such that we are no longer constrained to special purpose programming languages (like Nesl), but can apply our approach to standard functional languages, such as, Haskell and Standard ML.

The practical work of the project is currently focused on the integration of nested data parallelism into Haskell and the implementation of our translation and optimisation techniques into the Glasgow Haskell Compiler. Our approach is described in more detail in three papers, which discuss data parallel programming in Haskell, the translation of nested data parallelism, and optimisations by equational array fusion.

News

Current State

We are currently implementing the following three aspects of the system:

More details are available on Gabi Keller's project page.

The SCL Library

SCL is a highly portable library of collective operations whose interface is defined by an algebraic specification, to simplify compiler optimisations. It is implemented in C and includes runtime support for allocating and managing vector-based data structures. SCL, internally, uses a slim interface based on one-sided communication to access the communication primitives of the host machine or MPI-2. The slides of a talk outlining the design of SCL are available.

We are currently working on a Haskell binding to a revised version of SCL. In the meantime, the old library code is still accessible.

Software

Below are snapshots of the new parallel array library.

Old Stuff

The code of the array library and the flattening prototype compiler is available by anonymous CVS. The code is far from ready for general use, but may be of interest to other Haskell developers. Here is how you can get it (your input is in bold face; the password will, of course, not be echoed):


% cvs -d :pserver:anonymous@ceres.cse.unsw.edu.au:/home/chakcvs/cvs login
(Logging in to anonymous@ceres.cse.unsw.edu.au)
CVS password: anonymous
% cvs -d :pserver:anonymous@ceres.cse.unsw.edu.au:/home/chakcvs/cvs checkout flatten
list of checked out files
% cd flatten
% autoconf
      

The build process is a standard GNU-style ./configure && make. You will need at least version 4.08.x of GHC to build the code. To make array fusion work, you need GHC 5.00 upwards. However, there are still oustanding issues even with the latest development version of GHC, which leads to problems with some fusion rules and other optimisation problems. All this is being worked on. The array library is contained in the directory flatten/.

SCL releases:

Some source code is provided under the GPL (GNU General Public License) and some under the X11 license.

Related Publications

Many of the implementation techniques are based on Gabriele Keller's PhD thesis. We also have a list of publications related to nested data parallelism.

Related Projects

PSciCo @ CMU
PSciCo explores the use Nesl-style array-based parallel programming in Standard ML. The project covers the design of parallel algorithms as well as a thread-based implementation of nested data parallelism in the TILT compiler.
Irregular Parallel Algorithms @ UNC
This project explores the integration and compilation of nested data parallelism in essentially imperative languages, such as, Fortran dialects and Java. They are, in particular, also working on the flattening transformation.
Scandal @ CMU
This is were Nesl originated, but the project did also do a lot of work on parallel algorithms.

Project Members

Alphabetic list of core developers:
Manuel M. T. Chakravarty  chak@cse.unsw.edu.au
Gabriele Keller  keller@cse.unsw.edu.au
Roman Lechtchinsky  rl@cs.tu-berlin.de
Student(s) working in the project:
Rahul Bhargava  rbhargav@it.uts.edu.au
Former member(s) of the team:
Wolf Pfannenstiel  wolfp@cs.tu-berlin.de
Michael Schlosser  schlossm@cs.tu-berlin.de
Martin Simons  simons@cs.tu-berlin.de

Anybody who is interested to join the effort is very welcome!


1Nepal is an acronym for nested parallel language.


This page is part of Manuel Chakravarty's WWW-stuff.

Last modified: Fri Mar 31 15:10:55 EST 2006