Research On The Regularization Of Graph Algorithm And Its Processing Mechanism

Due to the importance of the analysis of the large-scale dynamic graph,many Timing iterative Graph Processing(TGP)jobs usually need to be generated for the processing of corresponding snapshots of the dynamic graph to get the results at different points of time.To improve the overall performance of dynamic graph processing,it is expected to run multiple TGP jobs concurrently.Although many GPU-based graph processing systems have been recently developed,for large-scale dynamic graphs,this concurrent way suffers from significant data access overhead due to the interference between these concurrently running jobs and a large volume of data transfer between CPU and GPU,which eventually incurs low GPU utilization ratio.In view of the above defects,this work noticed that the TGP jobs have strong temporal and spatial locality when they access different snapshots for their own processing,respectively,because most parts of the snapshots are the same and only a few parts are changing with time.It opens an opportunity for efficient concurrent execution of the TGP jobs by dramatically reducing CPU-GPU graph data transfer cost.Based on this observation,develop a large-scale dynamic graph processing system called EGraph is developed and can be integrated into existing GPU-accelerated static graph processing systems to make them efficiently support concurrent execution of TGP jobs on large-scale dynamic graphs with the help of GPU accelerators.Different from existing approaches,EGraph proposes an effective Loading-Processing-Switching(LPS)execution model.It is able to effectively reduce the overhead of CPU-GPU data transfer and ensures a higher GPU utilization ratio for efficient execution of the TGP jobs by fully utilizing the data access locality between the TGP jobs.To efficiently support the implementation of the LPS execution model,EGraph implements a structure-aware fine-grained dynamic graph management scheme to further reduce the redundant CPU-GPU data transfer cost,and supports the efficient concurrent processing of TGP jobs through the locality-aware dynamic graph concurrent processing scheme.Experimental results show that after integrating EGraph into the state-of-the-art outof-GPU-memory processing system,i.e.,Subway,the performance can be improved by 2.3-3.5 times.