Research And Optimization Of NXgraph Graph Processing System

Large graphcomputing has been a fundamental comuting pattern,and it is widely used in extensive applications,such as social network analysis,web search,recommendation systems.By optimizing I/Os and the multi-core parallel processing,single-machine graph processing systems achieve competitive performance with distributed graph processing systems,and thus have become a research hotspot.The NXgraph system is one of the best mainstream single-machine graph processing systems due to comprehensive optimizations.Graph processing can be divided into two phases: preprocessing and updating.NXgraph preprocessing algorithms generate a large amount of I/Os and merge operations.Since a single machine has limited I/O performance and the graph data sets are usually large,the I/O bottleneck degrades the graph processing performance.To solve this problem,the double-phase preprocessing algorithm is proposed.The graph data set is divided into multiple shovel files,and then these files are merged using the efficient k-way merge algorithm to produce the sub-shard file.When the memory is large enough to store two copies of the vertex data of a graph,NXgraph uses the singlephase update(SPU)algorithm to compute and update vertex attribute.SPU has superior performance,but requires large memory space so as to be unavailable for big graphs.To reduce the memory requirement,the column-oriented single-phase update algorithm(COSPU)is proposed to store only one copy of the vertex data in the memory and perform column-oriented asynchronous updates.NXgraph uses the mixed phase update algorithm(MPU),when the memory can hold only a part of the vertex data.To reduce the number of read and write operations to hub files,multiplex cycle update algorithm(MUCU)is proposed.By reusing the memory space for vertex data and loading interval vertex data from the disk on demand,MUCU greatly reduces the amount of IOs.Furthermore,MUCU uses the asynchronous mode to accelerate the convergence speed.The experiment shows that the double-phase preprocessing algorithm significantly reduce the I/Os and merge operations,achieving an average of 27.6% performance improvement,compared with the original preprocessing algorithm.in addition,compared with MPU,MUCU improves the performance up to 18%,compared with SPU,COSPU significantly reduces the required memory size for large graph processing,enhancing the applicability.