Efficient compilation of high-level data parallel algorithms | Zendy

Dan Suciu | Zendy; Val Tannen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Efficient compilation of high-level data parallel algorithms

Author(s) -

Dan Suciu,

Val Tannen

Publication year - 1994

Publication title -

scholarlycommons (university of pennsylvania)

Language(s) - English

Resource type - Conference proceedings

ISBN - 0-89791-671-9

DOI - 10.1145/181014.181032

Subject(s) - recursion (computer science) , computer science , overhead (engineering) , complexity class , computational complexity theory , parallel algorithm , parallel computing , algorithm , class (philosophy) , theoretical computer science , core (optical fiber) , programming language , artificial intelligence , telecommunications

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research