Loading AI tools
来自维基百科,自由的百科全书
整体同步并行(Bulk Synchronous Parallel)抽象机器,是用来设计并行算法的计算模型,由哈佛大学莱斯利·瓦利安特提出,他希望像冯·诺伊曼体系结构那样,架起计算机程序语言和体系结构间的桥梁,故又称其为桥接模型(Bridging Model)。
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计算机构成自:
这通常解释为可以跟进不同的计算线程的一组处理器,每个处理器配备了快速局部内存并用通信网络互连起来。BSP算法严重依赖第三个特征;计算是在一系列的全局“超级步骤”中行进的,它由三部分构成:
计算和通信活动不必须在时间上依次安排。通信典型的采用单边的“put”和“get”直接远程内存访问(DRMA)调用的形式,而不用成对的双边“send”和“receive”消息传递调用。屏障同步化终结超级步骤:它确保所有单边通信都正确终结。基于双边通信的系统于每次消息发送中隐式包含了这种同步化代价。屏障同步的方法依赖于BSP计算机的硬件设施。在Valiant的最初论文中[1],这个设施周期的检查当前超级步骤的末端是否被全局性的到达了。这个检查的周期指示为。
这个模型展示在右侧的示意图中。进程不被当作有特定的线性次序(从左至右或反之),并可以按任何方式映射到处理器。
BSP模型通过对问题的超额分解和对处理器的超额认订,还非常适合于对分布式内存计算启用自动内存管理。计算被分开进入比实有的物理处理器更多的逻辑进程中,并且进程随机的被指派到处理器。这种策略在统计上可以证实会导致最佳的负载平衡,对于工作和通信二者都是如此。
在很多并行编程系统中,通信被认为是在个体行动的层面:发送和接收一个消息,内存到内存传送等。这是难于共事的,因为在并行编程中会有很多同时通信行动,而它们的交互典型的是复杂的。特别是,难于说出任何单一通信行动要完成到底要得花多少时间。
BSP模型认为通信行动是全体性的。这样做的效果是可以给出一组数据通信要花费的时间的上限。BSP把一个超级步骤的所有通信行动认作一个单元,并假定所有个体信息发送作为由固定大小的这个单元的一部分。
超级步骤的到来和外出信息的最大数目指示为。通信网络递送数据的能力通过参数来捕获,定义一个处理器花费时间来递送大小为1的个消息。
发送长度的消息显然要比大小为1的消息用时更长。但是,BSP模型不区分长度的1个消息和长度1的 个消息。在二者情况下代价都计为。
参数依赖于下列因素:
实际上,对于每个并行计算机的确定都是经验性的。注意不是规格化(normalise)的单字递送时间,而是在连续交通条件下的单字递送时间。
BSP模型的单边通信要求屏障同步。屏障是潜在的有代价的,但是避免了死锁或活锁的可能性,因为不能建立循环的数据依赖。检测并处理它们的工具是不需要的。
屏障同步的代价受到几个要素的影响:
屏障同步的代价指示为。注意如果BSP计算机的同步化机制是Valiant建议的那样[1],则。实际上,值的确定是经验性的。
屏障在大型的计算机上是代价高昂的,并随着更大的规模而逐渐增大。已有关于从现存算法中去除同步点的大量文献,包括在BSP计算和此外的语境下。例如,很多算法允许对超级步骤的全局结束的局部检测,简单的通过将局部信息比较于已经收到了的消息的数目。相较于最小的要求的通信延迟,这驱使全局同步的代价可计为零[4]。然而对将来的超级计算机架构和网络互连,这个最小延迟预期还会进一步增加;BSP模型,与其他并行计算模型一起,需要适应应对这种趋势。Multi-BSP[2]是基于BSP的一种解决方案。
超级步骤的代价确定自三项之和:最长的运行的局部计算的代价,在处理器之间全局通信的代价,和在超级步骤结束处屏障同步的代价。个处理器的超级步骤的代价是:
这里的是进程中局部计算的代价,而是进程发送或接收的消息的数目。注意这里假定了同构处理器。更常见的表达式写为:
这里的和取了最大值。算法的代价是每个超级步骤的代价的总和:
这里的是超级步骤的数目。、和通常建模为函数,随着问题大小而变化。BSP算法的这三个特征通常采用渐进符号,比如。
对BSP的兴趣近年来有所飙升,Google通过Pregel这样的技术,将它接受为大规模的图分析的主要技术。还有就是新一代的Apache Hadoop将MapReduce模型与Hadoop下部构造的余下部分拆解开来,现有活跃的开源项目在Hadoop顶上增加显式的BSP编程,以及其他高性能并行编程模型,例如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编程。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.