Circular Buffers with Multiple Overlapping Windows for Cyclic Task Graphs

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

Abstract

Multimedia applications process streams of values and can often be represented as task graphs. For performance reasons, these task graphs are executed on multiprocessor systems. Inter-task communication is performed via buffers, where the order in which values are written into a buffer can differ from the order in which they are read. Some existing approaches perform inter-task communication via first-in-first-out buffers in combination with reordering tasks and require applications with affne index-expressions. In our previous work, we used circular buffers with a non-overlapping read and write window, such that a reordering task is not required. However, these windows can cause deadlock for cyclic task graphs. In this paper, we introduce circular buffers with multiple overlapping windows that do not delay the release of locations and therefore they do not introduce deadlock for cyclic task graphs. We show that buffers with multiple overlapping read and write windows are attractive, because they avoid that a buffer has to be selected from which a value has to be read or into which a value has to be written. This significantly simplifies the extraction of a task graph from a sequential application. These buffers are also attractive, because a buffer capacity equal to the array size is sufficient for deadlock-free execution, instead of performing global analysis to compute sufficient buffer capacities. Our case-study presents two applications that require these buffers.
Original languageUndefined
Title of host publicationTransactions on High-Performance Embedded Architectures and Compilers III
EditorsP. Stenström
Place of PublicationBerlin
PublisherSpringer
Number of pages18
ISBN (Print)9783642194474
DOIs
Publication statusPublished - 12 Mar 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume6590
ISSN (Print)1864-306X

Keywords

  • IR-76021

Cite this

Bijlsma, T., Bekooij, M. J. G., & Smit, G. J. M. (2011). Circular Buffers with Multiple Overlapping Windows for Cyclic Task Graphs. In P. Stenström (Ed.), Transactions on High-Performance Embedded Architectures and Compilers III (Lecture Notes in Computer Science; Vol. 6590). Berlin: Springer. https://doi.org/10.1007/978-3-642-19447-4
Bijlsma, T. ; Bekooij, Marco Jan Gerrit ; Smit, Gerardus Johannes Maria. / Circular Buffers with Multiple Overlapping Windows for Cyclic Task Graphs. Transactions on High-Performance Embedded Architectures and Compilers III. editor / P. Stenström. Berlin : Springer, 2011. (Lecture Notes in Computer Science).
@inbook{fadf3b86decd436690f08e90da0d6c38,
title = "Circular Buffers with Multiple Overlapping Windows for Cyclic Task Graphs",
abstract = "Multimedia applications process streams of values and can often be represented as task graphs. For performance reasons, these task graphs are executed on multiprocessor systems. Inter-task communication is performed via buffers, where the order in which values are written into a buffer can differ from the order in which they are read. Some existing approaches perform inter-task communication via first-in-first-out buffers in combination with reordering tasks and require applications with affne index-expressions. In our previous work, we used circular buffers with a non-overlapping read and write window, such that a reordering task is not required. However, these windows can cause deadlock for cyclic task graphs. In this paper, we introduce circular buffers with multiple overlapping windows that do not delay the release of locations and therefore they do not introduce deadlock for cyclic task graphs. We show that buffers with multiple overlapping read and write windows are attractive, because they avoid that a buffer has to be selected from which a value has to be read or into which a value has to be written. This significantly simplifies the extraction of a task graph from a sequential application. These buffers are also attractive, because a buffer capacity equal to the array size is sufficient for deadlock-free execution, instead of performing global analysis to compute sufficient buffer capacities. Our case-study presents two applications that require these buffers.",
keywords = "IR-76021",
author = "T. Bijlsma and Bekooij, {Marco Jan Gerrit} and Smit, {Gerardus Johannes Maria}",
year = "2011",
month = "3",
day = "12",
doi = "10.1007/978-3-642-19447-4",
language = "Undefined",
isbn = "9783642194474",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
editor = "P. Stenstr{\"o}m",
booktitle = "Transactions on High-Performance Embedded Architectures and Compilers III",

}

