Application Of The Betweenness Centrality In The Scheduling Problem Of Directed Acyclic Graph

When scheduling a directed acyclic graph G=(V,E)with communication costs on a homogeneous computing platform,we schedule node set V to P1,…,Pp on these p processors,the makespan M is minimized,it is necessary to balance the processor load and data communication.List-based scheduling algorithm is the early research direction of this kind of problem.The disadvantage of this kind of heuristic algorithm is that it can not make shortterm sacrifice for global benefit.Clustering-based scheduling algorithm is a hot research direction of this kind of problem.It can better organize the local relationship between task nodes and reduce the data communication between processors.In this work,we propose a directed acyclic graph preprocessing algorithm BET-*for some clustering-based scheduling algorithms under the duplex single-port communication model.In the clustering-based scheduling algorithm,the whole algorithm can be divided into two modules.One is the partition module,what we do is divide V into k subsets V1,V2,…,Vk,and then minimize the edges in E whose source node and target node belong to different subsets,and the other is the scheduling module,which does the work of scheduling the partition results to each processor.The idea of our preprocessing algorithm is to identify the important nodes in the graph,and then change the partition results by the partition module of the clustering-based scheduling algorithm,so as to reduce the makespan M.Our proposed algorithm BET-*is a graph preprocessing algorithm that can be preceded by the existing clustering-based scheduling algorithm,which can achieve good compatibility.It can be deployed in some clustering-based scheduling algorithms based on acyclic partition in addition to our experimental content,which is equivalent to a preprocessing module.We introduce the betweenness centrality to help us identify the important nodes in the directed acyclic graph,and then we change the output of the graph partitioning algorithm by changing the node weights w and edge weights c around the important nodes.We analyze the impact of the location of important nodes in a partition.We believe that important nodes in a partition’s centre can reduce the makespan more than they at the border of a partition.The test of our algorithm shows that compared with the benchmark algorithm,our algorithm can bring stable benefits and reduce the makespan.Our analysis shows that this is mainly due to reducing the communication congestion between processors,making full use of the parallelism of calculation,input and output of a single processor and the synergy between multiple processors,reducing the waiting time of processors.In addition,we conducted extensive experiments to verify the stability of our graph preprocessing algorithm.As a pre algorithm,our algorithm is pre applied to six algorithms:BLEST-PART,ETF-PART,BL-EST-BUSY,ETF-BUSY,BL-EST-MACRO,ETF-MACRO and comparative experiments are carried out one by one.In the higher number of partitions and the higher communication cost of the scheduling directed acyclic graph,our algorithm can be more fully applied,and almost all instances exceed the benchmark algorithm.In terms of the time complexity of the algorithm,because our algorithm is a preprocessing algorithm,algorithm complexity does not exceed the O(p2|V|+|V|log+|V|+p|E|)with the lowest algorithm complexity in the baseline,we did not increase the overall time complexity.We tested the running time of our algorithm compared with the benchmark algorithm.Our conclusion is that our algorithm realizes the optimization of the results at an acceptable running time cost,which is a positive work.However,our algorithm has no advantage compared with the benchmark algorithm on those graphs with low communication cost.In general,we analyze the development of the current scheduling algorithm.Then we propose a preprocessing algorithm to optimize the algorithm results at an acceptable time cost.In the experimental part,we also analyze the influence of several parameters on our algorithm.Our conclusion is that the applicable scenario of our algorithm is to deal with those communication intensive graphs.Finally,as a prospect,we believe that this set of preprocessing ideas has good expansibility.In addition to the betweenness centrality,there are many network centrality indicators that can be studied.The betweenness centrality is based on the shortest path,but the longest path is more important in scheduling problem,and may get better results.