RMOT: Recursion in model order for task execution time estimation in a software pipeline

This paper addresses the problem of execution time estimation for tasks in a software pipeline independent of the application structure or the underlying architecture. A regression model is developed to obtain the estimates from previously observed data. To improve the quality of the estimates execution times of predecessor task in a software pipeline is exploited. Since the Model order (number of past observations required to obtain optimal estimate) cannot be determined at design time and to circumvent this, we propose means to dynamically update the order and hence obtain a critical-fit model without resorting to analytical benchmarking or calibration runs. The estimation scheme comprises of two estimation methods, namely `Wiener-Hopf´ and Order-recursive estimation. The selection of the estimation method is automatic and depends on the required quality of the estimate against a user selectable threshold. In order recursion, new model order is obtained in conjunction to estimates, so order recursion solve the system both for order and estimate simultaneously. We experimented on two multicore platforms using H.264 decoder, a control dominant, computationally demanding application. Results show that estimates obtained by our method are up to 39% better in case of the first task in the software pipeline. The estimate quality improves significantly for the task with predecessor(s) in pipeline and comparison shows up to 54% improvement in estimation results.