CMU-CS-95-170

This research was sponsored in part by the Wright Laboratory, Aeronautical Systems Center, Air Force Materiel Command, USAF, and the Advanced Research Projects Agency (ARPA) under grant number F33615-93-1-1330. It was also supported in part by an NSF Young Investigator Award under grant number CCR-9258525, and by Finmeccanica.
The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of Wright Laboratory or the U. S. Government.

Data-parallel, parallel algorithms, supercomputers, nested parallelism, PRAM model, parallel programming languages, collection-oriented languages.

Abstract:

This report describes NESL, a strongly-typed, applicative, data-parallel language. NESL is intended to be used as a portable interface for programming a variety of parallel and vector computers, and as a basis for teaching parallel algorithms. Parallelism is supplied through a simple set of data-parallel constructs based on sequences, including a mechanism for applying any function over the elements of a sequence in parallel and a rich set of parallel functions that manipulate sequences.

NESL fully supports nested sequences and nested parallelism--the ability to take a parallel function and apply it over multiple instances in parallel. Nested parallelism is important for implementing algorithms with irregular nested loops (where the inner loop lengths depend on the outer iteration) and for divide-and-conquer algorithms. NESL also provides a performance model for calculating the asymptotic performance of a program on various parallel machine models. This is useful for estimating running times of algorithms on actual machines and, when teaching algorithms, for supplying a close correspondence between the code and the theoretical complexity.

This report defines NESL and describes several examples of algorithms coded in the language. The examples include algorithms for median finding, sorting, string searching, finding prime numbers, and finding a planar convex hull. NESL currently compiles to an intermediate language called VCODE, which runs on vector multiprocessors (the CRAY C90 and J90), distributed memory machines (the IBM SP2, Intel Paragon, and Connection Machine CM-5), and sequential workstations. For many algorithms, the current implementation gives performance close to optimized machine-specific code for these machines.

Note: This report is an updated version of CMU-CS-92-103, which described version 2.4 of the language, and of CMU-CS-93-129, which described version 2.6 of the language. Some other documents that describe NESL are:

• The user's manual [11].
• An overview of the implementation with some timing results [8].
• A formal definition of the NESL cost model [23].

NESL: A Nested Data-Parallel Language (Version 3.1)

Guy E. Blelloch

Tue Nov 28 14:01:42 EST 1995

• Contents
• Introduction
  • Parallel Operations on Sequences
  • Nested Parallelism
  • Pairs
  • Types
  • Deriving Complexity
• Examples
  • String Searching
  • Primes
  • Planar Convex-Hull
• Language Definition
  • Data
    • Atomic Data Types
    • Sequences ([])
    • Record Types (datatype)
  • Functions and Constructs
    • Conditionals (if)
    • Binding Local Variables (let)
    • The Apply-to-Each Construct ({})
    • Defining New Functions (function)
    • Top-Level Bindings (=)
• References
• The NESL Grammar
• List of Functions
  • Scalar Functions
  • Sequence Functions
  • Functions on Any Type
  • Functions for Manipulating Strings
  • Functions with Side Effects
• Implementation Notes
• Index
• About this document ...