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

Tabl e 2 Minimal number of input tokens n i 1 / n i 2 necessary on cluster g γ input port i 1 / i 2 and
maximal number of output tokens n o 1 / n o 2 producible on the cluster output ports o 1 / o 2 with these
input tokens
(

n i 1 , n i 2 , ( 0 , 0 , ( 0 , 1 , ( 2 , 0 , ( 2 , 1 , ( 2 , 2 , ( 2 , 3 , ( 4 , 2 , ( 4 , 3 , ( 4 , 4 , ···

n o 1 , ) ···

For example, to produce two tokens on output port o 2 , two tokens are required from both input
ports i 1 and i 2 . The maximal number of output tokens producible from these input tokens are two
output tokens on o 1 and o 2

n o 2 ) 0 , 0 ) 0 , 1 ) 2 , 0 ) 2 , 1 ) 2 , 2 ) 2 , 3 ) 4 , 2 ) 4 , 3 ) 4 , 4

a b

1 actor Add() i 1 ; i 2 ==> o 1 :
2 action i 1 :[u], i 2 :[v]==> o 1 :[u+v]
3end
4end
5 actor Sub() i 3 ; i 4 ==> o 2 :
6 action i 3 :[u], i 4 :[v]==> o 2 :[u-v]
7end
8end

1 actor a 1 () i 1 ; i 2 ; i 3 ; i 4 ==> o 1 ; o 2 :
2 action i 1 :[u], i 2 :[v]==> o 1 :[u+v]
3 end
4 action i 3 :[u], i 4 :[v]==> o 2 :[u-v]
5 end
6 end

Fig. 23 A CAL actor and its decomposition into two SDF actors. ( a )A CAL actor which combines
the function of both an addition as well as a subtraction actor, ( b ) Decomposition of the actor from
( a ) into two actors one doing addition and the other one subtraction

contains cycles, as normally, these values would all be depicted as unique vertices.
As can be seen from Fig. 22 a ,b there is a one-to-one correspondence between the
vertices and edges in the Hasse diagram and the states and transitions in the cluster
FSM . For a more technical explanation of deriving the cluster FSM from the Hasse
diagram we again refer the reader to [ 14 ] . Furthermore, there exists a more advanced
representation of the cluster FSM via so-called Rules [ 15 ] which allows a more
compact representation, thus reducing the code size required to represent the quasi-
static schedule .

5.2 Statically Schedulable Regions in CAL

While the clustering algorithm presented in Sect. 5.1 assumes that the static
subgraph which will be clustered consists of pure SDF or CSDF actors, Janneck
et al. [ 20 ] have presented a methodology to derive static parts from dynamic CAL
actors. To exemplify, we consider the CAL actor depicted in Fig. 23 a . This actor
does not exhibit SDF semantics, but it can be decomposed into the two SDF actors
as depicted in Fig. 23 b . The idea from [ 20 ] presents a systematic algorithm to
decompose a dynamic CAL actor into SDF actors and a dynamic residual actor.
The analysis determines a statically related group of ports for each actor. Each
such group of ports is later transformed into an SDF actor. Connected subgraphs of
these derived SDF actors can then be scheduled quasi-statically.