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

    3 Citations (Scopus)
    11 Downloads (Pure)


    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
    Number of pages10
    ISBN (Print)978-1-4503-2941-5
    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


    Conference17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014
    Abbreviated titleSCOPES
    CitySt. Goar
    Internet address


    • 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


    Dive into the research topics of 'Single-rate approximations of cyclo-static synchronous dataflow graphs'. Together they form a unique fingerprint.

    Cite this