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.