Energy-efficient Task Scheduling On Heterogeneous Computing Systems

Due to the limited capabilities of standalone computers,large-scale applications such as scientific computing and data analysis are usually processed by distributed computing systems with multiple processing units connected by a high-speed network.Particularly,heterogeneous computing systems that consist of various cheap and heterogeneous devices are commonly used because of their functional complementarity and good scalability,and they are ubiquitous in fields of big data,supercomputing,grid computing and cloud computing.However,with the increasing size of these systems,energy consumption becomes a critical issue not only because of the high electricity costs but also due to the environmental impacts.Therefore,reducing the energy consumption by the use of software techniques has become an urgent problem,which gains growing attentions and supports from academic,industrial and governmental fields.This dissertation focuses on task scheduling to reduce the energy consumption as well as minimize the overall schedule length,namely makespan,of parallel applications on heterogeneous computing systems.The purpose of this research is to provide energy-efficient task scheduling strategies with high and bounded scheduling performance at expense of a low time complexity.An energy-efficient task scheduling includes task prioritization,processor selection and frequency assignment,which comprise the final schedule and affect the performance individually.Based on the analysis of the schedule structures,each above factors are extensively studied while corresponding scheduling algorithms are designed.The effectivenesses of these algorithms are also theoretically proofed and experimentally evaluated.The main contributions of this dissertation are summarized as follows:(1)The models and the complexity of energy-efficient task scheduling are analyzed and the techniques for energy optimization are concluded.Traditional task scheduling concentrates on minimizing the makespan,whereas energy-efficient task scheduling considers energy consumption additionally.By the theoretical and experimental studies on traditional schedulers,most of them are found to have overused processors,resulting in unnecessary energy consumption.To tackle this problem,a heuristic is proposed to eliminate the redundant processors.Besides,as another routine technique for energy reduction,dynamic voltage frequency scaling has been widely adopted in many energy-efficient schedulers by means of slack reclamation,the effectiveness of this technique and its optimality under combinations of multiple frequencies are proofed in this dissertation.(2)Considering frequency assignments,an energy-efficient task scheduling algorithm based on linear programming is proposed to provide optimal solutions.In this occasion,energy optimization is conducted after a time-efficient schedule is given,the problem thus turns to be a single-objective optimization problem,which can be solved by linear programming.By introducing two decision variables,namely frequency duty factor and time interval,the objective function of energy minimization is set up and the linear constraints about task dependencies and deadline are established based on the given schedule.Finally,the best frequency assignments can be straightforwardly given by a mature set of linear programming tools in polynomial time,revealing that such problem belongs to the P class.The comparative results on randomly generated task graphs demonstrates that the proposed algorithm can reduce 11.5% of energy dissipation compared to HEFT,while improving EES and MVFS-DVFS in terms of runtime efficiency by 3 times.(3)Considering processor selections and frequency assignments,an energy-efficient task scheduling algorithm based on variable neighborhood search is proposed.In this occasion,task scheduler should be aware of minimizing the makespan and the energy consumption simultaneously.Recent methods heavily rely on a normalized metric which can not provide satisfied and bounded performance.In view of this,the variable neighborhood search meta-heuristic is applied to search suboptimal solutions.A time-efficient schedule is used as a starting point while two neighborhood structures are designed to reduce the makespan and the energy consumption,respectively.The searching process is performed and pruned in different trajectories to provide bounded schedules efficiently.The experimental results on both randomly-generated and realworld applications suggest that the proposed method breaks the bottleneck of energy-savings offered by frequency refinements,achieving improvements in makespan and energy by 1.3%and 22.3%,respectively.(4)Considering task prioritizations,processor selections and frequency assignments,an energy-efficient task scheduling algorithm based multi-objective memetic algorithm is proposed.Based on an evolutionary framework,different task priority queues are explored by genetic operations,and time-efficient schedules for each queue are provided by an earliestfinish-time based heuristic.Then,the variable neighborhood search method is launched with sampling rate towards a more promising region.Besides,a time-efficient schedule is introduced as a baseline and a good seed in the initial population while a Pareto Archive is set up to record the optimized solutions by means of non-dominated sorting.The experimental results reveals that the proposed algorithm reduce makespan and energy by 4.4% and 29.9%,respectively.Meanwhile,the evolutionary efficiency is improved by 180 times compared to the HECS algorithm.