Research On An Improved Real-time Task Scheduling Algorithm For Heterogeneous Multiprocessors

With the development of science, and it put forward demands and challenges to computer for better, faster and stronger of the processing power. Multi-processor technology is a breakthrough in this challenge, and the task scheduling technology is one of the most important technologies of this breakthrough. With the further development of technology, the development of multi-processor toward the direction of heterogeneous multi-processor, which each processor will process the same task with different speed, and as a result this heterogeneity rendering the task scheduling issues become more complex.In the research of scheduling algorithm, the most commonly used models for task scheduling is DAG (directed acyclic graph). Task scheduling problem has been proved to be an NP complete problem, Most existing heterogeneous multi-processor real-time task scheduling algorithm work as follow:firstly, it classify tasks into clusters and assign these clusters to different processors, and then it schedule the tasks .As both Real-Time Scalable Duplication based Algorithm and Heterogeneous Earliest Finish Time Algorithm take tasks' execute time, processors' idle state and tasks' precedence relationship into account, so the time complexity of the algorithms is high.To solve the problem this paper propose a new scheduling algorithm HRTSA (Heterogeneous Real-time Task Scheduling Algorithm) for multiprocessors, In this algorithm we firstly we use Minimum Execute Time for Clustering based on precursor constraint in the classifying clusters stage in order to lower the time complexity, and in order to make a good guarantee of task, HRTSA make improvement in placing and scheduling stages. Main tasks of this paper are as follow:Because of the fact of real-time tasks in heterogeneous multi-processor have different processors execution time, we assigned the nodes, which on the same processor have minimum execution time, to the same processor according to the relationship of the task. That is Minimum Execute Time for Clustering based on precursor constraint strategy. This strategy only considers the execution time of node and relations with the former trend, which can effectively reduce time complexity of the clustering algorithm.When there is some processor, which are excellent compared to the others, Minimum Execute Time for Clustering based on precursor constraint will assign lots of nodes to this excellent one. It will bring a problem that the excellent processor will be overload and others will be free. So when putting the clusters to the processors we apply Processors Load Balanced Algorithm strategy. To solve this problem this method of placement keep the processor load balancing while improving the tasks' processing effectively.In order to reduce the communication delay of and task take full advantage of processor, we use three copy strategies to improve the efficiency of task execution.. Remove redundancy strategy is used in our algorithm to promote processor's utilization, which removes the unnecessary redundancy of nodes of the processor. This strategy can improve the efficiency of each processor.To estimate the effectiveness of the algorithm proposed in this paper, we implements this algorithm and the competitor algorithm on the PC platform using Visual C++6.0.The experiment results shows that HRTSA algorithm, which uses strategy of Minimum Execute Time for Clustering based on precursor constraint effectively reduces the algorithm's time complexity, through using multiple scheduling strategy, our algorithm has lower time complexity, higher scheduling success rate, and higher speedup.