DARPA/ISTO Quarterly Report

Abstract

A system of rules and techniques is developed for derivation of various classes of parallel algorithms including: 1) Systolic algorithms for various fixed connection networks; 2) Randomized parallel algorithms; 3) Parallel algorithms for tree and graph problems; and 4) Parallel algorithms for algebraic problems. The development is emphasized of fundamental derivation techniques that can be utilized in as wide a class of parallel algorithms as possible. The specific algorithms to be derived have themselves been carefully chosen to be as fundamental as possible. Algorithms and areas currently under investigation include: parallel list ranking, parallel graph connectivity, automatic parallel compilation from segmented straight-line programs, and derivation of pipelined algorithms for small-diameter networks.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1989
Accession Number
ADA216452

Entities

People

  • John Reif

Organizations

  • Duke University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • California
  • Compilers
  • Computations
  • Computer Programming
  • Computers
  • Contracts
  • Diameters
  • Geometry
  • Language
  • Lists (Data Structures)
  • Models
  • Parallel Computing
  • Product Prototyping
  • Programming Languages
  • Textbooks

Readers

  • Business Analytics
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.