• 中国精品科技期刊
  • 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
shu
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
shu
张珩, 张立波, 武延军. 基于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
shu
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
shu

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

  • 1(中国科学院软件研究所 北京 100190)

  • 2(中国科学院大学 北京 100049) (zhangheng@nfs.iscas.ac.cn)

基金项目: 中国科学院战略性先导科技专项(XDA06010600)
详细信息

  • 中图分类号: TP316.4

Large-Scale Graph Processing on Multi-GPU Platforms

  • 1(Institute of Software, Chinese Academy of Sciences, Beijing 100190)

  • 2(University of Chinese Academy of Sciences, Beijing 100049)

HTML全文

    摘要
  • 摘要: 在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.
    • HTML全文
    • 参考文献(0)
    • 相关文章
    • 施引文献(63)

  • 期刊类型引用(30)

    1. 马超红，郝新丽，孟小峰，张旭康. 机器学习赋能的多维数据查询处理研究综述. 计算机学报. 2025(01): 100-123 . 百度学术
    2. 姜璐璐，高锦涛. 面向机器学习的数据库参数调优技术综述. 计算机工程与应用. 2024(03): 1-16 . 百度学术
    3. 刘帅，乔颖，罗雄飞，赵怡婧，王宏安. 时序数据库关键技术综述. 计算机研究与发展. 2024(03): 614-638 . 本站查看
    4. 赖思超，吴小莹，彭煜玮，彭智勇. 数据库索引调优技术综述. 计算机研究与发展. 2024(04): 929-954 . 本站查看
    5. 朱镕佳，杨宇轩，李振东，陈硕，唐朝阳，唐晓雨. 基于树莓派的智能零售系统设计. 现代信息科技. 2024(19): 189-192+198 . 百度学术
    6. 蔡盼，张少敏，刘沛然，孙路明，李翠平，陈红. 智能数据库学习型索引研究综述. 计算机学报. 2023(01): 51-69 . 百度学术
    7. 曹蓉，鲍亮，崔江涛，李辉，周恒. 数据库系统参数调优方法综述. 计算机研究与发展. 2023(03): 635-653 . 本站查看
    8. 杨荣利，王伟，杨栋，周东阳. 基于两因素模糊时间序列的一次风机指标预测. 电子设计工程. 2023(07): 91-94+99 . 百度学术
    9. 唐楚哲 ，王肇国 ，陈海波 . 机器学习方法赋能系统软件：挑战、实践与展望. 计算机研究与发展. 2023(05): 964-973 . 本站查看
    10. 张政，段怡，高志峰，张欢. 机器学习在手术中液体治疗的应用. 中国数字医学. 2023(07): 81-85 . 百度学术
    11. 杜维柱，张晓华，卢毅，王书渊，沈彦伶. 基于机器学习与数值预报技术的电网短期临近气象预警模型设计. 电子设计工程. 2023(19): 99-103 . 百度学术
    12. 曹卫东，金超. 基于birch聚类的可更新机器学习索引模型. 计算机工程与设计. 2023(11): 3328-3334 . 百度学术
    13. 王鹏. “智慧工会”实现路径. 科技资讯. 2022(02): 10-12 . 百度学术
    14. 张静，农昌瑞，张海兵，张亚周. 基于深度学习的发动机叶片故障检测技术. 航空发动机. 2022(01): 68-75 . 百度学术
    15. 孟小峰，余艳. 在跨学科交叉融合中深发展社会计算与社会智能. 计算机科学. 2022(04): 3-8 . 百度学术
    16. 欧群雍，谭同德，冯学晓. 基于机器学习的软件定义网络数据流子序列匹配算法. 国外电子测量技术. 2022(04): 70-76 . 百度学术
    17. 杜清华，张凯. 一种高效的跨平台工作流优化方法. 计算机工程. 2022(07): 13-21+28 . 百度学术
    18. 姬莉霞，赵耀，马郑祎，赵润哲，张晗. 基于iForest-BiLSTM-Attention的数据库负载预测方法. 郑州大学学报(理学版). 2022(06): 66-73 . 百度学术
    19. 张洲，金培权，谢希科. 学习索引:现状与研究展望. 软件学报. 2021(04): 1129-1150 . 百度学术
    20. 潘璇，徐思涵，蔡祥睿，温延龙，袁晓洁. 基于深度学习的数据库自然语言接口综述. 计算机研究与发展. 2021(09): 1925-1950 . 本站查看
    21. 蒙芳，翟建丽. 学习行为大数据可视化的网络数据库学习仿真. 计算机仿真. 2021(09): 216-220 . 百度学术
    22. 陈镭. 基于机器学习的数据库系统自动调参研究. 软件导刊. 2021(11): 148-151 . 百度学术
    23. 崔栋，温巧燕，张华，王华伟. QML：一种混合空间索引结构. 通信学报. 2021(12): 1-16 . 百度学术
    24. 陶镇威. 基于机器学习的Oracle数据库故障预测技术探索. 现代工业经济和信息化. 2020(02): 70-71 . 百度学术
    25. 桂树强，周实，张家季，耿欣. 基于BIM的轨道交通项目管理框架体系研究与实践. 人民长江. 2020(03): 147-152 . 百度学术
    26. 宋雨萌，谷峪，李芳芳，于戈. 人工智能赋能的查询处理与优化新技术研究综述. 计算机科学与探索. 2020(07): 1081-1103 . 百度学术
    27. 陈珂锐，孟小峰. 机器学习的可解释性. 计算机研究与发展. 2020(09): 1971-1986 . 本站查看
    28. 唐吉深，覃少华. 大型数据库重复记录检测与优化研究. 现代电子技术. 2020(17): 77-81 . 百度学术
    29. 蔡洪浩，罗应华，张荣鑫，杨喻淳. 基于机器学习的智能光电对抗系统. 电子技术与软件工程. 2020(13): 79-80 . 百度学术
    30. 陶姿邑. 基于深度学习的数据库重复记录检测算法. 微型电脑应用. 2020(12): 174-176 . 百度学术

    其他类型引用(33)

    • 资源附件(0)
计量
  • 文章访问数:  1324
  • HTML全文浏览量:  4
  • PDF下载量:  1070
  • 被引次数: 63
出版历程
  • 发布日期:  2018-01-31

目录

摘要
HTML全文
    参考文献(0)
    相关文章
    施引文献(63)
    资源附件(0)

    /

    返回文章
    返回
    邮件订阅 RSS
    微信订阅号<br/>（实时资讯）

    微信订阅号
    （实时资讯）

    微信服务号<br/>（同步网站）

    微信服务号
    （同步网站）

    微信视频号<br/>（视频分享）

    微信视频号
    （视频分享）

    CCF<br/>（扫码入会）

    CCF
    （扫码入会）

    版权所有 © 《计算机研究与发展》编辑部

    本系统由北京仁和汇智信息技术有限公司开发  百度统计