Optimization On Partitioning Methods And Processing Workflow Of Distributed Graph-Processing Systems

To analyze large-sclae graphs,distributed graph-processing systems first assign vertices and edges over computing nodes with a graph partitioning method,and then iteratively compute vertex values according to certain processing workflow,until graph algorithms converge.Therefore,the graph partitioning methods and processing workflow largely determine the performance of distributed graph-processing systems.Traditional distributed graph-processing systems are typically built on homogeneous computing platforms,and operate on static graph structures.However,as graph processing has become more widely-applied,the latest systems are required to efficiently execute on heterogeneous computing platforms.Moreover,they should adapt to the online updates and queries to graphs,and also optimize for the popular bipartite graphs.To meet the above key requirements,this paper conducts in-depth research from the following three aspects.Optimization on partitioning methods to realize workload balance in heterogeneous clusters.A real-world cluster is usually heterogeneous.However,existing systems assume that the cluster is homogeneous,and thus assign the same amount of workload to each node in the graph partitioning phase.As a result,at every iteration of a graph algorithm,brawny nodes accomplish local computation faster than wimpy nodes,incurring workload imbalance among computing nodes.To solve this problem,this paper proposes a graph partitioning method Laro,which migrates vertices among computing nods to realize workload balance.To build an efficient migration plan,Laro has overcome three challenges:(1)To quantify the workload imbalance,Laro introduces the Relative Standard Deviation(RSD)of processing times of all nodes as the characterization parameter;(2)To restore workload balance,Laro regards decreasing the RSD of processing times as the migration goal;(3)To reduce migration overhead,Laro proposes a threshold and a“double-check”strategy to limit the migration frequency.To be specific,at end of every iteration,the master nodes will compute the RSD of processing times of all computing nodes.If the RSDs in two consecutive iterations are both greater than the threshold,workload imbalance is detected.After that,heavy-load nodes migrate vertices and edges to corresponding light-load nodes in parallel.Finally,the new locations of all migrated vertices are stored on each computing node.Evaluation results show that,compared with the two existing partitioning methods Skewed Hash and GPS-dynamic,Laro decreases the computation time of graph algorithms by 1.23 x and 1.20 x respectively.Optimization on processing workflow to improve computational efficiency for dynamic graph structures.To analyze a dynamic graph structure,existing systems typically maintain a series of versions.While executing graph algorithms on current version,they often cache graph-structured updates in a buffer.When certain conditions are satisfied,all cached updates will be applied onto current version,to construct a new version.Finally,graph algorithms are executed on the new version,to obtain up-to-date results.Nevertheless,for widely-used monotonic graph algorithms,the cached updates can be preprocessed in the buffer before being applied,to improve computational efficiency on the new version.To this end,this paper proposes the graph processing workflow Gra PU,which preprocesses cached updates in three sequential phases:(1)Updates Classification,it identifies the graph data that are actually affected by current updates,by classifying the vertices involved in updates according to connected components;(2)Updates Precomputation,it generates a set of intermediate values that can be leveraged to facilitate convergence of algorithms,by precomputing the values of vertices involved in updates.(3)High-degree Vertex Division,it balances the computation times of all vertices,by identifying the highdegree vertices involved in updates and distributing their edges over multiple nodes.After the cached updates are applied,Gra PU adopts the subgraph-centric computational model to calculate vertex values in the new version.Besides,Gra PU presents a subgraph-centric data layout for I/O efficiency of graph data,as well as a subgraphlevel workload balancing strategy for workload balance among subgraphs.Evaluation results show that,compared with the existing system Kineo Graph,Gra PU decreases the computation time of graph algorithms by 4.55 x.Optimization on partitioning methods to reduce communication overhead for bipartite graphs.In a bipartite graph,the vertices are separated into two disjoint subsets,and each edge connects a pair of vertices coming from different subsets.Bipartite graphs have been widely used in Machine Learning and Data Mining(MLDM)area.However,existing systems are obvious to the unique structure of bipartite graphs.As a result,these systems generate inappropriate partitioning for bipartite graphs,and suffer from high communication overhead and workload imbalance when executing MLDM algorithms.To address these issues,this paper first summarizes three features of bipartite graphs and MLDM algorithms:(1)In most MLDM algorithms,each vertex value is a vector consisting of multiple elements;(2)In a bipartite graph,the sizes of two vertex-subsets are highly lopsided;(3)Within a vertex-subset,the vertices usually exhibit power-law degree distribution.Based on the three features,this paper proposes a graph partitioning method Gra Bi,which partitions a bipartite graph first vertically and then horizontally,to achieve high-quality partitioning.In the vertical partitioning,Gra Bi divides each vectored vertex into several vertex-chunks,and thus the bipartite graph is divided into several layers.In the horizontal partitioning,Gra Bi assigns the vertex-chunks in the larger vertex-subset first within each layer,and decomposes these vertex-chunks into one or more subchunks.Finally,Gra Bi distributes the sub-chunks uniformly over computing nodes,by using a set of hash functions.Evaluation results show that,compared with the three existing partitioning methods Hybrid-cut,Bi-cut,and 3D-partitioner,Gra Bi decreases the computation time of MLDM algorithms by 3.12 x,3.41 x,and 1.30 x respectively.