• 中国精品科技期刊
  • 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]Zhang Jing, Ju Jialiang, Ren Yonggong. Double-Generators Network for Data-Free Knowledge Distillation[J]. Journal of Computer Research and Development, 2023, 60(7): 1615-1627. DOI: 10.7544/issn1000-1239.202220024
    [2]Cheng Haodong, Han Meng, Zhang Ni, Li Xiaojuan, Wang Le. Closed High Utility Itemsets Mining over Data Stream Based on Sliding Window Model[J]. Journal of Computer Research and Development, 2021, 58(11): 2500-2514. DOI: 10.7544/issn1000-1239.2021.20200554
    [3]Li Xuebing, Chen Yang, Zhou Mengying, Wang Xin. Internet Data Transfer Protocol QUIC: A Survey[J]. Journal of Computer Research and Development, 2020, 57(9): 1864-1876. DOI: 10.7544/issn1000-1239.2020.20190693
    [4]Liu Bingyi, Wu Libing, Jia Dongyao, Nie Lei, Ye Luyao, Wang Jianping. Data Uplink Strategy in Mobile Cloud Service Based Vehicular Ad Hoc Network[J]. Journal of Computer Research and Development, 2016, 53(4): 811-823. DOI: 10.7544/issn1000-1239.2016.20151150
    [5]Wang Qiang, Li Xiongfei, Wang Jing. A Data Placement and Task Scheduling Algorithm in Cloud Computing[J]. Journal of Computer Research and Development, 2014, 51(11): 2416-2426. DOI: 10.7544/issn1000-1239.2014.20130749
    [6]Zhang Peng, Wang Guiling, Xu Xuehui. A Data Placement Approach for Workflow in Cloud[J]. Journal of Computer Research and Development, 2013, 50(3): 636-647.
    [7]Han Donghong, Gong Pizhen, Xiao Chuan, Zhou Rui. Load Shedding Strategies on Sliding Window Joins over Data Streams[J]. Journal of Computer Research and Development, 2011, 48(1): 103-109.
    [8]Liu Xuejun, Xu Hongbing, Dong Yisheng, Qian Jiangbo, Wang Yongli. Mining Frequent Closed Patterns from a Sliding Window over Data Streams[J]. Journal of Computer Research and Development, 2006, 43(10): 1738-1743.
    [9]Jin Hai, Luo Fei, Zhang Qin, and Zhang Hao. An Efficient Data Transfer Protocol for P2P-Based High Performance Computing[J]. Journal of Computer Research and Development, 2006, 43(9): 1543-1549.
    [10]Qian Jiangbo, Xu Hongbing, Wang Yongli, Liu Xuejun, Dong Yisheng. Simultaneous Sliding Window Join Approach over Multiple Data Streams[J]. Journal of Computer Research and Development, 2005, 42(10): 1771-1778.
  • Cited by

    Periodical cited type(8)

    1. 李清清,于欣宁,王海峰. GPU异构集群的协同计算引擎设计研究. 计算机应用与软件. 2024(12): 15-22+28 .
    2. 王庆桦. 动态数据处理平台分布式缓存替换算法仿真. 计算机仿真. 2020(02): 294-298 .
    3. 曲海成,于思淼,刘万军,王鑫源. 面向CUDA程序的性能预测框架. 电子学报. 2020(04): 654-661 .
    4. 张珩,崔强,侯朋朋,武延军,赵琛. 面向GPU平台的复杂网络core分解方法研究. 软件学报. 2020(04): 1225-1239 .
    5. 姜丽丽,李叶飞,豆龙龙,陈智麒,钱柱中. 面向大数据的图模式挖掘概率算法. 计算机应用研究. 2020(12): 3545-3551 .
    6. 杨世伟,蒋国平,宋玉蓉,涂潇. 基于GPU的稀疏矩阵存储格式优化研究. 计算机工程. 2019(09): 23-31+39 .
    7. 刘振鹏,薛雷,张彬,王雪峰. 最小延时问题GPU并行加速变邻域搜索方法. 科学技术与工程. 2018(29): 216-221 .
    8. 沈华峰,冯新扬,邵超. 一种云环境下图数据中带边权重的隐私保护方法. 电视技术. 2018(10): 30-33 .

    Other cited types(3)

Catalog

    Article views (1324) PDF downloads (1070) Cited by(11)

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return