Efficient Compilation of High-Level Data Parallel Algorithms.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1994
Accession Number
ADA290362

Entities

People

  • Dan Suciu
  • Val Tannen

Organizations

  • University of Pennsylvania

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Calculus
  • Computations
  • Computer Programming
  • Computers
  • Databases
  • High Level Languages
  • Information Science
  • Language
  • Parallel Computing
  • Programming Languages
  • Recursive Functions
  • Scalar Functions
  • Sequences
  • Simulations
  • Translations

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Aerial Unmanned Vehicle Swarm Micro Periodontal Dentistry.
  • Parallel and Distributed Computing.