茶年 · 中文维基百科

整体同步并行

Wikipedia · 2025-12-26 维基百科 👁 1 阅读

整体同步并行（Bulk Synchronous Parallel）抽象机器，是用来设计并行算法的计算模型，由哈佛大学莱斯利·瓦利安特提出，他希望像冯·诺伊曼体系结构那样，架起计算机程序语言和体系结构间的桥梁，故又称其为桥接模型（Bridging Model）。

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

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

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

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

模型
BSP计算机构成自：

部件（component）：例如处理器，它们胜任处理局部内存事务，

网络：它在成对的这种部件之间路由消息，

同步设施：它是允许所有或子集的部件进行同步化的硬件设施。

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

并发计算：所有参与处理器可以进行本地计算，就是说每个处理器只能利用在这个处理器的快速本地内存内存储的数值。计算与所有其他计算异步发生但可以经由通信搭接（overlap）。

通信：处理器相互之间交换数据来促成远程数据存储能力。

屏障同步：当一个处理器到达一个屏障点的时候，它一直等待到所有其他处理器也到达同样这个屏障。

计算和通信活动不必须在时间上依次安排。通信典型的采用单边的“put”和“get”直接远程内存访问（DRMA）调用的形式，而不用成对的双边“send”和“receive”消息传递调用。屏障同步化终结超级步骤：它确保所有单边通信都正确终结。基于双边通信的系统于每次消息发送中隐式包含了这种同步化代价。屏障同步的方法依赖于BSP计算机的硬件设施。在Valiant的最初论文中。然而对将来的超级计算机架构和网络互连，这个最小延迟预期还会进一步增加；BSP模型，与其他并行计算模型一起，需要适应应对这种趋势。Multi-BSP和Apache Giraph。

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

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

参阅

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

引用
外部連結

#计算模型 #并行计算

评论 (0)

  • 还没有评论，来抢沙发吧。