Run-time Prediction of Execution Times of Stream-oriented Applications in Multiprocessors On-chip

For stream-oriented applications, it is a challenging problem to predict the total execution time of a loop consisting of multiple tasks with data-dependent task execution delays executed in a pipeline-like manner on a multiprocessor system on-chip. Embedded applications can profit from such prediction at run-time, e.g. for power and quality-of-service management. For this purpose, we propose a generic loop execution time estimate giving a tight upper bound and taking parallelism into account. Our estimate is an algebraic expression of a few a priori parameters describing the frequency and the value of changes of the task execution delays. Our method is based on a timing analysis of the loop. To illustrate how our method can be applied in practice, we use an MPEG-4 algorithm for decoding video object shape as a case study.

(pdf version of the complete report)

Back to the list of technical reports.