整体同步并行计算模型

BSP是哈佛大学计算机科学家Leslie Valiant在1980年代开发的，决定性文章发表于1990年^[1]。

在1990年至1992年间，Leslie Valiant在普林斯顿和哈佛，与牛津大学的Bill McColl致力于分布式内存BSP编程模型的工作。在1992年至1997年间，McColl在牛津领导了一个大型研究组开发了各种BSP编程库、语言和工具，还有多种大规模并行BSP算法。随着兴趣和势头的增长，McColl接着领导了源自牛津、哈佛、佛罗里达、普利斯顿、贝尔实验室、哥伦比亚和乌特勒支的一个组织为BSP编程开发并在1996年出版了BSPlib标准。

Valiant在2000年代开发了BSP模型的一个扩展，在2011年出版为Multi-BSP模型^[2]。

在2017年，McColl开发了BSP模型的一个主要新扩展，提供了在AI、分析和HPC的大规模并行中的错误容忍和tail容忍^[3]。

BSP计算构成自：

1. 部件（component）：例如处理器，它们胜任处理及或（英语：And/or）局部内存事务，
2. 网络：它在成对的这种部件之间路由消息，
3. 屏障（barrier）：它是允许所有或子集的部件进行同步化的硬件设施。

这通常解释为可以跟进不同的计算线程的一组处理器，每个处理器配备了快速局部内存并用通信网络互连起来。BSP算法严重依赖第三个特征；计算是在一系列的全局“超级步骤”中行进的，它由三部分构成：

1. 并发计算：所有参与处理器可以进行本地计算，就是说每个处理器只能利用在这个处理器的快速本地内存内存储的数值。计算与所有其他计算异步发生但可以经由通信搭接（overlap）。
2. 通信：处理器相互之间交换数据来促成远程数据存储能力。
3. 同步：当一个处理器到达一个屏障点的时候，它一直等待到所有其他处理器也到达同样这个屏障。

计算和通信活动不必须在时间上依次安排。通信典型的采用单边的“put”和“get”直接远程内存访问（DRMA）调用的形式，而不用成对的双边“send”和“receive”消息传递调用。屏障同步化终结超级步骤：它确保所有单边通信都正确终结。基于双边通信的系统于每次消息发送中隐式包含了这种同步化代价。屏障同步的方法依赖于BSP计算机的硬件设施。在Valiant的最初论文^[1]中，这个设施周期的检查当前超级步骤的末端是否被全局性的到达了。这个检查的周期指示为${\displaystyle L}$ 。

这个模型展示在右侧的示意图中。进程不被当作有特定的线性次序（从左至右或反之），并可以按任何方式映射到处理器。

BSP模型通过对问题的超额分解和对处理器的超额认订，还非常适合于对分布式内存计算启用自动内存管理。计算被分开进入比实有的物理处理器更多的逻辑进程中，并且进程随机的被指派到处理器。这种策略在统计上可以证实会导致最佳的负载平衡，对于工作和通信二者都是如此。

在很多并行编程系统中，通信被认为是在个体行动的层面：发送和接收一个消息，内存到内存传送等。这是难于共事的，因为在并行编程中会有很多同时通信行动，而它们的交互典型的是复杂的。特别是，难于说出任何单一通信行动要完成到底要得花多少时间。

BSP模型认为通信行动是全体性的。这样做的效果是可以给出一组数据通信要花费的时间的上限。BSP把一个超级步骤的所有通信行动认作一个单元，并假定所有个体信息发送作为由固定大小的这个单元的一部分。

超级步骤的到来和外出信息的最大数目指示为${\displaystyle h}$ 。通信网络递送数据的能力通过参数${\displaystyle g}$ 来捕获，定义一个处理器花费时间${\displaystyle hg}$ 来递送大小为1的${\displaystyle h}$ 个消息。

发送长度${\displaystyle m}$ 的消息显然要比大小为1的消息用时更长。但是，BSP模型不区分长度${\displaystyle m}$ 的1个消息和长度1的 ${\displaystyle m}$ 个消息。在二者情况下代价都计为${\displaystyle mg}$ 。

参数${\displaystyle g}$ 依赖于下列因素：

• 在通信网络内用来交互的协议。
• 处理器和通信网络二者所做的缓冲区管理。
• 在网络中使用的路由策略。
• BSP运行时系统。

实际上，对于每个并行计算机${\displaystyle g}$ 的确定都是经验性的。注意${\displaystyle g}$ 不是规格化（normalise）的单字递送时间，而是在连续交通条件下的单字递送时间。

BSP模型的单边通信要求屏障同步。屏障是潜在的有代价的，但是避免了死锁或活锁的可能性，因为不能建立循环的数据依赖。检测并处理它们的工具是不需要的。

屏障同步的代价受到几个要素的影响：

