1(中国科学院软件研究所 北京 100190); 2(中国科学院大学 北京 100049) (zhangheng@nfs.iscas.ac.cn)
出版日期: 2018-02-01基金资助:中国科学院战略性先导科技专项(XDA06010600)Large-Scale Graph Processing on Multi-GPU Platforms
Zhang Heng1,2, Zhang Libo1, WuYanjun11(Institute of Software, Chinese Academy of Sciences, Beijing 100190); 2(University of Chinese Academy of Sciences, Beijing 100049)
Online: 2018-02-01摘要/Abstract
摘要： 在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上也表现良好.
参考文献
相关文章 9
| [1] | 林霄, 姬硕, 岳胜男, 孙卫强, 胡卫生. 面向跨数据中心网络的节点约束存储转发调度方法[J]. 计算机研究与发展, 2021, 58(2): 319-337. |
| [2] | 王一舒,袁野,刘萌,王国仁. 大规模时序图数据的查询处理与挖掘技术综述[J]. 计算机研究与发展, 2018, 55(9): 1889-1902. |
| [3] | 谢承翰,陆赛杰,王皓,彭力. 无线传感器网络中基于事件驱动的输出反馈控制[J]. 计算机研究与发展, 2017, 54(11): 2639-2645. |
| [4] | 刘冰艺,吴黎兵,贾东耀,聂雷,叶璐瑶,汪建平. 基于移动云服务的车联网数据上传策略[J]. 计算机研究与发展, 2016, 53(4): 811-823. |
| [5] | 王强, 李雄飞, 王婧. 云计算中的数据放置与任务调度算法[J]. 计算机研究与发展, 2014, 51(11): 2416-2426. |
| [6] | 张 鹏, 王桂玲, 徐学辉,. 云计算环境下适于工作流的数据布局方法[J]. , 2013, 50(3): 636-647. |
| [7] | 王卓薇, 许先斌, 赵武清, 何水兵, 张玉萍,. 基于GPU的GRAPES模型并行加速及性能优化[J]. , 2013, 50(2): 401-411. |
| [8] | 赵鹏 李思昆. SoC数据映射中的快速应用程序存储分析方法[J]. , 2010, 47(2): 361-369. |
| [9] | 金 海 罗 飞 章 勤 张 浩. 一个基于P2P高性能计算的高效数据传输协议[J]. , 2006, 43(9): 1543-1549. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3629
