Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs

M.H. Wiggers, Marco Jan Gerrit Bekooij, Marco J.G. Bekooij, Gerardus Johannes Maria Smit

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

    62 Citations (Scopus)

    Abstract

    A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure, which means that tasks wait for space in output buffers. Consequently buffer capacities affect the throughput. This requires the derivation of buffer capacities that both result in a satisfaction of the throughput constraint, and also satisfy the constraints on the maximum buffer capacities. Existing exact solutions suffer from the computational complexity that is associated with the required conversion from a cyclo-static dataflow graph to a single-rate dataflow graph. In this paper we present an algorithm, with polynomial computational complexity, that does not require this conversion and that obtains close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our multi-processor system. For this application, we see that a cyclo-static dataflow model can reduce the buffer capacities by 50% compared to a multi-rate dataflow model.
    Original languageUndefined
    Title of host publicationDAC '07: Proceedings of the 44th annual conference on Design automation
    Place of PublicationNew York, NY, USA
    PublisherACM Press
    Pages658-663
    Number of pages6
    ISBN (Print)978-1-59593-627-1
    DOIs
    Publication statusPublished - Jun 2007

    Publication series

    Name
    PublisherACM Press
    NumberLNCS4549

    Keywords

    • CAES-EEA: Efficient Embedded Architectures
    • IR-61918
    • METIS-242198
    • EWI-11059

    Cite this

    Wiggers, M. H., Bekooij, M. J. G., Bekooij, M. J. G., & Smit, G. J. M. (2007). Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. In DAC '07: Proceedings of the 44th annual conference on Design automation (pp. 658-663). [10.1109/DAC.2007.375247] New York, NY, USA: ACM Press. https://doi.org/10.1109/DAC.2007.375247