整体同步并行计算模型

Viliant,Bill McColl提出的模型

整体同步并行计算模型(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个任务并行执行，一个处理器（计算节点）上存在若干个并行执行的任务，任务由若干个顺序执行的超级步组成。

特点

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

参数

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

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

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

有关术语

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

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

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省