Research On Task Scheduling For Multicore Processor

Task scheduling for multi-corer parallel system is that, according to some scheduling rules and strategies, all tasks of complicated process are assigned to multi-core parallel system by a certain implementation order, to make the tasks parallel processing. It is strong NP-complete, which is the hardest among the NP-difficult problems. The technology of task scheduling for multi-core has been deeply studied by worldwide researchers for decades, many schedule models and algorithms were proposed for it, however the scheduling efficiency of these algorithms is low and algorithms can not adapt to the changing situation of processor resources. Thus this technique based on multi-core parallel system is not yet a mature field. In this paper, the task scheduling for multi-core parallel system is studied, which considers the execution efficiency of the scheduling and considers the condition that the scheduling result can be changed to adjust the multi-core processor that has uncertain number. So it has important theoretical and practical significance.For the problem that the complete time and complexity of present algorithms is high, a scheduling algorithm based on task duplication is presented. Firstly change the task graph into simple join-structure graph by duplicating tasks. Then use a strategy which makes each join-node task forming scheduling combination, the strategy is that: choose a condition which can make join-node task begin at the earliest time, to merge join-node task into pre-task's task combination to form scheduling combination. This strategy achieve that the beginning of join-node task is in advance and every pre-task can execute in parallel on different cores, and finally the scheduling efficiency is improved.For the problem that when the processing resource is absence the algorithm can not adapt to the changing situation of processor resources and the communication cost between cores is highly frequency, a scheduling algorithm is presented to realize scheduling task based on the specific number of core so that achieve full parallel processing of multi-core. First divide task graph into unrelated run-sequences to eliminate the relationship between tasks. Then allocate each run-sequence to one of cores. If the number of core is less than the number of run-sequence, join two run-sequences by using a strategy to reduce the number of run-sequence. It has realized the full parallel processing of working-core.For the problem that when the processing resource is sufficient the communication cost of present algorithm is high, a advanced algorithm which reduce the communication cost is presented. The method is that the structure of task graph is simplified, and then the tasks are merged one by one. It has reduced the communication cost meanwhile the complete time and complexity of algorithm is low.