Accession Number : ADA290362

Title :   Efficient Compilation of High-Level Data Parallel Algorithms.

Descriptive Note : Technical rept.,

Corporate Author : PENNSYLVANIA UNIV PHILADELPHIA DEPT OF COMPUTER AND INFORMATION SCIENCE

Personal Author(s) : Suciu, Dan ; Tannen, Val

PDF Url : ADA290362

Report Date : APR 1994

Pagination or Media Count : 17

Abstract : 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.

Descriptors :   *PARALLEL PROCESSING, *HIGH LEVEL LANGUAGES, PARALLEL PROCESSORS, TIME, RECURSIVE FUNCTIONS, CALCULUS OF VARIATIONS.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE