Parallel Programming on Graphs
这些课主要讲了关于图并行算法,包括pagerank等算法。
PageRank
PageRank 算法可以见https://en.wikipedia.org/wiki/PageRank#math_2
\[R[i]=\frac{1-\alpha}{N}+\alpha \sum_{j \text { linksto } i} \frac{R[j]}{\text { Outlinks }[j]} \]graph lab实现
![image-20221125124137531](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125124137531.png)
我没有使用过graphlab这个库,但是我猜测主要是,实现三个接口。
gather
用于实现pagerank的正向计算,也就是计算某个vertex的所有入边能够提供的rank贡献。
apply
用于更新当前点的rank值,也就是使用公式将gather的结果进行计算。
scatter
有点类似于反向更新,即当前vertex的rank值更新之后,同时去更新其邻居的值。(这里scatter_edges 返回NO_EDGES,意味着不需要更新其邻居)
这个实现的算法如何收敛?教授抛出的这个问题,我开始想法是直接执行多轮迭代就是可以收敛吗?但是其实还有更好的办法。
graphLab还提供了这个signal的功能,意味着将当前vertex加入到任务池中,或者说工作队列中。
基于signal算法,可以将外圈的迭代放到算法的执行中。使用一个count标识执行的轮数。如果小于10轮,那么将当前点放入到工作队列中继续执行。
![image-20221125124854489](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125124854489.png)
但是还可以利用scatter
,如果某个点的rank值进行了更新,那么就将其邻居vertex进行signal加入到工作队列。
![image-20221125125357350](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125125357350.png)
并行BFS
这里教授使用了Ligra作为了例子
![image-20221125142457708](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125142457708.png)
我上github一看,这个项目基本上已经死了。还有腾讯开源的图计算框架柏拉图也死了,有点好奇,这些图计算框架是现在都不做了,还是大公司当做自己的商业机密不在开源?
![image-20221125141555174](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125141555174.png)
每次利用frontier中的节点进行遍历,并行更新frontier,迭代执行EDGEMAP
直到遍历所有点。
对于稀疏图算法
![image-20221125141806632](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125141806632.png)
因为每个点都会加入一遍到result中,这样就会访问到所有点的记录,即所有出边。
对于稠密图算法
这里考虑的是出边,理想情况下,只需要执行一遍就可以遍历所有节点。
Graph sharding
如果对一个大图进行操作,可以无法将整张图完全放到内存中,这时候就需要对graph中sharding,这和数据库中的sharding思想很类似。
streaming graph computation
有一说一,这章节和我实习做的磁盘图索引优化工作关系挺大的。我们的需求也是当内存无法将图索引完全放入时候,就需要放入磁盘当中,因为ANNS的图算法的检索算法有点类似于BFS,这就会产生很多的4KB磁盘随机读,我们做的事情就是提升这个访问磁盘图索引的局部性。和这里教授提到的思想很接近,不过我们做的粒度更加小一点。
![image-20221125143717330](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125143717330.png)
把一部分点的所有入边放到同一个shard中,并且按照source vertex ID进行排序。
![image-20221125144424015](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125144424015.png)
![image-20221125144750151](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125144750151.png)
![image-20221125144759829](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125144759829.png)
图压缩
即对邻接表进行压缩
![image-20221125144931921](https://image-2021-wu.oss-cn-beijing.aliyuncs.com/image/image-20221125144931921.png)
我觉得不太靠谱。。。,但是教授说这样可以提高Cache的命中率,因为可以有更多数据放到cache中。