Max-plus algebraic throughput analysis of synchronous dataflow graphs

Robert de Groote; Jan Kuper; Haitze J. Broersma; Gerardus Johannes Maria Smit

doi:10.1109/SEAA.2012.20

Max-plus algebraic throughput analysis of synchronous dataflow graphs

Robert de Groote
, Jan Kuper
, Haitze J. Broersma
, Gerardus Johannes Maria Smit

Discrete Mathematics and Mathematical Programming

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

31 Citations (Scopus)

913 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 language	Undefined
Title of host publication	38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA)
Place of Publication	USA
Publisher	IEEE
Pages	29-38
Number of pages	10
ISBN (Print)	978-1-4673-2451-9
DOIs	https://doi.org/10.1109/SEAA.2012.20
Publication status	Published - 2012
Event	38th EUROMICRO Conference on Software Engineering and Advanced Applications, SEAA 2012 - Cesme, Izmir, Turkey Duration: 5 Sept 2012 → 8 Sept 2012 Conference number: 38

Publication series

Name
Publisher	IEEE Computer Society

Conference

Conference	38th EUROMICRO Conference on Software Engineering and Advanced Applications, SEAA 2012
Abbreviated title	SEAA
Country/Territory	Turkey
City	Cesme, Izmir
Period	5/09/12 → 8/09/12

Keywords

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

Access to Document

10.1109/SEAA.2012.20

Cite this

@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 ; 38th EUROMICRO Conference on Software Engineering and Advanced Applications, SEAA 2012 ; Conference date: 05-09-2012 Through 08-09-2012",

year = "2012",

doi = "10.1109/SEAA.2012.20",

language = "Undefined",

isbn = "978-1-4673-2451-9",

publisher = "IEEE",

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

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 - Conference code: 38

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

CY - USA

T2 - 38th EUROMICRO Conference on Software Engineering and Advanced Applications, SEAA 2012

Y2 - 5 September 2012 through 8 September 2012

ER -