Gemini论文笔记_sparse push pull

论文地址：osdi16/osdi16-zhu.pdf

代码笔记：sanzo.top/Paper/Gemini

介绍

（1）Gemini采用稀疏-稠密、信号-槽抽象，将push-pull混合模型从共享内存扩展到分布式场景。

（2）基于块划分模式，是一种低开销的扩展设计同时保持了顶点的局部访问。

（3）采用压缩顶点索引的双模式

（4）基于NUMA感知的子分区使节点内的访问更加高效

（5）位置感知的块划分和细粒度的work-stealing同时提高了节点内和节点间的负载平衡。

图处理抽象

顶点保存信息，边是不可修改的对象。

支持双向边和单向边，双向边转化为一对有向边。

图处理的执行时通过顶点沿边的更新，知道图状态收敛或者达到指定的迭代次数。

活跃顶点是将要更新的顶点，活跃边是活跃顶点的出边。

双更新传播模型

在图处理过程中，活跃边可能是dense或sparse。

例如CC在开始的时候是dense，经过几次迭代之后大部分的点接受到他们最终的label就会变为sparse的状态；SSSP开始的时候是sparse，活跃顶点增多就会变成dense，当算法接近收敛再次变为sparse状态。

sparse更适合用push模式（更新沿着活跃点的出边传递），dense更适合pull模式（顶点的更新通过搜集入边顶点的状态）。

Gemini采用Ligra提出的一种在push和pull自适应切换的方法，阈值为$\frac{|E|}{20}$，区别在于Gemini将进行分区并分布到多个节点上，通过显式的消息传递进行通信和更新。

基于块的分区

上图的例子是将图上6个点，平均分为3个部分（白色为master，黑色为mirror），在dense模式下每个分区的mirror节点是分区中节点的出边邻居节点，这些mirror节点采用pull聚集当前分区节点的状态，然后更新远端的节点。

采用块划分可以很容易的通过边界判断节点的隶属关系，同时也简化了顶点数据表示，每个节点只负责实顶点数组的拥有部分并将其分配在连续的内存页中，不需要压缩顶点状态的空间消耗。

双模式的边表示

Gemini使用CSR和CSC表示图的状态，每个分区对边进行编号，sparse是指向分区的边，dense是当前分区指出的边。

通过Bitmap辅助sparse模式下的CSR的表示，标记指向当前分区的点，方便后续的判断。

采用双压缩辅助dense模式下的CSC的表示，保存当前分区指出的点vtx和对应边的偏移量。

位置感知的分区

Gemini的图分区同时考虑了顶点的局部性和边的密集型，根据$\alpha |V_i|+|E_i^D|$来进行划分，$\alpha =8\times (p-1)$。

NUMA感知的子分区

利用NUMA的内存访问特性，在每个节点继续对图进行划分，来减少远程CPU内存的访问。

协同调度

Gemini将集群中的节点通过MPI组成一个环，使计算和通信重叠。

对于第一个分区来说的调度来说，共分为三个阶段，Batch沿着分区编号递增的方向发送，沿着分区编号递减的方向接受。

细粒度的Working-Stealing

虽然节点间的负载均衡通过Gemini的局部块划分来保证，但是当分区变小就不能很好的保证分区的平衡。

基于块分区方案可以对连续的顶点进行处理，提高了缓存利用率和消息批处理，结合OpenMP，Gemini的每个线程首先完成自己core的分区任务，然后通过原子操作获取其他分区的任务进行处理，这样虽然带来了一些开销，但是提高了节点内部的负载平衡。

作者的实验环境是 8 nodes, 2 sockets per node, 12 cores per socket, and 64 vertices per mini-chunk。

实验

作者使用了5种算法进行测试：PageRank（PR）、connected components（CC）、single source shortest path（SSSP）、breadth first search（BFS）、betweenness centrality（BC），PR执行20次迭代，其余的执行到算法收敛。

同时于Power Graph、GraphX、PowerLyra、Ligra、Galois进行对比。

使用的数据集为：

在单个节点上Ligra、Galois、Gemini的对比：

Gemini在PR和BC上比其他系统性能好，在CC、SSSP、BFS上处在第二。

因为Gemini消息抽象（signal-slot）带来了额外的开销，尤其是计算任务少的算法（BFS），而其他系统访问活跃顶点的所有边，创建和活跃边成正比的成本，有效地掩盖了消息生成的开销。

另外其他的系统采用共享内存，可以很快的获取顶点最后的状态，而基于BSP通信机制的Gemini则需要经过多个迭代，存在滞后性。

在8个节点上的运行对比：

可以看出Gemini在不同算法和数据集上的运行速度远高于其他系统，最高有39.8x的提升。

在8个节点运行的内存消耗：

虽然Gemini需要存储两份边的信息供spare和dense模式使用，但是实际的内存得到很好的控制。

节点内的扩展性对比：

使用COST metrix得到Gemini需要3 cores才能超过优化过单线程的性能。

Gemini可以在2、4、8 cores下实现1.9、3.7、6.8倍的速度提升。

随着core的增加，core之间的负载均衡成为性能提升的挑战，Gemini仍然可以在12、24cores下带来9.4、15.5倍的提升。

节点间的扩展性对比：

上图是Gemini与扩展性表现最好的开源系统PowerLyra的对比。

在weibo-2013上Gemini和PowerLyra的扩展性相当，都是接近线性的增长。在小图wnwiki-2013两个系统表现的都不好。

在twitter-2010上Gemini在4个节点后扩展性很差，主要和顶点的索引访问和消息的产生/消费的瓶颈。随着节点的增加，每个分区的顶点数和边数都能显著减少，但是分区的mirror节点不能很快的减少，这就增加的处理的成本。

设计选择

对于Gemini的几个主要的设计，很难比较其中个别设计的贡献，而且当逐个添加这些优化到基准系统时，测试的表现收益取决于使用的顺序。

自适应的sparse/dense双模式

从图中可以看出，sparse和dense的性能差距十分显著，PR适合dense模式，CC开始适合dense模式当大多数节点保持活跃时适合sparse模式，对于SSSP，sparse在大多数迭代中更优于dense模式，除了许多顶点被更新的迭代。

Gemini可以采用更优的模式，在76次迭代的CC种有2次的误选，在172次迭代的SSSP有5次误选。这些误选都是发生在两种模式中间。

基于块的分区

chunking和hash（x % p）的性能对比：

多种分区方法的预处理和执行的时间对比：

有无NUMA的对比：

在不使用socket-level子分区的情况下，交错的内存分配保留对图拓扑，顶点的所有访问状态，以及跨两个套接字分配的消息缓冲区。 相反，应用套接字级别的子分区，远程内存访问已显着减少，因为
它们仅在working-stealing或访问其他套接字产生的消息时发生。

增强的顶点索引表示

相比于使用传统的CSR/CSC，使用Bitmap和双压缩的稀疏列可以减少19.4%-24.3%的内存。

负载均衡

Gemini的分区策略比只按照顶点或边的划分性能更高。

三种节点内负载均衡策略的性能对比：

静态的多核工作分区不能确保多核性能的有效利用，每个core预先计算和working-stealing的结合更完美。