Research On Static Task Scheduling Algorithm Based On Heterogeneous Multi-core Processors

With the development of semiconductor manufacturing process, the number of transistor that can be integrated into unit area has reaches the limit. The single core processor ran into insurmountable that cannot overcome and multi core processor gradually become the hot and focus of study on processor, which are divided into homogeneous multi-core processor and heterogeneous multi-core processor. Experts and scholars and people in the industry generally believe that the heterogeneous multi-core processors will be the mainstream processor in the future. The sequence of task scheduling will influence the performance of the processor directly, so research on the task scheduling based on heterogeneous multi-core processor has become a research hotspots.Task scheduling on heterogeneous multi-core processor has been proved to be a NP complete problem. There is no algorithm can get its optimal solution in polynomial time now. The existing algorithms are mostly using heuristic algorithm to obtain the approximate solution and the priority list scheduling algorithm which is one of them is widely used. HEFT(Heterogeneous Earlier classic Finish Time) algorithm and HCNF(Heterogeneous Critical Node First) algorithm are two typical priority list scheduling algorithm. HEFT algorithm schedules tasks according to the non-ascending order of ranku and assigns tasks using interval insertion technique. HCNF algorithm schedules the key tasks first and assigns tasks using task replication technique.The two algorithms have some problems, such as the result of task scheduling is not ideal and the idle time of processor is more and so on. Many experts and scholars have put forward the improvement scheme for them. The effects of the constraint dependency between tasks on task scheduling should been synthesis and the idle time of processor should been made full use by using interval insertion technique and task replication technique. This paper takes the advantages of the typical algorithm and comprehensives improvement strategy of experts and scholars to improve algorithm based on the existing algorithm. In order to evaluate the performance of the improved algorithm, this article explains the realization process of the improved algorithm through testing a specific case and contrasts the scheduling result. Then it designs the test scheme, schedules the DAG task graphs which are generates randomly and analyzes and compares the experiment results. Proved by experiment, the improved algorithm can shorten the task scheduling length in a certain extent and increase the performance of processor.