Max-plus algebraic throughput analysis of synchronous dataflow graphs

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

19 Citations (Scopus)
192 Downloads (Pure)

Abstract

In this paper we present a novel approach to throughput analysis of synchronous dataflow (SDF) graphs. Our approach is based on describing the evolution of actor firing times as a linear time-invariant system in max-plus algebra. Experimental results indicate that our approach is faster than state-of-the-art approaches to throughput analysis of SDF graphs. The efficiency of our approach is due to an exploitation of the regular structure of the max-plus system's graphical representation, the properties of which we thoroughly prove.
Original languageUndefined
Title of host publication38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA)
Place of PublicationUSA
PublisherIEEE Computer Society
Pages29-38
Number of pages10
ISBN (Print)978-1-4673-2451-9
DOIs
Publication statusPublished - 2012
Event38th EUROMICRO Conference on Software Engineering and Advanced Applications, SEAA 2012 - Cesme, Izmir, Turkey
Duration: 5 Sep 20128 Sep 2012
Conference number: 38

Publication series

Name
PublisherIEEE Computer Society

Conference

Conference38th EUROMICRO Conference on Software Engineering and Advanced Applications, SEAA 2012
Abbreviated titleSEAA
CountryTurkey
CityCesme, Izmir
Period5/09/128/09/12

Keywords

  • METIS-296180
  • EWI-22747
  • Streaming Applications
  • IR-83472
  • Timing analysis
  • Data flow
  • Max-plus algebra

Cite this

de Groote, R., Kuper, J., Broersma, H. J., & Smit, G. J. M. (2012). Max-plus algebraic throughput analysis of synchronous dataflow graphs. In 38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA) (pp. 29-38). USA: IEEE Computer Society. https://doi.org/10.1109/SEAA.2012.20
de Groote, Robert ; Kuper, Jan ; Broersma, Haitze J. ; Smit, Gerardus Johannes Maria. / Max-plus algebraic throughput analysis of synchronous dataflow graphs. 38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA). USA : IEEE Computer Society, 2012. pp. 29-38
@inproceedings{22b52c17a4da4c92a9562ff7c868a31a,
title = "Max-plus algebraic throughput analysis of synchronous dataflow graphs",
abstract = "In this paper we present a novel approach to throughput analysis of synchronous dataflow (SDF) graphs. Our approach is based on describing the evolution of actor firing times as a linear time-invariant system in max-plus algebra. Experimental results indicate that our approach is faster than state-of-the-art approaches to throughput analysis of SDF graphs. The efficiency of our approach is due to an exploitation of the regular structure of the max-plus system's graphical representation, the properties of which we thoroughly prove.",
keywords = "METIS-296180, EWI-22747, Streaming Applications, IR-83472, Timing analysis, Data flow, Max-plus algebra",
author = "{de Groote}, Robert and Jan Kuper and Broersma, {Haitze J.} and Smit, {Gerardus Johannes Maria}",
note = "10.1109/SEAA.2012.20",
year = "2012",
doi = "10.1109/SEAA.2012.20",
language = "Undefined",
isbn = "978-1-4673-2451-9",
publisher = "IEEE Computer Society",
pages = "29--38",
booktitle = "38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA)",
address = "United States",

}

de Groote, R, Kuper, J, Broersma, HJ & Smit, GJM 2012, Max-plus algebraic throughput analysis of synchronous dataflow graphs. in 38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA). IEEE Computer Society, USA, pp. 29-38, 38th EUROMICRO Conference on Software Engineering and Advanced Applications, SEAA 2012, Cesme, Izmir, Turkey, 5/09/12. https://doi.org/10.1109/SEAA.2012.20

Max-plus algebraic throughput analysis of synchronous dataflow graphs. / de Groote, Robert; Kuper, Jan; Broersma, Haitze J.; Smit, Gerardus Johannes Maria.

38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA). USA : IEEE Computer Society, 2012. p. 29-38.

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

TY - GEN

T1 - Max-plus algebraic throughput analysis of synchronous dataflow graphs

AU - de Groote, Robert

AU - Kuper, Jan

AU - Broersma, Haitze J.

AU - Smit, Gerardus Johannes Maria

N1 - 10.1109/SEAA.2012.20

PY - 2012

Y1 - 2012

N2 - In this paper we present a novel approach to throughput analysis of synchronous dataflow (SDF) graphs. Our approach is based on describing the evolution of actor firing times as a linear time-invariant system in max-plus algebra. Experimental results indicate that our approach is faster than state-of-the-art approaches to throughput analysis of SDF graphs. The efficiency of our approach is due to an exploitation of the regular structure of the max-plus system's graphical representation, the properties of which we thoroughly prove.

AB - In this paper we present a novel approach to throughput analysis of synchronous dataflow (SDF) graphs. Our approach is based on describing the evolution of actor firing times as a linear time-invariant system in max-plus algebra. Experimental results indicate that our approach is faster than state-of-the-art approaches to throughput analysis of SDF graphs. The efficiency of our approach is due to an exploitation of the regular structure of the max-plus system's graphical representation, the properties of which we thoroughly prove.

KW - METIS-296180

KW - EWI-22747

KW - Streaming Applications

KW - IR-83472

KW - Timing analysis

KW - Data flow

KW - Max-plus algebra

U2 - 10.1109/SEAA.2012.20

DO - 10.1109/SEAA.2012.20

M3 - Conference contribution

SN - 978-1-4673-2451-9

SP - 29

EP - 38

BT - 38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA)

PB - IEEE Computer Society

CY - USA

ER -

de Groote R, Kuper J, Broersma HJ, Smit GJM. Max-plus algebraic throughput analysis of synchronous dataflow graphs. In 38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA). USA: IEEE Computer Society. 2012. p. 29-38 https://doi.org/10.1109/SEAA.2012.20