Worst-Case Throughput Analysis of SDF-Based Parametrized Dataflow

Dynamic dataflow models of computation (MoCs) have been introduced to provide designers with enough expressive power to capture increasing levels of dynamism in modern streaming applications. Among dynamic dataflow MoCs, parametrized dataflow MoCs hold an important place as they integrate dynamic parameters and run-time adaptation of parameters in a structured way. In this work, we analyze the temporal behaviour of an important class of parametrized dataflow MoCs based on synchronous dataflow (SDF). We refer to such models as SDF-based parametrized dataflow (SDF-PDF). We show that our analysis allows to derive tighter worst-case throughput guarantees than the existing techniques. To achieve this, we introduce the (max,+) algebraic semantics of the model. Thereafter, we model run-time parameter adaptation using the theory of (max,+) automata, where the maximum cycle mean (MCM) analysis of the (max,+) automaton structure immediately yields the worst-case throughput value. We evaluate our approach on a representative case study from the multimedia domain.