- Author:
- Joseph T Buck
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. Necessary and sufficient conditions for bounded-length schedules, as well as sufficient conditions 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 algorithm 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 a analysis, as well as in the theory of certain stream languages, are discussed. Finally, an implementation of these techniques using Ptolemy, an object-oriented 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 language).
Cited By
- Dubrulle P, Louise S, Sirdey R and David V A low-overhead dedicated execution support for stream applications on shared-memory cmp Proceedings of the tenth ACM international conference on Embedded software, (143-152)
- Madahar B, Alston I, Aulagnier D, Schurer H, Thomas M and Saget B (2003). How rapid is rapid prototyping? analysis of ESPADON programme results, EURASIP Journal on Advances in Signal Processing, 2003, (580-593), Online publication date: 1-Jan-2003.
- Lee E and Parks T Dataflow process networks Readings in hardware/software co-design, (59-85)
- Thiele L, Strehl K, Ziegenbein D, Ernst R and Teich J FunState—an internal design representation for codesign Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, (558-565)
- Eisenring M and Teich J Domain-specific interface generation from dataflow specifications Proceedings of the 6th international workshop on Hardware/software codesign, (43-47)
Recommendations
Scheduling dynamic dataflow graphs with bounded memory using the token flow model
ICASSP'93: Proceedings of the 1993 IEEE international conference on Acoustics, speech, and signal processing: plenary, special, audio, underwater acoustics, VLSI, neural networks - Volume IThis paper builds upon research by Lee [1] 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 ...
On the b-chromatic number of regular bounded graphs
A b-coloring of a graph is a proper coloring such that every color class contains a vertex adjacent to at least one vertex in each of the other color classes. The b-chromatic number of a graph G, denoted by b(G), is the maximum integer k such that G ...