Integrated Modeling Using Finite State Machines and Dataflow Graphs - Signal Processing Systems - page 962

enabled state transition, the values are interpreted as ε values indicating the absence

of values. Note that even an value produces a token in the enclosing dataflow

graph. This solution is a little unsatisfactory and indeed there is another approach to
handle this case. The FSM can be embedded into a heterochronous dataflow graph .

ε

FSM in Heterochronous Dataflow : The idea of heterochronous dataflow ( HDF )
is similar to parameterized dataflow modeling [ 3 ] , that is dynamic behavior is
allowed and is represented via FSMs .However,all FSMs in the heterochronous
dataflow graph are forced to only change state once the heterochronous dataflow
graph has executed a full iteration. This constraint ensures that the consumption and
production rates of the HDF actor does not change while the HDF graph executes its
iteration. However, after the iteration is finished, the HDF actors are free to update
their state leading to new consumption and production rates for the HDF actors
in the system. With these new consumption and production rates, a new balance
equation is solved and a new repetition vector calculated which is executed in the
next iteration. For the duration of this next iteration, all HDF actors have to keep
their consumption and production rates unmodified.
Let us consider again Fig. 3 . But now instead of an SDF domain, we use an HDF
domain. In the case that actor A is in state q 0 , to execute a full iteration of the HDF
graph, the actors A and B are executed exactly once. Note that while actor A is
executed, it remains in state q 0 regardless of the value i 1 [ 0 ] of the first token (note

that tokens carrying values are still tokens and not absence of tokens) on input port

i 1 . After the full iteration of the HDF graph (

ε

1) has finished, the FSM of
actor A may change its state to q 1 depending on the value i 1 [

γ A = γ B =

of the first token on
input port i 1 . In the case that actor A is now in state q 1 , a full iteration of the HDF
graph corresponds to the sole execution of actor A . After the full iteration of the
HDF graph has finished, the FSM of actor A may change its state to q 0 depending
on the value i 2 [

0 ]

0 ] of the first token on input port i 2 .

2.2.2 Refining FSM States via Dataflow Graphs

Previously, we have seen how an FSM can be used to refine a dataflow actor. On
the opposite side, an FSM can be used to coordinate between multiple dataflow
graphs. This coordination is achieved by refining FSM states by dataflow graphs.
The dataflow graph is composed into a single actor which is executed if the FSM
is in the refined state. To refine a state by a dataflow graph , a notion of iteration is
necessary as the execution of one reaction of the FSM has to terminate. An iteration
has been chosen as a natural boundary to stop the execution of the embedded
dataflow graph. However, the existence of a finite iteration is undecidable for general
dataflow graphs. Hence, the application of refinements of states to dataflow graphs
is restricted in *charts to certain subclasses of dataflow, e.g., synchronous dataflow
graphs ( SDF )[ 29 ] and cyclo-static dataflow graphs ( CSDF )[ 7 ] , which provide such
a notion of iteration naturally. Moreover, combining the actors in a subgraph of a
dataflow graph into a single actor, which will execute an iteration for the subgraph,
is not always possible. The problem is treated in detail in Sect. 5 .