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

a b

g n

i 1 ( 4 ) ∧ o 1 ( 3 )=( a 1 ; a 1 ; a 2 )

a 3

t 1
t 2

s 0 s 1

g γ

i 1 o 1

a 1 a 2

2 2 3 3

i 1 ( 2 ) ∧ o 1 ( 3 )=( a 1 ; a 2 )

Fig. 14 Example of a cluster and its cluster FSM. ( a ) Data flow graph g n with a cluster g γ ,( b )
Cluster FSM g γ .R belonging to cluster g γ

Definition 9 (Cluster FSM ). The cluster FSM of a cluster g γ is a tuple g γ .R =

q )

( T , Q , q 0 ) containing a finite set of transitions T t =( q , req , cons , prod , f sched , ,

a finite set of states Q ,andan initial state q 0 ∈ Q . Cluster and Actor FSMs differ in

their possible actions f action / f sched which are selected from the actor functionality

F func in the case of actor FSMs and are scheduling sequences

F sched in the case
of cluster FSMs . A scheduling sequence f sched ∈ F sched is a finite sequence of
actor/cluster firings from the actors/clusters contained in the dataflow graph g γ ,i.e.,
F sched = A ∗ . 6 g γ .

In summary, a cluster FSM is an actor FSM which simply has a different
mechanism controlling the execution of the contained actors in the cluster. To
represent structural hierarchy a cluster without a cluster FSM is generated. In
this case the actors contained in the cluster are self-scheduled ,i.e.,theyfireas
soon as sufficient tokens and free places permit it. To exemplify, we consider the
network graph depicted in Fig. 14 a . It contains a cluster g γ with actors a 1 and a 2 .
The scheduling of these actors is given by the cluster FSM depicted in Fig. 14 b .
The actions of this cluster FSM are sequences of actor firings, e.g., from

transition t 1 which specified to fire actor a 1 twice followed by a firing of actor a 2 .
Without a cluster FSM the cluster g γ is self-scheduled, e.g., the actor a 1 might fire a
third time before actor a 2 is fired.

( a 1 , a 1 , a 2 )

3 Automatic Model Extraction

In order to be able to apply MoC specific analysis methods such as static schedule
generation or deadlock detection, it is important to recognize data flow models of
computation such as SDF and CSDF . We will show that this can be accomplished by

6 We use the “ . ”-operator, e.g., g γ . A , for member access of tuples whose members have been
explicitly named in their definition, e.g., member A of cluster g γ from Definition 7 . Weuse A ∗ to
denote the set of all possible finite sequences of actors/clusters a ∈ A , i.e., A ∗ = n ∈{ 0 , 1 ,...} A n .An
element of this set can be interpreted as a static schedule of actors/clusters which can be fired one
after the other.