Latency analysis of homogeneous synchronous dataflow graphs using timed automata

Guus Kuiper, Marco J.G. Bekooij

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

2 Citations (Scopus)
59 Downloads (Pure)

Abstract

There are several analysis models and corresponding temporal analysis techniques for checking whether applications executed on multiprocessor systems meet their real-time constraints. However, currently there does not exist an exact end-to-end latency analysis technique for Homogeneous Synchronous Dataflow with auto-concurrency (HSDFa) models that takes the correlation between the firing durations of different firings into account. In this paper we present a transformation of strongly connected HSDFa models into timed automata models. This enables an exact end-to-end latency analysis because the correlation between the firing durations of different firings is taken into account. In a case study we compare the latency obtained using timed automata and a Linear Program (LP) based analysis technique that relies on a deterministic abstraction and compare their run-times as well. Exact end-to-end latency analysis results are obtained using timed automata, whereas this is not possible using deterministic timed-dataflow models.
Original languageEnglish
Title of host publicationProceedings of the 2017 Design, Automation & Test in Europe (DATE)
Subtitle of host publication27–31 March 2017, Swisstech, Lausanne, Switzerland
PublisherIEEE
Pages902-905
ISBN (Print)978-3-9815370-9-3
DOIs
Publication statusPublished - Mar 2017
Event2017 Design, Automation & Test in Europe Conference & Exhibition, DATE 2017 - Lausanne, Switzerland
Duration: 27 Mar 201731 Mar 2017
https://www.date-conference.com/date17/

Conference

Conference2017 Design, Automation & Test in Europe Conference & Exhibition, DATE 2017
Abbreviated titleDATE
CountrySwitzerland
CityLausanne
Period27/03/1731/03/17
Internet address

Cite this

Kuiper, G., & Bekooij, M. J. G. (2017). Latency analysis of homogeneous synchronous dataflow graphs using timed automata. In Proceedings of the 2017 Design, Automation & Test in Europe (DATE): 27–31 March 2017, Swisstech, Lausanne, Switzerland (pp. 902-905). IEEE. https://doi.org/10.23919/DATE.2017.7927116
Kuiper, Guus ; Bekooij, Marco J.G. / Latency analysis of homogeneous synchronous dataflow graphs using timed automata. Proceedings of the 2017 Design, Automation & Test in Europe (DATE): 27–31 March 2017, Swisstech, Lausanne, Switzerland. IEEE, 2017. pp. 902-905
@inproceedings{be08a6405df84de9a2f8b572c6028f2e,
title = "Latency analysis of homogeneous synchronous dataflow graphs using timed automata",
abstract = "There are several analysis models and corresponding temporal analysis techniques for checking whether applications executed on multiprocessor systems meet their real-time constraints. However, currently there does not exist an exact end-to-end latency analysis technique for Homogeneous Synchronous Dataflow with auto-concurrency (HSDFa) models that takes the correlation between the firing durations of different firings into account. In this paper we present a transformation of strongly connected HSDFa models into timed automata models. This enables an exact end-to-end latency analysis because the correlation between the firing durations of different firings is taken into account. In a case study we compare the latency obtained using timed automata and a Linear Program (LP) based analysis technique that relies on a deterministic abstraction and compare their run-times as well. Exact end-to-end latency analysis results are obtained using timed automata, whereas this is not possible using deterministic timed-dataflow models.",
author = "Guus Kuiper and Bekooij, {Marco J.G.}",
year = "2017",
month = "3",
doi = "10.23919/DATE.2017.7927116",
language = "English",
isbn = "978-3-9815370-9-3",
pages = "902--905",
booktitle = "Proceedings of the 2017 Design, Automation & Test in Europe (DATE)",
publisher = "IEEE",
address = "United States",

}

Kuiper, G & Bekooij, MJG 2017, Latency analysis of homogeneous synchronous dataflow graphs using timed automata. in Proceedings of the 2017 Design, Automation & Test in Europe (DATE): 27–31 March 2017, Swisstech, Lausanne, Switzerland. IEEE, pp. 902-905, 2017 Design, Automation & Test in Europe Conference & Exhibition, DATE 2017, Lausanne, Switzerland, 27/03/17. https://doi.org/10.23919/DATE.2017.7927116

Latency analysis of homogeneous synchronous dataflow graphs using timed automata. / Kuiper, Guus ; Bekooij, Marco J.G.

Proceedings of the 2017 Design, Automation & Test in Europe (DATE): 27–31 March 2017, Swisstech, Lausanne, Switzerland. IEEE, 2017. p. 902-905.

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

TY - GEN

T1 - Latency analysis of homogeneous synchronous dataflow graphs using timed automata

AU - Kuiper, Guus

AU - Bekooij, Marco J.G.

PY - 2017/3

Y1 - 2017/3

N2 - There are several analysis models and corresponding temporal analysis techniques for checking whether applications executed on multiprocessor systems meet their real-time constraints. However, currently there does not exist an exact end-to-end latency analysis technique for Homogeneous Synchronous Dataflow with auto-concurrency (HSDFa) models that takes the correlation between the firing durations of different firings into account. In this paper we present a transformation of strongly connected HSDFa models into timed automata models. This enables an exact end-to-end latency analysis because the correlation between the firing durations of different firings is taken into account. In a case study we compare the latency obtained using timed automata and a Linear Program (LP) based analysis technique that relies on a deterministic abstraction and compare their run-times as well. Exact end-to-end latency analysis results are obtained using timed automata, whereas this is not possible using deterministic timed-dataflow models.

AB - There are several analysis models and corresponding temporal analysis techniques for checking whether applications executed on multiprocessor systems meet their real-time constraints. However, currently there does not exist an exact end-to-end latency analysis technique for Homogeneous Synchronous Dataflow with auto-concurrency (HSDFa) models that takes the correlation between the firing durations of different firings into account. In this paper we present a transformation of strongly connected HSDFa models into timed automata models. This enables an exact end-to-end latency analysis because the correlation between the firing durations of different firings is taken into account. In a case study we compare the latency obtained using timed automata and a Linear Program (LP) based analysis technique that relies on a deterministic abstraction and compare their run-times as well. Exact end-to-end latency analysis results are obtained using timed automata, whereas this is not possible using deterministic timed-dataflow models.

U2 - 10.23919/DATE.2017.7927116

DO - 10.23919/DATE.2017.7927116

M3 - Conference contribution

SN - 978-3-9815370-9-3

SP - 902

EP - 905

BT - Proceedings of the 2017 Design, Automation & Test in Europe (DATE)

PB - IEEE

ER -

Kuiper G, Bekooij MJG. Latency analysis of homogeneous synchronous dataflow graphs using timed automata. In Proceedings of the 2017 Design, Automation & Test in Europe (DATE): 27–31 March 2017, Swisstech, Lausanne, Switzerland. IEEE. 2017. p. 902-905 https://doi.org/10.23919/DATE.2017.7927116