Nepal - A Compiler for Nested Data Parallelism
The Nepal
Compiler is a testbed for research into the high-performance
implementation of nested data parallel
languages. Its aim is to simplify the implementation of algorithms that
operate on irregular data structures like sparse matricies or have irregular
control flow, while ensuring efficient and portable code with emphasis on
distributed-memory multiprocessors.
The Nepal system makes use of functional programming in two ways: It
compiles a purely functional, nested data parallel language and the compiler
is entirely implemented in the higher-order lazy functional language Haskell. While nested data parallelism can also
be expressed in an imperative language, a functional language significantly
simplifies devising and researching the optimisation techniques, which are
crucial for an efficient parallel implementation. The compiler is entirely
built around the idea of compilation as program transformation and,
in particular, applies Blelloch's flattening transformation and a variant
of deforestation, which preserves the parallelism in the optimised program.
- Developer:
Manuel M. T.
Chakravarty,
Gabriele Keller,
Wolf Pfannenstiel,
Roman Lechtchinsky,
Martin Simons
- Contact:
-
Manuel M. T. Chakravarty
Institute of Information Sciences and Electronics
Tennoudai 1-1-1
University of Tsukuba
Tsukuba, Ibaraki 305-8573
Japan
Tel.: +81 298 53-5532
Fax.: +81 298 50-3603 (or 53-5206)
Email: chak@score.is.tsukuba.ac.jp
- Number of sites: 3
- Number of users: so far, only the developers
- In use: still under development
- Language: Haskell
- Compilers:
Glasgow Haskell Compiler
- Line count: about 14K Haskell & 2K runtime system in C
- Availability: The source code of developer releases is freely
available at www.score.is.tsukuba.ac.jp/~chak/nepal/; the compiler works on every system supported by the
Glasgow Haskell Compiler; the runtime system supports the Cray T3E &
clusters of Unix/Linux workstations that have MPI (including one-sided
communication)
- Related publications:
-
How
Portable is Nested Data Parallelism?.
Manuel M. T. Chakravarty and Gabriele Keller.
In W. Cheng and A. S. M. Sajeev, editors, Proceedings of 6th Annual
Australasian Conference on Parallel And Real-Time Systems (PART '99),
LNCS, Springer-Verlag, 1999.
-
On the
Distributed Implementation of Aggregate Data Structures by Program
Transformation. Gabriele Keller and Manuel M. T. Chakravarty. In
José Rolim et al, editors, Parallel and Distributed Processing,
Fourth International Workshop on High-Level Parallel Programming Models and
Supportive Environments (HIPS'99), pp 108-122, LNCS 1586, Springer
Verlag, 1999.
-
Flattening
Trees. Gabriele Keller and Manuel M. T. Chakravarty.
In David Pritchard and Jeff Reeve, editors,
Euro-Par'98, Parallel Processing, pp 709-719,
LNCS 1470, Springer-Verlag, 1998.
-
A Calculational Approach to Flattening Nested Data Parallelism in
Functional Languages.
Gabriele Keller and Martin Simons.
In J. Jaffar and R. H. C. Yap, editors, Concurrency and Parallelism,
Programming, Networking, and Security: Second Asian Computing Science
Conference, ASIAN'96, pp. 234-243, LNCS 1179,
Springer Verlag, 1996.