Article

Free access

Research on synthesis of concurrent computing systems (Extended Abstract)

Author:

Richard M. KingAuthors Info & Claims

ISCA '83: Proceedings of the 10th annual international symposium on Computer architecture

Pages 39 - 46

https://doi.org/10.1145/800046.801636

Published: 13 June 1983 Publication History

PDF eReader

Abstract

The object of our research is the codification of programming knowledge for the synthesis of concurrent programs. We present sample rules and techniques that we show can be used to derive two concurrent algorithms: dynamic programming (for the class of problems that run in polynomial time on sequential machines) and array multiplication. For both derived concurrent versions the code runs 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. We expect these rules to generalize to other classes of algorithms.

We have also discovered a pair of techniques called virtualization and aggregation. This pair of techniques (plus the seven rules) is shown to be powerful enough to synthesize Kung's systolic array architecture [Kung-76] from a specification of matrix multiplication.

References

[1]

Aho and Ullman "The Theory of Parsing, Translation and Compiling"; Volume 1, Prentice-Hall, Pp. 314-320

Digital Library

Google Scholar

[2]

Aho, Hopcroft and Ullman "The Design and Analysis of Computer Algorithms", Addison Wesley Pp. 67-68

Digital Library

Google Scholar

[3]

Thomas C. Brown "Inference Requirements Analysis and Implementation Proposal for Two Synthesis Rules", Kestrel Tech Report #KES.U.82.10, 1982, Chapter 2

Google Scholar

[4]

Sally A. Browning "The Tree Machine: A Highly Concurrent Computing Environment", California Institute of Technology Ph.D. Thesis, 1980

Digital Library

Google Scholar

[5]

Cordell Green, Daniel Chapiro, and Thomas Pressburger "Research on Synthesis of Concurrent Computing Systems", 1981, Kestrel Tech Report

Google Scholar

[6]

Cordell Green, et. al. "Research on Knowledge-Based Programming and Algorithm Design—1981", 1981, Kestrel Tech Report #KES.U.81.2

Google Scholar

[7]

Elaine Kant "Efficiency Considerations in Program Synthesis: A Knowledge-Based Approach", Stanford Ph.D. Thesis, 1979

Digital Library

Google Scholar

[8]

Richard M. King "Synthesis of Concurrent Computing Systems", Kestrel Tech Report #KES.U.82.10, 1982, Chapter 1

Google Scholar

[9]

Donald Knuth "The Art of Computer Programming"; Volume 3, Addison Wesley, Pp. 433-447

Digital Library

Google Scholar

[10]

H.T. Kung and Charles E. Leiserson "Systolic Arrays for VLSI", Sparse Matrix Proceedings, 1978

Google Scholar

[11]

Richard J. Lipton and Jacobo Valdef "Census Functions: an Approach to VLSI Upper Bounds", IEEE Symposium on the Foundations of Computer Science, 1981 Pp. 13-22

Google Scholar

Cited By

View all

Zedan H(1990)Key references in distributed computer systems 1959–1989Distributed Computer Systems10.1016/B978-0-408-02938-4.50016-4(193-295)Online publication date: 1990
https://doi.org/10.1016/B978-0-408-02938-4.50016-4
Anantharaman TBisiani RAiso H(1986)A hardware accelerator for speech recognition algorithmsProceedings of the 13th annual international symposium on Computer architecture10.5555/17407.17382(216-223)Online publication date: 1-Jun-1986
https://dl.acm.org/doi/10.5555/17407.17382
Anantharaman TBisiani R(1986)A hardware accelerator for speech recognition algorithmsACM SIGARCH Computer Architecture News10.1145/17356.1738214:2(216-223)Online publication date: 1-May-1986
https://dl.acm.org/doi/10.1145/17356.17382
Show More Cited By

Index Terms

Research on synthesis of concurrent computing systems (Extended Abstract)
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

Research on synthesis of concurrent computing systems (Extended Abstract)

The object of our research is the codification of programming knowledge for the synthesis of concurrent programs. We present sample rules and techniques that we show can be used to derive two concurrent algorithms: dynamic programming (for the class of ...
Transactions for concurrent object-oriented programming systems
OOPSLA/ECOOP '88: Proceedings of the 1988 ACM SIGPLAN workshop on Object-based concurrent programming
Concurrent object-oriented programming systems (COOPS) require support for fault tolerance, concurrency control, consistent commitment of changes and program-initiated rollback. It is sometimes suggested that the classical transaction processing model ...
Extended abstract: a race-free hardware modeling language
MEMOCODE '05: Proceedings of the 2nd ACM/IEEE International Conference on Formal Methods and Models for Co-Design

We describe race-free properties of a hardware description language called GEZEL. The language describes networks of cycle-true finite-state-machines with datapaths (FSMDs). We derive a set of four rules under which a network of such FSMDs satisfies the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISCA '83: Proceedings of the 10th annual international symposium on Computer architecture

June 1983

424 pages

ISBN:0897911016

DOI:10.1145/800046

ACM SIGARCH Computer Architecture News Volume 11, Issue 3
June 1983
413 pages
ISSN:0163-5964
DOI:10.1145/1067651
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
200
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)17

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zedan H(1990)Key references in distributed computer systems 1959–1989Distributed Computer Systems10.1016/B978-0-408-02938-4.50016-4(193-295)Online publication date: 1990
https://doi.org/10.1016/B978-0-408-02938-4.50016-4
Anantharaman TBisiani RAiso H(1986)A hardware accelerator for speech recognition algorithmsProceedings of the 13th annual international symposium on Computer architecture10.5555/17407.17382(216-223)Online publication date: 1-Jun-1986
https://dl.acm.org/doi/10.5555/17407.17382
Anantharaman TBisiani R(1986)A hardware accelerator for speech recognition algorithmsACM SIGARCH Computer Architecture News10.1145/17356.1738214:2(216-223)Online publication date: 1-May-1986
https://dl.acm.org/doi/10.1145/17356.17382
Lam M(1985)A Transformational Model of VLSI Systolic DesignComputer10.1109/MC.1985.166279818:2(42-52)Online publication date: 1-Feb-1985
https://dl.acm.org/doi/10.1109/MC.1985.1662798

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Research on synthesis of concurrent computing systems (Extended Abstract)

Transactions for concurrent object-oriented programming systems

Extended abstract: a race-free hardware modeling language