Research On Static Task Scheduling Of Heterogeneous Computing System Based On Metaheuristic

Heterogeneous computing system consists of some processors with different architectures.The operational performance of the system improvements due to each processor choose the right task to process.The scheduling of task rely on scheduling algorithm and the efficient task scheduling algorithm is the key to enhance performance of the heterogeneous system.The task scheduling in heterogeneous computing system problem has been proven to be NP complete problem and there is no way to get the optimal solution in the polynomial time.For a more efficient algorithm,studies to answer those questions are underway.Heuristics and metaheuristic were considered to be the effective way to solve this problem.Metaheuristic is easy to fall into local optimal and does not make full use of idle time of processors.In order to shorten the scheduling length,we used chemical reaction optimization algorithm and genetic algorithm in this paper,combined with the local search and global search,used interval insertion and task duplication to study the task scheduling problem.Detailed works are as follows:The drawback of existing metaheuristic algorithms is lacking the global searching ability.So we have designed elementary reactions and figured out an metaheuristic task scheduling algorithm based on chemical reaction optimization.Firstly,we use the topological sorting to determine the scheduling sequence of task.Secondly,four elementary reactions were used to reorder the task sequence.The purpose is to find out the optimal solution within solution space.Task allocation strategy is based on the earliest finish time(EFT),each task is assigned to the processor with minimum EFT.In order to verify the feasibility and efficiency of the this algorithm,a simulation system for test and verify the performance of the proposed algorithm is designed.The results show that our algorithm have shorter scheduling length compared with list simulated annealing altorithm and CPOP altorithm.Many scheduling algorithms have low CPU usage rates when they scheduling the high communication to computation ratio(CCR)task graph,so we applied interval insertion and task duplication to genetic algorithm and designed a heuristic task scheduling algorithm based on task duplication and genetic algorithm.The algorithm records the critical predecessor tasks of all tasks first.Then copy the critical predecessor task of the current task to it's processor tentatively in each iteration.If the AFT of current task can ahead of schedule,then confirm that the duplication is effective,otherwise discard this redundant predecessor tasks.This strategy can effectively reduce the communication overhead due to adjacent tasks were assigned to different processors and started some tasks in advance.The simulation results show that the improved scheduling algorithm better than HEFT and CPOP list scheduling algorithm in makespan,speedup and schedule length ratio.