Aperiodic multiprocessor scheduling for real-time stream processing applications


Wiggers, Maarten Hendrik (2009) Aperiodic multiprocessor scheduling for real-time stream processing applications. thesis.

open access
Abstract:This thesis presents an algorithm that uses a new dataflow model, variable-
rate phased dataflow, to compute buffer capacities that guarantee satisfaction
of timing and resource constraints for task graphs that have inter-task synchro-
nisation 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 exemplified 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 mod-
elled 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 exe-
cutions 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 algo-
rithm has an attractive computational complexity. Every cyclo-static dataflow
graph that is an intuitive model of a task graph is a variable-rate phased dataflow
graph, i.e. every cyclo-static data
ow 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.
Item Type:Thesis
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/61568
Official URL:http://dx.doi.org/10.3990/1.9789036528504
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page