[PPOPP 15] PoweSwitch: 基于同步异步切换的分布式大规模图处理系统学习总结

- 日理万妓 2022-05-22 03:35 195阅读 0赞

今天要讲的文章PPOPP 2015年的一篇文章，SYNC or ASYNC Time to Fuse for Distributed Graph-Parallel Computation。本文主要想解决的问题就是：作者仔细分析了同步模式和异步模式的优势和劣势。同步模式批量发送消息,大大提高网络利用率。由于消息被批量发送，同步模式更加适合于消息通信量大的算法（IO敏感型），并且每个顶点上的计算是轻量级的。异步模式能够加速程序的收敛。并且它十分适合CPU敏感型的算法。并且有些图处理算只适合异步模式。然后作者对于图收敛的进展情况，提出了吞吐量的概念。吞吐量具体就是指单位时间内，活跃顶点执行的数量。作者对于不同的图算法进行了性能测试，作者发现在一个图算法中。不同的时期会适合不同的执行模式。有的时期适合做同步，比如活跃顶点的数量较多。有的时期适合做异步模式。但是现有的工作都只采用同步执行模式或者异步执行模式。针对这个问题：作者提出了PowerSwitch，Hybrid Executions混合执行模式。Hsync将一系列的执行程序分成多个时间间隔（epochs），并定期评估下一个时期模式切换的潜在益处。 监视使用模式的速度，预测未来模式的速度。 在每个时间间隔，Hsync采用同步或异步模式来调度和更新顶点。

## 1.BackGround ##

图结构的计算广泛应用于不同的应用场景。比如说社交媒体Twitter每天发送4亿条Twitter文、Facebook用户关系、flickr图片关系、YouTube视频数据。

![70][]

## 2.图并行计算 ##

现有的图计算都采用一种“Think as Vertex”以顶点为中心的计算。每个图计算的程序都在做一种以顶点为中心的点程序。图计算的特征有连接的数据集，就是图数据的依赖。顶点的随机数据访问，图计算一般都是一种迭代收敛算法。分布式图计算都是用来支持大规模图数据以及复杂的计算和存储支持。

分布式图计算用户定义了一组图计算逻辑。首先输入图数据，图数据包括顶点和邻居边。然后经过一系列迭代算法后最后图数据达到收敛状态。现有的图处理框架都首先都采用负载均衡的算法，将大图数据均匀的放置在不同的机器中进行迭代计算。集群然后进行调度计算，直到整个图数据收敛。

## 3.同步和异步执行模式 ##

### 3.1 同步执行模式 ###

同步模式即相邻两步迭代之间存在同步控制，所有任务均完成该步的工作之后，才可以启动下一次迭代计算，发往第k次迭代的消息仅在第k次迭代时对顶点可见。同步执行模式在两次相邻的迭代之间，存在Barrier的限制，所有任务均完成该步的工作之后，才可以启动下一次迭代计算。在正在的同步计算模式实现下，同步模式下使用两个位图来相应地识别当前和下一次迭代中的活跃顶点。当消息激活顶点时，位图会更新。迭代后，所有消息都已处理完毕，并且每个Worker中的两个位图被翻转。

**优势：**批量发送消息,大大提高网络利用率。由于消息被批量发送，同步模式更加适合于消息通信量大的算法（IO敏感型），并且每个顶点上的计算是轻量级的。

**   缺点：**

1.在大多数图算法中，同步模式存在迭代计算收敛不对称的缺点。这意味着大多数顶点会很快的收敛在少部分的迭代后。然而存在一些顶点收敛速率很慢，需要很多轮的迭代计算。

2.同步模式不适用于一些图处理算法：图着色算法旨在使用最少的颜色将不同的颜色分配给相邻的顶点。在贪婪的实现中，所有的顶点同时选择最小的颜色。因为具有相同颜色的相邻顶点将根据相同的之前颜色来同时来回地选取相同的颜色。

![70 1][]

### 3.2 异步执行模式 ###

异步模式即相邻两步迭代之间不存在同步控制，各任务独立进行迭代计算，不存在相互等待。在迭代过程中，当消息到达接收方后，目的顶点可以立即启动计算处理，并广播新的计算结果，而不必同步等待所有顶点均收到所有消息数据。对于异步模式，这里有一个全局优先级（例如FIFO）队列调度活跃顶点。每个Worker线程都有一个本地待处理队列来保存停滞的活跃顶点，这可能会等待来自相邻顶点的消息的响应。

**优势：**

1.异步模式能够加速程序的收敛。并且它十分适合CPU敏感型的算法。

2.并且有些图处理算只适合异步模式

**缺点：**

1.异步模式存在顶点lock contention开销。对于相邻顶点来说，异步模式通过分开调用Gather、Apply、Scatter阶段来避免数据竞争，也就是说其中某个顶点程序会被lock，需要等待相邻顶点某个阶段执行完成。

2.异步模式频繁的发送消息，CPU不断的封装TCP\\IP包，浪费了CPU的利用率。

![70 2][]

## 4. 实验分析同步异步执行模式 ##

![70 3][]

作者对于不同的图算法进行了性能测试，作者发现在一个图算法中。不同的时期会适合不同的执行模式。有的时期适合做同步，比如活跃顶点的数量较多。有的时期适合做异步模式。但是现有的工作都只采用同步执行模式或者异步执行模式。没有一种执行模式适合所有的算法。所以作者提出了PowerSwitch：基于切换的分布式大规模图处理系统。

## 5. How to Switch ##

既然在整个图计算收敛的过程中，不同的计算模式有着不同的性能特征。作者提出了在不同的阶段采用最适合当前计算模式的执行。那么现在问题就是如何进行高效的切换？

![70 4][]

当从同步执行模式切换到异步模式的时候，同步模型的下一次迭代的bitmap中的所有活跃顶点都将导入到异步模式中的去全局队列中去。

当从异步执行模式切换到同步模式的时候，PowerSwitch禁止所有工作线程从全局队列获取新顶点，然后将全局队列中的所有顶点中的所有活跃顶点导入到Sync引擎中当前顶点的位图，直到所有计算在待处理的活动顶点计算完成之后。

## 6. When to Switch ##

既然解决了高效的两个执行模式切换的问题。那么现在问题就是什么时候进行切换？作者提出了一种切换模型Switch Timing。

![70 5][]

作者根据采用同步的执行速率和采用异步的执行速率比较，然后选择相应最优的同步执行模式或者异步执行模式。

## 7. Architecture ##

![70 6][]

## 8. Evaluation ##

![70 7][]

[70]: /images/20220522/1c2dc831b9b1469793ef01860c291052.png
[70 1]: /images/20220522/637b3c60cd204870930981219c7a757c.png
[70 2]: /images/20220522/03a9f3694e434abc8a655f02af78ad97.png
[70 3]: /images/20220522/c665ed1bb655494c97eb0cc3c238de4b.png
[70 4]: /images/20220522/26528c28c6934eb1a83e16235b364d94.png
[70 5]: /images/20220522/6267d305c3e24e16b3bbae587265e733.png
[70 6]: /images/20220522/36eeb24c11694fa086ce7b614555a3e0.png
[70 7]: /images/20220522/a6774ac9b38a4bbaa2000007cbf9987e.png