并行算法的抽象模型.ppt

《并行算法的抽象模型.ppt》由会员分享，可在线阅读，更多相关《并行算法的抽象模型.ppt（41页珍藏版）》请在三一办公上搜索。

1、并行算法的抽象模型,并行算法的定义和分类,并行算法的定义算法并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。并行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法,并行算法的表达,描述语言可以使用类Algol、类Pascal等；在描述语言中引入并行语句。并行语句示例Par-do语句（Do in parallle）算法要并行执行 for i=1 to n par-do end forfor all语句（几个处理器同时执行相同的操作）for all Pi,where 0ik end for,并行算法的复杂性度量,串行算法的复杂性度量

2、最坏情况下的复杂度(Worst-CASE Complexity)期望复杂度(Expected Complexity)并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。处理器数p(n)并行算法成本c(n):c(n)=t(n)p(n)总运算量W(n):并行算法求解问题时所完成的总的操作步数。,并行算法的复杂性度量,Brent定理令W(n)是某并行算法A在运行时间T(n)内所执行的运算量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n)时间内执行完毕。W(n)和c(n)密切相关P=O(W(n)/T(n)时，W(

3、n)和c(n)两者是渐进一致的对于任意的p，c(n)W(n)一个算法在运行过程中，不一定都能充分地利用有效地处理器去工作。,并行算法的同步,同步概念同步是在时间上强使各执行进程在某一点必须互相等待；可用软件、硬件和固件的办法来实现。同步语句示例算法4.1 共享存储多处理器上求和算法 输入：A=(a0,an-1),处理器数p 输出：S=ai Begin(1)S=0(2.3)lock(S)(2)for all Pi where 0ip-1 do S=S+L(2.1)L=0(2.4)unlock(S)(2.2)for j=i to n step p do end for L=L+aj End end

4、 for end for,并行算法的通信,通信（使用通信原语）共享存储多处理器使用：global read(X,Y)和global write(X,Y)分布存储多计算机使用：send(X,i)和receive(Y,j)通信语句示例算法4.2 分布存储多计算机上矩阵向量乘算法 输入：处理器数p,A划分为B=A1.n,(i-1)r+1.ir,x划分为w=w(i-1)r+1;ir 输出：P1保存乘积AX Begin(1)Compute z=Bw(2)if i=1 then yi=0 else receive(y,left)endif(3)y=y+z(4)send(y,right)(5)if i=1

5、then receive(y,left)End,抽象模型的概念,并行计算模型通常指从并行算法的设计和分析出发，将各种并行计算机（至少某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。从更广的意义上说，并行计算模型为并行计算提供了硬件和软件界面，在该界面的约定下，并行系统硬件设计者和软件设计者可以开发对并行性的支持机制，从而提高系统的性能。,并行计算机的抽象模型,并行计算机的理论模型是从物理模型抽象的；为开发并行算法提供了一种方便的框架；用这些模型可求得并行计算机的理论性能界限；可在芯片制作前估算芯片区的VLSI复杂性和执行时间。,一、时间与空间复杂性计算机求解一个规模为s的问题的算

6、法复杂性取决于：执行时间存储空间,时间复杂性：时间复杂性g(s)为O(f(s)，可读作“数量级为f(s)”，如存在正的常量c和s0，则对所有ss0的非负值就有g(s)cf(s)。,空间复杂性为问题规模s的函数。渐近空间复杂性(asymptotic spacecomplexity)主要与大问题的数据存储有关，而程序(代码)存储的需求和输入数据的存储不考虑在内。串行算法的时间复杂性简称为串行复杂性;并行算法的时间复杂性就称为并行复杂性;并行复杂性应比串行复杂性低，至少是相近。只考虑确定性算法。,并行随机存取机模型(Parallel RandomAccess Machine，PRAM)目的：可用来开

7、发并行算法和分析可扩展性及复杂性。,PRAM模型,基本概念由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。结构图,在PRAM上的一个并行程序由n个进程组成，其中第i个进程留驻在第i个处理器上，且由一串指令所组成。在每个基本时间步(称为周期)，每个处理器执行一条指令。这些指令包括数据传送、算/逻、控制流以及I/O指令，在典型的顺序计算机中均有这些指令。,1.同构性规模为1的PRAM退化为传统的RAM。这种机器为SISD。当处理器多于1个时，一个PRAM将访问多个数据流，且通常可执行多个指令流。因

8、此PRAM是一个MIMD机器。,址空间 PRAM模型所有进程对所有存储单元均有相等的访问时间-均匀存储器访问(UMA)模型。针对多计算机不合适-在多计算机中，每个处理机有它自己的分离地址空间。这些机器被称为具有多地址空间。多计算机的处理机间通信不是通过共享变量，而是借助消息传递。,存储器模型各种方案的主要区别在于如何协调CW的冲突。四种PRAM模型方案都与存储器读写如何处理有关。(1)EREW-PRAM模型这种模型禁止一台以上处理机同时读、写同一存储单元(Snir，1982；Karp和Ramachandran，1988)。这是限制最大的PRAM模型。(2)CREW-PRAM模型用互斥使写冲突避

9、免。可以并行读同一存储单元。,(3)ERCW-PRAM模型允许互斥读或并行写同一存储单元。(4)CRCW-PRAM模型允许在同一时刻并行读或者并行写。,PRAM模型,分类PRAM-CRCW并发读并发写CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入 PRAM-CREW并发读互斥写 PRAM-EREW互斥读互斥写 计算能力比较PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模拟

10、PRAM-CREW和PRAM-CRCW,与物理模型的差异 实际上，这种并行计算机是不存在的。共享存储器SIMD机是与PRAM模型最接近的结构。更确切地说，共享存储的同步MIMD模式运行。,四种PRAM方案中，EREW和CRCW是应用最普遍的模型。每个CRCW算法可用一个EREW算法来模拟。CRCW算法比一个等效的EREW要快，经证明，最好的n处理机EREW算法要比任一个n-处理机CRCW算法慢O(logn)倍。对研究结构规则的并行性来说，用PRAM比用实际机器模型要好得多。PRAM能指出实际并行计算机性能的上限。,PRAM模型,优点适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同

11、步等细节。缺点不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素,异步APRAM模型,基本概念又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。,异步PRAM模型APRAM是一个异步的PRAM模型，简记为APRAM模型特点：由p个处理器组成；每个处理器都有其本地存储器、局部时钟和局部程序；处理器间的通信经过共享全局存储器；无全局时钟各处理器异步地独立执行各自的指令；处理器任何时间依赖关系需明确地在各处理器的程序中加入同步(路)障(Synchr

12、onization Barrier)；一条指令可在非确定但有限的时间内完成。,APRAM模型中的指令类型有四类指令：全局读将全局存储单元中的内容读入局存单元中；局部操作对局存中的数执行操作，其结果存入局存中；全局写将局存单元中的内容写入全局存储单元中；同步同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后，才能执行其局部程序。,APRAM模型中完成的计算 计算是由一系列用同步障分开的全局相所组成。在各全局相内，每个处理器异步地运行其局部程序；每个局部程序中的最后一条指令是一条同步障指令；各处理器均可异步地读取和写入全局存储器，在同一相内不允许两个处理器访问同一单元。不同的处理器访

13、问存储单元总是由一同步障所分开，所以指令完成时间上的差异并不影响整个计算,异步APRAM模型,计算过程由同步障分开的全局相组成,APRAM模型中的时间计算使用APRAM模型计算算法的时间复杂度时，假定局部操作取单位时间；全局读写时间为d它定量化了通信延迟，代表读/写全局存储器的平均时间，d随机器中的处理器增加而增加；同步障的时间为B它是处理器数P的非降函数B=B(P)。,在APRAM中假定上述参数服从如下关系：2dBP同时：B(P)O(dlogP)或B(P)O(dlogP/logd)。令tph为全局相内各处理器指令执行时间中最长者，则整个程序运行时间T为各相的时间之和加上B乘以同步障次数，即:

14、T=tph+B同步障次数,APRAM模型,优缺点 易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型,BSP模型BSP-Bulk Synchronization Parallel1.BSP模型的提出：哈佛大学的Leslie Valiant提出：块同步并行(BSP)，用以克服PRAM模型的缺点，但保留其简单性。一个BSP计算机由n个结点(处理器和存储器对)所组成。,BSP模型,基本概念由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。模型参数p：处理器数(带有存储器)l：同步障

15、时间(Barrier synchronization time)g：带宽因子(time steps/packet)=1/bandwidth 选路器吞吐率,特点：一个BSP程序有n个进程，每个驻留在一个结点上。基本时间单位是周期(或时间步)。程序按严格的超步序列执行。同步路障迫使进程等待BSP计算机是MIMD系统BSP模型是超步级的松同步在一个超步中，不同进程以不同速率异步执行。BSP模型交互机制是共享变量或是消息传递,BSP模型,计算过程由若干超级步组成，每个超级步计算模式为左图优缺点 强调了计算和通讯的分离，提供了一个编程环境，易于 程序复杂性分析。但需要显 式同步机制，限制至多h条 消息的

16、传递等。,一个超步执行时间的确定计算时间w处理器中完成计算操作所需的最大周期数。同步开销为L。通信开销为gh周期g是实现h关系的比例系数，常数。,结论：执行一个超步的时间为w+gh+L,关于BSP模型的实际优点和评论：比起PRAM模型来，BSP模型更为现实除了用于进程管理的并行性开销外，它考虑了所有其他开销。,logP模型,基本概念由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。模型参数L：network latencyo：communication overheadg：gap=1/bandwidthP：#processors注：L和g反映了通讯网络的容量,logP模型,优缺点 捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。BSP vs.LogPBSPLogP：BSP块同步BSP子集同步BSP进程对同步LogPBSP可以常数因子模拟LogP，LogP可以对数因子模拟BSPBSPLogP+BarriersOverheadBSP提供了更方便的程设环境，LogP更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程,