Inter-Task Communication via Overlapping Read and Write Windows for Deadlock-Free Execution of Cyclic Task Graphs

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    4 Citations (Scopus)
    64 Downloads (Pure)

    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.
    Original languageUndefined
    Title of host publicationInternational Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (IC-SAMOS)
    Place of PublicationLos Alamitos
    PublisherIEEE Computer Society Press
    Pages140-148
    Number of pages9
    ISBN (Print)978-1-4244-4501-1
    DOIs
    Publication statusPublished - 20 Jul 2009
    Event2009 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation, IC-SAMOS 2009 - Samos, Greece
    Duration: 20 Jul 200923 Jul 2009

    Publication series

    Name
    PublisherIEEE Computer Society Press
    NumberIEEE catal

    Conference

    Conference2009 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation, IC-SAMOS 2009
    Abbreviated titleIC-SAMOS
    CountryGreece
    CitySamos
    Period20/07/0923/07/09

    Keywords

    • METIS-263997
    • EWI-16005
    • IR-67988

    Cite this

    Bijlsma, T., Bekooij, M. J. G., & Smit, G. J. M. (2009). Inter-Task Communication via Overlapping Read and Write Windows for Deadlock-Free Execution of Cyclic Task Graphs. In International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (IC-SAMOS) (pp. 140-148). Los Alamitos: IEEE Computer Society Press. https://doi.org/10.1109/ICSAMOS.2009.5289225