Research Of Task Scheduling Algorithm Based On Critical Path For Multi-core

The main purpose of the research of multi-core task scheduling algorithm ishow to shorten the total task execution time. This problem has already beenproved to be entirely problem NP. According to this problem scholars have beenstudied and proposed scheduling many algorithms. However, these algorithmscan still be improved. In this paper, a task scheduling algorithm based on criticalpath for multi-core was proposed, which can improve the utilization rate of coresand reduce the execution time of task. So the researches of this problem haveboth theoretic value and practical value.For the problem that current scheduling algorithm did not consider that thenodes on the critical path have a major impact on the ending time of tasks, led totask completion time delayed; a scheduling algorithm based on critical path andtask duplication (CPTD) was proposed. Firstly duplicated fork-nodes to changethe task graph into products processing tree, then found the critical path in theprocessing tree, and made the father nodes of the nodes on critical path began towork at the earliest time. These operations can advance the start time of nodes oncritical path. The purpose of the above operation is to shorten the implementationof the mandate of the total time. Theoretical analysis shows that the algorithmcan achieve a single task fully parallel processing on multi-core, also can shortenthe completion time of the tasks.For the problem that a node on critical path was scheduled the rest part ofthe critical path may have been changed, the next node may not belong to criticalpath anymore, led to task completion time delayed. A scheduling algorithm basedon dynamic critical path and task duplication was proposed. Firstly duplicatedfork-nodes to change the task graph into products processing tree, then found thecritical path in the sub trees, and made the father nodes of the nodes on criticalpath began to work at the earliest time. When the sub tree has been scheduled, change the sub tree to a virtual node. Add the virtual node into a sub tree which itbelongs.For the problem of current single-task scheduling for multi-core can not beadjusted to the number of core, a scheduling algorithm based on task duplicationwas proposed, to realize scheduling task based on the specific number of core sothat achieve full parallel processing of multi-core. The method is that: first inorder to reduce the communication between cores, divide single-task graph intounrelated run-sequences, then if the number of core is less than the number ofrun-sequence, join two run-sequences which has the minimal impact on the totalexecution time. This algorithm can not only realize the full parallel processing ofworking-core but also maximize the reduction of communication cost.