EGraph: Efficient Concurrent GPU-Based Dynamic Graph Processing
Article
Zhang, Yu, Liang, Yuxuan, Zhao, Jin, Mao, Fubing, Gu, Lin, Liao, Xiaofei, Jin, Hai, Liu, Haikun, Guo, Song, Zeng, Yangqing, Hu, Hang, Li, Chen, Zhang, Ji and Wang, Biao. 2023. "EGraph: Efficient Concurrent GPU-Based Dynamic Graph Processing." IEEE Transactions on Knowledge and Data Engineering. 35 (6), pp. 5823-5836. https://doi.org/10.1109/TKDE.2022.3171588
| Article Title | EGraph: Efficient Concurrent GPU-Based Dynamic Graph Processing |
|---|---|
| ERA Journal ID | 17876 |
| Article Category | Article |
| Authors | Zhang, Yu, Liang, Yuxuan, Zhao, Jin, Mao, Fubing, Gu, Lin, Liao, Xiaofei, Jin, Hai, Liu, Haikun, Guo, Song, Zeng, Yangqing, Hu, Hang, Li, Chen, Zhang, Ji and Wang, Biao |
| Journal Title | IEEE Transactions on Knowledge and Data Engineering |
| Journal Citation | 35 (6), pp. 5823-5836 |
| Number of Pages | 14 |
| Year | 2023 |
| Publisher | IEEE (Institute of Electrical and Electronics Engineers) |
| ISSN | 1041-4347 |
| 1558-2191 | |
| Digital Object Identifier (DOI) | https://doi.org/10.1109/TKDE.2022.3171588 |
| Web Address (URL) | https://ieeexplore.ieee.org/abstract/document/9767630 |
| Abstract | In many applications of the analysis of dynamic graph, many Timing iterative Graph Processing (TGP) jobs usually need to be generated for the processing of the corresponding snapshots of the dynamic graph to obtain the results at different points of time. For high throughput of such applications, it is expected to run the TGP jobs on the GPU concurrently. Although many GPU-based systems have been recently developed, for out-of-GPU-memory dynamic graph processing, this concurrent way suffers from significant data access overhead due to a large volume of data transfer between CPU and GPU and the interference between these concurrently running jobs, which eventually incurs low GPU utilization ratio. In this work, we observed that the TGP jobs have strong temporal and spatial similarity when they access different snapshots for their own processing as most parts of the snapshots are the same and only a few parts are changing with time. It creates ideal opportunities for efficient concurrent execution of the TGP jobs by dramatically reducing CPU-GPU graph data transfer cost. Based on this observation, we develop the first GPU-based dynamic graph processing system EGraph , which can be integrated into the existing out-of-GPU-memory static graph processing systems to enable them to efficiently support concurrent execution of TGP jobs on dynamic graphs with the help of GPU accelerators. Different from the existing approaches, we propose in EGraph 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 similarity between the TGP jobs. Experimental results show that the existing GPU-accelerated systems achieve performance improvements of 2.3-3.5 times after being integrated with EGraph. |
| Keywords | data access cost; GPU; dynamic graph processing; throughput |
| ANZSRC Field of Research 2020 | 460999. Information systems not elsewhere classified |
| Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
| Byline Affiliations | Huazhong University of Science and Technology, China |
| University of Southern Queensland | |
| Zhejiang Lab, China |
Permalink -
https://research.usq.edu.au/item/z274q/egraph-efficient-concurrent-gpu-based-dynamic-graph-processing
62
total views0
total downloads4
views this month0
downloads this month