Research Of Dynamic Task Scheduling Algorithm On Heterogeneous CMP

With the increasingly concern on high performance computing field in native and abroad,the processor frequency and chip integration have been greatly improved.However,due to chip area's limitation and gradually approaching the upper limit of integration,the improvement of the processor performance becomes more difficult.Based on the development and tendency of processor,the multi-core processors appear and become the most popular processors.Meanwhile,the research around task scheduling algorithms for multi-core processor launches out,and two types of scheduling algorithms including static scheduling and dynamic scheduling arise.Since the static task scheduling algorithm cannot dynamically adjust itself to the running state of processor in real time,it can not be applied to the increasingly diverse applications.The dynamic task scheduling thus becomes the focus of the research on multiprocessor task scheduling.On the basis of common dynamic task scheduling algorithms' analyzing results,the paper proposes a dynamic scheduling algorithm.The algorithm relies on the dependency task of heterogeneous multi-core processor to make up the shortcomings and deficiencies in task randomly assigning in its first mission and ignoring among the task communication costs.It uses task scheduling mechanism based on a centralized scheduling mode,and uses the global and local scheduling queue as the task scheduling structure as a basis for the design task scheduler,and divides the implementation process into two parts: task assignment and task execution.In the task assignment phase,firstly,scan all of the tasks in global task queue and build a list of scheduled tasks on the judgment condition whether the direct precursor task can be scheduled.At the same time,use offline analyzing techniques to obtain task computing attributes,take successor task's execution time as a part of calculating for desired value of tasks which could be scheduled,and introduce the value into the cost of executing tasks in processor.Then,use the desired value and implementation cost to calculate the probability of task scheduling in processor and make it as a criterion.Finally,when the local task queue's length meets,achieve the task assignment.In the task execution phase,in order to solve the empty waiting situation due to tasks to be suspended,the algorithm adopts task duplication ideological to duplicate tasks from another processor's precursor tasks if the earliest start time of execution can be advanced.To ensure the processor system can keep its load balancing state before the nexttask assignment,when the processor makes a request for task scheduling,the algorithm in this paper uses task migration technology to make the processor system turn to be balanced again.Finally,to verify the effectiveness of the proposed algorithm on solving the dependency task dynamic scheduling problem,the paper evaluates the related parameters by using a fair and reasonable performance and obtains the test cases by using TGFF random task graph generator.The paper makes a test for the proposed algorithm through four test schemes in Simics experimental platform,and then does statistical analysis to the experimental results.The experimental results show that the proposed dependency task dynamic scheduling algorithm can solve the problem more effectively when tasks assignment is not accurate and communication cost between different processors are ignored and so on.Besides,the overall task completion time and the speedup of the proposed algorithm are also greatly improved.