Single-rate approximations of cyclo-static synchronous dataflow graphs

Robert de Groote, P.K.F. Holzenspies, Jan Kuper, Gerardus Johannes Maria Smit

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

    Abstract

    Exact analysis of synchronous dataflow (sdf) graphs is often considered too costly, because of the expensive transformation of the graph into a single-rate equivalent. As an alternative, several authors have proposed approximate analyses. Existing approaches to approximation are based on the operational semantics of an sdf graph. We propose an approach to approximation that is based on functional semantics. This generalises earlier work done on multi-rate sdf graphs towards cyclo-static sdf (csdf) graphs. We take, as a starting point, a mathematical characterisation, and derive two transformations of a csdf graph into hsdf graphs. These hsdf graphs have the same size as the csdf graph, and are approximations: their respective temporal behaviours are optimistic and pessimistic with respect to the temporal behaviour of the csdf graph. Analysis results computed for these single-rate approximations give bounds on the analysis results of the csdf graph. As an illustration, we show how these single-rate approximations may be used to compute bounds on the buffer sizes required to reach a given throughput.
    Original languageEnglish
    Title of host publicationProceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014)
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery (ACM)
    Pages11-20
    Number of pages10
    ISBN (Print)978-1-4503-2941-5
    DOIs
    Publication statusPublished - 10 Jun 2014
    Event17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014 - St. Goar, Germany
    Duration: 10 Jun 201411 Jun 2014
    Conference number: 17
    http://www.scopesconf.org/scopes-14/

    Conference

    Conference17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014
    Abbreviated titleSCOPES
    CountryGermany
    CitySt. Goar
    Period10/06/1411/06/14
    Internet address

    Fingerprint

    Rate of Approximation
    Data Flow
    Graph in graph theory
    Approximation
    Operational Semantics
    Buffer
    Throughput

    Keywords

    • EWI-24805
    • EC Grant Agreement nr.: FP7/2007-2013
    • METIS-304119
    • EC Grant Agreement nr.: FP7/610686
    • IR-91351
    • EC Grant Agreement nr.: FP7/318490

    Cite this

    de Groote, R., Holzenspies, P. K. F., Kuper, J., & Smit, G. J. M. (2014). Single-rate approximations of cyclo-static synchronous dataflow graphs. In Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014) (pp. 11-20). New York: Association for Computing Machinery (ACM). https://doi.org/10.1145/2609248.2609249
    de Groote, Robert ; Holzenspies, P.K.F. ; Kuper, Jan ; Smit, Gerardus Johannes Maria. / Single-rate approximations of cyclo-static synchronous dataflow graphs. Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014). New York : Association for Computing Machinery (ACM), 2014. pp. 11-20
    @inproceedings{16ad87e8704248b097a6d310992e181b,
    title = "Single-rate approximations of cyclo-static synchronous dataflow graphs",
    abstract = "Exact analysis of synchronous dataflow (sdf) graphs is often considered too costly, because of the expensive transformation of the graph into a single-rate equivalent. As an alternative, several authors have proposed approximate analyses. Existing approaches to approximation are based on the operational semantics of an sdf graph. We propose an approach to approximation that is based on functional semantics. This generalises earlier work done on multi-rate sdf graphs towards cyclo-static sdf (csdf) graphs. We take, as a starting point, a mathematical characterisation, and derive two transformations of a csdf graph into hsdf graphs. These hsdf graphs have the same size as the csdf graph, and are approximations: their respective temporal behaviours are optimistic and pessimistic with respect to the temporal behaviour of the csdf graph. Analysis results computed for these single-rate approximations give bounds on the analysis results of the csdf graph. As an illustration, we show how these single-rate approximations may be used to compute bounds on the buffer sizes required to reach a given throughput.",
    keywords = "EWI-24805, EC Grant Agreement nr.: FP7/2007-2013, METIS-304119, EC Grant Agreement nr.: FP7/610686, IR-91351, EC Grant Agreement nr.: FP7/318490",
    author = "{de Groote}, Robert and P.K.F. Holzenspies and Jan Kuper and Smit, {Gerardus Johannes Maria}",
    note = "eemcs-eprint-24805",
    year = "2014",
    month = "6",
    day = "10",
    doi = "10.1145/2609248.2609249",
    language = "English",
    isbn = "978-1-4503-2941-5",
    pages = "11--20",
    booktitle = "Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014)",
    publisher = "Association for Computing Machinery (ACM)",
    address = "United States",

    }

    de Groote, R, Holzenspies, PKF, Kuper, J & Smit, GJM 2014, Single-rate approximations of cyclo-static synchronous dataflow graphs. in Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014). Association for Computing Machinery (ACM), New York, pp. 11-20, 17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014, St. Goar, Germany, 10/06/14. https://doi.org/10.1145/2609248.2609249

    Single-rate approximations of cyclo-static synchronous dataflow graphs. / de Groote, Robert; Holzenspies, P.K.F.; Kuper, Jan; Smit, Gerardus Johannes Maria.

    Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014). New York : Association for Computing Machinery (ACM), 2014. p. 11-20.

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

    TY - GEN

    T1 - Single-rate approximations of cyclo-static synchronous dataflow graphs

    AU - de Groote, Robert

    AU - Holzenspies, P.K.F.

    AU - Kuper, Jan

    AU - Smit, Gerardus Johannes Maria

    N1 - eemcs-eprint-24805

    PY - 2014/6/10

    Y1 - 2014/6/10

    N2 - Exact analysis of synchronous dataflow (sdf) graphs is often considered too costly, because of the expensive transformation of the graph into a single-rate equivalent. As an alternative, several authors have proposed approximate analyses. Existing approaches to approximation are based on the operational semantics of an sdf graph. We propose an approach to approximation that is based on functional semantics. This generalises earlier work done on multi-rate sdf graphs towards cyclo-static sdf (csdf) graphs. We take, as a starting point, a mathematical characterisation, and derive two transformations of a csdf graph into hsdf graphs. These hsdf graphs have the same size as the csdf graph, and are approximations: their respective temporal behaviours are optimistic and pessimistic with respect to the temporal behaviour of the csdf graph. Analysis results computed for these single-rate approximations give bounds on the analysis results of the csdf graph. As an illustration, we show how these single-rate approximations may be used to compute bounds on the buffer sizes required to reach a given throughput.

    AB - Exact analysis of synchronous dataflow (sdf) graphs is often considered too costly, because of the expensive transformation of the graph into a single-rate equivalent. As an alternative, several authors have proposed approximate analyses. Existing approaches to approximation are based on the operational semantics of an sdf graph. We propose an approach to approximation that is based on functional semantics. This generalises earlier work done on multi-rate sdf graphs towards cyclo-static sdf (csdf) graphs. We take, as a starting point, a mathematical characterisation, and derive two transformations of a csdf graph into hsdf graphs. These hsdf graphs have the same size as the csdf graph, and are approximations: their respective temporal behaviours are optimistic and pessimistic with respect to the temporal behaviour of the csdf graph. Analysis results computed for these single-rate approximations give bounds on the analysis results of the csdf graph. As an illustration, we show how these single-rate approximations may be used to compute bounds on the buffer sizes required to reach a given throughput.

    KW - EWI-24805

    KW - EC Grant Agreement nr.: FP7/2007-2013

    KW - METIS-304119

    KW - EC Grant Agreement nr.: FP7/610686

    KW - IR-91351

    KW - EC Grant Agreement nr.: FP7/318490

    U2 - 10.1145/2609248.2609249

    DO - 10.1145/2609248.2609249

    M3 - Conference contribution

    SN - 978-1-4503-2941-5

    SP - 11

    EP - 20

    BT - Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014)

    PB - Association for Computing Machinery (ACM)

    CY - New York

    ER -

    de Groote R, Holzenspies PKF, Kuper J, Smit GJM. Single-rate approximations of cyclo-static synchronous dataflow graphs. In Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2014). New York: Association for Computing Machinery (ACM). 2014. p. 11-20 https://doi.org/10.1145/2609248.2609249