Towards component-based (max,+) algebraic throughput analysis of hierarchical synchronous data flow models

M. Skelin, M.C.W. Geilen

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

2 Citations (Scopus)
2 Downloads (Pure)

Abstract

Synchronous (or static) dataflow (SDF) is deemed the most stable and mature model to represent streaming systems. It is useful, not only to reason about functional behavior and correctness of such systems, but also about non-functional aspects, in particular timing and performance constraints. When talking about performance, throughput is a key metric. Within the SDF domain, hierarchical SDF models are of special interest as they enable compositional modeling, which is a necessity in the design of large systems. Techniques exist to analyze throughput of synchronous dataflow models. If the model is hierarchical, it first needs to be flattened before these techniques can be applied (for exact analysis at least). Furthermore, all of these techniques are adversely affected by the increase in the graph’s repetition vector entries. In this paper, for a loosely defined class of hierarchical synchronous dataflow models, we argue that these dependence issues can be mitigated by taking advantage of the hierarchical structure rather than by flattening the graph. We propose a hierarchical extension to an existing technique that is based on the (max,+) algebraic semantics of SDF

Original languageEnglish
Title of host publicationComputer Safety, Reliability, and Security
Subtitle of host publicationSAFECOMP 2017 Workshops, ASSURE, DECSoS, SASSUR, TELERISE, and TIPS, Trento, Italy, September 12, 2017, Proceedings
EditorsS. Tonetta, E. Schoitsch, F. Bitsch
Place of PublicationDordrecht
PublisherSpringer
Pages462-476
Number of pages15
ISBN (Electronic)978-3-319-66284-8
ISBN (Print)978-3-319-66283-1
DOIs
Publication statusPublished - 2017
Event2nd International Workshop on Timing Performance in safety Engineering (TIPS 2017) - Trento, Italy
Duration: 12 Sep 201712 Sep 2017
Conference number: 2

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10489 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Workshop on Timing Performance in safety Engineering (TIPS 2017)
Abbreviated titleTIPS 2017
Country/TerritoryItaly
CityTrento
Period12/09/1712/09/17

Keywords

  • (max, +) algebra
  • Dataflow
  • Hierarchy
  • Performance analysis

Fingerprint

Dive into the research topics of 'Towards component-based (max,+) algebraic throughput analysis of hierarchical synchronous data flow models'. Together they form a unique fingerprint.

Cite this