1并行计算模型分析

《1并行计算模型分析》由会员分享，可在线阅读，更多相关《1并行计算模型分析（39页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,并行处理及体系结构,实践部分,联系方式：,信息科学与工程学院计算机系,信息馆413 王璿,E-mail:,研究方向：并行计算、生物计算,主要参考文献,1 陈国良等编著 并行算法实践 2004年 高等教育出版社,2.Bary Wilkinson著 陆鑫达译 并行程序设计 2002年 机械工业出版社,3.Calvin Lin等著，陆鑫达译 并行程序设计原理 2009年 机械工业出版社,4.Brian Goetz等著，Java并发编程实战 2012 机械工业出版社,问题的并行求解过程,一个物理问题并行求解的最终目

2、的是将该问题映射到并行机上，这一物理上的映射是通过不同层次上的抽象映射来实现的。,在并行机上求解问题，首先要写出求解问题的并行算法。并行算法是在并行计算模型上设计出来的，而并行计算模型是从不同的并行计算机体系结构模型中抽象出来的。然后，根据并行算法进行并行程序设计。,为了达到将问题的并行求解算法转化为特定的适合并行计算模型的并行算法的目的。需要解决两方面的问题：,首先是问题的并行求解算法必须能够将问题内在的并行特征充分体现出来,，,否则并行求解算法将无法利用这些并行特征，从而使问题的高效并行求解成为不可能；,其次是并行求解模型要和并行计算模型尽量吻合，,这样，就为问题向并行机上的高效解决提供了

3、前提。,1 并行计算模型,什么是并行计算模型？,并行计算模型是并行计算机,基本特征的抽象,。并行计算模型从并行计算机中,抽取,若干个能够反映计算特征的可以计算或者可以测量的,参数,，按照,模型所定义的计算行为,构造成本函数，从而进行算法的性能分析，是算法设计和分析的基础。,编程模型,计算模型,体系结构模型,机器模型,用户,系统,1.1 PRAM模型,（,Parallel Random Access Machine,）,又称为SIMD-SM模型（共享存储的SIMD）。由Fortune和Wyllie1978年提出,。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。,

4、在PRAM中有一个,同步时钟,，所有操作都是同步进行的。,结构图,回顾：共享存储的多处理机模型,PRAM模型特点,优点：适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。,缺点：不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素,模型中使用了一个全局共享存储器，且局存容量较小，,不足以描述分布主存多处理机的性能瓶颈，,而且共享单一存储器的假定，,显然不适合于分布存储结构的MIMD机器,PRAM模型是同步的，因此，,所有的指令都按照锁步的方式,操作,，用户虽然感觉不到同步的存在，,但同步的存在的确很耗费时间,，,而且不能反映现实中很多系统的异步性,PRAM模型假设了每个

5、处理器可在单位时间访问,共享存储器的任一单元，因此要求处理机间通信无延迟、,无限带宽和无开销，略去了实际存在,比如资源竞争和有限带宽，这是不现实的,1.2 异步APRAM模型,基本概念,又称分相（Phase）PRAM或MIMD-SM。,每个处理器有其局部存储器、局部时钟、局部程序,；,无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障,。,计算过程：由同步障分开的全局相组成,计算时间,设局部操作为单位时间；全局读/写平均时间为d，,d随着处理器数目的增加而增加；,同步路障时间为B=B(p)非降函数。,满足关系,令 为全局相内各处理器执行时间

