Loop scheduling to minimize cost with data mining and prefetching for heterogeneous DSP
Meikang Qiu, Zhiping Jia, Chun Xuc, Zili Shao, Ying Liu, Edwin H.‐M. Sha · 2006
In real-time embedded systems, such as multimedia and video applications, cost and time are the most important issues and loop is the most critical part. Due to the uncertainties in execution time of some tasks, this paper models each varied execution time as a probabilistic random variable. We proposes a novel algorithm to minimize the total cost while satisfying the timing constraint with a guaranteed confidence probability. First, we use data mining to predict the distribution of execution time and find the association rules between execution time and different inputs from history table. Then we use rotation scheduling to obtain the best assignment for total cost minimization, which is called the HAP problem in this paper. Finally, we use prefetching to prepare data in