Research On Task Duplication Based Multi-core Scheduling Algorithm

With the development of integrated circuit technology,the fabrication of semiconductor is gradually approaching its limit.Single-core processors has entered a bottleneck,and multi-core processors have emerged at the historic moment and received extensive attention.Task scheduling algorithm is one of the key factors for whether their parallel computing capabilities are fully utilized for multi-core processors.Based on the extensive study of the existing static task scheduling algorithms for multicore processors,the task scheduling algorithm based on replication is taken as the research object.In order to improve the poor scheduling result caused by the large deviation between the estimated path and the actual one and solve the problem of insufficient solution space search,a task-duplication scheduling algorithm with resource constraints for heterogeneous multi-core processors(TDSA-RC)and a task duplication scheduling algorithm based on genetic iteration for homogeneous multi-core processors(TDSA-GI)are proposed respectively.Among these two algorithms,the TDSA-RC makes the parameter calculation more accurate by supplementing resource constraints in the parameter calculation process.The algorithm also improves the layout optimization method to expand the search range of the algorithm solution space,and filters and deletes redundant tasks to reduce unnecessary calculations introduced in task duplication phase.The TDSA-GI improves the performance of the scheduling algorithm by combining task duplication with genetic iteration which possess excellent solution space search capabilities.At the same time,as for TDSA-GI,this paper proposes a hierarchical-based macro block division to solve the possible problems of duplication node failure in iterative-duplication algorithms.To verify the performance of TDSA-RC and TDSA-GI,the makespan of the final layout are selected as the criterion for judging the performance of the algorithm,and tests the performance of the TDSA-RC and the TDSA-GI through scheduling comparison experiments between randomly generated task graphs and three practical task graphs.The result of the comparison experiment shows that,comparing with the existing algorithms,both TDSA-RC and TDSA-GI could effectively improve the parallelism and shorten the scheduling length of parallel tasks.