Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure

Maarten Wiggers; Marco J.G. Bekooij; Pierre G. Jansen; Gerard J.M. Smit

doi:10.1145/1176254.1176260

Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure

Maarten Wiggers
, Marco J.G. Bekooij
, Pierre G. Jansen
, Gerard J.M. Smit

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

181 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 language	English
Title of host publication	CODES+ISSS '06
Subtitle of host publication	Proceedings of the 4th International Conference on Hardware/Software Codesign an System Synthesis
Place of Publication	New York, NY
Publisher	Association for Computing Machinery
Pages	10-15
Number of pages	6
ISBN (Print)	1-59593-370-0
DOIs	https://doi.org/10.1145/1176254.1176260
Publication status	Published - Oct 2006
Event	4th International Conference on Hardware/Software Codesign an System Synthesis, CODES+ISSS 2006 - Seoul, Korea, Republic of Duration: 22 Oct 2006 → 25 Oct 2006 Conference number: 4

Conference

Conference	4th International Conference on Hardware/Software Codesign an System Synthesis, CODES+ISSS 2006
Abbreviated title	CODES+ISSS
Country/Territory	Korea, Republic of
City	Seoul
Period	22/10/06 → 25/10/06

Keywords

2020 OA procedure
CAES-EEA: Efficient Embedded Architectures

Access to Document

10.1145/1176254.1176260

ArticleFinal published version, 192 KBLicence: Taverne

2 Report
1 Conference contribution

Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure
Wiggers, M. H., Bekooij, M. J. G., Jansen, P. G. & Smit, G. J. M., Apr 2007, 13th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'07). Los Alamitos, CA, USA: IEEE, p. 281-292 12 p. (Proceedings IEEE Real Time and Embedded Technology and Applications Symposium (RTAS); vol. 2007, no. 13).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
31 Link opens in a new tab Citations (Scopus)

267 Downloads (Pure)
Efcient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure
Wiggers, M. H., Bekooij, M., Bekooij, M. J. G., Jansen, P. G. & Smit, G. J. M., 17 Oct 2006, Enschede: Centre for Telematics and Information Technology (CTIT). 10 p. (CTIT technical reports series; no. 06-64)
Research output: Book/Report › Report › Professional

File
Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure
Wiggers, M. H., Bekooij, M. J. G., Jansen, P. G. & Smit, G. J. M., 1 Jul 2006, Enschede: Centre for Telematics and Information Technology (CTIT). 6 p. (CTIT technical reports series; no. 06-48)
Research output: Book/Report › Report › Professional

Open Access
File

Cite this

Wiggers, 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. In CODES+ISSS '06: Proceedings of the 4th International Conference on Hardware/Software Codesign an System Synthesis (pp. 10-15). Association for Computing Machinery. https://doi.org/10.1145/1176254.1176260

@inproceedings{a52a655708804201a9e4b72b0c1af74a,

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 = "2020 OA procedure, CAES-EEA: Efficient Embedded Architectures",

author = "Maarten Wiggers and Bekooij, \{Marco J.G.\} and Jansen, \{Pierre G.\} and Smit, \{Gerard J.M.\}",

year = "2006",

month = oct,

doi = "10.1145/1176254.1176260",

language = "English",

isbn = "1-59593-370-0",

pages = "10--15",

booktitle = "CODES+ISSS '06",

publisher = "Association for Computing Machinery",

address = "United States",

note = "4th International Conference on Hardware/Software Codesign an System Synthesis, CODES+ISSS 2006, CODES+ISSS ; Conference date: 22-10-2006 Through 25-10-2006",

}

Wiggers, M, Bekooij, MJG, Jansen, PG & Smit, GJM 2006, Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure. in CODES+ISSS '06: Proceedings of the 4th International Conference on Hardware/Software Codesign an System Synthesis. Association for Computing Machinery, New York, NY, pp. 10-15, 4th International Conference on Hardware/Software Codesign an System Synthesis, CODES+ISSS 2006, Seoul, Korea, Republic of, 22/10/06. https://doi.org/10.1145/1176254.1176260

Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure. / Wiggers, Maarten; Bekooij, Marco J.G.; Jansen, Pierre G. et al.
CODES+ISSS '06: Proceedings of the 4th International Conference on Hardware/Software Codesign an System Synthesis. New York, NY: Association for Computing Machinery, 2006. p. 10-15.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure

AU - Wiggers, Maarten

AU - Bekooij, Marco J.G.

AU - Jansen, Pierre G.

AU - Smit, Gerard J.M.

N1 - Conference code: 4

PY - 2006/10

Y1 - 2006/10

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 - 2020 OA procedure

KW - CAES-EEA: Efficient Embedded Architectures

U2 - 10.1145/1176254.1176260

DO - 10.1145/1176254.1176260

M3 - Conference contribution

SN - 1-59593-370-0

SP - 10

EP - 15

BT - CODES+ISSS '06

PB - Association for Computing Machinery

CY - New York, NY

T2 - 4th International Conference on Hardware/Software Codesign an System Synthesis, CODES+ISSS 2006

Y2 - 22 October 2006 through 25 October 2006

ER -

Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure

Abstract

Conference

Keywords

Access to Document

Fingerprint

Research output