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 language | Undefined |
---|---|
Title of host publication | 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools |
Place of Publication | Los Alamitos |
Publisher | IEEE |
Pages | 37-44 |
Number of pages | 6 |
ISBN (Print) | 978-0-7695-3782-5 |
DOIs | |
Publication status | Published - 2009 |
Event | 12th 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 2009 → 29 Aug 2009 Conference number: 12 http://www.iuma.ulpgc.es/dsd09/ |
Publication series
Name | |
---|---|
Publisher | IEEE Computer Society Press |
Conference
Conference | 12th EUROMICRO Conference on Digital System Design, DSD 2009 |
---|---|
Abbreviated title | DSD |
Country/Territory | Greece |
City | Patras |
Period | 27/08/09 → 29/08/09 |
Internet address |
Keywords
- IR-69797
- EWI-17350
- Data flow computing - multiprocessing systems - processor scheduling - task analysis - time division multiplexing
- METIS-264515