Research on Synthesis of Concurrent Computing Systems.

Abstract

The object of our research is the codification of programming knowledge for the synthesis of concurrent programs. This final report presents the derivation of two concurrent algorithms: dynamic programming (for the class of problems that run in polynomial time on sequential machines) and array multiplication. Both derived concurrent versions run in linear time. The concurrent versions are significant and complex algorithms, though they are not new and already have been reported in the literature. The synthesis knowledge for these derivations is embodied in seven synthesis rules, preliminary versions of which are presented in this report. The rules will probably generalize to other classes of algorithms but we have not explored that issue yet. We have also discovered a pair of techniques called virtualization and aggregation. This pair of techniques (plus the other seven rules) is shown to be powerful enough to synthesize Kung's systolic array architecture (Kung-76) from a specification of matrix multiplication.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1982
Accession Number
ADA130048

Entities

People

  • Cordell Green
  • Richard M. King
  • Thomas C. Brown

Organizations

  • Kestrel Institute

Tags

Communities of Interest

  • Air Platforms
  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Case Studies
  • Computations
  • Computer Programming
  • Dynamic Programming
  • Geometry
  • Governments
  • Language
  • Multiprocessors
  • Optimization
  • Parallel Computing
  • Parallel Processing
  • Recognition
  • Sequences
  • Three Dimensional
  • Topology

Fields of Study

  • Computer science
  • Engineering

Readers

  • Linear Algebra
  • Parallel and Distributed Computing.
  • Theoretical Analysis.