N-Body Separators Support Tree Graph Connectivity
Click on any of the above.

NESL: A Parallel Programming Language

NESL is a parallel language developed at Carnegie Mellon by the SCandAL project. It integrates various ideas from the theory community (parallel algorithms), the languages community (functional languages) and the system's community (many of the implementation techniques). The most important new ideas behind NESL are

  1. Nested data parallelism: this feature offers the benefits of data parallelism, concise code that is easy to understand and debug, while being well suited for irregular algorithms, such as algorithms on trees, graphs or sparse matrices (see the examples above or in our library of algorithms).
  2. A language based performance model: this gives a formal way to calculated the work and depth of a program. These measures can be related to running time on parallel machines.
The main emphasis in the design of NESL was to make parallel programming easy and portable. Algorithms are typically significantly more concise in NESL than in most other parallel programming languages. Furthermore the code closely resembles high-level pseudocode. Here is a comparison of a parallel quicksort in NESL and MPI (10 lines of code vs. 1700). Of course this comes at the cost of placing more responsibility on the compiler and runtime system for achieving good efficiency.
- An interactive tutorial and overview
- Papers on NESL
- A library of parallel algorithms
- Algorithm animations
- An online interpreter
- What is NESL used for?
- Getting the current release
- Quick reference guide
NESL currently runs on Unix workstations, the IBM SP-2, the Thinking Machines CM5, the Cray C90 and J90, the MasPar MP2, and the Intel Paragon. Our recent effort has been on an portable MPI back end, and an implementation for symmetric multiprocessors, such as the SGI Power Challenge or the DEC AlphaServer.

NESL is loosely based on the programming language ML.

Papers on NESL

A complete list of NESL related papers can be found in our list of publications. Here is an annotated bibliography of the papers that are most relevant to NESL.
- Programming Parallel Algorithms. Describes and motivates the two main ideas behind NESL, nested data parallelism and the language based performance model. It appears in CACM, Mar 1996.

- Implementation of a Portable Nested Data-Parallel Language. Outlines the current implementation of NESL and gives some performance numbers on a variety of parallel machines. It appears in JPDC, Nov 1994.

- NESL: A Nested Data-Parallel Language. The language definition, including a complete list of functions. It does not contain the operational semantics (see below).

- NESL User's Manual. Describes how to set up the NESL environment and how to use the various features in NESL (such as tracing, profiling and using remote machines).

- A Provable Time and Space Efficient Implementation of NESL. Includes the operational semantics of NESL and a proof that the work and depth bounds can be mapped into running time on various machine models.

What is NESL used for?

Teaching: We have found NESL very useful for teaching parallel algorithms. It has allowed us to do give out homework assignments with significantly more interesting problems than would be possible with other languages. For example here is a homework assignment on the finite-volume method for fluid flow. This involves setting up the problem using the Delaunay triangulation of an unstructured mesh, and then solving it using the conjugate gradient technique on an irregular sparse matrix. This is a two week assignment. Other assignments include finding all-closest-pairs in the plane and shortest paths in a graph. Here is a course on parallel algorithms for which we use NESL.

Algorithm Experimentation: We have used NESL extensively for running experiments on algorithms. In particular it has allowed us to quickly compare the work required by various algorithms and improve the algorithms. Here are some of the algorithms we have experimented with using NESL:

- Delaunay triangulation:We have run experiments on a variety of parallel algorithms for planar Delaunay triangulation and have developed a practical variant of an algorithm of Edelsbrunner and Shi. This work is described in the paper Developing a practical projection-based parallel Delaunay algorithm which appears in the the Proceedings of the ACM Symposium on Computational Geometry, May 1996.

- The N-body problem: We have compared three algorithms for the N-body problem: the Barnes-Hut, Greengard's algorithm and a hybrid. All three were code in NESL and the relative costs under various assumptions were studied. This work is described in the paper A Practical Comparison of N-Body Algorithms which appears in the proceedings of the Dimacs implementation challenge workshop, October 1994.

- Graph Connectivity We have compared several algorithms for graph connectivity and derived a hybrid technique which appears very promising. This work is described in the paper A Comparison of Data-Parallel Algorithms for Connected Components which appears in the proceedings of the ACM Symposium on Parallel Algorithms and Architectures, June 1994.

- Others:Other algorithms experiments that have used NESL include a comparison of graph separators and the development of a support tree conjugate gradient technique.

Algorithm Animation: NESL is very well suited for developing animations of parallel algorithms. All the animations on the algorithm animations page are fully written in NESL as is the Pittsburgh Map server. NESL has a well developed library of window routines. Many were specifically designed with animations in mind. Also, the execution image for the animations can be quite small requiring little effort on the part of the host machine. Even though the full NESL image is large, only the intermediate code (VCODE) along with the VCODE interpreter is required to run a NESL applications.

blelloch@cs.cmu.edu. Comments welcome!