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

M. Skelin; M.C.W. Geilen

doi:10.1007/978-3-319-66284-8_39

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 proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Computer Safety, Reliability, and Security
Subtitle of host publication	SAFECOMP 2017 Workshops, ASSURE, DECSoS, SASSUR, TELERISE, and TIPS, Trento, Italy, September 12, 2017, Proceedings
Editors	S. Tonetta, E. Schoitsch, F. Bitsch
Place of Publication	Dordrecht
Publisher	Springer
Pages	462-476
Number of pages	15
ISBN (Electronic)	978-3-319-66284-8
ISBN (Print)	978-3-319-66283-1
DOIs	https://doi.org/10.1007/978-3-319-66284-8_39
Publication status	Published - 2017
Event	2nd International Workshop on Timing Performance in safety Engineering (TIPS 2017) - Trento, Italy Duration: 12 Sept 2017 → 12 Sept 2017 Conference number: 2

Publication series

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

Conference

Conference	2nd International Workshop on Timing Performance in safety Engineering (TIPS 2017)
Abbreviated title	TIPS 2017
Country/Territory	Italy
City	Trento
Period	12/09/17 → 12/09/17

Keywords

(max, +) algebra
Dataflow
Hierarchy
Performance analysis

Access to Document

10.1007/978-3-319-66284-8_39

Cite this

Skelin, M., & Geilen, M. C. W. (2017). Towards component-based (max,+) algebraic throughput analysis of hierarchical synchronous data flow models. In S. Tonetta, E. Schoitsch, & F. Bitsch (Eds.), Computer Safety, Reliability, and Security : SAFECOMP 2017 Workshops, ASSURE, DECSoS, SASSUR, TELERISE, and TIPS, Trento, Italy, September 12, 2017, Proceedings (pp. 462-476). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10489 LNCS). Springer. https://doi.org/10.1007/978-3-319-66284-8_39

Skelin, M. ; Geilen, M.C.W. / Towards component-based (max,+) algebraic throughput analysis of hierarchical synchronous data flow models. Computer Safety, Reliability, and Security : SAFECOMP 2017 Workshops, ASSURE, DECSoS, SASSUR, TELERISE, and TIPS, Trento, Italy, September 12, 2017, Proceedings. editor / S. Tonetta ; E. Schoitsch ; F. Bitsch. Dordrecht : Springer, 2017. pp. 462-476 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c80f140bafee4d629b3158454e924119,

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

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{\textquoteright}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",

keywords = "(max, +) algebra, Dataflow, Hierarchy, Performance analysis",

author = "M. Skelin and M.C.W. Geilen",

year = "2017",

doi = "10.1007/978-3-319-66284-8\_39",

language = "English",

isbn = "978-3-319-66283-1",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "462--476",

editor = "S. Tonetta and E. Schoitsch and F. Bitsch",

booktitle = "Computer Safety, Reliability, and Security",

address = "Germany",

note = "2nd International Workshop on Timing Performance in safety Engineering (TIPS 2017), TIPS 2017 ; Conference date: 12-09-2017 Through 12-09-2017",

}

Skelin, M & Geilen, MCW 2017, Towards component-based (max,+) algebraic throughput analysis of hierarchical synchronous data flow models. in S Tonetta, E Schoitsch & F Bitsch (eds), Computer Safety, Reliability, and Security : SAFECOMP 2017 Workshops, ASSURE, DECSoS, SASSUR, TELERISE, and TIPS, Trento, Italy, September 12, 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10489 LNCS, Springer, Dordrecht, pp. 462-476, 2nd International Workshop on Timing Performance in safety Engineering (TIPS 2017), Trento, Italy, 12/09/17. https://doi.org/10.1007/978-3-319-66284-8_39

Towards component-based (max,+) algebraic throughput analysis of hierarchical synchronous data flow models. / Skelin, M.; Geilen, M.C.W.
Computer Safety, Reliability, and Security : SAFECOMP 2017 Workshops, ASSURE, DECSoS, SASSUR, TELERISE, and TIPS, Trento, Italy, September 12, 2017, Proceedings. ed. / S. Tonetta; E. Schoitsch; F. Bitsch. Dordrecht: Springer, 2017. p. 462-476 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10489 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Skelin, M.

AU - Geilen, M.C.W.

N1 - Conference code: 2

PY - 2017

Y1 - 2017

N2 - 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

AB - 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

KW - (max, +) algebra

KW - Dataflow

KW - Hierarchy

KW - Performance analysis

UR - https://www.scopus.com/pages/publications/85029495975

U2 - 10.1007/978-3-319-66284-8_39

DO - 10.1007/978-3-319-66284-8_39

M3 - Conference contribution

AN - SCOPUS:85029495975

SN - 978-3-319-66283-1

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 462

EP - 476

BT - Computer Safety, Reliability, and Security

A2 - Tonetta, S.

A2 - Schoitsch, E.

A2 - Bitsch, F.

PB - Springer

CY - Dordrecht

T2 - 2nd International Workshop on Timing Performance in safety Engineering (TIPS 2017)

Y2 - 12 September 2017 through 12 September 2017

ER -

Skelin M, Geilen MCW. Towards component-based (max,+) algebraic throughput analysis of hierarchical synchronous data flow models. In Tonetta S, Schoitsch E, Bitsch F, editors, Computer Safety, Reliability, and Security : SAFECOMP 2017 Workshops, ASSURE, DECSoS, SASSUR, TELERISE, and TIPS, Trento, Italy, September 12, 2017, Proceedings. Dordrecht: Springer. 2017. p. 462-476. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-66284-8_39

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this