Buffer Capacity Computation for Throughput-Constrained Modal Task Graphs

    Research output: Contribution to journalArticleAcademicpeer-review

    20 Citations (Scopus)
    132 Downloads (Pure)


    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
    Issue number2
    Publication statusPublished - Dec 2010


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

    Cite this