Worst-case performance analysis of SDF-based parameterized dataflow

M. Skelin, M.C.W. Geilen, F. Catthoor, S. Hendseth

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
67 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)439-460
Number of pages22
JournalMicroprocessors and Microsystems
Volume52
DOIs
Publication statusPublished - Jul 2017

Keywords

  • Max-plus algebra
  • Parameterized dataflow
  • SDF -based parameterized dataflow
  • Synchronous dataflow
  • Worst-case performance

Fingerprint

Dive into the research topics of 'Worst-case performance analysis of SDF-based parameterized dataflow'. Together they form a unique fingerprint.

Cite this