Dynamic Dataflow Graphs - Signal Processing Systems - page 890

a b

Switch and Select If-then-else

Fig. 1 ( a ) Switch and select actors in Boolean dataflow, and ( b ) an if-then-else construct expressed
in terms of Boolean dataflow

A BDF select actor has a single control input port s c ; two additional input ports
( data input ports ) s x and s y ; and a single output port s o . Similar to the control port of
the switch actor, the s c port accepts Boolean valued tokens, and the production rate
on the s o port is statically fixed at one token per invocation. On each invocation of
the select actor data is copied from a single token from either s x or s y to s o depending
on whether the corresponding control token value is true or false respectively.
Switch and select actors can be integrated along with other actors in various ways
to express different kinds of control constructs. For example, Fig. 1 b illustrates an
if-then-else construct, where the actors A and B are applied conditionally based on a
stream of control tokens. Here A and B are synchronous dataflow (SDF) actors that
each consume one token and produce one token on each invocation.
Buck has developed scheduling techniques to automatically derive efficient
control structures from BDF graphs under certain conditions [ 11 ] . Buck has also
shown that BDF is Turing complete, and furthermore, that SDF augmented with just
switch and select (and no other dynamic dataflow actors) is also Turing complete.
This latter result provides a convenient framework with which one can demonstrate
Turing completeness for other kinds of dynamic dataflow models, such as the
enable-invoke dataflow model described in Sect. 5 . In particular, if a given model
of computation can express all SDF actors as well as the functionality associated
with the BDF switch and select actors, then such a model can be shown to be Turing
complete.