Synchronous Dataflow

Graph transformations

This section explains the various graph transformation algorithms that are implemented in SDF3.

Limit auto-concurrency

Tool sdf3transform-sdf --transform 'model_autoconc(<max>)'
API modelAutoConcurrencyInSDFgraph()

The SDF Model-of-Computation assumes that infinitly many compute resources are available. Using this assumption, it allows multiple simultanious firings of the same actor (i.e. it allows auto-concurrency). Auto-concurrency can be limited by adding self-edges to actors.

In this example, the auto-concurrency of the actors is limited to 3. This means that only three instances of each actor can be firing simultaneously.

Model storage-space constraints

Tool sdf3transform-sdf --transform 'model_buffersize'
API modelBufferSizeInSDFgraph()

Back-edges can be used to model storage-space constraints on the channels of an SDFG. SDF3 can automatically add these back-edges to an SDFG when storage constrains are available for the channels of this SDFG.

In this example, the storage space of the channels alpha and beta is limited to respectively 4 and 2 tokens. The constraint on the first channel (alpha) is modeled with a back-edge from actor B to actor A that contains initially 4 tokens.

SDFG to HSDFG conversion

Tool sdf3transform-sdf --transform 'to_hsdf'
API transformSDFtoHSDF()

Any SDFG can be converted to a correpsonding HSDFG in which all rates are equal to one. This is done using an algorithm described by Sriram and Bhattacharyya in "Embedded Multiprocessors Scheduling and Synchronization" (Marcel Dekker, 2000). Note that the conversion can lead to an exponential increase in the number of actors in the HSDFG. The number of actors in the resulting HSDFG depends on the entries of the actors in the repetition vector.


Tool sdf3transform-sdf --transform 'unfold(<count>)'
API unfoldHSDF()

Unfolding of an SDFG creates additional scheduling freedom. Unfolding requires first a transformation of the SDFG to an HSDFG. After that, all actors are copied as often as required for the unfolding and the sequence edges between the actor copies are constructed such that all inherent dependencies between the actor firings are respected.

In this example, the SDFG is unfolded one time. This enables scheduling algorithms to schedule more copies of actor A before scheduling actor B. For some graphs, this may allow schedules which can achieve a higher throughput. This is especially usefull for blocking schedules.