Research On Key Technologies Of Efficient Graph Analytics Systems

Graph is a powerful data structure.In the real world,many entries and relations between them can be abstracted into vertices and edges in the graph.Graph analytics has a vital practical significance for valuable information.In recent years,graph data has grown rapidly,and the number of vertices has reached the scale of billions or even more in many areas,such as web search,social graph,biological information,etc.In addition,graph analytics suffers from the power-law distribution and random-access characteristics result in low temporal and spatial locality.The above problem poses a serious challenge for an effective graph analytics platform.Graph analytics on single-machine has gradually become a research hotspot because of its advantages,such as giving full play to the performance of processors,more efficient communication between threads,and concise and easy-to-understand programming.We focus on the challenges of graph analytics and study the key technologies of graph analytics platform.The main work and innovations are as follows:1.A method for redundant array construction based on flash memory.Flash has the advantages of high bandwidth,good random read/write performance and low latency.But there is still a gap between flash and DRAM.We explore the construction method of the high-speed flash array in order to provide external storage for graph analytics.We choose SATA and PCIe solid state disks and build flash arrays of three models: RAIS0,RAIS5,and RAIS6.Then,we analyze the effect of queue depth and request granularity on the performance of the flash array.And we study the behaviors of the flash array under four popular filesystems: XFS,EXT4,F2 FS,and BtrFS.Finally,we give some suggestions to build a high-speed flash array and make IO optimizations according to the IO characteristics of applications.2.An out-of-core graph analytics platform for NUMA architecture-HPGraph.Currently,servers typically have multiple processors and are connected in a NUMA architecture.Processors access local memory at much higher performance than remote memory.We design and implement an out-of-core graph analytics platform based on NUMA architecture.We adopt NUMA-aware data partitioning and access patterns in order to reduce remote memory access,fine-grained edge blocks filtering strategy that can effectively reduce external memory access,and a work-stolen mechanism to keep load balance among threads.Furthermore,we utilize the high bandwidth of flash array to accelerate graph processing efficiency.We made a detailed evaluation on real-world and synthetic data sets,the results show that HPGraph always outperforms GridGraph and can achieve up to 130% performance improvement.3.An in-memory graph analytics platform for many-core memory system-Ants.Compared with multi-core processors,many-core processors have more computing cores and can provide more parallel computing power.Meanwhile,the network interconnects between cores on processors are more complex.We design and implement an in-memory graph analytics platform on KNL server-Ants.It is mainly optimized for heterogeneous memory and cache-false sharing problem.Experiments show that our data partitioning mechanism can give full play to the respective advantages of heterogeneous memory,and task schedule strategy largely reduces the overhead of communication and memory access caused by cache-false sharing.Ants can achieve a maximum 9X acceleration ratio relative to the popular graph analytics platform-Ligra.Furthermore,we verify the applicability and effectiveness of the task schedule strategy on multi-core memory systems.4.An in-memory fast truss decomposition algorithm-pTD.Truss decomposition plays an important role in graph mining.After an in-depth analysis of truss decomposition steps,we find that the triangle counting operations in the initialization phase and computation phase are very similar.Thus,we propose a fast inmemory truss decomposition algorithm-pTD.We move up the triangle counting operations in the computation phase to initialize the support value of edges in the initialization phase and save the intermediate results for the computation phase as well.This method can help reduce the whole computation and processing time.We have built a high-speed flash array for the huge intermediate results and developed computation overlap with IO strategy for further optimization.Our experiments on real datasets verify that pTD can achieve a maximum 5X acceleration relative to the classical in-memory truss decomposition algorithm.