Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs

    Research output: Book/ReportReportProfessional

    66 Downloads (Pure)

    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
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages6
    Publication statusPublished - 22 Nov 2006

    Publication series

    NameCTIT Technical Report Series
    PublisherCentre for Telematics and Information Technology, University of Twente
    No.06-70
    ISSN (Print)1381-3625

    Keywords

    • EWI-7659
    • CAES-EEA: Efficient Embedded Architectures
    • IR-66538
    • METIS-238699

    Cite this

    Wiggers, M. H., Bekooij, M. J. G., & Smit, G. J. M. (2006). Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. (CTIT Technical Report Series; No. 06-70). Enschede: Centre for Telematics and Information Technology (CTIT).
    Wiggers, M.H. ; Bekooij, Marco Jan Gerrit ; Smit, Gerardus Johannes Maria. / Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. Enschede : Centre for Telematics and Information Technology (CTIT), 2006. 6 p. (CTIT Technical Report Series; 06-70).
    @book{516c475fa0994fdda6cb5b564c7ded83,
    title = "Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs",
    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.",
    keywords = "EWI-7659, CAES-EEA: Efficient Embedded Architectures, IR-66538, METIS-238699",
    author = "M.H. Wiggers and Bekooij, {Marco Jan Gerrit} and Smit, {Gerardus Johannes Maria}",
    year = "2006",
    month = "11",
    day = "22",
    language = "Undefined",
    series = "CTIT Technical Report Series",
    publisher = "Centre for Telematics and Information Technology (CTIT)",
    number = "06-70",
    address = "Netherlands",

    }

    Wiggers, MH, Bekooij, MJG & Smit, GJM 2006, Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. CTIT Technical Report Series, no. 06-70, Centre for Telematics and Information Technology (CTIT), Enschede.

    Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. / Wiggers, M.H.; Bekooij, Marco Jan Gerrit; Smit, Gerardus Johannes Maria.

    Enschede : Centre for Telematics and Information Technology (CTIT), 2006. 6 p. (CTIT Technical Report Series; No. 06-70).

    Research output: Book/ReportReportProfessional

    TY - BOOK

    T1 - Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs

    AU - Wiggers, M.H.

    AU - Bekooij, Marco Jan Gerrit

    AU - Smit, Gerardus Johannes Maria

    PY - 2006/11/22

    Y1 - 2006/11/22

    N2 - 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.

    AB - 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.

    KW - EWI-7659

    KW - CAES-EEA: Efficient Embedded Architectures

    KW - IR-66538

    KW - METIS-238699

    M3 - Report

    T3 - CTIT Technical Report Series

    BT - Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs

    PB - Centre for Telematics and Information Technology (CTIT)

    CY - Enschede

    ER -

    Wiggers MH, Bekooij MJG, Smit GJM. Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. Enschede: Centre for Telematics and Information Technology (CTIT), 2006. 6 p. (CTIT Technical Report Series; 06-70).