Buffer Capacity Computation for Throughput-Constrained Modal Task Graphs

    Research output: Contribution to journalArticleAcademicpeer-review

    20 Citations (Scopus)
    98 Downloads (Pure)

    Abstract

    Increasingly, stream-processing applications include complex control structures to better adapt to changing conditions in their environment. This adaptivity often results in task execution rates that are dependent on the processed stream. Current approaches to compute buffer capacities that are sufficient to satisfy a throughput constraint have limited applicability in case of data-dependent task execution rates. In this article, we present a dataflow model that allows tasks to have loops with an unbounded number of iterations. For instances of this dataflow model, we present efficient checks on their validity. Furthermore, we present an efficient algorithm to compute buffer capacities that are sufficient to satisfy a throughput constraint. This allows to guarantee satisfaction of a throughput constraint over different modes of a stream processing application, such as the synchronization and synchronized modes of a digital radio receiver.
    Original languageUndefined
    Article number17
    Pages (from-to)17:1-17:59
    Number of pages59
    JournalACM transactions on embedded computing systems
    Volume10
    Issue number2
    DOIs
    Publication statusPublished - Dec 2010

    Keywords

    • data-dependent inter-task synchronisation
    • EWI-19114
    • Data flow
    • IR-75309
    • Multiprocessor
    • METIS-277466

    Cite this

    @article{b630f0d7050848778ced5da803a528b9,
    title = "Buffer Capacity Computation for Throughput-Constrained Modal Task Graphs",
    abstract = "Increasingly, stream-processing applications include complex control structures to better adapt to changing conditions in their environment. This adaptivity often results in task execution rates that are dependent on the processed stream. Current approaches to compute buffer capacities that are sufficient to satisfy a throughput constraint have limited applicability in case of data-dependent task execution rates. In this article, we present a dataflow model that allows tasks to have loops with an unbounded number of iterations. For instances of this dataflow model, we present efficient checks on their validity. Furthermore, we present an efficient algorithm to compute buffer capacities that are sufficient to satisfy a throughput constraint. This allows to guarantee satisfaction of a throughput constraint over different modes of a stream processing application, such as the synchronization and synchronized modes of a digital radio receiver.",
    keywords = "data-dependent inter-task synchronisation, EWI-19114, Data flow, IR-75309, Multiprocessor, METIS-277466",
    author = "M.H. Wiggers and Bekooij, {Marco Jan Gerrit} and Smit, {Gerardus Johannes Maria}",
    note = "10.1145/1880050.1880053",
    year = "2010",
    month = "12",
    doi = "10.1145/1880050.1880053",
    language = "Undefined",
    volume = "10",
    pages = "17:1--17:59",
    journal = "ACM transactions on embedded computing systems",
    issn = "1539-9087",
    publisher = "Association for Computing Machinery (ACM)",
    number = "2",

    }

    Buffer Capacity Computation for Throughput-Constrained Modal Task Graphs. / Wiggers, M.H.; Bekooij, Marco Jan Gerrit; Smit, Gerardus Johannes Maria.

    In: ACM transactions on embedded computing systems, Vol. 10, No. 2, 17, 12.2010, p. 17:1-17:59.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Buffer Capacity Computation for Throughput-Constrained Modal Task Graphs

    AU - Wiggers, M.H.

    AU - Bekooij, Marco Jan Gerrit

    AU - Smit, Gerardus Johannes Maria

    N1 - 10.1145/1880050.1880053

    PY - 2010/12

    Y1 - 2010/12

    N2 - Increasingly, stream-processing applications include complex control structures to better adapt to changing conditions in their environment. This adaptivity often results in task execution rates that are dependent on the processed stream. Current approaches to compute buffer capacities that are sufficient to satisfy a throughput constraint have limited applicability in case of data-dependent task execution rates. In this article, we present a dataflow model that allows tasks to have loops with an unbounded number of iterations. For instances of this dataflow model, we present efficient checks on their validity. Furthermore, we present an efficient algorithm to compute buffer capacities that are sufficient to satisfy a throughput constraint. This allows to guarantee satisfaction of a throughput constraint over different modes of a stream processing application, such as the synchronization and synchronized modes of a digital radio receiver.

    AB - Increasingly, stream-processing applications include complex control structures to better adapt to changing conditions in their environment. This adaptivity often results in task execution rates that are dependent on the processed stream. Current approaches to compute buffer capacities that are sufficient to satisfy a throughput constraint have limited applicability in case of data-dependent task execution rates. In this article, we present a dataflow model that allows tasks to have loops with an unbounded number of iterations. For instances of this dataflow model, we present efficient checks on their validity. Furthermore, we present an efficient algorithm to compute buffer capacities that are sufficient to satisfy a throughput constraint. This allows to guarantee satisfaction of a throughput constraint over different modes of a stream processing application, such as the synchronization and synchronized modes of a digital radio receiver.

    KW - data-dependent inter-task synchronisation

    KW - EWI-19114

    KW - Data flow

    KW - IR-75309

    KW - Multiprocessor

    KW - METIS-277466

    U2 - 10.1145/1880050.1880053

    DO - 10.1145/1880050.1880053

    M3 - Article

    VL - 10

    SP - 17:1-17:59

    JO - ACM transactions on embedded computing systems

    JF - ACM transactions on embedded computing systems

    SN - 1539-9087

    IS - 2

    M1 - 17

    ER -