3.3.3　图计算框架

图计算框架，基本上都遵循分布式同步（Bulk Synchronous Parallell，BSP）的计算模式。BSP模式的准则是批量同步（Bulk Synchrony），其独特之处在于超步（Superstep）概念的引入。如图3⁃20所示，一次计算过程由一系列全局超步组成。如图3⁃21所示，每一个超步包含并行计算（Local Computation）、全局通信（Communication）以及栅栏同步（Barrier Synchronisation，等待通信行为结束）三个阶段。

图3⁃20　超步

图3⁃21　超步三过程

BSP模式有以下几个特点：(https://www.daowen.com)

①将计算划分为一个一个的超步（Superstep），有效避免死锁。

②将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅仅完成点到点的消息传递，不提供组合、复制和广播等功能，这样做既掩盖具体的互连网络拓扑，又简化了通信协议。

③采用障碍同步的方式、以硬件实现的全局同步和可控的粗粒度级，是执行紧耦合同步式并行算法的有效方式。

基于BSP模式，比较成熟的图计算框架有 Pregel、GraphLab和Spark GraphX等。