Bijlsma, T, Bekooij, MJG & Smit, GJM 2011, Circular Buffers with Multiple Overlapping Windows for Cyclic Task Graphs. in P Stenström (ed.), Transactions on High-Performance Embedded Architectures and Compilers III. Lecture Notes in Computer Science, vol. 6590, Springer, Berlin. https://doi.org/10.1007/978-3-642-19447-4

Circular Buffers with Multiple Overlapping Windows for Cyclic Task Graphs. / Bijlsma, T.; Bekooij, Marco Jan Gerrit; Smit, Gerardus Johannes Maria.

Transactions on High-Performance Embedded Architectures and Compilers III. ed. / P. Stenström. Berlin : Springer, 2011. (Lecture Notes in Computer Science; Vol. 6590).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

TY - CHAP

T1 - Circular Buffers with Multiple Overlapping Windows for Cyclic Task Graphs

AU - Bijlsma, T.

AU - Bekooij, Marco Jan Gerrit

AU - Smit, Gerardus Johannes Maria

PY - 2011/3/12

Y1 - 2011/3/12

N2 - Multimedia applications process streams of values and can often be represented as task graphs. For performance reasons, these task graphs are executed on multiprocessor systems. Inter-task communication is performed via buffers, where the order in which values are written into a buffer can differ from the order in which they are read. Some existing approaches perform inter-task communication via first-in-first-out buffers in combination with reordering tasks and require applications with affne index-expressions. In our previous work, we used circular buffers with a non-overlapping read and write window, such that a reordering task is not required. However, these windows can cause deadlock for cyclic task graphs. In this paper, we introduce circular buffers with multiple overlapping windows that do not delay the release of locations and therefore they do not introduce deadlock for cyclic task graphs. We show that buffers with multiple overlapping read and write windows are attractive, because they avoid that a buffer has to be selected from which a value has to be read or into which a value has to be written. This significantly simplifies the extraction of a task graph from a sequential application. These buffers are also attractive, because a buffer capacity equal to the array size is sufficient for deadlock-free execution, instead of performing global analysis to compute sufficient buffer capacities. Our case-study presents two applications that require these buffers.

AB - Multimedia applications process streams of values and can often be represented as task graphs. For performance reasons, these task graphs are executed on multiprocessor systems. Inter-task communication is performed via buffers, where the order in which values are written into a buffer can differ from the order in which they are read. Some existing approaches perform inter-task communication via first-in-first-out buffers in combination with reordering tasks and require applications with affne index-expressions. In our previous work, we used circular buffers with a non-overlapping read and write window, such that a reordering task is not required. However, these windows can cause deadlock for cyclic task graphs. In this paper, we introduce circular buffers with multiple overlapping windows that do not delay the release of locations and therefore they do not introduce deadlock for cyclic task graphs. We show that buffers with multiple overlapping read and write windows are attractive, because they avoid that a buffer has to be selected from which a value has to be read or into which a value has to be written. This significantly simplifies the extraction of a task graph from a sequential application. These buffers are also attractive, because a buffer capacity equal to the array size is sufficient for deadlock-free execution, instead of performing global analysis to compute sufficient buffer capacities. Our case-study presents two applications that require these buffers.

KW - IR-76021

U2 - 10.1007/978-3-642-19447-4

DO - 10.1007/978-3-642-19447-4

M3 - Chapter

SN - 9783642194474

T3 - Lecture Notes in Computer Science

BT - Transactions on High-Performance Embedded Architectures and Compilers III

A2 - Stenström, P.

PB - Springer

CY - Berlin

ER -

Bijlsma T, Bekooij MJG, Smit GJM. Circular Buffers with Multiple Overlapping Windows for Cyclic Task Graphs. In Stenström P, editor, Transactions on High-Performance Embedded Architectures and Compilers III. Berlin: Springer. 2011. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-19447-4