Approaches For Efficient Concurrent Graph Processing On Heterogeneous Environment

Graph computing can excavate potential behaviors and relationships of things,which is widely used in service recommendation,fraud detection,venture capital analysis,marketing,disease modeling and other fields.With the development of the Internet,graph algorithms are emerging as the scale of graph explodes.Many graph algorithms concurrently process the shared graph structure which are called concurrent graph processing jobs.GPUs have higher parallel computing power than CPUs,so heterogeneous environment composed of CPUs and GPUs is more suitable for large-scale graph processing.However,in existing GPU-based graph processing systems,concurrent graph processing jobs access to the shared graph along different paths.Due to severe bandwidth competition and cache interference,they face low throughput.In order to solve the above problems,data-driven concurrent graph processing jobs execution mechanism is implemented to support efficient concurrent computing.Firstly,the asynchronous communication mechanism is established on a multi-GPU node to realize the asynchronous programming model of graph algorithms and avoid synchronous overhead of synchronous programming model.Secondly,the data-driven concurrent graph processing jobs execution mechanism is implemented in GPU.Specifically,graph structure is divided into partitions to load into cache along an order,and each graph partition is processed by multiple jobs concurrently.In addition,a scheduler for graph partitions is implemented to maximize the correlations of concurrent jobs.Finally,we assign priorities for vertices to reduce the redundant work that may arise from the asynchronous programming model.The experiment results show that the GPU-based graph computing system can reduce overhead of data access and improve the throughput of concurrent graph processing jobs compared with existing systems.