• 中国精品科技期刊
  • 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]Wang Qihong, Jia Hongjie, Huang Longxia, Mao Qirong. Semantic Contrastive Clustering with Federated Data Augmentation[J]. Journal of Computer Research and Development, 2024, 61(6): 1511-1524. DOI: 10.7544/issn1000-1239.202220995
    [2]Zhou Zhiping, Zhu Shuwei, Zhang Daowen. Multiobjective Clustering Algorithm with Fuzzy Centroids for Categorical Data[J]. Journal of Computer Research and Development, 2016, 53(11): 2594-2606. DOI: 10.7544/issn1000-1239.2016.20150467
    [3]Wu Yingjie, Tang Qingming, Ni Weiwei, Sun Zhihui, Liao Shangbin. A Clustering Hybrid Based Algorithm for Privacy Preserving Trajectory Data Publishing[J]. Journal of Computer Research and Development, 2013, 50(3): 578-593.
    [4]Hou Wei, Dong Hongbin, Yin Guisheng. A Membership Degree Refinement-Based Evolutionary Clustering Algorithm[J]. Journal of Computer Research and Development, 2013, 50(3): 548-558.
    [5]Chong Zhihong, Ni Weiwei, Liu Tengteng, and Zhang Yong. A Privacy-Preserving Data Publishing Algorithm for Clustering Application[J]. Journal of Computer Research and Development, 2010, 47(12).
    [6]Liang Jiye, Bai Liang, Cao Fuyuan. K-Modes Clustering Algorithm Based on a New Distance Measure[J]. Journal of Computer Research and Development, 2010, 47(10): 1749-1755.
    [7]Lü Zonglei, Wang Jiandong, Li Ying, and Zai Yunfeng. An Index of Cluster Validity Based on Modal Logic[J]. Journal of Computer Research and Development, 2008, 45(9): 1477-1485.
    [8]Zhang Gang, Liu Yue, Guo Jiafeng, and Cheng Xueqi. A Hierarchical Search Result Clustering Method[J]. Journal of Computer Research and Development, 2008, 45(3): 542-547.
    [9]Jin Yifu, Zhu Qingsheng, Xing Yongkang. An Algorithm for Clustering of Outliers Based on Key Attribute Subspace[J]. Journal of Computer Research and Development, 2007, 44(4): 651-659.
    [10]Zheng Xin and Lin Xueyin. Locality Preserving Clustering for Image Database[J]. Journal of Computer Research and Development, 2006, 43(3): 463-469.

Catalog

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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return