Inter-Task Communication via Overlapping Read and Write Windows for Deadlock-Free Execution of Cyclic Task Graphs
Bijlsma, Tjerk and Bekooij, Marco J.G. and Smit, Gerard J.M. (2009) Inter-Task Communication via Overlapping Read and Write Windows for Deadlock-Free Execution of Cyclic Task Graphs. In: 9th International Conference on Systems, Architectures, Modeling and Simulation, SAMOS 2009, 20-23 July 2009, Samos, Greece.
|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 with first-in-first-out buffers and reordering tasks and require applications with affine index expressions. Other approaches communicate containers, in which values can be accessed in any order, such that a reordering task is not required. However, these containers delay the release of locations, which can cause deadlock in cyclic task graphs.
In this paper, we introduce circular buffers with overlapping windows for deadlock-free execution of cyclic task graphs that may contain non-affine index expressions. Inside the windows, values can be written or read in an arbitrary order, such that a reordering task is not required. Deadlock is avoided by releasing a written location directly from the write window. The approach is demonstrated for the cyclic task graph of an orthogonal frequency-division multiplexing (OFDM) receiver application, containing non-affine index expressions.
|Item Type:||Conference or Workshop Item|
|Copyright:||© 2009 ACM|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/67988|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 263997