Systolic algorithms as programs

DOI10.1007/BF01661171MaRDI QIDQ1087008zbMATH OpenFDO

Authors K. Mani Chandy, Jayadev Misra

Publication date 1986

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01661171

zbMATH Keywords

invariantsLU-decompositionmatrix multiplicationmultiple assignmentprogram developmentproofs of programs

Mathematics Subject Classification ID

Theory of operating systems (68N25) Algorithms in computer science (68W99)

Review text

We represent a systolic algorithm by a program consisting of one multiple assignment statement that captures its operation and data flow. We use invariants to develop such programs systematically. We present two examples, matrix multiplication and LU-decomposition of a matrix.

Recommendations

• scientific article; zbMATH DE number 4100593
• scientific article; zbMATH DE number 53038
• scientific article; zbMATH DE number 3896291
• Systolic algorithms
• A systolic algorithm for dynamic programming
• Systolic algorithms for the dynamic programming problem
• scientific article; zbMATH DE number 108384
• On the design of some systolic algorithms
• Synthesis of systolic algorithm design
• The derivation of systolic implementations of programs

Cites work

• An example of stepwise refinement of distributed programs: quiescence detection
• The Design of Optimal Systolic Arrays

Cited in

(12)

• The formal development of a parallel program performing LU-decomposition
• The derivation of systolic implementations of programs
• A systolic algorithm for dynamic programming
• Developments in concurrent Kleene algebra
• Communication patterns and input patterns in distributed computing (invited talk)
• scientific article; zbMATH DE number 4100593 (Why is no real title available?)
• Systolic algorithms for the dynamic programming problem
• scientific article; zbMATH DE number 53038 (Why is no real title available?)
• Generic systolic arrays: A methodology for systolic design
• A notational approach to formulation of systolic array programs
• Towards systolizing compilation
• The projection of systolic programs

This page was built for publication: Systolic algorithms as programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1087008)