• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Zhang Heng, Zhang Libo, WuYanjun. Large-Scale Graph Processing on Multi-GPU Platforms[J]. Journal of Computer Research and Development, 2018, 55(2): 273-288. DOI: 10.7544/issn1000-1239.2018.20170697
Citation: Zhang Heng, Zhang Libo, WuYanjun. Large-Scale Graph Processing on Multi-GPU Platforms[J]. Journal of Computer Research and Development, 2018, 55(2): 273-288. DOI: 10.7544/issn1000-1239.2018.20170697

Large-Scale Graph Processing on Multi-GPU Platforms

More Information
  • Published Date: January 31, 2018
  • GPU-based node has emerged as a promising direction toward efficient large-scale graph processing, which is relied on the high computational power and scalable caching mechanisms of GPUs. Out-of-core graphs are the graphs that exceed main and GPU-resident memory capacity. To handle them, most existing systems using GPUs employ compact partitions of fix-sized ordered edge sets (i.e., shards) for the data movement and computation. However, when scaling to platforms with multiple GPUs, these systems have a high demand of interconnect (PCI-E) bandwidth. They suffer from GPU underutilization and represent scalability and performance bottlenecks. This paper presents GFlow, an efficient and scalable graph processing system to handle out-of-core graphs on multi-GPU nodes. In GFlow, we propose a novel 2-level streaming windows method, which stores graph’s attribute data consecutively in shared memory of multi-GPUs, and then streams graph’s topology data (shards) to GPUs. With the novel 2-level streaming windows, GFlow streams shards dynamically from SSDs to GPU devices’ memories via PCI-E fabric and applies on-the-fiy updates while processing graphs, thus reducing the amount of data movement required for computation. The detailed evaluations demonstrate that GFlow significantly outperforms most other competing out-of-core systems for a wide variety of graphs and algorithms under multi-GPUs environment, i.e., yields average speedups of 256X and 203X over CPU-based GraphChi and X-Stream respectively, and 1.3~2.5X speedup against GPU-based GraphReduce (single-GPU). Meanwhile, GFlow represents excellent scalability as we increase the number of GPUs in the node.
  • Related Articles

    [1]Fu Liguo, Pang Jianmin, Wang Jun, Zhang Jiahao, Yue Feng. Formal Model of Correctness and Optimization on Binary Translation[J]. Journal of Computer Research and Development, 2019, 56(9): 2001-2011. DOI: 10.7544/issn1000-1239.2019.20180513
    [2]Zhou Zhibin, Wang Guojun, Liu Qin, Jia Weijia. A RFID Anonymous Grouping Proof Protocol Using Dual-Layer Verification[J]. Journal of Computer Research and Development, 2018, 55(12): 2674-2684. DOI: 10.7544/issn1000-1239.2018.20170787
    [3]Fu Yanyan, Zhang Min, Chen Kaiqu, Feng Dengguo. Proofs of Data Possession of Multiple Copies[J]. Journal of Computer Research and Development, 2014, 51(7): 1410-1416.
    [4]Li Tao, Zhang Jingzhong. Machine Proofs in Geometry Based on Complex Number Method[J]. Journal of Computer Research and Development, 2013, 50(9): 1963-1969.
    [5]Ma Yanfang, Zhang Min, Chen Yixiang. Formal Description of Software Dynamic Correctness[J]. Journal of Computer Research and Development, 2013, 50(3): 626-635.
    [6]Wang Yong, Fang Juan, Ren Xingtian, and Lin Li. Formal Verification of TCG Remote Attestation Protocols Based on Process Algebra[J]. Journal of Computer Research and Development, 2013, 50(2): 325-331.
    [7]Wang Changjing. Verifying the Correctness of Loop Optimization Based on Extended Logic Transformation System μTS[J]. Journal of Computer Research and Development, 2012, 49(9): 1863-1873.
    [8]Jing Shuxu, He Fazhi, Cai Xiantao, Cheng Yuan. A Method for Object Reference in Collaborative Modeling System[J]. Journal of Computer Research and Development, 2011, 48(11): 2031-2038.
    [9]Si Tiange, Tan Zhiyong, and Dai Yiqi. A Security Proof Method for Multilevel Security Models[J]. Journal of Computer Research and Development, 2008, 45(10): 1711-1717.
    [10]Wang Guilin, Qing Sihan. Security Notes on Two Cheat-Proof Secret Sharing Schemes[J]. Journal of Computer Research and Development, 2005, 42(11): 1924-1927.

Catalog

    Article views (1325) PDF downloads (1070) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return