A Refinement Theory for Timed-Dataflow Analysis with Support for Reordering

J.P.H.M. Hausmans, Marco Jan Gerrit Bekooij

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

6 Citations (Scopus)

Abstract

Real-time stream processing applications executed on embedded multiprocessor systems often have strict throughput and latency constraints. Violating these constraints is undesired and temporal analysis methods are therefore used to prevent such violations. These analysis methods use abstractions of the analyzed applications to simplify their temporal analysis. Refinement theories have enabled the creation of deterministic abstractions of stream processing applications that are executed on multiprocessor systems. Prominent examples of such abstract models are deterministic timed-dataflow models which can be efficiently analyzed because they only have one behavior. An important aspect of a stream processing application can be that it makes use of reordered data streams between tasks. An example is the bit-reversed ordered stream produced by a FFT task. However, existing abstraction/refinement theories do not support such reordering behavior or do not handle this type of behavior correctly. This is because existing refinement theories assume that the temporal behavior of applications is orthogonal to their functional behavior, whereas this orthogonality does not always hold in the case of reordered data streams. In this paper we introduce a new refinement theory in which the potential interaction between temporal and functional behavior is taken into account. The introduced theory supports reordering of data and can therefore be used to validate existing systems with such reordering. Furthermore, the theory enables showing that deterministic dataflow models that do not apply reordering can be used as valid abstractions of systems in which reordering takes place. The applicability of the refinement theory is demonstrated by creating deterministic timed-dataflow model abstractions of a DVB-T application, and a communication network in which data is reordered. With these dataflow models the guaranteed throughput and buffer capacities of implementation options are compared.
Original languageUndefined
Title of host publicationProceedings of the 13th International Conference on Embedded Software, EMSOFT 2016
PublisherAssociation for Computing Machinery (ACM)
Pages-
Number of pages10
ISBN (Print)978-1-4503-4485-2
DOIs
Publication statusPublished - 12 Oct 2016

Publication series

Name
PublisherACM

Keywords

  • METIS-318558
  • IR-101824
  • Timed Dataflow
  • EWI-27320

Cite this

Hausmans, J. P. H. M., & Bekooij, M. J. G. (2016). A Refinement Theory for Timed-Dataflow Analysis with Support for Reordering. In Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016 (pp. -). Association for Computing Machinery (ACM). https://doi.org/10.1145/2968478.2968489
Hausmans, J.P.H.M. ; Bekooij, Marco Jan Gerrit. / A Refinement Theory for Timed-Dataflow Analysis with Support for Reordering. Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016. Association for Computing Machinery (ACM), 2016. pp. -
@inproceedings{c3b783f3accb4677b0464362ea51354a,
title = "A Refinement Theory for Timed-Dataflow Analysis with Support for Reordering",
abstract = "Real-time stream processing applications executed on embedded multiprocessor systems often have strict throughput and latency constraints. Violating these constraints is undesired and temporal analysis methods are therefore used to prevent such violations. These analysis methods use abstractions of the analyzed applications to simplify their temporal analysis. Refinement theories have enabled the creation of deterministic abstractions of stream processing applications that are executed on multiprocessor systems. Prominent examples of such abstract models are deterministic timed-dataflow models which can be efficiently analyzed because they only have one behavior. An important aspect of a stream processing application can be that it makes use of reordered data streams between tasks. An example is the bit-reversed ordered stream produced by a FFT task. However, existing abstraction/refinement theories do not support such reordering behavior or do not handle this type of behavior correctly. This is because existing refinement theories assume that the temporal behavior of applications is orthogonal to their functional behavior, whereas this orthogonality does not always hold in the case of reordered data streams. In this paper we introduce a new refinement theory in which the potential interaction between temporal and functional behavior is taken into account. The introduced theory supports reordering of data and can therefore be used to validate existing systems with such reordering. Furthermore, the theory enables showing that deterministic dataflow models that do not apply reordering can be used as valid abstractions of systems in which reordering takes place. The applicability of the refinement theory is demonstrated by creating deterministic timed-dataflow model abstractions of a DVB-T application, and a communication network in which data is reordered. With these dataflow models the guaranteed throughput and buffer capacities of implementation options are compared.",
keywords = "METIS-318558, IR-101824, Timed Dataflow, EWI-27320",
author = "J.P.H.M. Hausmans and Bekooij, {Marco Jan Gerrit}",
note = "eemcs-eprint-27320",
year = "2016",
month = "10",
day = "12",
doi = "10.1145/2968478.2968489",
language = "Undefined",
isbn = "978-1-4503-4485-2",
publisher = "Association for Computing Machinery (ACM)",
pages = "--",
booktitle = "Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016",
address = "United States",

}

