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
An interactive tutorial and overviewNESL 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.
Papers on NESL
A library of parallel algorithms
An online interpreter
What is NESL used for?
Getting the current release
Quick reference guide
NESL is loosely based on the programming language ML.
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.
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.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.
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.
The development of NESL was funded in part by NSF under an NYI (award CCR-9258525).