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)

Abstract

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
Pages17-24
Number of pages8
ISBN (Print)978-1-4673-8035-5
DOIs
Publication statusPublished - Aug 2015
Event18th Euromicro Conference on Digital System Design (DSD 2015) - Funchal, Portugal
Duration: 26 Aug 201528 Aug 2015
Conference number: 18
https://paginas.fe.up.pt/~dsd-seaa-2015/dsd2015/

Conference

Conference18th Euromicro Conference on Digital System Design (DSD 2015)
Abbreviated titleDSD 2015
Country/TerritoryPortugal
CityFunchal
Period26/08/1528/08/15
OtherConference co-located with the 41st Euromicro Conference on Software Engineering and Advanced Applications (SEAA 2015)
Internet address

Keywords

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

Fingerprint

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

Cite this