A Priority-Based Budget Scheduler with Conservative Dataflow Model

Marcel Steine, Marco Jan Gerrit Bekooij, M.H. Wiggers

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

    17 Citations (Scopus)

    Abstract

    Currently, the guaranteed throughput of a stream processing application, mapped on a multi-processor system, can be computed with a conservative dataflow model, if only time division multiplex (TDM) schedulers are applied. A TDM scheduler is a budget scheduler. Budget schedulers can be characterized by two parameters: budget and replenishment interval. This paper introduces a priority-based budget scheduler (PBS), which is a budget scheduler that additionally associates a priority with every task. PBS improves the guaranteed minimum throughput of a stream processing application compared to TDM, given the same amount of resources. We construct a conservative dataflow model for a task scheduled by PBS. This dataflow model generalizes previous work, because it is valid for a sequence of execution times instead of one execution time per task which results in an improved accuracy of the model. Given this dataflow model, we can compute the guaranteed minimum throughput of the task graph that implements the stream processing application. Experiments confirm that a significantly higher guaranteed minimum throughput of the task graph can be obtained with PBS instead of TDM schedulers and that a conservative bound on the guaranteed throughput of the task graph can be computed with a dataflow model. Furthermore, our bound on the guaranteed throughput of the task graph is accurate, if the buffer capacities in the task graph do not affect the guaranteed throughput.
    Original languageUndefined
    Title of host publication12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools
    Place of PublicationLos Alamitos
    PublisherIEEE Computer Society
    Pages37-44
    Number of pages6
    ISBN (Print)978-0-7695-3782-5
    DOIs
    Publication statusPublished - 2009
    Event12th EUROMICRO Conference on Digital System Design, DSD 2009: Architectures, Methods and Tools - Conference and Cultural Centre of the University of Patras, Patras, Greece
    Duration: 27 Aug 200929 Aug 2009
    Conference number: 12
    http://www.iuma.ulpgc.es/dsd09/

    Publication series

    Name
    PublisherIEEE Computer Society Press

    Conference

    Conference12th EUROMICRO Conference on Digital System Design, DSD 2009
    Abbreviated titleDSD
    CountryGreece
    CityPatras
    Period27/08/0929/08/09
    Internet address

    Keywords

    • IR-69797
    • EWI-17350
    • Data flow computing - multiprocessing systems - processor scheduling - task analysis - time division multiplexing
    • METIS-264515

    Cite this