Research On Heterogeneous And Multi-core Graph Computing Systems

With the rapid development of Internet and the coming of big data era,the need to analyze massive and large volume of data becomes urgent.As an abstract data structure,many applications use graphs to represent large scale data in real scenarios,and use graph data structure to describe the relationships among data,such as mining relations in social networks,recommending goods in e-commerce systems,and analyzing the impact of traf-fic accidence on road networks.In addition,many unstructured data is often transformed to graphs for post processing and analysis.The research on large scale graph process-ing has become a hot topic in academia and industry.In recent years,many systems and state-of-the art techniques for graph computing are emerging(including distributed systems and heterogeneous systems),which propose new computing models or design high perfor-mance runtime systems,in order to adapt to the features of graph data such as large-scale,dynamically-changing and achieve high efficiency when processing big graph data.Based on these trends,designing and implementing high performance graph processing systems has important implications in theoretical research and application development.This article presents the work that has been conducted on heterogeneous and multi-core graph processing systems.Its main contributions are as follows.First,current endeavors on GPU-based graph computing can be classified as specialized graph computing systems and generalized graph computing frameworks.The former uses GPUs to on accelerate a certain graph algorithm such as breadth-first traversal.The latter focuses on the design of general frameworks that provides easy-to-use interfaces to develop different graph algorithms.There are many excellent achievements in both camps.How-ever,the differences and commonalities on the design,implementation,and optimization between these two kinds of systems are still unclear to us.How close is the performance of a generalized framework to a specialized system?Does specialized systems always outper-form generalized frameworks in all testing cases?Considering the different optimization ob-jective in these systems,which key metrics that are critical to performance should be selected for comparison of generalized and specialized systems?To answer these questions,the ar-ticle performs an in-depth analysis of two representative graph processing systems from the perspective of specialization and generalization.The experiments include the global perfor-mance evaluation and low-level measurement metric comparison.The results reveal several key issues in the design and implementation of GPU graph computing systems,which have important implications for future research.Second,from the perspective of programmability,existing GPU graph programming models are more complex,which involves too much low-level details and increases the diffi-culty in programming,as compared to traditional vertex-based models.In addition,from the performance perspective,current designs of GPU-based graph processing systems still have problems in balancing workload among GPU threads and in optimizing coalesced global memory accesses.To address these issues,the article proposes a new graph computing model for GPUs and presents the design and implementation of a high-performance GPU graph processing system.The new model is composed of two components:one is the edge compute function that is responsible for sending messages to the message buffer;the other is the vertex compute function that receives messages from the buffer and performs compu-tation based on these messages.Several key design choices and optimizations including the approximate sorting to optimize unbalanced workload,the column based data layout to opti-mize global memory access,and a high-performance runtime system optimized for complex hardware environments,make our system outperforms existing systems significantly.Third,existing single-machine graph processing systems focuses more on optimizing I/O access(disk or SSD)or memory access(in-memory graph processing systems),and pays less attention on the parallel programming model on multi-core systems.Thus,the achievable performance on such systems is limited.Based on multi-core processors,this article presents the design and implementation of a high performance single-machine graph processing system,which addresses three problems.The first is to exploit the features of multi-core processors to design a highly scalable programming model to avoid thread man-agement cost in operating systems and runtime systems.The second is to implement a highly efficient message passing based synchronous mechanism to cooperate with the new model.The last one is to design efficient data access pattern and memory mapping based I/O to achieve desired performance,inheriting the characteristics of programmability of existing systems.Our system achieves much higher performance as compared to the state-of-the-art.