article

Open access

Conversion from data-driven to synchronous execution in loop programs

Editor: Susan L. Graham Authors:

Janice E. Cuny,

Lawrence SnyderAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 9, Issue 4

Pages 599 - 617

https://doi.org/10.1145/29873.31334

Published: 01 October 1987 Publication History

PDF eReader

Abstract

Conversion algorithms are presented that would enable programmers to write programs in a high-level, data flow language and then run those programs on a synchronous machine. A model of interprocess communication systems is developed in which both data-driven and synchronous execution modes are represented. Balancing equations are used to characterize a subclass of parallel programs, called loop programs, for which conversions are possible. We show that all loop programs having the finite buffer property can be converted into synchronous mode. Finally two algorithms for the conversion of loop programs are presented and discussed.

References

[1]

BAILEY, D. A., CUNY, J. E., AND MACLEOo, B.B. Coordination in the Poker Parallel Programming Environment: A parallel code optimization. Tech. Rep. 85-21, University of Massachusetts, Amherst, Aug. 1985.

Google Scholar

[2]

CUNY, J. E., AND SNYDER, L. Testing the coordination predicate. IEEE Trans. Comput. 33, 3 (Mar. 1984), 201-208.

Google Scholar

[3]

GANNON, D., SNYDER, L., AND VAN ROSENDALE, J. Programming substructure computations for elliptic problems on the CHiP computer. In Impact o{ New Computing Systems on Computational Mechanics, A. K. Noor (Ed.), American Society of Mechanical Engineers, 1983.

Google Scholar

[4]

KARP, R., AND MILLER, R.E. Parallel program schemata. J. Comput. Syst. Sci. 3 (May 1969), 147-195.

Google Scholar

[5]

PETERSON, J.L. Petri nets. ACM Comput. Surv. 9, 3 (Mar. 1977), 223-252.

Crossref

Google Scholar

[6]

CUNY, g. E., AND SNYDER, L. A model for analyzing generalized interprocessor communication system. In AlgorithmicaUy-specialized Computers, L. Snyder, L. Jamieson, H. Siegel, and D. Gannon (Eds.), 1985, pp. 7-16.

Google Scholar

[7]

KARP, R. M., AND MILLER, R.E. Properties of a model for parallel computations: Determinacy, termination and queuing. SIAMJ. Appl. Math. 14 (Nov. 1966), 1390-1411.

Google Scholar

[8]

KuNa, H. T., ANO LEISERSON, C.E. Systolic arrays (for VLSI). Tech. Rep. CS-79-103, Carnegie- Mellon University, Pittsburgh, Pa., 1979.

Google Scholar

[9]

LEISERSON, C. E., ANO SAXE, J.B. Optimizing synchronous system. In Proceedings o{ the 22nd Symposium on the Foundations of Computer Science. IEEE, New York (1981), pp. 23-36.

Google Scholar

[10]

CUNY, J. E., AND SNYDER, L. Compilation of data-driven programs for synchronous execution. In Proceedings of the lOth Symposium on Principles of Programming Languages. ACM, New York (1983), pp. 197-202.

Crossref

Google Scholar

[11]

DENNIS, J. B., AND RONO, G.G. Maximum pipelining of array operations on static data flow machine. In Proceedings of the 1983 International Conference on Parallel Processing. IEEE, New York, 1983, pp. 331-334.

Google Scholar

[12]

RON(~, G.G. Pipelined mapping of homogeneous data flow programs. In Proceedings of the 1984 International Conference on Parallel Processing. IEEE, New York, 1984, pp. 532-534.

Google Scholar

[13]

SNYDER, L. Parallel programming and the Poker Programming Environment. Computer 17, 7 (1984), 27-37.

Google Scholar

Cited By

View all

Scheler FSchröder-Preikschat W(2011)THE RTSC: MIGRATING EVENT-TRIGGERED SYSTEMS TO TIME-TRIGGERED SYSTEMSSoftware—Practice & Experience10.1002/spe.109941:12(1491-1515)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1002/spe.1099
Scheler FSchröder-Preikschat W(2010)The RTSCProceedings of the 2010 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing10.1109/ISORC.2010.11(34-41)Online publication date: 5-May-2010
https://dl.acm.org/doi/10.1109/ISORC.2010.11
Ladkin PSimons B(1995)Static Deadlock Analysis for CSP-Type CommunicationsResponsive Computer Systems: Steps Toward Fault-Tolerant Real-Time Systems10.1007/978-1-4615-2271-3_5(89-102)Online publication date: 1995
https://doi.org/10.1007/978-1-4615-2271-3_5
Show More Cited By

Index Terms

Conversion from data-driven to synchronous execution in loop programs
1. Computer systems organization
  1. Architectures
    1. Other architectures
    2. Parallel architectures
      1. Multiple instruction, multiple data
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management

Recommendations

Compilation of data-driven programs for synchronous execution
POPL '83: Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

We present algorithms that convert a class of parallel programs, called loop programs, from data-driven mode to synchronous mode. Such algorithms enable programmers to use a high-level, data-driven programming language without forfeiting the efficiency ...
Efficient Pipelining of Synchronous Dataflow Graphs Via Graph Conversion
Synchronous dataflow graphs (SDFGs) are widely used to model streaming applications that exhibit data-driven and iterative execution patterns. Graph conversion techniques, such as retiming, unfolding, and pipelining, are commonly used to optimize the ...
A compiler optimization to reduce execution time of loop nest

In this paper, a compiler optimization to reduce the execution time of loop nest is proposed. Loop tiling is used to optimize loop nest. Loop tiling is the well-known optimization for improving locality. However, it has a count result that increases the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 9, Issue 4

Oct. 1987

213 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/29873

Editor:
Susan L. Graham

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1987

Published in TOPLAS Volume 9, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
319
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)6

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Scheler FSchröder-Preikschat W(2011)THE RTSC: MIGRATING EVENT-TRIGGERED SYSTEMS TO TIME-TRIGGERED SYSTEMSSoftware—Practice & Experience10.1002/spe.109941:12(1491-1515)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1002/spe.1099
Scheler FSchröder-Preikschat W(2010)The RTSCProceedings of the 2010 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing10.1109/ISORC.2010.11(34-41)Online publication date: 5-May-2010
https://dl.acm.org/doi/10.1109/ISORC.2010.11
Ladkin PSimons B(1995)Static Deadlock Analysis for CSP-Type CommunicationsResponsive Computer Systems: Steps Toward Fault-Tolerant Real-Time Systems10.1007/978-1-4615-2271-3_5(89-102)Online publication date: 1995
https://doi.org/10.1007/978-1-4615-2271-3_5
Ladkin PSimons B(1994)Static analysis of multiway synchronizationProceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research10.5555/782185.782224Online publication date: 31-Oct-1994
https://dl.acm.org/doi/10.5555/782185.782224
Ladkin PSimons BKennedy KPolychronopoulos C(1992)Compile-time analysis of communicating processesProceedings of the 6th international conference on Supercomputing10.1145/143369.143417(248-259)Online publication date: 1-Aug-1992
https://dl.acm.org/doi/10.1145/143369.143417
Snyder L(1984)Parallel Programming and the Poker Programming EnvironmentComputer10.1109/MC.1984.165918317:7(27-36)Online publication date: 1-Jul-1984
https://dl.acm.org/doi/10.1109/MC.1984.1659183

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Compilation of data-driven programs for synchronous execution

Efficient Pipelining of Synchronous Dataflow Graphs Via Graph Conversion

A compiler optimization to reduce execution time of loop nest

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations