基于GPU的大规模图计算系统与应用
|||
作者介绍：钟健龙博士，2013年毕业于Xtra, 现供职于GraphSQL Inc，主要研究兴趣为GPU计算、高性能数据处理与分析。本文主要用于学术交流，所发言论不代表所供职的单位。
大规模图数据（graph data）的计算与存储是当下工业界和学术界都非常热门的话题。就在一周前，美国苹果公司两亿美元低调收购了成立只有三年之久的机器学习公司Turi，布局人工智能和机器学习领域。而Turi的起源正是图计算领域大名鼎鼎的GraphLab【1】项目。从Turi官网可以看到Turi的产品主要运用在推荐系统、顾客精确细分、反欺诈等领域。这些领域面临的数据往往缺乏结构（unstructured data）而且内部关系紧密而复杂，传统的关系数据库面对这种类型的数据非常吃力，尤其是当今数据规模越来越巨大。本文的主角，像GraphLab、Pregel【2】这类把数据存成图结构的并行图计算框架（Parallel Graph Processing Framework），却能为这种数据的提供实时或者准实时的处理性能。
Xtra小组从2010年开始进行并行图计算框架的研究，我们选择的突破方向是引入计算性能比传统CPU强悍千百倍的GPU（Graphics Processing Unit）。2013年我们发布了世界上首个完全基于GPU的并行图数据处理框架Medusa【3】, 并且开源于https://github.com/JianlongZhong/Medusa, “Medusa: Building GPU-based Parallel Sparse Graph Applications with Sequential C/C++ Code”.
Medusa解决了两个核心问题：1. 如何让不懂GPU编程的人可以用上GPU的强悍性能处理图数据；2. 如何让图计算问题尽可能高效地运行在GPU上。
尽管CUDA/OpenCL这类编程环境已经让GPU编程开始“平民化”，但是由于GPU架构的复杂性（成千上万的核心和复杂的内存系统），高效地运用GPU往往需要比较长的学习周期（这也是为什么很多人刚开始用GPU写出来的程序甚至还不如单线程的CPU程序快）。Medusa提供了六个简洁的API，用来操作图数据的顶点和边以及数据交换。这些API都是跟CPU编程无异的串行C/C++程序。Medusa内部自动地将这些串行的程序转换成并行的GPU程序，当然这些转换都是对用户透明的；用户只需要会写C程序，就能使用Medusa。
图计算的另一个挑战是其天生的“不规则性”。首先，图数据自身非常不规则，每个顶点可能带有不同的数据，不同数量的边和邻居顶点，等等。对GPU体系结构有了解的童鞋应该都知道，GPU“喜欢”的是规则的运算（矩阵计算，图像图形计算等）。要让不规则的图计算跑在GPU上并且保证GPU能被充分利用是一件非常困难的事情。Medusa从体系结构和编程模型上提出了一些列的创新来保证图计算在GPU上的高效运行。
使用Medusa写出的图计算程序，不经优化一般可以比单核CPU要快一到两个数量级。从Medusa的第一版原型出来已经过去三年多，现在看来，Medusa的最大贡献也许不是我们提出的各种优化技巧和编程模型创新，而是证明了引入GPU来解决图问题的可行性。我们也看到很多出色的后续工作在开展。
其他相关工作：Medusa使用了BSP（Bulk-Synchronous-Parallel），很多机器学习的应用使用异步的迭代计算模型往往能更快达到收敛。在Medusa以后，有不少系统对GPU上的图计算进行进一步的提高和改进。
在Xtra小组参与合作的华中科技大学的Frog项目（http://grid.hust.edu.cn/xhshi/projects/frog.html）巧妙的运用了graph coloring来实现GPU上的异步图计算：
（图片来自于http://grid.hust.edu.cn/xhshi/projects/frog.html）
来自加州大学戴维斯分校的Gunrock项目（http://gunrock.github.io/gunrock/doc/latest/index.html）同样是一个完全运行在GPU上的并行图计算框架。Gunrock基本延续了Medusa的思路，在编程模型和算法实现上做了更深的优化，在某些应用上取得了数倍好于Medusa的性能。
（图片来自于blazegraph.com）
基于GPU的图数据处理解决方案已经成功商业化：美国新创公司BlazeGraph（www.blazegraph.com）的基于GPU加速的图数据库（声称比CPU内存图数据库快100倍）的很多技术都可以在他们的论文（MapGraph: A High Level API for Fast Development of High Performance Graph Analytics on GPUs, GRADES'14）中看到。MapGraph也参考了Medusa的实现，我们的成果也是间接服务了工业界啊:-)
（图片来自于blazegraph.com）
图计算的挑战和机遇：我们认为基于GPU的图计算系统还有很多没有解决的具有挑战性的研究问题，主要是来自于图的新应用和GPU新特征。a) 如何有效的处理动态图结构，b) 如何利用新的架构特点例如Pascal GPU的HBM, mixed precision compute, NV-Link. HBM将会有512GB/S of memory bandwidth。
【1】https://en.wikipedia.org/wiki/GraphLab
【2】Pregel: a system for large-scale graph processing, Grzegorz Malewicz, et al, SIGMOD '10
【3】[TPDS’2014] Jianlong Zhong* and Bingsheng He. Medusa: Simplified Graph Processing on GPUs. IEEE TPDS: IEEE Transactions on Parallel and Distributed System, vol.25, no.6, pp.1543-1552, June 2014, doi: 10.1109/TPDS.2013.111.Author: Jianlong Zhong (edited by Bingsheng He)
http://blog.sciencenet.cn/blog-3224193-996943.html