M. Qiu (USA), Z. Jia (PRC), C. Xue (USA), Z. Shao (PRC), Y. Liu and E.H.-M. Sha (USA)
Probability, scheduling, data mining, prefetch, heteroge neous
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 un certainties in execution time of some tasks, this paper models each varied execution time as a probabilistic ran dom variable. We proposes a novel algorithm to mini mize 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 rota tion 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 effec tiveness of our algorithm. Our approach can handle loops efficiently. In addition, it is suitable to both soft and hard real-time systems.
Important Links:
Go Back
