Worst-case throughput analysis of SDF-based parametrized dataflow

Mladen Skelin, Marc Geilen, F. Catthoor, Sverre Hendseth

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Title of host publication2015 Euromicro Conference on Digital System Design (DSD), 26-28 August 2015, Funchal
Place of PublicationLos Amalitos
PublisherIEEE Computer Society
Number of pages8
ISBN (Print)978-1-4673-8035-5
Publication statusPublished - Aug 2015
Event18th Euromicro Conference on Digital System Design (DSD 2015) - Funchal, Portugal
Duration: 26 Aug 201528 Aug 2015
Conference number: 18


Conference18th Euromicro Conference on Digital System Design (DSD 2015)
Abbreviated titleDSD 2015
OtherConference co-located with the 41st Euromicro Conference on Software Engineering and Advanced Applications (SEAA 2015)
Internet address


  • synchronous dataflow (SDF)
  • SDF-based parametrized dataflow (SDF-PDF)
  • (max,+) algebra
  • worst-case throughput


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

Cite this