Efficient Computation of Buffer Capacities for Multi-Rate 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

34 Citations (Scopus)
51 Downloads (Pure)

Abstract

A key step in the design of multi-rate real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure as caused by bounded buffers in order to control jitter. This requires the derivation of buffer capacities that both satisfy the temporal constraints as well as constraints on the buffer capacity. Existing exact solutions suffer from the computational complexity associated with the required conversion from a multi-rate 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 determines close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our network based multi-processor system.
Original languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages6
Publication statusPublished - 1 Jul 2006

Publication series

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

Keywords

  • CAES-EEA: Efficient Embedded Architectures
  • EWI-6995
  • IR-66382
  • METIS-237412

Cite this

Wiggers, M. H., Bekooij, M., Bekooij, M. J. G., Jansen, P. G., & Smit, G. J. M. (2006). Efficient Computation of Buffer Capacities for Multi-Rate Real-Time Systems with Back-Pressure. (CTIT technical reports series; No. 06-48). Enschede: Centre for Telematics and Information Technology (CTIT).
Wiggers, M.H. ; Bekooij, Marco ; Bekooij, Marco Jan Gerrit ; Jansen, P.G. ; Smit, Gerardus Johannes Maria. / Efficient Computation of Buffer Capacities for Multi-Rate Real-Time Systems with Back-Pressure. Enschede : Centre for Telematics and Information Technology (CTIT), 2006. 6 p. (CTIT technical reports series; 06-48).
@book{c364b0753cd244e2947c9e9cc37e7939,
title = "Efficient Computation of Buffer Capacities for Multi-Rate Real-Time Systems with Back-Pressure",
abstract = "A key step in the design of multi-rate real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure as caused by bounded buffers in order to control jitter. This requires the derivation of buffer capacities that both satisfy the temporal constraints as well as constraints on the buffer capacity. Existing exact solutions suffer from the computational complexity associated with the required conversion from a multi-rate 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 determines close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our network based multi-processor system.",
keywords = "CAES-EEA: Efficient Embedded Architectures, EWI-6995, IR-66382, METIS-237412",
author = "M.H. Wiggers and Marco Bekooij and Bekooij, {Marco Jan Gerrit} and P.G. Jansen and Smit, {Gerardus Johannes Maria}",
year = "2006",
month = "7",
day = "1",
language = "Undefined",
series = "CTIT technical reports series",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "06-48",
address = "Netherlands",

}

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

Efficient Computation of Buffer Capacities for Multi-Rate 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. 6 p. (CTIT technical reports series; No. 06-48).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Efficient Computation of Buffer Capacities for Multi-Rate 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/7/1

Y1 - 2006/7/1

N2 - A key step in the design of multi-rate real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure as caused by bounded buffers in order to control jitter. This requires the derivation of buffer capacities that both satisfy the temporal constraints as well as constraints on the buffer capacity. Existing exact solutions suffer from the computational complexity associated with the required conversion from a multi-rate 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 determines close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our network based multi-processor system.

AB - A key step in the design of multi-rate real-time systems is the determination of buffer capacities. In our multi-processor system, we apply back-pressure as caused by bounded buffers in order to control jitter. This requires the derivation of buffer capacities that both satisfy the temporal constraints as well as constraints on the buffer capacity. Existing exact solutions suffer from the computational complexity associated with the required conversion from a multi-rate 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 determines close to minimal buffer capacities. The algorithm is applied to an MP3 play-back application that is mapped on our network based multi-processor system.

KW - CAES-EEA: Efficient Embedded Architectures

KW - EWI-6995

KW - IR-66382

KW - METIS-237412

M3 - Report

T3 - CTIT technical reports series

BT - Efficient Computation of Buffer Capacities for Multi-Rate 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. Efficient Computation of Buffer Capacities for Multi-Rate Real-Time Systems with Back-Pressure. Enschede: Centre for Telematics and Information Technology (CTIT), 2006. 6 p. (CTIT technical reports series; 06-48).