Scheduling dynamic dataflow graphs with bounded memory using the token flow model

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 sta...

Full description

Saved in:
Bibliographic Details
Main Authors: Buck, J.T., Lee, E.A.
Format: Conference Proceeding
Language:English
Subjects:
Analytical models
Data analysis
Digital signal processing
Dynamic scheduling
Hardware
Parallel machines
Parallel processing
Pipelines
Signal processing algorithms
System recovery
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
ISSN:1520-6149
2379-190X
DOI:10.1109/ICASSP.1993.319147