Dataflow Analysis for Multiprocessor Systems with Non-Starvation-Free Schedulers

J.P.H.M. Hausmans, S.J. Geuns, M.H. Wiggers, Marco Jan Gerrit Bekooij

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

16 Citations (Scopus)
60 Downloads (Pure)

Abstract

Dataflow analysis techniques are suitable for the temporal analysis of real-time stream processing applications. However, the applicability of these models is currently limited to systems with starvation-free schedulers, such as Time-Division Multiplexing (TDM) schedulers. Removal of this limitation would broaden the application domain of dataflow analysis techniques significantly. In this paper we present a temporal analysis technique for Homogeneous Synchronous Dataflow (HSDF) graphs, that is also applicable for systems with non-starvation-free schedulers. Unlike existing dataflow analysis techniques, the proposed analysis technique makes use of an enabling-jitter characterization and iterative fixed-point computation. The presented approach is applicable for arbitrary (cyclic) graph topologies. Buffer capacity constraints are taken into account during the analysis and sufficient buffer capacities can be determined afterwards. The approach presented in this paper is the first approach that considers non-starvation-free schedulers in combination with arbitrary HSDF graphs. The proposed dataflow analysis technique is implemented in a tool. This tool is used to evaluate the analysis technique using examples that illustrate some important differences with other temporal analysis methods. The case-study discusses how the method presented in this paper can be used to solve a problem with the inaccuracy of the temporal analysis results of a real-time stream processing system. This stream processing system consists of an FM receiver together with a DAB receiver application which both share a Digital Signal Processor (DSP).
Original languageUndefined
Title of host publicationProceedings of the 16th International Workshop on Software and Compilers for Embedded Systems
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages13-22
Number of pages10
ISBN (Print)978-1-4503-2142-6
DOIs
Publication statusPublished - 19 Jun 2013
Event16th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2013 - Schloss Rheinfels, St. Goar, Germany
Duration: 19 Jun 201321 Jun 2013
Conference number: 16
http://www.scopesconf.org/scopes-13/

Publication series

Name
PublisherACM

Conference

Conference16th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2013
Abbreviated titleSCOPES
CountryGermany
CitySt. Goar
Period19/06/1321/06/13
Internet address

Keywords

  • IR-86748
  • METIS-297743
  • EWI-23535

Cite this

Hausmans, J. P. H. M., Geuns, S. J., Wiggers, M. H., & Bekooij, M. J. G. (2013). Dataflow Analysis for Multiprocessor Systems with Non-Starvation-Free Schedulers. In Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems (pp. 13-22). New York: Association for Computing Machinery (ACM). https://doi.org/10.1145/2463596.2463603
Hausmans, J.P.H.M. ; Geuns, S.J. ; Wiggers, M.H. ; Bekooij, Marco Jan Gerrit. / Dataflow Analysis for Multiprocessor Systems with Non-Starvation-Free Schedulers. Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems. New York : Association for Computing Machinery (ACM), 2013. pp. 13-22
@inproceedings{4dc08f49bf4f49b691a86610583ce98b,
title = "Dataflow Analysis for Multiprocessor Systems with Non-Starvation-Free Schedulers",
abstract = "Dataflow analysis techniques are suitable for the temporal analysis of real-time stream processing applications. However, the applicability of these models is currently limited to systems with starvation-free schedulers, such as Time-Division Multiplexing (TDM) schedulers. Removal of this limitation would broaden the application domain of dataflow analysis techniques significantly. In this paper we present a temporal analysis technique for Homogeneous Synchronous Dataflow (HSDF) graphs, that is also applicable for systems with non-starvation-free schedulers. Unlike existing dataflow analysis techniques, the proposed analysis technique makes use of an enabling-jitter characterization and iterative fixed-point computation. The presented approach is applicable for arbitrary (cyclic) graph topologies. Buffer capacity constraints are taken into account during the analysis and sufficient buffer capacities can be determined afterwards. The approach presented in this paper is the first approach that considers non-starvation-free schedulers in combination with arbitrary HSDF graphs. The proposed dataflow analysis technique is implemented in a tool. This tool is used to evaluate the analysis technique using examples that illustrate some important differences with other temporal analysis methods. The case-study discusses how the method presented in this paper can be used to solve a problem with the inaccuracy of the temporal analysis results of a real-time stream processing system. This stream processing system consists of an FM receiver together with a DAB receiver application which both share a Digital Signal Processor (DSP).",
keywords = "IR-86748, METIS-297743, EWI-23535",
author = "J.P.H.M. Hausmans and S.J. Geuns and M.H. Wiggers and Bekooij, {Marco Jan Gerrit}",
note = "10.1145/2463596.2463603",
year = "2013",
month = "6",
day = "19",
doi = "10.1145/2463596.2463603",
language = "Undefined",
isbn = "978-1-4503-2142-6",
publisher = "Association for Computing Machinery (ACM)",
pages = "13--22",
booktitle = "Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems",
address = "United States",

}

