Research On Task Allocation And Scheduling For Heterogeneous Multicore Systems Based On Dynamic Programming

In recent years,the increasingly prominent energy issue makes heterogeneous multicore architecture attract more and more widely attention.Heterogeneous multicore systems can effectively control the running speed and processing power with low-power task allocation and scheduling strategy,which becomes one of the most important ways to reduce system power consumption.However,task allocation and scheduling on heterogeneous multicore systems is a typical NP-complete problem,and existing algorithms mainly depended on the random search strategy.With the increasing scale of the problem,the solving speed of random search algorithms declined sharply,and they easily fell into local optimal solution,so they can not effectively reduce system power consumption.Since the minimum system energy consumption problem of the tree-structured applica-tion has the quality of optimal substructure,the optimal tree allocation algorithm,based on the dynamic programming method,was designed to find the optimal solution.For the gen-eral application,its minimum system energy consumption problem does not have the optimal substructure properties,so the optimal solution can not be obtained by using dynamic program-ming.However,by transferring the optimal algorithm,we proposed a heuristic algorithm that can generate near optimal solution.Compared to the random search strategy,the proposed heuristic had better performance and energy-saving effect.After completing the task allocation,a minimum resource scheduling algorithm was pro-posed to determine the resource configuration.The minimum resource scheduling algorithm used a two-stage heuristic strategy:Firstly,use the scheduling policy of as late as possible(ALAP)to determine the lower bound of each processor;Then,the revised list scheduling al-gorithm was used to determine the execution configuration of each task,to ensure that the tasks can be completed within the given time constraint,and the number of each core was minimized.To verify the performance of the algorithm,we designed a simulation system.The algo-rithms proposed in this paper and several existing algorithms were simulated and implemented based on this system.Two group of experiments are designed for tree-structured applications and general structure applications,respectively.The proposed algorithms in this paper were evaluated from two aspects of energy-saving rate and the runtime of algorithms,compared with Integer linear programming algorithm,genetic algorithm and priority strategy of unit value on knapsack problem.Experimental results showed that the proposed algorithms were better than the existing algorithms with better performance and quicker solving speed,and can effectively reduce system energy consumption.