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

as a static actor. In that sense, the algorithm only provides a sufficient criterion.
A sufficient and necessary criterion cannot be given as the problem is undecidable
in the general case.
The algorithm starts by trying to determine a classification candidate from a
breadth-first search of the FSM . This candidate is later checked for consistency
with the entire FSM state space.

Definition 10 (Classification Candidate). A possible CSDF behavior of the actor
is captured by a classification candidate c =( ρ 0 , ρ 1 ,... ρ τ − 1 ) where each ρ =

( cons , prod ) represents a phase of the CSDF behavior and τ is the number of phases.

To exemplify, we consider Fig. 15 b . In this cases we have two phases, i.e., τ =

2, where the first phase ( ρ 0 ) consumes one token from port i 1 and produces one

token on port o 1 while the second phase ( ρ 1 ) consumes one token from port i 2 and

produces one token on port o 2 .
It can be observed that all paths starting from the initial actor FSM state q 0 must
comply with the classification candidate .Furthermore,as CSDF exhibits cyclic
behavior, the paths must also contain a cycle. We now search for such a path
p of transitions t i in the actor FSM starting from the initial state

q 0 via a breadth-first search . The path can be decomposed into an acyclic prefix
path p a and a cyclic path p c such that p

=( t 1 , t 2 ,..., t n )

p a p c ,i.e., p a =(

= t 1 , t 2 ,... t i − 1 ) being the

prefix and p c =( being the cyclic part. The breadth-first search finds

the shortest path which loops back onto itself.
After such a path p has been found, it will be contracted by unifying adjacent
transitions t i , t i + 1 if t i only consumes tokens or t i + 1 only produces tokens. For
clarification, we look at Fig. 16 b ,d. In both depicted FSMs the transition t 2 consumes
and produces exactly as much tokens as the transitions sequence

t i , t i + 1 ,... t n )

( t 3 , t 4 ) .However,

the transition sequence in Fig. 16 d is equivalent to the single transition t 2

while in Fig. 16 b the transition sequence cannot be contracted due to the changed
order between the consumption of tokens on i 2 and the production of tokens on o 2 .
For further illustration, both FSMs have been used in a dataflow graph depicted
in Fig. 17 a . The resulting dependencies between the transitions in a transition trace
of the actors a 2 and a 3 are shown in Fig. 17 b . As can be seen in Fig. 17 c ifthe
transition sequence

( t 3 , t 4 )

of actor a 3 is contracted into a single transition t c ,then
the resulting dependencies of t c are exactly the same as for transition t 2 .Thisisthe
reason why the FSM from Fig. 16 d can be classified into a CSDF actor with an actor
FSM as depicted in Fig. 15 b . Furthermore, the contraction is a valid transformation
as it does not change the data dependencies in the dataflow graph. This can be
seen by comparing the transition dependencies depicted in Fig. 17 b ,c. Compacting
the transition sequence

( t 3 , t 4 )

of actor a 3 generates the transition t c , which has a
data dependency from the consumption of a token on i 2 to the production of a
token on o 2 . However, the previous transition sequence

( t 3 , t 4 )

( t 3 , t 4 ) also induces this data

dependency as t 4 can only be executed after t 3 .
In contrast to this, the contraction of the transition sequence of actor

a 2 into a transition t d does introduce a new erroneous data dependency from
the consumption of a token on i 2 to the production of a token on o 2 . The data

( t 3 , t 4 )