Dynamic Dataflow Graphs - Signal Processing Systems - page 903

6.2 Analysis

Various analysis techniques exist for SADF, allowing the evaluation of both quali-
tative properties (such as consistency and absence of deadlock) and best/worst-case
and average-case quantitative properties (like minimal and average throughput).
Consistency of SADF graphs is briefly discussed now. The MPEG-4 decoder is
an example of a class of SADF graphs where each scenario is like a consistent SDF
graph and scenario changes occur at iteration boundaries of these scenario graphs
(but still pipelined). Such SADF graphs are said to be strongly consistent [ 70 ] , which
is easy to check as it results from structural properties only. The SADF graph of the
MP3 decoder does not satisfy these structural properties (for Mixed frames), but it
can still be implemented in bounded memory. The required consistency property
is called weak consistency [ 66 ] . Checking weak consistency requires taking the
possible (sub)scenario sequences as captured by the state machines associated to
detectors into account, which complicates a consistency check considerably.
Analysis of quantitative properties and the efficiency of the underlying tech-
niques depend on the selected type of state machine associated to detectors as well
as the chosen time model. For example, one possibility is to use non-deterministic
state machines, which merely specify what sequences of (sub)scenarios can occur
but not how often. This is typically used for best/worst-case analysis. Applying the
techniques in [ 20 , 23 , 24 ] then allows computing that a throughput of processing
0

253 frames per kCycle can be guaranteed for the MPEG-4 decoder. An alternative
is to use probabilistic state machines (i.e., Markov chains), which additionally
capture the occurrence probabilities of the (sub)scenario sequences to allow for
average-case analysis as well. Assuming that scenarios I , P 0 , P 30 , P 40 , P 50 , P 60 , P 70 ,
P 80 and P 99 of the MPEG-4 decoder may occur in any order and with probabilities
0

.

04 respectively, the techniques
in [ 67 ] allow computing that the MPEG-4 decoder processes on average 0

. 12, 0 . 02, 0 . 05, 0 . 25, 0 . 25, 0 . 09, 0 . 09, 0 . 09 and 0 .

426
frames per kCycle. The techniques presented in [ 71 ] combine the association
of Markov chains to detectors with exponentially distributed execution times to
analyze the response time distribution of the MPEG-4 decoder for completing the
first frame.
The semantics of SADF graphs where Markov chains are associated to detectors
while assuming generic discrete execution time distributions 5 has been defined
in [ 66 ] using Timed Probabilistic Systems (TPS). Such transition systems opera-
tionalize the behavior with states and guarded transitions that capture events like
the begin and end of each of the two steps in firing actors and progress of time.
In case an SADF graph yields a TPS with finite state space, it is amenable to
analysis techniques for (Priced) Timed Automata or Markov Decision Processes and
Markov Chains by defining reward structures as also used in (probabilistic) model
checking. Theelen et al. [ 67 ] discusses that specific properties of dataflow models in

.

5 This covers the case of constant execution times as so-called point distributions [ 66 , 67 ] .