Researches On Energy-Efficiency Aware Scheduling For Heterogeneous Computing

Enabled to provide high throughput of information service and cost-effective pro-cessing amounts of data, the large-scale computing system represented by the high performance cluster, is definitely the most powerful production tool in the era of "Inter-net+" covering various fields, such as national politics, social economy and people’s life. Meanwhile, there has been a progressive increase in the energy-consumption pro-portion of information communication technology (ICT) industry to the world every year. Green computing, closely related to environmental protection and sustainable de-velopment of human beings, has attracted increasing attention of many investigators recently. Energy efficiency management in high performance computing (HPC) field has actually been the key issue for operation of data and computing centers.Resource management is in charge of responding the requests of users, effectively scheduling tasks and reasonably assigning resources. Task scheduling as the core of resource management is responsible for task ranking and resource allocation on a set of processing elements with arbitrary characteristics, which aims to satisfy the quality of services (QoS), usually related to the total execution time or resource utilization. Previ-ous studies have shown that most of the parallel scheduling problems are NP-complete, even in the case of a simplified model. Combining software real-time scheduling with hardware energy-conservation techniques, such as DVFS(dynamic voltage and fre-quency scaling) and DPM(dynamic power management), scheduling integrated with energy-efficiency awareness aims at high energy-efficiency that is an evaluation index of QoS(quality of service), rather than high performance. So it is the effectual way to conforming to such scientific development as green computing, and emphasis and difficulty of researches on computer science and application.To adapt to QoS demands such as low energy, high scalability and load balancing, this paper focuses on the model and algorithms of heterogeneous scheduling integrated with energy-efficiency awareness for mass-data intensive applications. Supported by the National High Technology Research and Development Program of China under Grant No.2006AA01A113("Research and application of grid platform for public com-puting services"),2012AA01A306("Research and application of authentic animation rendering system") and the National Natural Science Foundation of China under Grant No.61070017("Research on power-aware scheduling in data intensive applications"), this topic is an intersectant subject of heterogeneous system in HPC, real-time dynamic scheduling, distributed artificial intelligence and green sustainable computing. It has blazed a new path for researches on heterogeneous scheduling integrated with energy-efficiency awareness, and laid the foundations for the related theory and technology. With ICT energy consumption increasing, cloud computing widely applied and system scale continuously expanding, the study is of theoretic innovation and as a guideline in practice.· On the theoretical research, an energy-efficiency aware and multi-objective op-timization scheduling model is firstly presented via quantization of multidimen-sional and mutative-scale limitation parameters of practical DVFS-processor mod-els in heterogeneous systems, which is the research foundation and the core. On the other hand, two novel multi-objective optimization scheduling algorithms are presented with multidisciplinary crossover study, based on the algorithm on behalf of classic or emerging meta-heuristics and due to NP completeness of problem, the diversity of environments, new demands of applications and compromise of scheduling objectives. The two complement each other with mutual coordination.· Some technological breakthroughs are achieved, including boundary conditions for different heterogeneous computing and grid scheduling and descriptions of real-time variation of scheduling indexes (stringent timing constraints, and energy-efficiency).In brief, there are mainly four innovations in this paper as follows.1. We put forward a heterogeneous scheduling model integrated with energy effi-ciency awareness. The proposed method introduces energy-efficient technologies into the design of real-time scheduling software, in terms the processor model from homogeneous systems to heterogeneous systems, the task model from inde-pendent tasks to dependent tasks, the DVFS processor model from ideal to practi-cal multidimensional and mutative-scale limitation. Based on DAG models of the parallel real-time tasks and taking into account heterogeneous characteristics of computing resources, an energy-efficiency aware multi-objective model reusable with ease is firstly presented via mathematical quantization of multi QoS dispatch-ing indexes including energy budgets. Furthermore, the theoretical analysis and experimental results show that the model helps to get more energy conservation on the premise that the optimal scheduling of parallel dependent tasks can be sat-isfied, with remarkable advantages under the condition of high loads.2. This paper develops an artificial immune algorithm with multidisciplinary con-text for modeling self-organizing co-evolution of genes and memes, which is for heterogeneous multi-objective scheduling optimization problems with strong con-straints and lack of field knowledge and To overcome the major drawbacks to the algorithms, such as inferior local search ability, premature convergence, random walk and low precision of the final solutions. We start the research in terms of the antibody encoding and decoding technology, and multi-objective evaluation of affinities. Then the related mechanisms of immunology and cognitive psychol-ogy are discussed in details, which root in fine-grained gene affinity, mathematical formulation of memes, self-organizing co-evolution of genes and memes and evo-lutionary feedback depthmodel. Meanwhile, hybrid parallel meta-heuristics are designed combining coarse-grained models with master-slave models based on the hybrid multi-core CPU+GPU architecture of newly developed HPC-clusters. Furthermore, the theoretical analysis and experimental results highlight the effec-tiveness and efficiency of the proposed algorithm.3. We propose an algorithm modeling multi-objectively self-adaptive evolution of swarm intelligence and based on DAG sorting. The particle vectors are repre-sented supporting DAG sorting by depth values and coupling strength for het-erogeneous scheduling and in view of the analysis and comparison of existing algorithms; linear continuous evolution of the particle swarm is modeled based on mathematics, physics dynamic and distributed artificial intelligence, etc; the local optimizer is introduced, which is self-adaptively learning from elite intelligence; and the theoretical analysis and experimental results are provided in details. The first two improvements help to enhance the abilities of global searching candi-date solution to heterogeneous scheduling problems for better Pareto approximate solutions, while the local optimizer keeps Pareto solutions good distribution and diversity.4. This paper presents the simulation method and evaluation system of the model and algorithms in view of the particularity of heterogeneous scheduling researches. The competitive advantage of evaluation experiments is a test suite of large di-mension instances which model realistic heterogeneous computing regarding all the heterogeneity and consistency combinations for each dimension, greater than the twelve instances in the classical literatures. Some breakthroughs have been made in key areas, including boundary conditions for different heterogeneous computing and grid scheduling and descriptions of real-time variation of schedul-ing indexes (stringent timing constraints, and energy-efficiency). The experimen-tal results not only highlight higher efficacy and better scalability for the proposed approaches, but also show the impact of the scheduling model in terms of energy efficiency in the range of acceptable complexity.The theoretical analysis, simulation experiment and evaluation results of this pa-per have shown that, the research achievements not only effectively reduce the energy consumption in mass-data intensive applications, but also assure quality of public com-puting services that can meet the multi-objective requirements of customers. They have as well highlighted the effectiveness of the proposed approaches to solve energy effi-ciency management problems of heterogeneous real-time systems.