A PROVABLE TIME AND SPACE EFFICIENT IMPLEMENTATION OF NESL

In this paper we prove time and space bounds for the implementation of the programming language NESL on various parallel machine models. NES L is a sugared typed lambda-calculus with a set of array primitives an d an explicit parallel map over arrays. Our results extend previous wo rk on provable implementation bounds for functional languages by consi dering space and by including arrays. For modeling the cost of NESL we augment a standard call-by-value operational semantics to return two cost measures: a DAG representing the sequential dependences in the co mputation, and a measure of the space taken by a sequential implementa tion. We show that a NESL program with w work (nodes in the DAG), d de pth (levels in the DAG), and s sequential space can be implemented on a p processor butterfly network, hypercube, or CRCW PRAM using O(w/p d log p) time and O(s + dp log p) reachable space.(1) For programs wi th sufficient parallelism these bounds are optimal in that they give l inear speedup and use space within a constant factor of the sequential space.