一、什么是BSP模型
概述
BSP(Bulk Synchronous Parallel，整体同步并行计算模型)是一种并行计算模型，由英国计算机科学家Viliant在上世纪80年代提出。Google发布的一篇论文(《Pregel: A System for Large-Scale Graph Processing》)使得这一概念被更多人所认识，据说在Google 80%的程序运行在MapReduce上，20%的程序运行在Pregel上。和MapReduce一样，Google并没有开源Pregel，Apache按Pregel的思想提供了类似框架Hama。
并行计算模型介绍
并行计算模型通常指从并行算法的设计和分析出发，将各种并行计算机（至少某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。从更广的意义上说，并行计算模型为并行计算提供了硬件和软件界面，在该界面的约定下，并行系统硬件设计者和软件设计者可以开发对并行性的支持机制，从而提高系统的性能。
常用的并行计算模型有：PRAM模型、LogP模型、BSP模型、C3模型、BDM模型。
二、BSP模型基本原理
BSP模型是一种异步MIMD-DM模型（DM: distributed memory，SM: shared memory），BSP模型支持消息传递系统，块内异步并行，块间显式同步，该模型基于一个master协调，所有的worker同步(lock-step)执行, 数据从输入的队列中读取，该模型的架构如图所示：
另外，BSP并行计算模型可以用 p/s/g/I 4个参数进行描述：
P为处理器的数目(带有存储器)。
s为处理器的计算速度。
g为每秒本地计算操作的数目/通信网络每秒传送的字节数，称之为选路器吞吐率，视为带宽因子 (time steps/packet)=1/bandwidth。
i为全局的同步时间开销,称之为全局同步之间的时间间隔 (Barrier synchronization time)。
那么假设有p台处理器同时传送h个字节信息，则gh就是通信的开销。同步和通信的开销都规格化为处理器的指定条数。
BSP计算模型不仅是一种体系结构模型，也是设计并行程序的一种方法。BSP程序设计准则是整体同步(bulk synchrony)，其独特之处在于超步(superstep)概念的引入。一个BSP程序同时具有水平和垂直两个方面的结构。从垂直上看,一个BSP程序由一系列串行的超步(superstep)组成,如图所示:
这种结构类似于一个串行程序结构。从水平上看，在一个超步中，所有的进程并行执行局部计算。一个超步可分为三个阶段，如图所示:
本地计算阶段，每个处理器只对存储本地内存中的数据进行本地计算。
全局通信阶段，对任何非本地数据进行操作。
栅栏同步阶段，等待所有通信行为的结束。
三、BSP模型特点
1. BSP模型将计算划分为一个一个的超步(superstep)，有效避免死锁。
2. 它将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅仅完成点到点的消息传递，不提供组合、复制和广播等功能，这样做既掩盖具体的互连网络拓扑，又简化了通信协议；
3. 采用障碍同步的方式以硬件实现的全局同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员并无过分的负担；
4. 在分析BSP模型的性能时，假定局部操作可以在一个时间步内完成，而在每一个超级步中，一个处理器至多发送或接收h条消息（称为h-relation）。假定s是传输建立时间，所以传送h条消息的时间为gh+s，如果 ，则L至少应该大于等于gh。很清楚，硬件可以将L设置尽量小（例如使用流水线或大的通信带宽使g尽量小），而软件可以设置L的上限（因为L越大，并行粒度越大）。在实际使用中，g可以定义为每秒处理器所能完成的局部计算数目与每秒路由器所能传输的数据量之比。如果能够合适的平衡计算和通信，则BSP模型在可编程性方面具有主要的优点，而直接在BSP模型上执行算法（不是自动的编译它们），这个优点将随着g的增加而更加明显；
5. 为PRAM模型所设计的算法，都可以采用在每个BSP处理器上模拟一些PRAM处理器的方法来实现。
四、BSP模型的评价
1. 在并行计算时，Valiant试图也为软件和硬件之间架起一座类似于冯·诺伊曼机的桥梁，它论证了BSP模型可以起到这样的作用，正是因为如此，BSP模型也常叫做桥模型。