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

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/Report › Report › Professional

49 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 language	Undefined
Place of Publication	Enschede
Publisher	Centre for Telematics and Information Technology (CTIT)
Number of pages	10
Publication status	Published - 17 Oct 2006

Publication series

Name	CTIT technical reports series
Publisher	Centre 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

Access to Document

Cite this

@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 = oct,

day = "17",

language = "Undefined",

series = "CTIT technical reports series",

publisher = "Centre for Telematics and Information Technology (CTIT)",

number = "06-64",

address = "Netherlands",

}

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 -