Research On Static Task Scheduling Algorithm Based On Heterogeneous CMP

With the emergence of CMP, how to improve their operational efficiency and maximize program parallelism gets much attention of foreign experts and scholars. System performance improved is not only relevant with hardware platform, but also inseparable from the optimization software design on hardware platform, only both of them fully integrated, to give full play the excellent performance of the own hardware platform and software design.Therefore, the task scheduling problem on CMP platform has become one of the hot issues of high-performance, high parallelism CMP area for research. In view of the excellent performance of CMP platform and future trend, this paper makes static task scheduling algorithm on heterogeneous CMP as a research subject, by designing a static task scheduling algorithm with excellent performance suitable for hardware platform, which can shorten the time to complete all the tasks execution, give full play to the advantages of performance of the heterogeneous CMP and to improve the efficiency of CMP.In this paper, by the analysis of CMP architecture, task scheduling technique and the existing four classic and static task scheduling algorithms on heterogeneous CMP, for the shortage of the existing static scheduling algorithm on CMP, and then proposes a global comparatively optimum task scheduling algorithm. Firstly, the new algorithm merges some special tasks of the task graph for optimization; and then constructs a list of task scheduling,this phase consists of hierarchical of task graph, marking critical task node and computing task priority weight of three sequential execution processes; Finally, in the task allocation while adding redundant tasks processed, and two processes executed alternately until completing all tasks scheduled. The new algorithm ensures drill scheduled task, considering giving critical tasks higher priority, shorten the total completion time of the entire task graph.In the task assignment phase, using interval insertion and task duplication technique, by inserting and duplication in the idle time slot necessarily, by copying the critical parent of the current task in advance of the earliest finish time of the current task, while the redundant tasks were detected, deleted, and made full use of the processor resources, ahead of completion time of the subsequent tasks, and then can promptly remove redundant tasks in scheduling result, avoid wasting processor resourses, while reducing the implementation of execution time of all tasks, and ultimately enhance the performance of the entire CMP.In order to verify the feasibility and efficiency of the global comparatively optimum task scheduling algorithm,experiment in this paper randomly generates a number of task graphs with different characteristics by using TGFF, in the condition of the different hardware to test the algorithm, to verify the scheduling performance of the new algorithm in Matlab platform.Experimental results show that the new algorithm inherits the advantage of scheduling critical tasks preferentially in the existing algorithms, meanwhile, the problem that partial comparatively optimum scheduling result produced arising from the singleness of the existing algorithms task priority selection is improved, and can deal with the redundancy brought by task duplication effectively. During the execution of the entire tasks, parallelism between tasks is significantly improved, the total scheduling length of the tasks is also significantly reduced, and achieves the desired effect of the improved algorithm, and the algorithm achieves global comparatively optimum scheduling performance, which provides a certain reference value for the study of task scheduling problems on the heterogeneous CMP.