Study of Synchronous Dataflow

Haiyang Zheng
(Professor Edward A. Lee)
Mobies

The purpose of this project is to study some properties of synchronous dataflow (SDF) including the abstractions of actors and the composibility of SDF models. In a SDF model, actors have static firing rules: they consume and produce a fixed number of tokens in each firing. The token consumption and production rates of an actor are the abstraction of the actor. Based on this abstraction, an efficient, static schedule can be solved with the balance equations between actors. An important constraint about the firing rules of SDF is that an actor can't fire unless all its inputs have enough tokens. Sometimes this constraint is too conservative in that some executable models fail to find the executable schedules [1,2]. This is because the SDF abstraction of the actors isn't sufficient.

This project aims to find a sufficient abstraction with the exposure of the internals of actors. The basic idea is to separate the computation and communication of an actor, and to abstract the communication part. The abstraction focuses on what conditions the actor affects in the environment. The schedule based on this abstraction reflects the computation of actors better than the general SDF schedule. This abstraction can be regarded as a refinement of the SDF abstraction.

This abstraction can be used to study the composibility of SDF models. A composite SDF model has several SDF models embedded inside. The SDF abstraction of this composite model is based on the solution of the balance equations between the actors inside. This abstraction indicates the requirement for the composite model to restore its original state. It also abstracts away some of the internal communication behaviors, which is valuable in the schedulability study of the composition of SDF models. Our new abstraction catches the communication part and the schedulability analysis can be done without flattening the composite models.

[1]
T. M. Parks, J. L. Pino, and E. A. Lee, "A Comparison of Synchronous and Cycle-Static Dataflow," Proc. Signals, Systems and Computers Conf., Vol. 1, 1996.
[2]
G. Bilsen, M. Engels, R. Lauwereins, and J. A. Peperstraete, "Cyclo-static Dataflow," IEEE Trans. Signal Processing, Vol. 44, No. 2, February 1996.

Send mail to the author : (hyzheng@eecs.berkeley.edu)


Edit this abstract