计算机科学

首页 > 计算机科学

整体同步并行计算模型

2018-09-03 09:37:22     所属分类:并发计算

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

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

目录

  • 1 超级步(SuperStep)
  • 2 并行宽松度(Parallel Slackness)
  • 3 其他特点
  • 4 参阅
  • 5 参考文献
  • 6 外部链接

超级步(SuperStep)

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

并行宽松度(Parallel Slackness)

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

其他特点

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

参阅

  • 并行计算

参考文献

  • Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, Volume 33 Issue 8, Aug. 1990

外部链接

  • 西安交通大学科系统所:并行计算、并行控制和并行信号处理算法[失效链接]
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/340460.html

上一篇:执行时间
下一篇:超线程
相关推荐