Consistency in dataflow graphs
- 1 April 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 2 (2) , 223-235
- https://doi.org/10.1109/71.89067
Abstract
Analytical properties of programming languages with dataflow graph semantics arediscussed. It is shown that one of the most serious problems with these languages is thatsubtle inconsistencies between parts of the dataflow graph can be inadvertently created.These inconsistencies can lead to deadlock, or in the case of nonterminating programs, tounbounded memory requirements. Consistency is defined to mean that the same numberof tokens is consumed as produced on any arc, in the long run. A token-flow model isdeveloped for testing for inconsistency. The method is a generalization of consistencychecks for synchronous dataflow (SDF) graphs. The token-flow model is compared tosimilar tests applied to hybrid dynamical systems. It is argued that dataflow semanticsmake steady-state analysis possible, leading to a simpler method in most cases.Keywords
This publication has 15 references indexed in Scilit:
- A denotational theory of synchronous reactive systemsInformation and Computation, 1992
- Hybrid dynamical systems theory and the Signal languageIEEE Transactions on Automatic Control, 1990
- Synchronous data flowProceedings of the IEEE, 1987
- Static Scheduling of Synchronous Data Flow Programs for Digital Signal ProcessingIEEE Transactions on Computers, 1987
- Resource managers in functional programmingJournal of Parallel and Distributed Computing, 1984
- Parallel Processing with Large-Grain Data Flow TechniquesComputer, 1984
- The U-InterpreterComputer, 1982
- Data Flow Program GraphsComputer, 1982
- Data Flow SupercomputersComputer, 1980
- A straightforward denotational semantics for non-determinate data flow programsPublished by Association for Computing Machinery (ACM) ,1978