article

Free access

Indeterminacy, monitors, and dataflow

Authors:

Arvind,

Kim P. Gostelow,

Wil PlouffeAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 11, Issue 5

Pages 159 - 169

https://doi.org/10.1145/1067625.806559

Published: 01 November 1977 Publication History

PDF eReader

Abstract

The work described in this paper began with a desire to include some linguistic concept of a resource manager within a dataflow language we have been designing [AGP76]. In doing so, we discovered that dataflow monitors (resource managers) provide a natural way of thinking about resources and especially their scheduling. Dataflow semantics are based upon a program composed of asynchronous operators interconnected by lines along which data tokens (messages) flow, such that when all of the input tokens for a given operator have arrived then that operator may fire (execute) by absorbing the input tokens, computing, and producing an output token as its result. These operations closely match one's intuitive model of resource managers (operators) passing signals (tokens) to one another for the purpose of synchronizing and scheduling resource usage. Previously though, dataflow languages [D73, K73, W75] have dealt only with the expression of highly asynchronous yet determinate computations; however, resource management characteristically involves indeterminate computation. The introduction here of dataflow monitors and an explicit nondeterministic merge operator for dataflow streams makes dataflow very well suited for expressing interprocess communication and operations on resources.

References

[1]

Arvind and Gostelow, K.P. Some relationships between asynchronous interpreters of a data flow language. Preprints of IFIP Working Conf. on Formal Description of Programming Concepts, Vol. 1, North-Holland, New York, 1977, pp. 4.1-4.25.

Google Scholar

[2]

Arvind and Gostelow, K.P. A computer capable of exchanging processing elements for time. Information Processing 77, B. Gilchrist (Ed.), North-Holland, New York, 1977, pp. 849-853.

Google Scholar

[3]

Arvind, Gostelow, K.P., and Plouffe, W.E. Programming in a viable data flow language. Technical Report 89, Dept. of Information & Computer Science, Univ. of California, Irvine, CA, Aug. 1976.

Google Scholar

[4]

Brinch Hansen, P.Operating Systems Principles. Prentice-Hall, Englewood Cliffs, NJ, 1973.

Digital Library

Google Scholar

[5]

Courtois, P.J., Heymans, F., and Parnas, D.L. Concurrent control with "readers" and "writers". Comm. ACM 14, 10 (Oct. 1971), 667-668.

Digital Library

Google Scholar

[6]

Dennis, J.B. First version of a data flow procedure language. Computation Structures Group Memo 92, Lab. for Computer Science, Cambridge, MA, Nov. 1973. (Revised in Aug. 1974; reissued as Technical Memorandum 61, May 1975.)

Google Scholar

[7]

Dennis, J.B. and Misunas, D.P. A preliminary architecture for a basic data-flow processor. Proc. Second Annual Symp. on Computer Architecture, Jan. 1975, pp. 126-132.

Digital Library

Google Scholar

[8]

Hoare, C.A.R. Monitors: An operating system structuring concept. Comm. ACM 17, 10 (Oct. 1974), 549-557.

Digital Library

Google Scholar

[9]

Karp, R.M. and Miller, R.E. Parallel program schemata. J. Comptr. Sys. Sci. 3, 2 (May 1969), 147-195.

Digital Library

Google Scholar

[10]

Kosinski, P.R. A data flow language for operating systems programming. SIGPLAN Notices (ACM) 8, 9 (Sept. 1973), 89-94.

Digital Library

Google Scholar

[11]

Patil, S.S. Closure properties of interconnections of determinate systems. Record of the Project MAC Conf. On Concurrent Systems and Parallel Computation, June 1970, pp. 107-116.

Digital Library

Google Scholar

[12]

Petri, C.A. Kommunikation mit automaten. Institut fur Angewandte Mathematik| der Universitat Bonn, Wegelerstrasse 10, Bonn, 1962.

Google Scholar

[13]

Rodriguez, J.E. A graph model for parallel computation. MAC-TR-64, Project MAC, M.I.T., Cambridge, MA, Sept. 1969.

Digital Library

Google Scholar

[14]

Weng, K.-S. Stream-oriented computation in recursive data flow schemas. Lab. for Computer Science, Cambridge, MA, Oct. 1975.

Google Scholar

Cited By

View all

Rucker ASundram SSmith CVilim MPrabhakar RKjølstad FOlukotun K(2024)Revet: A Language and Compiler for Dataflow Threads2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00016(1-14)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00016
Mazumdar SScionti AZuckerman SPortero A(2023)NoC-based hardware software co-design framework for dataflow thread managementThe Journal of Supercomputing10.1007/s11227-023-05335-879:16(17983-18020)Online publication date: 11-May-2023
https://dl.acm.org/doi/10.1007/s11227-023-05335-8
Kotlar M(2021)An Introduction to Controlflow and Dataflow SupercomputingHandbook of Research on Methodologies and Applications of Supercomputing10.4018/978-1-7998-7156-9.ch001(1-4)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-7156-9.ch001
Show More Cited By