Hausmans, JPHM, Geuns, SJ, Wiggers, MH & Bekooij, MJG 2013, Dataflow Analysis for Multiprocessor Systems with Non-Starvation-Free Schedulers. in Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems. Association for Computing Machinery (ACM), New York, pp. 13-22, 16th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2013, St. Goar, Germany, 19/06/13. https://doi.org/10.1145/2463596.2463603

Dataflow Analysis for Multiprocessor Systems with Non-Starvation-Free Schedulers. / Hausmans, J.P.H.M.; Geuns, S.J.; Wiggers, M.H.; Bekooij, Marco Jan Gerrit.

Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems. New York : Association for Computing Machinery (ACM), 2013. p. 13-22.

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

TY - GEN

T1 - Dataflow Analysis for Multiprocessor Systems with Non-Starvation-Free Schedulers

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

AU - Geuns, S.J.

AU - Wiggers, M.H.

AU - Bekooij, Marco Jan Gerrit

N1 - 10.1145/2463596.2463603

PY - 2013/6/19

Y1 - 2013/6/19

N2 - Dataflow analysis techniques are suitable for the temporal analysis of real-time stream processing applications. However, the applicability of these models is currently limited to systems with starvation-free schedulers, such as Time-Division Multiplexing (TDM) schedulers. Removal of this limitation would broaden the application domain of dataflow analysis techniques significantly. In this paper we present a temporal analysis technique for Homogeneous Synchronous Dataflow (HSDF) graphs, that is also applicable for systems with non-starvation-free schedulers. Unlike existing dataflow analysis techniques, the proposed analysis technique makes use of an enabling-jitter characterization and iterative fixed-point computation. The presented approach is applicable for arbitrary (cyclic) graph topologies. Buffer capacity constraints are taken into account during the analysis and sufficient buffer capacities can be determined afterwards. The approach presented in this paper is the first approach that considers non-starvation-free schedulers in combination with arbitrary HSDF graphs. The proposed dataflow analysis technique is implemented in a tool. This tool is used to evaluate the analysis technique using examples that illustrate some important differences with other temporal analysis methods. The case-study discusses how the method presented in this paper can be used to solve a problem with the inaccuracy of the temporal analysis results of a real-time stream processing system. This stream processing system consists of an FM receiver together with a DAB receiver application which both share a Digital Signal Processor (DSP).

AB - Dataflow analysis techniques are suitable for the temporal analysis of real-time stream processing applications. However, the applicability of these models is currently limited to systems with starvation-free schedulers, such as Time-Division Multiplexing (TDM) schedulers. Removal of this limitation would broaden the application domain of dataflow analysis techniques significantly. In this paper we present a temporal analysis technique for Homogeneous Synchronous Dataflow (HSDF) graphs, that is also applicable for systems with non-starvation-free schedulers. Unlike existing dataflow analysis techniques, the proposed analysis technique makes use of an enabling-jitter characterization and iterative fixed-point computation. The presented approach is applicable for arbitrary (cyclic) graph topologies. Buffer capacity constraints are taken into account during the analysis and sufficient buffer capacities can be determined afterwards. The approach presented in this paper is the first approach that considers non-starvation-free schedulers in combination with arbitrary HSDF graphs. The proposed dataflow analysis technique is implemented in a tool. This tool is used to evaluate the analysis technique using examples that illustrate some important differences with other temporal analysis methods. The case-study discusses how the method presented in this paper can be used to solve a problem with the inaccuracy of the temporal analysis results of a real-time stream processing system. This stream processing system consists of an FM receiver together with a DAB receiver application which both share a Digital Signal Processor (DSP).

KW - IR-86748

KW - METIS-297743

KW - EWI-23535

U2 - 10.1145/2463596.2463603

DO - 10.1145/2463596.2463603

M3 - Conference contribution

SN - 978-1-4503-2142-6

SP - 13

EP - 22

BT - Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems

PB - Association for Computing Machinery (ACM)

CY - New York

ER -

Hausmans JPHM, Geuns SJ, Wiggers MH, Bekooij MJG. Dataflow Analysis for Multiprocessor Systems with Non-Starvation-Free Schedulers. In Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems. New York: Association for Computing Machinery (ACM). 2013. p. 13-22 https://doi.org/10.1145/2463596.2463603