• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于Multi-GPU平台的大规模图数据处理

张珩, 张立波, 武延军

张珩, 张立波, 武延军. 基于Multi-GPU平台的大规模图数据处理[J]. 计算机研究与发展, 2018, 55(2): 273-288. DOI: 10.7544/issn1000-1239.2018.20170697
引用本文: 张珩, 张立波, 武延军. 基于Multi-GPU平台的大规模图数据处理[J]. 计算机研究与发展, 2018, 55(2): 273-288. DOI: 10.7544/issn1000-1239.2018.20170697
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
张珩, 张立波, 武延军. 基于Multi-GPU平台的大规模图数据处理[J]. 计算机研究与发展, 2018, 55(2): 273-288. CSTR: 32373.14.issn1000-1239.2018.20170697
引用本文: 张珩, 张立波, 武延军. 基于Multi-GPU平台的大规模图数据处理[J]. 计算机研究与发展, 2018, 55(2): 273-288. CSTR: 32373.14.issn1000-1239.2018.20170697
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. CSTR: 32373.14.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. CSTR: 32373.14.issn1000-1239.2018.20170697

基于Multi-GPU平台的大规模图数据处理

基金项目: 中国科学院战略性先导科技专项(XDA06010600)
详细信息
  • 中图分类号: TP316.4

Large-Scale Graph Processing on Multi-GPU Platforms

  • 摘要: 在GPU高性能节点上构建高效的大规模图数据的算法和系统已经日益成为研究热点,以GPU协处理器为计算核心不仅能够提供大规模线程的并行环境,也能提供高吞吐的内存和缓存访问机制.随着图的规模增大,相对大小局限的GPU的设备访存空间逐渐不能满足缓存整个图数据的应用需求,也催生了大量以单节点上外存I/O优化(out-of-core graph)为主要研究方向的大规模图数据处理系统.为了应对这一瓶颈,现有的算法和系统研究采用对图切分的压缩数据形式(即shards)用以数据传输和迭代计算.然而,这类研究扩展到Multi-GPU平台上往往性能的局限性表现在对PCI-E带宽的高依赖性,同时也由于Multi-GPU上任务负载不均衡而缺乏一定的可扩展性.为了应对上述挑战,提出并设计了基于Multi-GPU平台的支持高效、可扩展的大规模图数据处理系统GFlow.GFlow提出了全新的适用于Multi-GPU下的图数据Grid切分策略和双层滑动窗口算法,在将图的属性数据(点的状态集合、点/边权重值)缓存于各GPU设备之后,顺序加载图的拓扑结构数据(点/边集合)值各GPU中.通过双层滑动窗口,GFlow动态地加载数据分块从SSD存储至GPU设备内存,并顺序化聚合并应用处理过程中各GPU所生成的Updates.通过在9个现实图数据集上的实验结果可以看出,GFlow在Multi-GPU平台下相比其他支持外存图(out-of-core graph)处理的相关系统性能表现更为优异,对比CPU下的GraphChi和X-Stream分别提升25.6X和20.3X,对比GPU下支持外存图数据处理的GraphReduce系统单GPU提升1.3~2.5X.同时GFlow可扩展性在Multi-GPU上也表现良好.
    Abstract: 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.
  • 期刊类型引用(6)

    1. 郭晓龙,牛晋宇,杜永萍. 基于树莓派的高效卷积优化方法. 计算机技术与发展. 2023(05): 96-104 . 百度学术
    2. 辛明勇,祝健杨,徐长宝,姚浩,刘德宏. 基于循环神经网络的多核处理器层次化存储技术. 电子设计工程. 2023(22): 121-124+129 . 百度学术
    3. 王利伟,玄志武,徐洪洲,刘学. Windows环境下遥测数据并行拼接处理方法研究. 电子设计工程. 2021(02): 10-15 . 百度学术
    4. 孟慧玲,王耀彬,李凌,杨洋,王欣夷,刘志勤. TACLeBench中内核程序循环级推测并行性分析. 计算机应用. 2021(09): 2652-2657 . 百度学术
    5. 于海心,王晶,李晓锋. 基于改进RMS算法的多核嵌入式系统总线周期调度表优化设计. 火炮发射与控制学报. 2021(03): 71-75 . 百度学术
    6. 丁艳,张海文,孙永彦. 基于多网格技术的电网工程造价数据信息分析方法研究. 电子设计工程. 2021(19): 35-39 . 百度学术

    其他类型引用(8)

计量
  • 文章访问数:  1325
  • HTML全文浏览量:  4
  • PDF下载量:  1070
  • 被引次数: 14
出版历程
  • 发布日期:  2018-01-31

目录

    /

    返回文章
    返回