Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications

Philip Sebastian Kurtin, J.P.H.M. Hausmans, Marco Jan Gerrit Bekooij

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

12 Citations (Scopus)
40 Downloads (Pure)

Abstract

Stream processing applications executed on multiprocessor systems usually contain cyclic data dependencies due to the presence of bounded FIFO buffers and feedback loops, as well as cyclic resource dependencies due to the usage of shared processors. In recent works it has been shown that temporal analysis of such applications can be performed by iterative fixed-point algorithms that combine dataflow and response time analysis techniques. However, these algorithms consider resource dependencies based on the assumption that tasks on shared processors are enabled simultaneously, resulting in a significant overestimation of interference between such tasks. This paper extends these approaches by integrating an explicit consideration of precedence constraints with a notion of offsets between tasks on shared processors, leading to a significant improvement of temporal analysis results for cyclic stream processing applications. Moreover, the addition of an iterative buffer sizing enables an improvement of temporal analysis results for acyclic applications as well. The performance of the presented approach is evaluated in a case study using a WLAN transceiver application. It is shown that 56% higher throughput guarantees and 52% smaller end-to-end latencies can be determined compared to state-of-the-art.
Original languageUndefined
Title of host publicationIEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016
Place of PublicationUSA
PublisherIEEE Computer Society
Pages1-12
Number of pages12
ISBN (Print)978-1-4673-8639-5
DOIs
Publication statusPublished - 14 Apr 2016

Publication series

Name
PublisherIEEE Computer Society

Keywords

  • EWI-27005
  • IR-100362
  • METIS-316921

Cite this

Kurtin, P. S., Hausmans, J. P. H. M., & Bekooij, M. J. G. (2016). Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications. In IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016 (pp. 1-12). USA: IEEE Computer Society. https://doi.org/10.1109/RTAS.2016.7461325
Kurtin, Philip Sebastian ; Hausmans, J.P.H.M. ; Bekooij, Marco Jan Gerrit. / Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications. IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016. USA : IEEE Computer Society, 2016. pp. 1-12
@inproceedings{17d44acf5468432eabb43d6aecfc7496,
title = "Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications",
abstract = "Stream processing applications executed on multiprocessor systems usually contain cyclic data dependencies due to the presence of bounded FIFO buffers and feedback loops, as well as cyclic resource dependencies due to the usage of shared processors. In recent works it has been shown that temporal analysis of such applications can be performed by iterative fixed-point algorithms that combine dataflow and response time analysis techniques. However, these algorithms consider resource dependencies based on the assumption that tasks on shared processors are enabled simultaneously, resulting in a significant overestimation of interference between such tasks. This paper extends these approaches by integrating an explicit consideration of precedence constraints with a notion of offsets between tasks on shared processors, leading to a significant improvement of temporal analysis results for cyclic stream processing applications. Moreover, the addition of an iterative buffer sizing enables an improvement of temporal analysis results for acyclic applications as well. The performance of the presented approach is evaluated in a case study using a WLAN transceiver application. It is shown that 56{\%} higher throughput guarantees and 52{\%} smaller end-to-end latencies can be determined compared to state-of-the-art.",
keywords = "EWI-27005, IR-100362, METIS-316921",
author = "Kurtin, {Philip Sebastian} and J.P.H.M. Hausmans and Bekooij, {Marco Jan Gerrit}",
note = "eemcs-eprint-27005",
year = "2016",
month = "4",
day = "14",
doi = "10.1109/RTAS.2016.7461325",
language = "Undefined",
isbn = "978-1-4673-8639-5",
publisher = "IEEE Computer Society",
pages = "1--12",
booktitle = "IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016",
address = "United States",

}

Kurtin, PS, Hausmans, JPHM & Bekooij, MJG 2016, Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications. in IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016. IEEE Computer Society, USA, pp. 1-12. https://doi.org/10.1109/RTAS.2016.7461325

Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications. / Kurtin, Philip Sebastian; Hausmans, J.P.H.M.; Bekooij, Marco Jan Gerrit.

IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016. USA : IEEE Computer Society, 2016. p. 1-12.

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

TY - GEN

T1 - Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications

AU - Kurtin, Philip Sebastian

AU - Hausmans, J.P.H.M.

AU - Bekooij, Marco Jan Gerrit

N1 - eemcs-eprint-27005

PY - 2016/4/14

Y1 - 2016/4/14

N2 - Stream processing applications executed on multiprocessor systems usually contain cyclic data dependencies due to the presence of bounded FIFO buffers and feedback loops, as well as cyclic resource dependencies due to the usage of shared processors. In recent works it has been shown that temporal analysis of such applications can be performed by iterative fixed-point algorithms that combine dataflow and response time analysis techniques. However, these algorithms consider resource dependencies based on the assumption that tasks on shared processors are enabled simultaneously, resulting in a significant overestimation of interference between such tasks. This paper extends these approaches by integrating an explicit consideration of precedence constraints with a notion of offsets between tasks on shared processors, leading to a significant improvement of temporal analysis results for cyclic stream processing applications. Moreover, the addition of an iterative buffer sizing enables an improvement of temporal analysis results for acyclic applications as well. The performance of the presented approach is evaluated in a case study using a WLAN transceiver application. It is shown that 56% higher throughput guarantees and 52% smaller end-to-end latencies can be determined compared to state-of-the-art.

AB - Stream processing applications executed on multiprocessor systems usually contain cyclic data dependencies due to the presence of bounded FIFO buffers and feedback loops, as well as cyclic resource dependencies due to the usage of shared processors. In recent works it has been shown that temporal analysis of such applications can be performed by iterative fixed-point algorithms that combine dataflow and response time analysis techniques. However, these algorithms consider resource dependencies based on the assumption that tasks on shared processors are enabled simultaneously, resulting in a significant overestimation of interference between such tasks. This paper extends these approaches by integrating an explicit consideration of precedence constraints with a notion of offsets between tasks on shared processors, leading to a significant improvement of temporal analysis results for cyclic stream processing applications. Moreover, the addition of an iterative buffer sizing enables an improvement of temporal analysis results for acyclic applications as well. The performance of the presented approach is evaluated in a case study using a WLAN transceiver application. It is shown that 56% higher throughput guarantees and 52% smaller end-to-end latencies can be determined compared to state-of-the-art.

KW - EWI-27005

KW - IR-100362

KW - METIS-316921

U2 - 10.1109/RTAS.2016.7461325

DO - 10.1109/RTAS.2016.7461325

M3 - Conference contribution

SN - 978-1-4673-8639-5

SP - 1

EP - 12

BT - IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016

PB - IEEE Computer Society

CY - USA

ER -

Kurtin PS, Hausmans JPHM, Bekooij MJG. Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications. In IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2016. USA: IEEE Computer Society. 2016. p. 1-12 https://doi.org/10.1109/RTAS.2016.7461325