Index Terms

Indeterminacy, monitors, and dataflow
1. Information systems
  1. Data management systems
    1. Middleware for databases
      1. Distributed transaction monitors
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Data flow languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Monitors

Recommendations

Indeterminacy, monitors, and dataflow
SOSP '77: Proceedings of the sixth ACM symposium on Operating systems principles

The work described in this paper began with a desire to include some linguistic concept of a resource manager within a dataflow language we have been designing [AGP76]. In doing so, we discovered that dataflow monitors (resource managers) provide a ...
Resource management in dataflow
FPCA '81: Proceedings of the 1981 conference on Functional programming languages and computer architecture

Recent proposals for nondeterministic facilities in high-level dataflow programming systems have stopped short of giving details of low-level implementation. The underlying machine is assumed to provide basic nondeterministic operations which lead to ...
A comparison of synchronous and cycle-static dataflow
ASILOMAR '95: Proceedings of the 29th Asilomar Conference on Signals, Systems and Computers (2-Volume Set)

We compare synchronous dataflow (SDF) and cyclo-static dataflow (CSDF), which are each special cases of a model of computation we call dataflow process networks. In SDF actors have static firing rules: they consume and produce a fixed number of data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 11, Issue 5

November 1977

175 pages

ISSN:0163-5980

DOI:10.1145/1067625

Issue’s Table of Contents

SOSP '77: Proceedings of the sixth ACM symposium on Operating systems principles
November 1977
180 pages
ISBN:9781450378673
DOI:10.1145/800214
Chairmen:
Saul Rosen,
Peter J. Denning

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1977

Published in SIGOPS Volume 11, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
486
Total Downloads

Downloads (Last 12 months)107
Downloads (Last 6 weeks)26

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rucker ASundram SSmith CVilim MPrabhakar RKjølstad FOlukotun K(2024)Revet: A Language and Compiler for Dataflow Threads2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00016(1-14)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00016
Mazumdar SScionti AZuckerman SPortero A(2023)NoC-based hardware software co-design framework for dataflow thread managementThe Journal of Supercomputing10.1007/s11227-023-05335-879:16(17983-18020)Online publication date: 11-May-2023
https://dl.acm.org/doi/10.1007/s11227-023-05335-8
Kotlar M(2021)An Introduction to Controlflow and Dataflow SupercomputingHandbook of Research on Methodologies and Applications of Supercomputing10.4018/978-1-7998-7156-9.ch001(1-4)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-7156-9.ch001
Lin HLi MJia CLiu JAn H(2019)Degree-of-Node Task Scheduling of Fine-Grained Parallel Programs on Heterogeneous SystemsJournal of Computer Science and Technology10.1007/s11390-019-1962-434:5(1096-1108)Online publication date: 6-Sep-2019
https://doi.org/10.1007/s11390-019-1962-4
Barth PNikhil R(2005)M-structures: Extending a parallel, non-strict, functional language with stateFunctional Programming Languages and Computer Architecture10.1007/3540543961_26(538-568)Online publication date: 6-Jul-2005
https://doi.org/10.1007/3540543961_26
Arvind Brock J(2005)Streams and managersOperating Systems Engineering10.1007/3-540-11604-4_66(452-465)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-11604-4_66
Brock JAckerman W(2005)Scenarios: A model of non-determinate computationFormalization of Programming Concepts10.1007/3-540-10699-5_102(252-259)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-10699-5_102
Jayaraman BKeller R(1986)Primitives for resource management in a demand-driven reduction modelInternational Journal of Parallel Programming10.1007/BF0141455515:3(215-244)Online publication date: 1-Jun-1986
https://dl.acm.org/doi/10.1007/BF01414555
Oldehoeft AJennings S(1984)Dataflow resource managers and their synthesis from open path expressionsIEEE Transactions on Software Engineering10.1109/TSE.1984.501023310:3(244-256)Online publication date: 26-May-1984
https://dl.acm.org/doi/10.1109/TSE.1984.5010233
Cohen AMyers TPark DFriedman DWise DSteele G(1982)Toward an algebra of nondeterministic programsProceedings of the 1982 ACM symposium on LISP and functional programming10.1145/800068.802155(235-242)Online publication date: 15-Aug-1982
https://dl.acm.org/doi/10.1145/800068.802155
Show More Cited By

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