6、最长者，则APRAM上的计算时间为,优缺点：,易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。,回顾：分布式存储多处理机模型,1.3 BSP模型,基本概念,由Valiant(1990)提出的，其含义为“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统。块内异步并行，块间显示同步。,模型参数,p:处理器数(带有存储器）,g:路由器吞吐率,（也称为带宽因子 1/bandwidth）处理器模块之间点对点传递消息的路由器；,L:同步障时间,全局同步之间的时间间隔,；,计算过程,由若干超级步组成，每个超级步计算模式为右图,优缺点,强调了计算和通讯

7、的分离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多h条 消息的传递等。,1.4 LogP模型,基本概念,由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。,模型参数,L：network latency,o：communication overhead,g：gap=1/bandwidth,P：#processors,注：L和g反映了通讯网络的容量,（1）L(Latency),表示源节点与接收节点进行消息传递所需要的等待或延迟时间的上限。,（2）o(overhead),处理器发送或接收一个消息所需的处理时

8、间开销。,（3）g(gap),表示一台处理机连续两次发送或接收消息时的最小时间间隔，其倒数即每个处理器的有效通信带宽。,（4）P(Processor),处理机/存储器模块个数,LogP模型上设计的算法和BSP模型上相似，只是算法不再有超级步的概念。所有的进程异步地执行，通过消息传递显示地同步，处理器接收到消息后可以立即在后面计算中使用，充分利用了处理器的计算资源.,优缺点,捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。,BSP,LogP,：,BSP,块同步,BSP,子集同步,BSP,进程对同步,L

9、ogP,回顾：分布式共享存储多处理机模型,1.5 分层模型,属于分布共享存储模型，包括均匀存储层次UMH模型和分布存储层次DRAM（h）模型及层次并行存储HPM模型等。,分层计算模型可将单一模型中的功能按要求分配到模型不同的层次中，缓解单一计算模型的精确性与可用性之间的矛盾。分层后，各层次模型职能不同，目标单一，各负其责，易于设计和实现。,实例：四种并行计算模型上N体问题求解算法,N体问题及其串行算法,N 体问题可以描述如下:在一定的物理空间中,分布有N个粒子,每对粒子间都存在相互作用力(如万有引力、库仑力等)。它们从一个初始的状态开始,每隔一定的时间步,由于粒子间的相互作用,粒子的状态会有一

10、个增量,需要对粒子的加速度、速度、位置信息进行更新。下面给出N 体问题的串行算法。,r,算法1.1 N 体问题求解的串行算法,输入:空间中N 个粒子的状态信息,包括初始速度、位置等信息。,输出:给出经过一个时间步后所有N 个粒子的新的状态信息。,Begin,(1)读入N 个粒子的初始信息,(2)For,i=1 to N,For,j=1 to N,If,ij,Then,计算粒子j 对粒子i 的作用力,并且累加;,Endif,Endfor,Endfor,(3)For i=1 to N,根据牛顿定律,用(2)中计算出的粒子i 受到的力更新粒子i 的状态信息,Endfor,N个天体，每个天体计算N-1

11、次受力，因此需要计算N(N-1)次受力。因此算法复杂度为O(N,2,),算法1.2 PRAM模型上N 体问题求解并行算法,Begin,(1)每个处理器读入N/P 个粒子的初始信息,(2),For all Pi Where i0,P-1 Par-Do,For j=iN/P+1 to(i+1)N/P Do,For k=1 to N Do,If jk Then,计算粒子k 对粒子j 的作用力,并且累加;,Endif,Endfor,Endfor,Endfor,/粒子j 各处理器中的N/P个粒子,/k 共享存储器中的N个粒子,原来串行算法的计算量平均分配给P个处理器。因此算法复杂度为O(N,2,/P),

12、(3)For all Pi Where i0,P-1 Par-Do,For j=iN/P+1 to(i+1)N/P Do,根据牛顿定律,用(2)中计算出的粒子j 受到的力更新粒子j 的状态信息,Endfor,Endfor,P个处理器各自负责计算N/P个粒子的受力以及对这些粒子的状态进行更新。因为SM因此不考虑通讯。,假设：N=16 P=4,SM,N/P,P,0,N/P,P,1,N/P,P,2,N/P,P,3,14,58,912,1316,116,1N/P,N/P+12N/P,2N/P+13N/P,3N/P+14N/P,1N,算法1.3 APRAM模型上N 体问题求解的并行算法,Begin,(1

13、)每个处理器处理N/P 个粒子,读入N/P 个粒子的初始状态信息;,(2),每个处理器将其上N/P 个粒子写入到共享单元SM中;,(3)Barrier;/*实施路障同步*/,(4)For all Pi Where i0,P-1 Par-Do,For j=1 to N/P Do,For k=1 to P-1 Do,For l=1 to N/P Do,u=(i+k)%P(N/P)+1;,计算Pi 中粒子j 和共享单元中粒子k 之间的作用力,并且累加;,Endfor,Endfor,Barrier;/*实施路障同步*/,Endfor,Endfor,/粒子j 各处理器自己的N/P个粒子,/k 除自己之外

14、的其他P-1个处理器,/l 共享单元中其他处理器中的N/P个粒子,/u 防止多个处理器同时读取同一个共享单元，每个处理器对共享单元中读取顺序不同。,第（4）步处理本处理机与共享单元中粒子之间的受力。其中计算某个粒子N-1个受力时，有(P-1)N/P个要从共享单元中读取。,(5),For all Pi Where i0,P-1 Par-Do,计算Pi 中N/P 个粒子间的作用力,并且累加;,Endfor,(6)For all Pi Where i0,P-1 Par-Do,For j=1 to N/P,根据牛顿定律,用(5)中计算出的粒子j 受到的力,更新粒子j的状态信息,Endfor,Endfo

15、r,第（5）步处理本处理机N/P个粒子之间的受力。其中计算某个粒子N-1个受力时，有N/P个从本地存储单元中读取。,根据第4和5步，每个处理器的计算时间仍为O(N,2,/P)。但第4步中，每个处理器异步读写全局存储器，令全局读写开销为d。计算某个粒子N-1个受力时，有(P-1)N/P个要从共享单元中读取，则需要时间为d(P-1)N/P。,因此算法复杂度为 O(N,2,/P)+d N,SM,LM,1N/P,LM,N/P+12N/P,P,0,P,1,P,2,P,3,1N/P,s,0,N/P+12N/P,s,1,2N/P+13N/P,s,2,3N/P+14N/P,s,3,LM,2N/P+13N/P,

16、LM,3N/P+14N/P,(2),(4)计算Pi 中粒子j 和共享单元中粒子k 之间的作用力,并且累加;,这里 u=(i+k)%P(N/P)+1;,i=0 k=1 u=(0+1)%4N/P+1=N/p+1,k=2 u=(0+2)%4N/P+1=2N/p+1,k=3 u=(0+3)%4N/P+1=3N/p+1,因此，P,0,号处理器读取共享存储器的顺序为s1,s2,s3,同理，P,1,号读取顺序为s2,s3,s0；P,2,号读取顺序为s3,s0,s1；,P,3,号读取顺序为s0,s1,s2,（4）,（5）处理本处理机N/P个粒子之间的受力,（5）,算法1.4 BSP模型上N 体问题并行算法,Begin,(1)每个处理器处理N/P 个粒子,读入N/P 个粒子的初始状态信息;,(2)For all Pi Where i0,P-1 Par-Do,计算Pi 内部粒子间的作用力;,Pi 把其内N/P 个粒子的状态信息发送给其右邻居;,Endfor,(3),Barrier,;,内部N/P个粒子受力计算(N/P),(N/P-1)，然后将本地N/P个粒子的状态信息发送,通讯时间为（N/P）,g。,则第