[科普中国]-整体同步并行计算模型-

整体同步并行计算模型(Bulk Synchronous Parallel Computing Model)，又名大同步模型或BSP模型，由哈佛大学Viliant和牛津大学Bill McColl提出。BSP的创始人是英国著名的计算机科学家Valiant，他希望像冯·诺伊曼体系结构那样，架起计算机程序语言和体系结构间的桥梁，故又称作桥模型(Bridge Model)。该模型使用了三个属性描述：模块(Components)、选路器（Router）和同步路障器执行时间。

定义整体同步并行计算模型（BSP模型）是由美国 Havard 大学的 L.G.Valiant教授在 1992 年作为一种并行计算模型提出的。BSP模型类似于一个并行随机存取模型，与之不同的是，他并不强调通信和同步。分析一个BSP算法的重要部分在于量化同歩和通信的需求。BSP模型把并行计算抽象为H个模块：处理器集合、发送消息的全局通讯网络、各处理器间的路障同步机制。BSP模型中并行计算的基本执行单元是超级步。一个BSP程序包含多个超级步，通过消息机制实现超级步中各个计算任务间的信息传递。在各超级步中，每个处理器均执行本地计算，并通过选路器接收和发送消息；然后进行全局检查，确定所有的处理器是否都己经完成该超级步；若是，则进入到下一超级步，否则下一个周期被分配给未完成的超级步。BSP模型迭代执行每一个超级步直到满足终止条件或者达到一定的超级步数强制终止。每一个超级步由本地计算，全局通信和路障同步兰个阶段组成。一个BSP程序通常有n个任务并行执行，一个处理器（计算节点）上存在若干个并行执行的任务，任务由若干个顺序执行的超级步组成1。

特点整体同步并行计算模型主要有以下几个特点：

创新的给出超步的概念，每一个超步均代表 BSP 模型中一次完整的并行计算过程，整个运算过程包含若干个串行超步，超步包含本地计算过程、运算节点间通讯过程和同步过程。超步中的三个阶段是严格串行的，即所有处理机本地计算结束后统一进行通讯过程，最后执行同步阶段。除此之外，每个运算单元在一个超步内只能传递或接收一次数据。该模型的实现中，所有的处理机 processor 节点由一个 Master 节点进行协调，来完成上述三个阶段2。

BSP放弃了程序局部性原理，从而简化的程序与实现的设计。这一点在并行计算中往往是一个好的特点，注意到一个大规模的计算中可能需要很多处理器，但实际上我们却不可能提供那么多处理器，于是一个处理器可能会被映射到多个虚拟进程，此时，附带的程序局部性原理反而会束缚处理器对存储器的访问。

选路器使用P2P的方式进行通信，从而有效的避免了拥塞。BSP模型将处理器和路由器分开，即将汁算任务和通信任务分开。路由器仅仅完成点到点的消息传递，并不提供组合、复制和广播等功能，这样做既掩盖了互连网的具体拓扑结构，又简化了通信协议。采用路障同步的方式实现的全局同步是在可控的粗粒度级别，从而提供了一种有效的方式执行紧耕合同步式并行算法，而程序员并不需要太多的负担。

参数BSP 模型包括以下四个主要参数：

L：时间周期（period）

g：路由（router）的吞吐量，即消息发送或接收所需时间

p：物理处理器数量

v：虚拟处理器数量

每经过L时间，Master 节点就会检查超步内所有处理机上的任务是否已经执行完毕。如果均执行结束，就开始下一个超步过程或结束程序的运行；如果没有结束，就会申请另一个L周期，直到所有任务都执行完毕。通常，时间周期L可以看作两个连续超步间最小的时间间隔。软件层面和硬件层面对时间周期的要求正好相反，软件层面要求时间周期L大一些，这样在编程过程中方便实现扩展性；而硬件方面则要求时间周期L尽可能的小，以提升执行的效率。为了提高处理器利用率，设计程序时应使每个超步内所有处理器的处理时间尽可能接近 L，使得每个运算单元完成自己的任务后不必长时间等待其他运算单元，尽快开始执行下一超步的任务。

通常路由网络传递消息具有 h-relation 限制，即每个组件最多接收或发送 h 条消息。h-relation 限制是对通讯过程的抽象描述，假设每个处理机最多发送 out 个消息到其他处理机，且每个处理机最多从其他处理机接收 in 个消息，那么 h-relation 限制可以描述为ℎ = 𝑜𝑢𝑡 @ 𝑖𝑛，其中@表示一种二维运算，通常为取最大值操作和加法操作。传统BSP 模型的超步中，严格遵循计算阶段在前，通讯阶段在后的顺序，并且障碍同步阶段是阻塞的。所以，相邻超步间是严格串行的。Rodrı́guez C 等人给出了“异步超步”（A-BSP）的概念，即去除超步内的障碍同步阶段，使多个超步之间可以异步运行，从而提升整个程序的并行程度以及运算单元的利用率。但是，该模型中超步结束之后需要进行阻塞式通讯，这样就隐含了一个同步过程。

有关术语本地计算；一个或多个处理器参与本地计算。计算发生在每一个参与计算的节点上，每个节点只使用存储在本地存储器上的数据，该些数据是在程序启动时加载数据阶段或上一个超级步的全局通信时放在本地存储器上的数据。每台处理器上的计算是独立的，从这个意义上看节点间的执行是异步的。

全局通信；某个处理器向其他处理器发出通信请求，每个处理器发送或等待消息。消息在节点之间进行交换。这种交换是单方面的以点对点的方式进行的。

路障同步；当一个任务执行完本地计算到达同步点时，它会等待其他所有的任务完成计算。本超级步中所有的数据通信在本次同步后生效，并提供给下一个超级步使用。当所有的通信结束后，确保每个处理器均执行完当前超级步中所有的计算和通信，并且通信过程中各处理器间的数据交换均已完成，然后进入到下一轮迭代。这种同步方式可避免死锁和数据竞争问题。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学