Inter-task communication via overlapping read and write windows for deadlock-free execution of cyclic task graphs
- 1 July 2009
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2009 International Symposium on Systems, Architectures, Modeling, and Simulation
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.Keywords
This publication has 11 references indexed in Scilit:
- SoC-CPublished by Association for Computing Machinery (ACM) ,2008
- Exploiting Thread-Level Parallelism in Lockstep Execution by Partially Duplicating a Single PipelineETRI Journal, 2008
- Efficient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure13th IEEE Real Time and Embedded Technology and Applications Symposium (RTAS'07), 2007
- Mapping Multi-Dimensional Signals into Hierarchical Memory OrganizationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- pn: A Tool for Improved Derivation of Process NetworksEURASIP Journal on Embedded Systems, 2007
- An Integer Linear Programming Approach to Classify the Communication in Process NetworksLecture Notes in Computer Science, 2004
- The MIT Alewife machine: architecture and performancePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Memory size reduction through storage order optimization for embedded parallel multimedia applicationsParallel Computing, 1997
- Cycle-static dataflowIEEE Transactions on Signal Processing, 1996
- The Tera computer systemPublished by Association for Computing Machinery (ACM) ,1990