计算机研究与发展

作者：张珩,张立波,武延军,

关键词：大规模图数据, multi-GPU, 图分块, 双层滑动窗口, 数据传输,

在GPU高性能节点上构建高效的大规模图数据的算法和系统已经日益成为研究热点，以GPU协处理器为计算核心不仅能够提供大规模线程的并行环境，也能提供高吞吐的内存和缓存访问机制.随着图的规模增大，相对大小局限的GPU的设备访存空间逐渐不能满足缓存整个图数据的应用需求，也催生了大量以单节点上外存I/O优化(out-of-coregraph)为主要研究方向的大规模图数据处理系统.为了应对这一瓶颈，现有的算法和系统研究采用对图切分的压缩数据形式(即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-coregraph)处理的相关系统性能表现更为优异，对比CPU下的GraphChi和X-Stream分别提升25.6X和20.3X，对比GPU下支持外存图数据处理的GraphReduce系统单GPU提升1.3~2.5X.同时GFlow可扩展性在Multi-GPU上也表现良好.

来源：2018年第2期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2018年第2期