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

PDF
1MB 
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 intertask synchro nisation behaviour that is dependent on the processed data stream and that have tasks that are scheduled by runtime 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 runtime 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 runtime schedulers that guarantee tasks a minimum resource budget are mod elled in data ow graphs. Instead of capturing the effects of runtime 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 cyclostatic dataflow graph that is an intuitive model of a task graph is a variablerate phased dataflow graph, i.e. every cyclostatic 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 cyclostatic dataflow graph. The validity of our analysis is confirmed by simulation in both a data ow simulator as well as in a cycleaccurate simulator. 
Item Type:  Thesis 
Faculty:  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 EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page