Strategies And Scheduling Algorithms For Reliability Of Processors And Energy Awareness On Heterogenous Computer Systems

With the continuous promotion of the chip technology,the development of computer systems has new features,which include heterogeneous architectures,large scale,and high performance etc.High-performance and heterogeneous computing systems are the chosen infrastructure for large-scale computing in various fields,such as scientific mathematics,engineering applications and so on.Meanwhile,it brings much convenience in people's daily life.However,the high performance comes with high resource consumption.The energy saving and system reliability enhancement are the emphasis and difficulty in the research of high-performance computing.This thesis will focus on the theme of green computing.In the current work,we study the performance of optimal energy management,the enhancement of reliability and maximizing the performance under a cost budget.Specifically,the main works and contributions are summarized in the following four aspects.Firstly,we conducted a research on scheduling of task set with precedence constraints in heterogeneous systems,and devising reliability-aware heuristic algorithms under the condition of energy budget.The traditional Complementary Metal Oxide Semiconductor(COMS)power model has a drawback which couldn't precisely reflect the relationship between the frequency of processor execution and the power consumptions.Therefore,in this work,we employ more reasonable power consumption model and adopt reliability model to quantify the effect of using dynamic voltage frequency scaling(DVFS)technology on processor transient fault during the execution of each task.Under the constraint of energy budget,our research try to maximize the system reliability for a given directed acyclic task graph(DAG)scheduling in heterogeneous systems.Three reliability aware heuristic algorithms(named Reliability-aware Heterogeneous Earliest Finish Time(RHEFT),Reliability-aware Critical-Path-On-a-Processor(RCPOP)and Reliability Maximization with Energy Constraint(RMEC))with low time complexity are developed in this thesis.In the presence of experiments for the proposed algorithms,11 different communications to calculation rates(CCR)and the number of different heterogeneous processors are configured for large number of random DAG task graph and real-world applications to run the algorithms.The experimental results show that RHEFT,RCPOP,and RMEC outperforming the best existing two algorithms in terms of enegy consumption ratio and probability of failure.Secondly,we conducted a research on scheduling of task set with precedence constraints in heterogeneous systems,by adopting the shared recovery technique to enhance the system reliability meanwhile we maintain the constraint of share deadline in the task set.It is a fact that the probability of transient fault occurrence is dozens even several hundred times of that of permanent faults.The DVFS technology and shared recovery technology are employed in this thesis to addresses the task set scheduling with both precedence constraints and share deadline constraint in the heterogeneous computing systems,even if transient faults happen.Three heuristic algorithms(named shared recovery for reliability aware of heterogeneous earliest finish time(SHRHEF),shared recovery for reliability aware of critical path on a processor(SHRCPOP),shared recovery for energy efficiency and system reliability maximization(SHRMEC))with shared recovery technology are devised.To evaluate the performance of the proposed algorithms,multiple CCR and dozens of numbers of processors are configured in different combinations.They are used to be configured in the experiments,while running the algorithms for a large number of random graphs and real-world applications.Every DAG for each configuration is performed for 1000 times to imitate the transient fault happening in different task.The enormous amount of experiment results show that the three proposed algorithms SHRHEF,SHRCPOP and SHRMEC can guarantee the application running with a high reliability and a low energy consumption even encountering the transient fault while tasks are executing.Thirdly,we conducted a research on the bi-objectives optimization to promote the system reliability and to reduce the energy consumption for the task set with precedence constraints in heterogeneous computing systems.The mode like pay-as-you-go requires the data center to provide a set of potential solutions.In this thesis,for the objectives of low system reliability and low energy consumption,a bi-objective algorithm(named Bi-Objective Genetic Algorithm(BOGA))is proposed for the task set with shared deadline constraint and precedence constraints over heterogeneous computing systems.In the beginning of the proposed algorithm,classic schemes are used to initiate the population with a priority queue.The single point crossover which obeys the dependent relations is employed to generate new individuals.To classify a better solution,the Pareto dominance is utilized to access the two candidate solutions.The modified method of fast-non-dominated-sort is exploited to identify the non-dominated front in the population.BOGA is implemented in a famous open source software framework named j Metal.And three real-world and parallel applications are used to test BOGA.The experiments demonstrate that BOGA can provide a series of different system reliability and energy consumption in compromise excellent candidate solutions for a given task set.Fourthly,considering the voltage switching overhead of processors,the research on scheduling tasks with an execution time following a statistical distribution in high performance embedded system is proposed herein.For some high-performance equipments which are sensitive to energy,the switching overheads generated during the process of frequency changing can't be ignored simply while applying DVFS technology.Therefore,based on the high performance embedded systems for both unique core and multi core,independent task sets which comply with statistical distributions are studied in this thesis.Two energy-aware algorithms(named Optimal algorithm for Uncertain Execution Time(OUET),UDPSM)are proposed.With respect to the proposed algorithms,benchmarks which obey uniform,Gaussian,and exponential distributions are used to be tested,respectively.In comparison with the existing algorithms ignoring switching overhead,OUET and UDPSM algorithms show better performance in terms of energy saving and no deadline mission ratios.