Research On A Topology-based Multilevel Algorithm For Large-scale Task Scheduling In Clouds

With the development and popularity of big data and artificial intelligence.The local stand-alone environment is difficult to meet the needs of users.Therefore,more and more tasks are uploaded to the cloud for computing.The scheduling algorithm determines how the cloud center allocates resources to tasks.Scheduling objectives include optimizing makespan and maintaining load balance.The task scheduling problem has been proved to be NP complete.Therefore,scholars have proposed many scheduling algorithms to find the suboptimal solution for the task scheduling problem.Although the traditional scheduling algorithm has excellent scheduling effect for small-scale scheduling problems,it has different challenges in the face of large-scale task scheduling problems.For example,the scheduling algorithm based on list has poor scheduling effect due to task scale,while the scheduling algorithm based on clustering has stable scheduling effect,but usually has high time complexityAiming at the large-scale task scheduling problem in heterogeneous environment in cloud computing,this paper proposes a topology based multi-level task scheduling algorithm（TBMSA）based on DAGP algorithm in large-scale integrated circuit design.Different from DAGP algorithm to solve the graph partition problem in homogeneous environment,TBMSA algorithm uses the traditional scheduling algorithm as the initial scheduling algorithm for the scheduling problem in heterogeneous environment.At the same time,it improves the refinement algorithm and considers the bandwidth between heterogeneous machines when calculating the gain value.Finally,it adds B-EST algorithm to calculate the execution order of tasks on different machines.TBMSA can be effectively compatible with traditional scheduling algorithms,optimize scheduling length and ensure machine load balance.TBMSA combines two traditional task scheduling algorithms with heft algorithm to verify the advantages of TBMSA algorithm.TBMSA algorithm first selects HEFT,a classical scheduling algorithm based on scheduling list scheduling,as the initial scheduling algorithm.HEFT algorithm is not effective in dealing with large-scale task scheduling,but it avoids this defect as the initial scheduling algorithm of TBMSA after multi-level compression.Experiments on random data sets show that TBMSA+HEFT algorithm has an average optimization of12.2%compared with the traditional HEFT algorithm in shortening the scheduling length.At the same time,in terms of load balancing,HEFT algorithm will deteriorate with the increase of the number of cluster machines,while the load imbalance of TBMSA+HEFT algorithm has been stable within 1.08.Because HEFT algorithm cannot dynamically update the scheduling priority,the scheduling effect will deteriorate with the expansion of task scale.Therefore,the initial scheduling algorithm is replaced by the clustering scheduling algorithm CMWSL based on dynamic update scheduling^[41].Although its scheduling effect will not deteriorate with the increase of task scale,its high time complexity can not be applied to large-scale scheduling.In TBMSA algorithm,CMWSL can be used as the initial scheduling algorithm to solve the large-scale task scheduling problem.Under the same data set,TBMSA+CMWSL has an average optimization of 14.4%compared with HEFT algorithm in shortening the scheduling length.Moreover,the load imbalance of TBMSA+CMWSL is always kept within 1.08.When the task node size is n=15000,the running time of TBMSA+CMWSL algorithm is only 4 hours,while the CMWSL algorithm needs more than ten days to schedule the task graph of this size.