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