Abstract
This thesis presents an algorithm that uses a new dataflow model, variable-rate phased data ow, to compute buffer capacities that guarantee satisfaction of timing and resource constraints for task graphs that have inter-task synchronisation behaviour that is dependent on the processed data stream and that have tasks that are scheduled by run-time schedulers that guarantee resource budgets. This is an important extension of data ow analysis techniques, which allows to model a larger class of applications and allows to include the effects of a larger class of run-time schedulers. This is exemplied by the case study with an MP3 playback application, for which we are not aware of alternative
approaches to compute buffer capacities that are sufficient to satisfy the timing constraints. Furthermore, we improved the accuracy with which the effects of run-time schedulers that guarantee tasks a minimum resource budget are modelled in data ow graphs. Instead of capturing the effects of run-time scheduling using response times, we capture these effects with a model that has a latency and a rate parameter. Response times do not capture that multiple task executions can occur subsequently in the same allocated budget. This is captured with the model with a latency and a rate parameter, which results in improved accuracy of the derived bounds on the temporal behaviour. Further, our algorithm has an attractive computational complexity. Every cyclo-static dataflow graph that is an intuitive model of a task graph is a variable-rate phased data
ow graph, i.e. every cyclo-static dataflow graph in which no actor has any auto-concurrency. The algorithm that computes buffer capacities has a polynomial complexity in the size of the cyclo-static dataflow graph. The validity of our analysis is confirmed by simulation in both a data ow simulator as well as in a cycle-accurate simulator.
approaches to compute buffer capacities that are sufficient to satisfy the timing constraints. Furthermore, we improved the accuracy with which the effects of run-time schedulers that guarantee tasks a minimum resource budget are modelled in data ow graphs. Instead of capturing the effects of run-time scheduling using response times, we capture these effects with a model that has a latency and a rate parameter. Response times do not capture that multiple task executions can occur subsequently in the same allocated budget. This is captured with the model with a latency and a rate parameter, which results in improved accuracy of the derived bounds on the temporal behaviour. Further, our algorithm has an attractive computational complexity. Every cyclo-static dataflow graph that is an intuitive model of a task graph is a variable-rate phased data
ow graph, i.e. every cyclo-static dataflow graph in which no actor has any auto-concurrency. The algorithm that computes buffer capacities has a polynomial complexity in the size of the cyclo-static dataflow graph. The validity of our analysis is confirmed by simulation in both a data ow simulator as well as in a cycle-accurate simulator.
Original language | English |
---|---|
Qualification | Doctor of Philosophy |
Supervisors/Advisors |
|
Thesis sponsors | |
Award date | 19 Jun 2009 |
Place of Publication | Enschede |
Publisher | |
Print ISBNs | 978-90-365-2850-4 |
DOIs | |
Publication status | Published - 19 Jun 2009 |
Keywords
- METIS-263950
- EWI-15801
- data flow analysis
- IR-61568