An Algorithm Research For Tasks Scheduling Of Parallel System On Multi-core Processor

With the popularity of the multi-core processor, multi-core technique is more and more . Although the existence of multi-core processor brings up much good, it also brings up more problems, one of them is the task scheduling technique.So far there is no clear standards and regulations of task scheduling based on multi-core system, since some researches have been made for task scheduling technique. This technique based on multi-core parallel system is not yet a mature field and needs more researches and explorations.This paper makes a deep research on task scheduling based on multi-core parallel system and makes a task scheduling model on this system. Then, the paper makes the task scheduling algorithm specified in multi-core parallel system based on this model.According to features of parallel system based on multi-core processor, the algorithm adds task allocation strategy and task duplication before task scheduling, and then makes more optimization to the algorithm. The algorithm consisits of three sections: task allocation, task duplication and task scheduling. Task allocation is an Heuristic Algorithm based on iteration to allocate threads belong to one process to the processor in the operation of task allocation. Task duplication keeps processors independent to each other and copies communication threads belong to different processors to one processor to execute. After above-mentioned operations, processors are independent to each other. The paper independently takes task scheduling to each processor with Genetic Algorithm.The paper tests the algorithm with Random Graph and multi-core platform simulated by Simics. In the Random Graph test, the paper tests the algorithm from task scales, CCRs and branches and verifies the algorithm validation and scheduling performances. Then, the paper makes the deeper test on multi-core platform simulated by Simics and confirms the effectivity of the algorithm under the real circumstance..The result of the experiment proves the algorithm shortens the scheduling time and has a obvious priority compared to traditional Genetic Algorithm.