Nesl: A nested data-parallel language

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 supercomputers, and as a basis for teaching parallel algorithms. Parallelism is supplied through a simple set of data-parallel constructs based on vectors, including a mechanism for applying any function over the elements of a vector in parallel, and a broad set of parallel functions that manipulate vectors. Nesl fully supports nested vectors and nested parallelism|the ability to take a parallel function and then apply it over multiple instances in parallel. Nested parallelism is impor-tant for implementing algorithms with complex and dynamically changing data structures, such as required in many graph or sparse matrix algorithms. Nesl also provides a mecha-nism for calculating the asymptotic running time for a program on various parallel machine models, including the parallel random access machine (PRAM). This is useful for approxi-mating running times of algorithms on actual machines, and when teaching algorithms to supply a close correspondence between the code and the theoretical complexity