图计算计算与通信模式

图计算计算与通信模式图计算系统使用的通信模式主要分为两种,推动(Push)和拉取(Pull):(1) 推动模式下每个顶点沿着边向邻居顶点传递消息,邻居顶点根据收到的消息更新自身的状态

所有的类Pregel系统采用的几乎都是这种计算和通信模式

(2) 拉取模式通常将顶点分为主副本和镜像副本,通信发生在每个顶点的两类副本之间而非每条边连接的两个顶点之间

GraphLab、PowerGraph、GraphX等采用的均为这种模式

除了通信的模式有所区别,推动和拉取在计算上也有不同的权衡:(1) 推动模式可能产生数据竞争,需要使用锁或原子操作来保证状态的更新是正确的

(2) 拉取模式尽管没有竞争的问题,但是可能产生额外的数据访问

Gemini则将两种模式融合起来,根据每一轮迭代参与计算的具体情况,自适应地选择更适合的模式

以上内容由大学时代综合整理自互联网,实际情况请以官方资料为准。

相关