# SCHEDULING DYNAMIC DATAFLOW GRAPHS WITH
BOUNDED MEMORY USING THE TOKEN FLOW MODEL

J. T. Buck
Technical Report UCB/ERL 93/69, Ph.D. Dissertation, Dept. of EECS,
University of California, Berkeley, CA 94720, 1993.

Postscript file

## ABSTRACT

This thesis presents an analytical model of the behavior of dataflow graphs
with data-dependent control flow. In this model, the number of tokens produced or
consumed by each actor is given as a symbolic function of the Boolean-valued tokens
in the system. Several definitions of consistency are discussed and compared. Neces
sary and sufficient conditions for bounded-length schedules, as well as sufficient con
ditions for determining whether a dataflow graph can be scheduled in bounded
memory are given. These are obtained by analyzing the properties of minimal cyclic
schedules, defined as minimal sequences of actor executions that return the dataflow
graph to its original state. Additional analysis techniques, including a clustering algo
rithm that reduces graphs to standard control structures (such as "if-then-else" and
"do-while") and a state enumeration procedure, are also described. Relationships
between these techniques and those used in Petri net analysis, as well as in the theory
of certain stream languages, are discussed.
Finally, an implementation of these techniques using Ptolemy, an object-ori
ented simulation and software prototyping platform, is described. Given a dynamic
dataflow graph, the implementation is capable either of simulating the execution of the
graph, or generating efficient code for it (in an assembly language or higher level lan
guage).