The Research Of Task Scheduling Algorithm Based On System Reliability

The performance of task scheduling algorithm could influence the property of the heterogeneous computing systems directly.With the scale of the heterogeneous computing systems expanding and the number of system processors increasing,the reliability of the system decrease,and,correspondingly,the reliability of the task scheduling algorithm running on the system also decrease.The reduction of the reliability would inevitably influence the efficiency of the task scheduling algorithm.In traditional scheduling algorithm,the total length of task scheduling is treated as a main standard to measure efficiency of task scheduling algorithm.However,in task scheduling algorithm,the reliability is the definite premise of guaranteeing the efficiency of the algorithm.Therefore,when designing the task scheduling algorithm based on heterogeneous computing systems,how to raise the reliability of task scheduling algorithm as much as possible has become the central issue and difficulty of task scheduling algorithm research.Generally,the measures widely utilized to raise the reliability of system are software redundancy method and hardware redundancy methods.Since hardware redundancy method requires extra cost,software redundancy method is more popular.Software redundancy method increases the reliability of system through task replication,which can be handled with by active replication schema.This paper mainly focuses on searching for the transmission link among processers with maximum reliability to transfer data based on active replication schema,in order to maximuming the system reliability of task scheduling algorithm,and focus on reducing the execution time of scheduling algorithm.The main works are as follows:Firstly,a maximize reliability tasks scheduling algorithm named RMSR(Replication-based Scheduling for Maximizing System Reliability)based on active replication schema is presented.By replicating task and then forming multiple task replicas,the number of which is determined by task reliability threshold,the algorithm ensures that the ultimate reliability of each task is higher than task reliability threshold.Meanwhile,the algorithm also takes the reliability of communications between heterogeneous computing system processors into consideration,by selecting the communication link with maximum reliability to transfer data.Secondly,the simulation experiment of RMSR algorithm in this paper is based on two different types of DAG graph.One kind of DAG graph is randomly generated graphs.In this kind of graph,it is verified that the system reliability of RMSR algorithms is higher than the other two known algorithms RASD and HEFT,according to the research in this paper based on four varied parameters,which are number of tasks,processors,parallel factor and CCR value.The other kind of graph is application graph of real-world problems.From the result of experiments,it is found that the reliability of RMSR algorithm is mostly affected by the number of tasks inputted.Experiment proves the validity of the proposed algorithm.Finally,a parallel tasks scheduling algorithm PRMSR(Parallel RMSR)based on RMSR algorithm is proposed in this paper,and it is realized by applying OpenMP programming model.The numerical analysis on the comparison between PRMSR algorithm and the RMSR algorithm theoretical speedup is also conducted.It is concluded that,as the number of tasks increases,theoretical speedup is similar to the number of parallel processor.