Research On Graph Processing System Scheduling For The CPU-GPU Heterogeneous Platform

Graph processing has a great potential to effectively solve extensive real-world problems,and GPU(Graph Processing Unit)based graph systems can offer surprisingly compelling speedups.Unfortunately,a wide spectrum of real-world graphs still cannot fit into the relatively ‘small' GPU memory to enjoy the high performance of in-memory computing.In this case,a large-scale graph must be partitioned into many subgraphs and streamed asynchronously to GPU.However,due to the frequently communication and redundant data transferring,graph systems based on heterogeneous architecture always show poor performance for the relative low-speed interface between CPU and GPU.Thus a novel GPU-accelerated graph processing system named Scaph has been presented.Scaph boosts performance significantly by reducing the amount of such redundant data transferred,thereby improving drastically the effective utilization of the CPU-GPU bandwidth.The key novelty of Scaph is to adaptively classify whether a subgraph is a high-value subgraph(amount of edges will be used for not only the current iteration but also the future iteration)or a low-value subgraph(otherwise)at each iteration.Scaph then schedules a sub-graph for graph processing on GPU using two graph schedule engines,one for high-value subgraphs,which will be streamed to GPU entirely and iterated over repeatedly,one for low-value subgraphs,for which a smaller subgraph containing all the necessary data for the current iteration will be constructed and transferred.Further,since the transferring data included in the low-value subgraph is constantly changing,Scaph adopts a fine-grained subgraph data manager to reduce the memory fragmentation and improve the utilization of global memory on GPU.A simple programming interface is also introduced to allow implementing the user-defined graph analysis on Scaph.Evaluation shows that Scaph outperforms the state-of-the-art heterogeneous graph systems by 3.16x(vs.Totem)and 6.82x(vs.Graphie),respectively.Further,Scaph shows better scalability compared with these works.Moreover,results also show that the valuebased differential scheduling optimization can significantly reduce the iteration times and total execution time with a wide spectrum of graphs and algorithms.