Hausmans, JPHM & Bekooij, MJG 2016, A Refinement Theory for Timed-Dataflow Analysis with Support for Reordering. in Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016. Association for Computing Machinery (ACM), pp. -. https://doi.org/10.1145/2968478.2968489

A Refinement Theory for Timed-Dataflow Analysis with Support for Reordering. / Hausmans, J.P.H.M.; Bekooij, Marco Jan Gerrit.

Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016. Association for Computing Machinery (ACM), 2016. p. -.

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

TY - GEN

T1 - A Refinement Theory for Timed-Dataflow Analysis with Support for Reordering

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

AU - Bekooij, Marco Jan Gerrit

N1 - eemcs-eprint-27320

PY - 2016/10/12

Y1 - 2016/10/12

N2 - Real-time stream processing applications executed on embedded multiprocessor systems often have strict throughput and latency constraints. Violating these constraints is undesired and temporal analysis methods are therefore used to prevent such violations. These analysis methods use abstractions of the analyzed applications to simplify their temporal analysis. Refinement theories have enabled the creation of deterministic abstractions of stream processing applications that are executed on multiprocessor systems. Prominent examples of such abstract models are deterministic timed-dataflow models which can be efficiently analyzed because they only have one behavior. An important aspect of a stream processing application can be that it makes use of reordered data streams between tasks. An example is the bit-reversed ordered stream produced by a FFT task. However, existing abstraction/refinement theories do not support such reordering behavior or do not handle this type of behavior correctly. This is because existing refinement theories assume that the temporal behavior of applications is orthogonal to their functional behavior, whereas this orthogonality does not always hold in the case of reordered data streams. In this paper we introduce a new refinement theory in which the potential interaction between temporal and functional behavior is taken into account. The introduced theory supports reordering of data and can therefore be used to validate existing systems with such reordering. Furthermore, the theory enables showing that deterministic dataflow models that do not apply reordering can be used as valid abstractions of systems in which reordering takes place. The applicability of the refinement theory is demonstrated by creating deterministic timed-dataflow model abstractions of a DVB-T application, and a communication network in which data is reordered. With these dataflow models the guaranteed throughput and buffer capacities of implementation options are compared.

AB - Real-time stream processing applications executed on embedded multiprocessor systems often have strict throughput and latency constraints. Violating these constraints is undesired and temporal analysis methods are therefore used to prevent such violations. These analysis methods use abstractions of the analyzed applications to simplify their temporal analysis. Refinement theories have enabled the creation of deterministic abstractions of stream processing applications that are executed on multiprocessor systems. Prominent examples of such abstract models are deterministic timed-dataflow models which can be efficiently analyzed because they only have one behavior. An important aspect of a stream processing application can be that it makes use of reordered data streams between tasks. An example is the bit-reversed ordered stream produced by a FFT task. However, existing abstraction/refinement theories do not support such reordering behavior or do not handle this type of behavior correctly. This is because existing refinement theories assume that the temporal behavior of applications is orthogonal to their functional behavior, whereas this orthogonality does not always hold in the case of reordered data streams. In this paper we introduce a new refinement theory in which the potential interaction between temporal and functional behavior is taken into account. The introduced theory supports reordering of data and can therefore be used to validate existing systems with such reordering. Furthermore, the theory enables showing that deterministic dataflow models that do not apply reordering can be used as valid abstractions of systems in which reordering takes place. The applicability of the refinement theory is demonstrated by creating deterministic timed-dataflow model abstractions of a DVB-T application, and a communication network in which data is reordered. With these dataflow models the guaranteed throughput and buffer capacities of implementation options are compared.

KW - METIS-318558

KW - IR-101824

KW - Timed Dataflow

KW - EWI-27320

U2 - 10.1145/2968478.2968489

DO - 10.1145/2968478.2968489

M3 - Conference contribution

SN - 978-1-4503-4485-2

SP - -

BT - Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016

PB - Association for Computing Machinery (ACM)

ER -

Hausmans JPHM, Bekooij MJG. A Refinement Theory for Timed-Dataflow Analysis with Support for Reordering. In Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016. Association for Computing Machinery (ACM). 2016. p. - https://doi.org/10.1145/2968478.2968489