Research Of Multi-core Processor Scheduling Algorithm Based On Task Clustering And Duplication

With the increase of information content that multi-core processor processingobject contains, the communication between different tasks becomes more and morefrequent, and people also have the higher requirements of the multi-core processorperformance.So that the multi-core processor scheduling faced the huge challenge.As the scheduling strategy based on task clustering and duplication can obtain betterscheduling result in the processor resources limited, large task quantity,andcommunication frequent system, the scheduling algorithm based on task clusteringand duplication as become the research hotspot in recent years.Traditional multi-core processors scheduling algorithms based on task clusteringand duplication have reduced communication overhead and speeded up task executionspeed in a certain extent, but the scheduling length and system utilization rate is notideal enough, and the optimize conditions are too complex.Besides the timecomplexity is too high. In order to improve the shortcomings in the traditionalalgorithm, this article proposes a new scheduling algorithm based on task clusteringand duplication. The new algorithm uses twice task replication clustering strategy toreduce the length scheduling of the tasks set, and to improve system utilization.Specific work is as follows:To counter the low task scheduling length of the LG、PPA algorithms which aretypical algorithms based on task clustering and duplication is too long and the timecomplexity problems is too high. Directed towards the situation, the new schedulingalgorithm by expanding the scope of task duplication, simplify copying conditions toreduce the communication overhead between tasks and the computational load. Thismethod put the duplicate range from the best precursor task extended to all precursortasks that meet the copy conditions, in order to shorten the scheduling length of theentire task set and further reduce the communication between different tasks. Besides,the new algorithm simplified the copy conditions is that the processor idle time isgreater than the execution time of the precursor tasks, in order to achieve the goal ofreducing the time cmplexity.To counter the low system utilization of processor in traditional algorithm, thenew algorithm proposes a task duplicate method that serves the process of mergeringcluste,in order to reduce the number of processors required and improve processorutilization.Under the premise does not affect the earliest start time of the sub-tasks, if precursor tasks which have not been replicated in the replication process of the firstround meet the scecond round of replication conditions,the tasks will be replicatedand to reduce the redundant clusters in the step of mergeing redundant clusters.Thatoperation can make sure the number of the necessary clusters as little as possible.To estimate the effectiveness of the algorithm proposed in this paper, weimplements this algorithm and the competitor algorithm on the PC platform usingMicrosoft Visual C++6.0. Besides, we compared and anlyzed the experimentaldata.Simulation results show that the proposed algorithm’s performance on schedulinglength and the number of the using processors is better than the typical algorithms’.Furthermore, the proposed algorithm has a smaller time complexity and benefits theperformance of the parallel distributed computer system.