Simultaneous Budget and Buffer Size Computation for Throughput-Constrained Task Graphs

M.H. Wiggers, Marco Jan Gerrit Bekooij, Marc C.W. Geilen, Twan Basten

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

    8 Citations (Scopus)
    132 Downloads (Pure)


    Modern embedded multimedia systems process multiple concurrent streams of data processing jobs. Streams often have throughput requirements. These jobs are implemented on a multiprocessor system as a task graph. Tasks communicate data over buffers, where tasks wait on sufficient space in output buffers before producing their data. For cost reasons, jobs share resources. Because jobs can share resources with other jobs that include tasks with data-dependent execution rates, we assume run-time scheduling on shared resources. Budget schedulers are applied, because they guarantee a minimum budget in a maximum replenishment interval. Both the buffer sizes as well as the budgets influence the temporal behaviour of a job. Interestingly, a trade-off exists: a larger buffer size can allow for a smaller budget while still meeting the throughput requirement. This work is the first to address the simultaneous computation of budget and buffer sizes. We solve this non-linear problem by formulating it as a second-order cone program. We present tight approximations to obtain a non-integral second-order cone program that has polynomial complexity. Our experiments confirm the non-linear trade-off between budget and buffer sizes.
    Original languageUndefined
    Title of host publicationProceedings of the Conference on Design, Automation and Test in Europe (DATE 2010)
    PublisherEuropean Design and Automation Association
    Number of pages4
    ISBN (Print)978-3-9810801-6-2
    Publication statusPublished - Mar 2010
    Event2010 Design, Automation & Test in Europe Conference & Exhibition, DATE 2010 - Dresden, Germany
    Duration: 8 Mar 201012 Mar 2010

    Publication series

    PublisherEuropean Design and Automation Association


    Conference2010 Design, Automation & Test in Europe Conference & Exhibition, DATE 2010
    Abbreviated titleDATE


    • METIS-270766
    • EWI-17698
    • IR-70468

    Cite this