Research On Parallel Task Scheduling Algorithms Based On Meta-heuristics On Heterogeneous Computing Systems

With the rapid development of scientific technology,and the rapidly accelerated change of information technology(IT),supercomputer plays a vital role in many fields of industries,agricultures,militaries,aerospace,social economy and our daily life,and it has become an important development direction in the field of computer science and IT technology.Resource management models and task scheduling strategies are the core issues and key technologies on heterogeneous high-performance computing systems.Task scheduling strategies play an important role in reducing the total execution time and increasing the efficient use of resources within the acceptable range of performance indicators and under the both the condition of meeting task priority and resource constraints.Resource management models and task scheduling strategies have become important issues in high-performance parallel computing in the past few decades.Due to the heterogeneity in supercomputer architectures and the complexity of the application softwares,and also due to the discrepancies required by,the application softwares for the different resources in order to perform,therefore,the parallel task scheduling problems on heterogeneous high-performance computing systems become a very complex issue.Many scholars proved that the parallel task scheduling problems on heterogeneous high-performance computing systems are well-known to be an NP-hard problem in its general form,even in the case of a simple model.It is a challenging research problem in the field of high-performance parallel computing.Especially,for solving a real-world problem,it is not realistic to achieve the optimal solution under the condition of the acceptable performance and computational complexity.To solve this kind of problems,traditional task scheduling research has focused on heuristic-based algorithms,an important class of which is the so-called list scheduling algorithms.The basic idea of the list scheduling consists of maintaining an ordered list of tasks by assigning priority to each task according to some greedy heuristics.The tasks are selected in order of priority and the ready task with the highest priority is removed from the list to be assigned to a processor which allows the earliest start time.The performance of these algorithms is heavily dependent on the effectiveness of the heuristics.They are not likely to produce consistent results on a wide range of problems,especially when the complexity of the task scheduling problem increases.Contrary to the heuristic-based algorithms,a guided-random-search-based(meta-heuristics)algorithm incorporates a combinatoric process in the search for solutions,which is less efficient and generates much higher computational cost than the heuristic-based algorithms.For this reason,trade-off between makespan and speed of convergence are required.In this thesis,I developed a hybrid approach by integrating intelligent meta-heuristics approaches with heuristic algorithms.The hybrid approach I proposed can achieve a similar performance in terms of makespan for DAG scheduling while reducing the scheduling overhead,when compared with the overhead of guided-random-search-based algorithms;and can achieve better performance than heuristic algorithms.The main research works of this thesis are as follows:1.I proposed the DHSGA algorithm,which can be adapted for a wide range of DAG applications on heterogeneous high-performance computing systems.The proposed DHSGA algorithm generates a lot of priority queues by a heuristic-based crossover operator and a heuristic-based mutation operator for dependent task applications.The DHSGA algorithm effectively avoids the drawbacks of the existing heuristicbased scheduling algorithms that are only effective for specific types of applications.2.I proposed a new approach to generate the initial population using three evaluation criteria: a good “seeding”,a good uniform coverage,and genetic diversity.A highquality solution,obtained from a heuristic technique,can help MPQGA find better solutions more quickly than it can from a random start.With a good uniform coverage,the individuals are well spread out to cover the whole feasible solution space.Genetic diversity of the initial population can help the GA be able to reach part of the feasible solution space as large as possible.3.I presented a Gaussian random walk approach to search for local optimal candidate solutions in the operator of on-wall ineffective collision.I proposed a novel selection approach based on the normal distribution,and used an exclusive-OR(XOR)operator between two strings to reduce a chance of cloning before new molecules are generated.Then a pseudo-random shuffle approach was employed to generate new molecules to help the operator of inter-molecular ineffective collision of my HCRO algorithm to keep the molecular diversity,and on the contrary,to realize the operator of synthesis to eliminate close relatives of the molecules.4.I presented a novel bottom-up slack reclamation approach with delay for DAG task scheduling on heterogeneous computing systems to reduce power consumption,and to avoids the high time complexity of the top-down slack reclamation approaches with delay.5.I proposed a bi-objective task scheduling algorithm for makespan and energy consumption based on NSGA-II on heterogeneous high-performance computing systems.I demonstrate through experimental results over a large set of randomly generated graphs as well as graphs of real-world problems with various characteristics that my proposed bi-objective task scheduling algorithm has a better performance.