整体同步并行计算模型

维基百科,自由的百科全书
跳转至: 导航搜索

整体同步并行计算模型(Bulk Synchronous Parallel Computing Model),又名大同步模型BSP模型,由哈佛大学Viliant和牛津大学Bill McColl提出。

BSP的创始人是英国著名的计算机科学家Valiant,他希望像冯·诺伊曼体系结构那样,架起计算机程序语言和体系结构间的桥梁,故又称作桥模型(Bridge Model)。该模型使用了三个属性描述:模块(Components)、选路器(Router)和同步路障器执行时间L。

超级步(SuperStep)[编辑]

在一个超级步中,各处理器均执行局部操作,并且可以通过选路器接收和发送消息,如果一个处理器至多可以接收/发送消息的数目是h条,那么该模型就是h-Relation的。若设g为信道的带宽之倒数,那么容易得出,传送h条消息所需要的时间是gh+s。如果一个超级步中某个处理器的计算没有完成,那么下一个超级步就被分给该处理器继续进行。 注意,在实际计算中,g常常可用每秒处理器所能完成局部计算数目和每秒选路器传送数据量的比来代替。

并行宽松度(Parallel Slackness)[编辑]

所有PRAM上的算法均可在BSP上模拟,每个BSP处理器所能模拟的PRAM数目即成为并行宽松度。

其他特点[编辑]

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

参阅[编辑]

参考文献[编辑]

外部連結[编辑]