The NESL System

Java [14] has been defined as ``a simple, object-oriented, distributed, interpreted, robust, secure, architecture-neutral, portable, high-performance, multithreaded, dynamic, buzzword-compliant, general-purpose programming language''.

In the same spirit of buzzword-compliance, NESL [3] is an interactive, high-level, strongly-typed, applicative, sequence-based, portable, nested data-parallel language. The primary data structure in NESL is the sequence, each element of which can itself be a sequence. Parallelism is expressed in NESL through an apply-to-each form over elements of sequences and through parallel operations on sequences.

The current NESL system consists of three layers, as shown in Figure 1 (see [7] for full details of the system). The front end of the system is an interactive compiler that lets users enter NESL expressions and programs. Every NESL expression is first compiled into an intermediate language called VCODE [5]. The compiler then invokes a VCODE interpreter (either locally or on a remote machine), passes it the VCODE via rcp or a distributed filesystem, and reads back the results. The VCODE interpreter is the back end of the system; using VCODE as a portable intermediate language allows the user to execute the same code transparently on different machines, ranging from a Unix workstation to a parallel supercomputer.

  
Figure 1: Components (boxes) and languages (lines) of the current NESL system. Solid lines represent translation, and dotted lines represent linkage to C libraries (rounded boxes).

The primary duties of the NESL compiler are implementing high-level aspects of the NESL language (such as type checking and the removal of higher-order code) and converting operations on arbitrarily nested sequences into operations on segmented vectors [2]. Although NESL was designed primarily to support efficient data-parallel programming, the high-level algorithmic nature of the language also makes it ideal for teaching and prototyping algorithms [4].

The middle layer of the system consists of the intermediate language VCODE and its interpreter. A VCODE program manipulates a stack of strongly-typed vectors. Each vector contains an arbitrary number of atomic values of a single type; VCODE vectors cannot be nested, unlike the NESL sequences they represent. The language provides a set of vector operations, stack manipulation instructions, and associated control and memory management instructions. The main tasks of the VCODE interpreter are managing the stack and vector memory efficiently, and implementing the vector operations via calls to CVL. The extra overhead of interpreting VCODE instructions, rather than executing a compiled version of them, is amortized over the length of the vectors on which they operate. Note that VCODE shares several properties with Java bytecode [10]: portability, strong typing, a stack-based execution model, and a design allowing for easy interpretation.

At the bottom of the system is CVL (C Vector Library), a machine-specific library that implements an abstract vector machine [6]. An example of a CVL function is add_wuz, which adds the corresponding elements of two integer vectors together and returns the results in a third vector. CVL is the only part of the system that must be rewritten for a new architecture [11].