Dynamic Dataflow and Boolean Dataflow in Ptolemy II

Synchronous dataflow (SDF) is the most special case of the dataflow models where the number of tokens produced and consumed by each actor is specified a priori and hence a static schedule can be calculated at compile time. On the other hand, process network (PN) is a superset of all dataflow models, where concurrent processes consume and produce (possibly infinite) streams of tokens and communicate through unidirectional first-in first-out channels. Dynamic dataflow (DDF) and Boolean dataflow (BDF) sit in between SDF and PN, where data-dependent and variable production and consumption are allowed.

Previously, DDF and BDF have been realized and several schedules have been constructed in Ptolemy Classic. A DDF schedule is a run time schedule which should be able to execute a graph forever if it is possible to execute forever and should be able to execute a graph forever in bounded memory if it is possible to execute forever in bounded memory and should execute the graph in a sequence of well-defined and determinate iterations so that the user can control the length of an execution by specifying the number of iterations to execute. BDF supports dynamic flow of control but still permits much of the scheduling work to be performed at compile time. The compile-time scheduler determines exactly how the flow of control will be altered at run time by the value of Boolean token on control arcs. It constructs an annotated schedule, which is a compile-time schedule where each firing is annotated with the run-time conditions under which the firing should occur.

In this project, we are building on the previous effort and realizing both domains in Ptolemy II. We have realized a DDF scheduler and the implementation of BDF is underway. We will further explore various optimization scheduling algorithms. We will also study the semantics of composing DDF/BDF with other Ptolemy II domains.

References:

[1] E.A. Lee, S. Bhattacharyya, J.T. Buck, W.T. Chang, M.J. Chen, B.L. Evans, E.E. Goei, S. Ha, P. Haskell, C.T. Huang, W.J. Huang, C. Hylands, A. Kalavade, A. Kamas, A. Lao, E.A. Lee, S. Lee, D.G. Messerschmitt, P. Murthy, T.M. Parks, J.L. Pino, J. Reekie, G. Sih, S. Sriram, M.P. Stewart, M.C. Williamson, K. White. "The Almagest," five volumes of documentation for Ptolemy Classic, a heterogeneous simulation and design environment supporting multiple models of computation and the predecessor to Ptolemy II, a Java-based environment.

[2] J. T. Buck, "Scheduling Dynamic Dataflow Graphs with Bounded Memory Using the Token Flow Model," Technical Memorandum UCB/ERL 93/69, Ph.D. Thesis, Dept. of EECS, University of California, Berkeley, CA 94720, 1993.

Last updated 10/17/05