Loop scheduling to minimize cost with data mining and prefetching for heterogeneous DSP

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 advance at run time. Experiments demonstrate the effectiveness of our algorithm. Our approach can handle loops efficiently. In addition, it is suitable to both soft and hard real-time systems.