Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure

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

    Research output: Book/ReportReportProfessional

    26 Downloads (Pure)

    Abstract

    A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multiprocessor 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 linear computational complexity, that does not require this conversion and that strives to obtain close to minimal buffer capacities. The algorithm is applied to an MP3 playback application that is mapped on our multi-processor system.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages10
    Publication statusPublished - 17 Oct 2006

    Publication series

    NameCTIT technical reports series
    PublisherCentre for Telematics and Information Technology, University of Twente
    No.06-64
    ISSN (Print)1381-3625

    Keywords

    • CAES-EEA: Efficient Embedded Architectures
    • IR-66487
    • EWI-7433
    • METIS-237415

    Cite this

    Wiggers, M. H., Bekooij, M., Bekooij, M. J. G., Jansen, P. G., & Smit, G. J. M. (2006). Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure. (CTIT technical reports series; No. 06-64). Enschede: Centre for Telematics and Information Technology (CTIT).
    Wiggers, M.H. ; Bekooij, Marco ; Bekooij, Marco Jan Gerrit ; Jansen, P.G. ; Smit, Gerardus Johannes Maria. / Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure. Enschede : Centre for Telematics and Information Technology (CTIT), 2006. 10 p. (CTIT technical reports series; 06-64).
    @book{2029f49ccb524d28b7b679b0b55a0ae0,
    title = "Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure",
    abstract = "A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multiprocessor 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 linear computational complexity, that does not require this conversion and that strives to obtain close to minimal buffer capacities. The algorithm is applied to an MP3 playback application that is mapped on our multi-processor system.",
    keywords = "CAES-EEA: Efficient Embedded Architectures, IR-66487, EWI-7433, METIS-237415",
    author = "M.H. Wiggers and Marco Bekooij and Bekooij, {Marco Jan Gerrit} and P.G. Jansen and Smit, {Gerardus Johannes Maria}",
    year = "2006",
    month = "10",
    day = "17",
    language = "Undefined",
    series = "CTIT technical reports series",
    publisher = "Centre for Telematics and Information Technology (CTIT)",
    number = "06-64",
    address = "Netherlands",

    }

    Wiggers, MH, Bekooij, M, Bekooij, MJG, Jansen, PG & Smit, GJM 2006, Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure. CTIT technical reports series, no. 06-64, Centre for Telematics and Information Technology (CTIT), Enschede.

    Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure. / Wiggers, M.H.; Bekooij, Marco; Bekooij, Marco Jan Gerrit; Jansen, P.G.; Smit, Gerardus Johannes Maria.

    Enschede : Centre for Telematics and Information Technology (CTIT), 2006. 10 p. (CTIT technical reports series; No. 06-64).

    Research output: Book/ReportReportProfessional

    TY - BOOK

    T1 - Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure

    AU - Wiggers, M.H.

    AU - Bekooij, Marco

    AU - Bekooij, Marco Jan Gerrit

    AU - Jansen, P.G.

    AU - Smit, Gerardus Johannes Maria

    PY - 2006/10/17

    Y1 - 2006/10/17

    N2 - A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multiprocessor 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 linear computational complexity, that does not require this conversion and that strives to obtain close to minimal buffer capacities. The algorithm is applied to an MP3 playback application that is mapped on our multi-processor system.

    AB - A key step in the design of cyclo-static real-time systems is the determination of buffer capacities. In our multiprocessor 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 linear computational complexity, that does not require this conversion and that strives to obtain close to minimal buffer capacities. The algorithm is applied to an MP3 playback application that is mapped on our multi-processor system.

    KW - CAES-EEA: Efficient Embedded Architectures

    KW - IR-66487

    KW - EWI-7433

    KW - METIS-237415

    M3 - Report

    T3 - CTIT technical reports series

    BT - Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure

    PB - Centre for Telematics and Information Technology (CTIT)

    CY - Enschede

    ER -

    Wiggers MH, Bekooij M, Bekooij MJG, Jansen PG, Smit GJM. Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure. Enschede: Centre for Telematics and Information Technology (CTIT), 2006. 10 p. (CTIT technical reports series; 06-64).