Research On Performance Optimization For Out-of-Core Graph Processing Systems

Graph processing is an important model in big data processing.It can be used to solve many problems like analysis of social networks,recommendation of products and roadworks plan.As the development of the techniques on Internet,smart terminal and social media,the scale of graph grows rapidly,which brings many challenges to storage,access and computing of graph.In order to handle these challenges,system researchers have developed a number of graph processing systems to manage,analyze and mine the large-scale graphs in recent years.The graph processing systems can be divided into three categories based on the computing platforms: distributed systems,(single-node)shared-memory systems,(single-node)out-of-core systems.Among these systems,out-of-core systems have drawn widespread attentions from researchers thanks to their better cost-efficiency and scalability in recent years.However,out-of-core systems usually suffer from poor performance and experiences of graph processing users due to ignoring the access patterns of graph algorithms and failing to efficiently utilize hardware resources such as disk and memory.To address these problems,we propose the following novel techniques to improve the performance of out-of-core graph processing systems.In order to solve the problem of inefficient subgraph construction problem of out-of-core graph processing systems,we propose a locality-optimized subgraph construction method.This method maintains both incoming edges and outgoing edges and sorts them by the destination and source vertices respectively during the computation.By this data organization method,system can maximize the sequential accesses to vertices and edges,which fully exploits the locality of data access to improve the cache efficiency and reduce the overhead of subgraph construction.Based on the method,we propose an efficient out-of-core graph processing system LOSC.To further improve system performance,LOSC adopts a compression-based edge storage format and a lightweight replication of interval vertices to improve storage and parallel computation efficiency.Evaluation results show that when compared with current subgraph construction method,the locality-optimized subgraph construction method can reduce the overhead of subgraph construction by 10.3x on average.Compared with two representative out-of-core systems Graph Chi and Grid Graph,LOSC can achieve an average speedup of 6.9x and 3.5x respectively.In order to improve the disk I/O efficiency of current out-of-core graph processing systems,we present an application-specific hybrid I/O access and vertex updating strategy.This strategy adopts two computing models,Row-oriented Push(ROP),and Column-oriented Pull(COP).ROP selectively accesses the active vertices and edges to avoid loading redundant data.COP scans all graph data during the computation to maximize the sequential I/O and ensure the access locality.Based on the I/O access features of different graph algorithms,system can adaptively select and switch between ROP and COP model,which achieves a good balance between I/O traffic and I/O access locality and significant improve the I/O efficiency.Based on this strategy,we propose a high-performance out-of-core graph processing system HUS-Graph.In order to support this strategy,HUS-Graph adopts a dual-blocks graph representation and an I/O-based performance scheme to improve the locality of data access and enable accurate switch of computing models.The evaluation results show that show that the I/O traffic of HUS-Graph is 18.4x and 8.8x smaller than that of Graph Chi and Grid Graph respectively.HUS-Graph outperforms Graph Chi and Grid Graph by 9.4x and 6.5x respectively.In order to overcome redundant data accesses and storage and severe I/O conflicts faced by existing out-of-core graph processing systems when handling concurrent graph processing(CGP)jobs,we propose a CGP-oriented computing model.When handling multiple CGP jobs,this computing model partitions a graph into several edge blocks that stored on disk,and loads each edge block into memory by a common order.When an edge block is loaded into memory,the CGP jobs can perform efficient parallel updating of vertices according to their own computing features.By this way,this computing model transfers the separate and random accesses to graph data to common and sequential accesses,which reduces redundant data accesses and storage and avoids competitions of I/O bandwidth.Based on the computing model,we propose a novel CGP-oriented out-of-core graph processing system Graph CP.To further improve system performance,Graph CP adopts a work-stealing strategy and a benefit-aware I/O access model to solve the work imbalance among CGP jobs and improve I/O efficiency respectively.Compared with current CGP-oriented graph processing systems that are based on distributed or shared-memory systems,Graph CP utilizes the cost-effective out-of-core solution to avoid the significant communication overheads or poor scalability Evaluation results show that compared with two state-of-the-art out-of-core graph processing systems Grid Graph and Graph Z and one CGP-oriented graph processing system Seraph,the I/O traffic of Graph CP is 5.3x,4.1x and 2.7x smaller than that of these systems respectively.And the system performance of Graph CP is 10.3x,4.6x and 2.1x faster respectively.