A Priority-Based Budget Scheduler with Conservative Dataflow Model


Share/Save/Bookmark

Steine, Marcel and Bekooij, Marco and Wiggers, Maarten (2009) A Priority-Based Budget Scheduler with Conservative Dataflow Model. In: 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools, 27-29 Aug. 2009, Patras, Greece.

[img]PDF
Restricted to UT campus only
: Request a copy
36Kb
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.
Item Type:Conference or Workshop Item
Copyright:© 2009 IEEE
Link to this item:http://purl.utwente.nl/publications/69797
Official URL:http://dx.doi.org/10.1109/DSD.2009.148
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page