The Research Of Parallel And Distributed Systems Energy-Aware Scheduling Strategies And Algorithms

Human beings make endless pursuing of higher computing power since the invention of computer,which propels the rapid development of computer system.The traditional solution is to continuously improve the CPU frequency to accelerate the processing speed.However,the limitations of physical components impose restrictions on the processing capability,which force people turn to multiple CPU system.Meanwhile,the distributed computing system,which is physically and logically connected by several individual computing resources,is under development as well.Consequently,the large scale integrated system and high frequency CPU lead to sharply increasing energy consumption as well as thermal issues.Therefore,we must find a solution of this critical problem,which is a serious constraint to the development of computing power.The research work of this paper is aimed at the energy consumption problems under embedded real-time system,parallel and distributed system and cloud computing system.With the consideration that different systems have different task characteristics and scheduling performance goals,we design an energy saving scheduling strategy to realize high productive computing with low power consumption.Firstly,to solve the problem of high energy consumption of embedded real-time system,a DVFS-based energy-aware scheduling algorithm is proposed for sporadic tasks,named CCDVSST.Dynamic Voltage/Frequency Scaling(DVFS)is a key technique for embedded systems to exploit multiple voltage and frequency levels to reduce energy consumption and to extend battery life.In traditional energy-aware scheduling,the processor frequency is scaled based on the priori knowledge of tasks,such as the period,the worst-case execution time(WCET)and so on.However,in actual,the interval between the arrival times of two continuous jobs is always less than the given period,and the actual execution time of a task in each period is always shorter than its WCET,so the real total workload is much less than the predicted workload,which needs lower computer capacity.Based on the difference between the real workload and the predicted one,the proposed algorithm introduced a method to calculate the dynamical changed workload,and presents when and how to scale the processor frequency dynamically based on the workload.In the research,a lot of theorems are given to prove that the real-time of CC-DVSST.The experimental results show that CC-DVSST can reduce the energy consumption effectively compared with its compared algorithm.Duplication-based scheduling algorithm is a kind of high performance scheduling algorithm for DAG tasks in parallel and distributed computing systems.However,due to the duplication strategy,each task is executed multiple times according to the generated schedule,which leads to a great amount of resource waste and extra energy overhead.To address this problem,an optimizing strategy,named EAMDS,is proposed for duplication-based algorithms to reduce the number of duplicated copies.In the paper,the analysis is given firstly to show that some duplicated copies generated by duplication-based algorithms are redundant,and then the method is introduced on how to search the redundant copies from a duplication-based schedule.In EAMDS,the tasks are processed in the non-decreasing order of priorities,from the exit task to the entry task until the redundant copies of all tasks are found.The EAMDS algorithm can reduce the energy consumption effectively without performance loss in terms of makespan.Due to the greedy strategy of traditional DAG scheduling algorithm,each task is assigned to the processor that minimizes its finish time and its immediate predecessor task is duplicated as far as possible.However,according to the analysis,the duplication of some tasks can only improve the finish time of their successor tasks but not the global finish time.Hence,delaying the finish time of some non-immediate predecessor tasks would not affect the whole performance but reduce the number of duplication copies.Based on the idea,we firstly propose a feedback redundant deleting scheduling algorithm RADS.An improved algorithm FOS is also proposed to delete the regenerated redundant copies once they are generated,and three steps are introduced to translate the non-redundant copies to redundant ones by moving tasks forwards or backwards or between processors.Experimental results show that the two algorithms perform better than the duplication-based algorithms in terms of energy consumption.In cloud computing environment,the cloud platform configured with fixed computing capacity cannot adapt to the varying task workload,which leads to two main problems.One is low quality of service when the task service requirement is greater than the capacity;the other is the waste of resource and energy when the capacity cannot afford the service requirement.To address the problems,this paper proposes a new resource management and task scheduling algorithm.In this strategy,a double resource renting scheme is designed firstly in which shortterm renting and long-term renting are combined,which is modelled as M/M/c+D queuing model.This service model can avoid the waste of resource and energy but guarantee a high service quality for all tasks.Based on the M/M/c+D queuing model,the factors affecting profit of cloud service providers are analyzed such as energy consumption,fixed cost,extra cost,and so on.Moreover,a profit maximization problem is formulated and solved combining partial derivatives method and dichotomy Search to obtain the optimizing server configuration such that the profit is maximized and the energy consumption is reduced.The methods of solving the idea solutions and the actual solutions are introduced,respectively.Experimental results show that our scheme outperforms the compared one in terms of service quality,energy consumption and profit.