Research On Stochastic Scheduling Algorithms In Heterogeneous Computing Platforms

With the development of science and technology,there are more and more complex applications that contain multiple tasks.This type of application is called workflow.Majority of these applications have huge computational needs.In order to meet the needs,heterogeneous distributed computing systems(clusters,grid,clouds etc.)become common.The main process of workflow scheduling is to allocate a large number of tasks to multiple computing resources.This process is critical to improving the performance of the application on the computing platform.In recent years,the study on workflow scheduling problems,especially in the context of heterogeneous computing environments,has attracted more and more attention.This kind of scheduling research often uses directed acyclic Graph(DAG)to represent the workflow application itself,so it is also called DAG scheduling.Most of existing DAG scheduling heuristics assume that execution times of tasks and communication times between tasks are fixed and known.However,realistic workflow execution is complex,and it is difficult to obtain accurate prediction of the calculation time and communication time.So it is more realistic to assume these times are random variables.Moreover,we assume that the expected random variables and the variance can be predicted?The DAG scheduling problems modeled in stochastic fashion are called stochastic scheduling.In this paper,we focus on how to schedule tasks to a set of interconnected heterogeneous computing resources to achieve better overall performance when the execution time and communication time of tasks satisfy a certain random distribution.A direct approach of extending the deterministic scheduling heuristics to solve their counterpart stochastic problems is to use the expectations of random variables as problem inputs.Therefore,this thesis first considers the classical deterministic scheduling algorithm HEFT,and explores the use of expectation as approximation weight in HEFT whether it is a good solution.The experiment results show that there is still a lot of room for improvement.Next,we try to extend deterministic DAG scheduling heuristic HEFT to achieve better performance,and propose a stochastic scheduling heuristic called RHEFT.We introduce stochastic strategy into the second phase of HEFT,that is assigning the task to the resource with minimum estimated execution finish time.By comparing RHEFT and HEFT with extensive simulation experiments,most of results show that RHEFT can not only significantly shorten the makespan,but also exhibit good scalability.In addition,we extend the RHEFT and introduce random policy into the comparison of the priority.The experiments show ERHEFT get higher performance in comparison with RHEFT.