Accession Number : ADA130048

Title :   Research on Synthesis of Concurrent Computing Systems.

Descriptive Note : Final technical rept. 2 Oct 81-30 Sep 82,

Corporate Author : KESTREL INST PALO ALTO CA

Personal Author(s) : King,Richard M ; Brown,Thomas C ; Green,Cordell

PDF Url : ADA130048

Report Date : Sep 1982

Pagination or Media Count : 45

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.

Descriptors :   *Computer programming, *Computer programs, Coding, Algorithms, Dynamic programming, Multiplication, Matrices(Mathematics), Parallel processing, Linearity, Time, Architecture, Synthesis, Transformations, Polynomials, Computer communications, Input output processing, Arrays, Optimization, Connectors, Reduction, Computers

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE