我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 执行时间理论 >

简述bsp模型说明执行一个超级步的时间有哪几项决定

归档日期:06-24       文本归类:执行时间理论      文章编辑:爱尚语录

  Hama其实只提供了一个图计算框架,算法都是需要自己去实现的。理想的情况是图文件分块,Peer尽可载入本地文件作计算,这样即加快了图载入时间也减少了网络传输。不过事实是可能不能这样假设,为使结构尽更简单,对图的切割往往只是将结点用简单的Hash算法分布到Peer上,不能对图作任何局部聚类的假设。

  ● 它将处理器和路由器分开,强调了计算任务和通信任务的分开,而路由器仅仅完成点到点的消息传递,不提供组合、复制和广播等功能,这样做既掩盖具体的互连网络拓扑,又简化了通信协议;

  ● 采用障碍同步的方式以硬件实现的全局同步是在可控的粗粒度级,从而提供了执行紧耦合同步式并行算法的有效方式,而程序员并无过分的负担;

  ● 在分析BSP模型的性能时,假定局部操作可以在一个时间步内完成,而在每一个超级步中,一个处理器至多发送或接收h条消息(称为h-relation)。假定s是传输建立时间,所以传送h条消息的时间为gh+s,如果 ,则L至少应该大于等于gh。很清楚,硬件可以将L设置尽量小(例如使用流水线或大的通信带宽使g尽量小),而软件可以设置L的上限(因为L越大,并行粒度越大)。在实际使用中,g可以定义为每秒处理器所能完成的局部计算数目与每秒路由器所能传输的数据量之比。如果能够合适的平衡计算和通信,则BSP模型在可编程性方面具有主要的优点,而直接在BSP模型上执行算法(不是自动的编译它们),这个优点将随着g的增加而更加明显;

  ● 为PRAM模型所设计的算法,都可以采用在每个BSP处理器上模拟一些PRAM处理器的方法来实现。理论分析证明,这种模拟在常数因子范围内是最佳的,只要并行宽松度(Parallel Slackness),即每个BSP处理器所能模拟的PRAM处理器的数目足够大。在并发情况下,多个处理器同时访问分布式的存储器会引起一些问题,但使用散列方法可以使程序均匀的访问分布式存储器。在PRAM-EREW情况下,如果所选用的散列函数足够有效,则L至少是对数的,于是模拟可以达到最佳,这是因为我们想在p个物理处理器的BSP模型上,模拟个虚拟处理器,可将个虚拟处理器分配个每个物理处理器。在一个超级步内,v次存取请求可以均匀分布,每个处理器大约v/p次,因此计算机执行本次超级步的最佳时间为O(v/p),且概率是高的。同样,在v个处理器的PRAM-CRCW模型中,能够在p个处理器(如果 ),和的BSP模型上用O(v/p)的时间也可以达到最佳模拟。

  ● 在并行计算时,Valiant试图也为软件和硬件之间架起一座类似于冯o诺伊曼机的桥梁,它论证了BSP模型可以起到这样的作用,正是因为如此,BSP模型也常叫做桥模型;

  ● 一般而言,分布存储的MIMD模型的可编程性比较差,但在BSP模型中,如果计算和通信可以合适的平衡(例如g=1),则它在可编程方面呈现出主要的优点;

  ● 在BSP模型上,曾直接实现了一些重要的算法(如矩阵乘、并行前序运算、FFT和排序等),他们均避免了自动存储管理的额外开销;

  ● BSP模型可以有效的在超立方体网络和光交叉开关互连技术上实现,显示出,该模型与特定的技术实现无关,只要路由器有一定的通信吞吐率;

  ● 在BSP模型中,超级步的长度必须能够充分的适应任意的h-relation,这一点是人们最不喜欢的;

  ● 在BSP模型中,在超级步开始发送的消息,即使网络延迟时间比超级步的长度短,它也只能在下一个超级步才能使用;

  ● BSP模型中的全局障碍同步假定是用特殊的硬件支持的,这在很多并行机中可能没有相应的硬件;

本文链接:http://guidoon.com/zhixingshijianlilun/129.html