Scheduling dynamic dataflow graphs with bounded memory using the token flow model
Joseph T. Buck, Edward A. Lee · IEEE International Conference on Acoustics Speech and Signal Processing · 1993
The authors build upon research by E. A. Lee (1991) concerning the token flow model, an analytical model for the behavior of dataflow graphs with data-dependent control flow, by analyzing the properties of cycles of the schedule: sequences of actor executions that return the graph to its initial state. Necessary and sufficient conditions are given for the existence of a bounded cyclic schedule as well as sufficient conditions for execution of the graph in bounded memory. The techniques presented apply to a more general class of dataflow graphs than previous methods.>
Cited by 464 works. doi:10.1109/icassp.1993.319147
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Digital communications
- The Structure of Scientific Revolutions
- Computer Architecture: A Quantitative Approach
- Petri nets: Properties, analysis and applications
- The C++ Programming Language
- Petri Net theory and the modeling of systems
- Can programming be liberated from the von Neumann style?
- Parallel Sequencing and Assembly Line Problems
- The program dependence graph and its use in optimization