Dynamic Dataflow Graphs - Signal Processing Systems - page 904

general and SADF in particular allow for substantial state-space reductions during
such analysis. The underlying techniques have been implemented in the SDF 3 tool
kit [ 62 ] , covering the computation of worst/best-case and average-case properties
for SADF including throughput and various forms of latency and buffer occupancy
metrics [ 68 ] . In case such exact computation is hampered by state-space explosion,
[ 68 , 70 ] exploit an automated translation into process algebraic models expressed in
the Parallel Object-Oriented Specification Language (POOSL) [ 69 ] , which allows
for statistical model checking (simulation-based estimation) of the properties. The
combination of Markov chains and exponentially distributed execution times has
been studied in [ 71 ] , using a process algebraic semantics based on Interactive
Markov Chains [ 33 ] to apply a general-purpose model checker for analyzing
response time distributions.
In case we abstract from the stochastic aspects of execution times and scenario
occurrences, SADF is still amenable to worst/best-case analysis. Since SADF
graphs are timed dataflow graphs, they exhibit linear timing behavior [ 20 , 43 , 76 ] ,
which facilitates network-level worst/best-case analysis by considering the worst/
best-case execution times for individual actors. For linear timed systems this is
know to lead to the overall worst/best-case performance. For the class of strongly-
consistent SADF graphs with a single detector (also called FSM-based SADF ),
very efficient performance analysis can be done based on a

-algebraic
interpretation of the operational semantics. It allows for worst-case throughput
analysis, some latency analysis and can find critical scenario sequences without
exploring the state-space of the underlying TPS. Instead, the analysis is performed
by means of state-space analysis and maximum-cycle ratio analysis of the equivalent
(

( max , +)

-automaton [ 20 , 23 , 24 ] . Geilen et al. [ 23 ] shows how this analysis can
be extended for the case that scenario behaviors are not complete iterations of the
scenario SDF graphs.

max , +)

6.3 Synthesis

FSM-based SADF graphs have been extensively studied for implementation on
(heterogeneous) multi-processor platforms [ 64 ] . Variations in resource requirements
need to be exploited to limit resource usage without violating any timing require-
ments. The result of the design flow for FSM-based SADF implemented in the SDF 3
tool kit [ 62 ] is a set of Pareto optimal mappings that provide a trade-off in valid
resource usages. For certain mappings, the application may use many computational
resources and few storage resources, whereas an opposite situation may exist for
other mappings. At run-time, the most suitable mapping is selected based on the
available resources not used by concurrently running applications [ 59 ] .
There are two key aspects of the design flow of [ 62 , 64 ] . The first concerns
mapping channels onto (possibly shared) storage resources. Like other dataflow
models, SADF associates unbounded buffers with channels, but a complete graph
may still be implemented in bounded memory. FSM-based SADF allows for