Worst-case performance analysis of SDF-based parameterized dataflow

Abstract

Dynamic dataflow models of computation (MoCs) have been introduced to provide designers with sufficient expressive power to capture increasing levels of dynamism in present-day streaming applications. Among dynamic dataflow MoCs, parameterized dataflow MoCs hold an important place. This is due to the fact that they allow for a compact representation of fine-grained data-dependent dynamics inherent to many present-day streaming applications.

However, these models have been primarily analyzed for functional behavior and correctness, while the (parametric) analysis of their temporal behavior has attracted less attention.

In this work, we (in a parametric fashion) analyze worst-case performance metrics (throughput and latency) of an important class of parameterized dataflow MoCs based on synchronous dataflow (SDF). We refer to such models as SDF-based parameterized dataflow (SDF-PDF). We show that parametric analysis in many cases allows to derive tighter conservative worst-case throughput and latency guarantees than the existing (nonparametric) techniques that rely on the creation of “worst-case SDF abstractions” of original parameterized specifications. Furthermore, we discuss how by using parametric analysis we can help address the scalability issues of enumerative analysis techniques.

To achieve this, we first introduce the Max-plus algebraic semantics of SDF-PDF. Thereafter, we model run-time adaptation of parameters using the theory of Max-plus automata. Finally, we show how to derive the worst-case performance metrics from the resulting Max-plus automaton structure.

We evaluate our approach on a representative case study from the multimedia domain.