In Proceedings of SPAA, June 1994.
We present a high-level parallel calculus for nested sequences, NSC, offered as a possible theoretical ``core'' of an entire class of collection-oriented parallel languages. NSC is based on while-loops as opposed to general recursion. A formal, machine independent definition of the parallel time complexity and the work complexity of programs in NSC is given. Our main results are: (1) We give a translation method for a particular form of recursion, called map-recursion, into NSC, that preserves the time complexity and adds an arbitrarily small overhead to the work complexity, and (2) We give a compilation method for NSC into a very simple vector parallel machine, which preserves the time complexity and again adds an arbitrarily small overhead to the work complexity.
See here for the paper.
Back to DB Group Homepage
sharker@saul.cis.upenn.edu