Circular Buﬀers with Multiple Overlapping Windows for Cyclic Task Graphs

Bijlsma, Tjerk and Bekooij, Marco J.G. and Smit, Gerard J.M. (2011) Circular Buﬀers with Multiple Overlapping Windows for Cyclic Task Graphs. In: Transactions on High-Performance Embedded Architectures and Compilers III. Lecture Notes in Computer Science, 6590 . Springer Verlag, Berlin. ISBN 9783642194474

PDF
Restricted to UT campus only
203Kb

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 ﬁrst-in-ﬁrst-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 signiﬁcantly simpliﬁes 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.
Item Type:	Book Section
Copyright:	© 2011 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Computer Architecture for Embedded Systems (CAES)
Link to this item:	http://purl.utwente.nl/publications/76021
Official URL:	http://dx.doi.org/10.1007/978-3-642-19447-4
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page