• 参与进来的并行计算的完成时间上的变化所施加的代价。举例来说，除了一个之外的所有进程都完成了它们在这个超级步骤内的工作，并等待最后的那个进程，而它仍有很多工作要完成。一个实现能做的最好的事情是确保所有进程工作在大致相同的问题大小上。
• 所有处理器达到全局一致性状态的代价。这依赖于通信网络，但也依赖于是否有专门硬件用于同步化，并依赖于处理器处理中断的方式。

屏障同步的代价指示为${\displaystyle l}$ 。注意如果BSP计算机的同步化机制是Valiant建议的那样^[1]，则${\displaystyle l<L}$ 。实际上，${\displaystyle l}$ 值的确定是经验性的。

屏障在大型的计算机上是代价高昂的，并随着更大的规模而逐渐增大。已有关于从现存算法中去除同步点的大量文献，包括在BSP计算和此外的语境下。例如，很多算法允许对超级步骤的全局结束的局部检测，简单的通过将局部信息比较于已经收到了的消息的数目。相较于最小的要求的通信延迟，这驱使全局同步的代价可计为零^[4]。然而对将来的超级计算机架构和网络互连，这个最小延迟预期还会进一步增加；BSP模型，与其他并行计算模型一起，需要适应应对这种趋势。Multi-BSP^[2]是基于BSP的一种解决方案。

超级步骤的代价确定自三项之和：最长的运行的局部计算的代价，在处理器之间全局通信的代价，和在超级步骤结束处屏障同步的代价。${\displaystyle p}$ 个处理器的超级步骤的代价是：

${\displaystyle max_{i=1}^{p}(w_{i})+max_{i=1}^{p}(h_{i}g)+l}$ ，

这里的${\displaystyle w_{i}}$ 是进程${\displaystyle i}$ 中局部计算的代价，而${\displaystyle h_{i}}$ 是进程${\displaystyle i}$ 发送或接收的消息的数目。注意这里假定了同构处理器。更常见的表达式写为：

${\displaystyle w+hg+l}$ ，

这里的${\displaystyle w}$ 和${\displaystyle h}$ 取了最大值。算法的代价是每个超级步骤的代价的总和：

${\displaystyle W+Hg+Sl=\sum _{s=1}^{S}w_{s}+g\sum _{s=1}^{S}h_{s}+Sl}$ ，

这里的${\displaystyle S}$ 是超级步骤的数目。${\displaystyle W}$ 、${\displaystyle H}$ 和${\displaystyle S}$ 通常建模为函数，随着问题大小而变化。BSP算法的这三个特征通常采用渐进符号，比如${\displaystyle H\in O(n/p)}$ 。

• 如果一个处理器至多可以接收/发送消息的数目是h条，那么该模型就是“h-Relation”的。如果一个超级步中某个处理器的计算没有完成，那么下一个超级步就被分给该处理器继续进行。
• 所有PRAM上的算法均可在BSP上模拟，每个BSP处理器所能模拟的PRAM数目即成为并行宽松度（Slackness）。
• BSP放弃了程序局部性原理，从而简化的程序与实现的设计。这一点在并行计算中往往是一个好的特点，注意到一个大规模的计算中可能需要很多处理器，但实际上我们却不可能提供那么多处理器，于是一个处理器可能会被映射到多个虚拟进程，此时，附带的程序局部性原理反而会束缚处理器对存储器的访问。
• 选路器使用P2P的方式进行通信，从而有效的避免了网络拥塞。

对BSP的兴趣近年来有所飙升，Google通过Pregel这样的技术，将它接受为大规模的图分析的主要技术。还有就是新一代的Apache Hadoop将MapReduce模型与Hadoop下部构造的余下部分拆解开来，现有活跃的开源项目在Hadoop顶上增加显式的BSP编程，以及其他高性能并行编程模型，例如Apache Hama（英语：Apache Hama）^[5]和Apache Giraph。

BSP已经被很多作者扩展来致力解决BSP在建模特定架构或计算范型上的不适合性。其中一个例子是可分解BSP模型。这个模型已经用于一些新建的编程语言和接口中，比如整体同步并行ML（BSML）^[6]、BSPLib^[7] 、Apache Hama^[5]和Pregel^[8]。

BSPLib标准的著名实现，是Paderborn大学BSP库^[9]，和Jonathan Hill的牛津BSP Toolset^[10]。现代实现包括：在消息传递接口顶上模拟BSP的BSPonMPI^[11]，和以现代共享内存架构为目标的MulticoreBSP^[12][13]。C语言版MulticoreBSP，特别知名于它的开启嵌套BSP运行的能力，从而允许显式的Multi-BSP编程。

• 并行编程模型
• 同步屏障

• BSP Worldwide （页面存档备份，存于互联网档案馆）
• BSP related papers （页面存档备份，存于互联网档案馆）
• BSML official website （页面存档备份，存于互联网档案馆）
• Paderborn University BSP library
• BSPonMPI （页面存档备份，存于互联网档案馆）
• MulticoreBSP （页面存档备份，存于互联网档案馆）