单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,并行计算,2009,年,3,月,10,日,第二篇 并行算法的设计,第四章 并行算法的设计基础,,第五章 并行算法的一般设计策略,,第六章 并行算法的基本设计技术,,第七章 并行算法的一般设计过程,,第四章 并行算法的设计基础,4.1,并行算法的基础知识,,4.2,并行计算模型,,4.1,并行算法的基础知识,4.1.1,并行算法的定义和分类,,4.1.2,并行算法的表达,,4.1.3,并行算法的复杂性度量,,4.1.4,并行算法中的同步和通信,并行算法的定义和分类,并行算法的定义,,算法,,并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解并行算法的分类,,数值计算和非数值计算,,同步算法和异步算法,,分布算法,,确定算法和随机算法,并行算法的表达,描述语言,,可以使用类,Algol,、类,Pascal,等；,,在描述语言中引入并行语句并行语句示例,,Par-do,语句,,,for i=1 to n par-do,,……,,end for,,for all,语句,,,for all Pi, where 0,≤i≤k,,……,,end for,并行算法的复杂性度量,串行算法的复杂性度量,,最坏情况下的复杂度,(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(n),和,c(n),两者是渐进一致的,,对于任意的,p,，,c(n)›W(n),,并行算法的同步,同步概念,,同步是在时间上强使各执行进程在某一点必须互相等待；,,可用软件、硬件和固件的办法来实现同步语句示例,,算法,4.1,共享存储多处理器上求和算法,,输入：,A=(a,0,,…,a,n-1,),,处理器数,p,,,输出：,S=Σa,i,,Begin,,(1)S=0 (2.3) lock(S),,(2)for all Pi where 0,≤,i,≤,p-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+a,j,End,,end for,,end for,并行算法的通信,通信,,共享存储多处理器使用：,global read(X,Y),和,global write(X,Y),,分布存储多计算机使用：,send(X,i),和,receive(Y,j),,通信语句示例,,算法,4.2,分布存储多计算机上矩阵向量乘算法,,,输入：处理器数,p, A,划分为,B=A[1..n,(i-1)r+1..ir],,,x,划分为,w=w[(i-1)r+1;ir],,,输出：,P,1,保存乘积,AX,,Begin,,(1) Compute z=Bw,,(2) if i=1 then y,i,=0 else receive(y,left) endif,,(3) y=y+z,,(4) send(y,right),,(5) if i=1 then receive(y,left),,End,4.2,并行计算模型,4.2.1 PRAM,模型,,4.2.2,异步,APRAM,模型,,4.2.3 BSP,模型,,4.2.4 logP,模型,,PRAM,模型,基本概念,,由,Fortune,和,Wyllie1978,年提出，又称,SIMD-SM,模型。
有一个集中的共享存储器和一个指令控制器，通过,SM,的,R/W,交换数据，隐式同步计算结构图,Control Unit,Interconnection Network,P,,,LM,,,P,,,LM,,,P,,,LM,,,P,,,LM,,,,Shared Memory,,,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,倍模拟,PRAM-CREW,和,PRAM-CRCW,,,,,,PRAM,模型,优点,,适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节,缺点,,不适合,MIMD,并行机，忽略了,SM,的竞争、通讯延迟等因素,异步,APRAM,模型,基本概念,,又称分相（,Phase,）,PRAM,或,MIMD-SM,。
每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过,SM,进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障指令类型,,(,1),全局读,(2),全局写,,(3),局部操作,(4),同步,异步,APRAM,模型,计算过程,,由同步障分开的全局相组成,,异步,APRAM,模型,计算时间,,,设局部操作为单位时间；全局读,/,写平均时间为,d,，,d,随着处理器数目的增加而增加；同步路障时间为,B=B(p),非降函数满足关系 ； 或,,令 为全局相内各处理器执行时间最长者，则,APRAM,上的计算时间为,,,优缺点,,,易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合,MIMD-DM,模型BSP,模型,基本概念,,由,Valiant(1990),提出的，“块”同步模型，是一种异步,MIMD-DM,模型，支持消息传递系统，块内异步并行，块间显式同步模型参数,,p,：处理器数,(,带有存储器,),,l,：同步障时间,(Barrier synchronization time),,g,：带宽因子,(time steps/packet)=1/bandwidth,,BSP,模型,计算过程,,由若干超级步组成，,,每个超级步计算模式为左图,,优缺点,,,强调了计算和通讯的分离，,,提供了一个编程环境，易于,,程序复杂性分析。
但需要显,,式同步机制，限制至多,h,条,,消息的传递等logP,模型,基本概念,,由,Culler(1993),年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步模型参数,,L,：,network latency,,o,：,communication overhead,,g,：,gap=1/bandwidth,,P,：,#processors,,注：,L,和,g,反映了通讯网络的容量,,,logP,模型,优缺点,,,捕捉了,MPC,的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析BSP vs. LogP,,BSP,,LogP,：,BSP,块同步,,BSP,子集同步,,BSP,进程对同步＝,LogP,,BSP,可以常数因子模拟,LogP,，,LogP,可以对数因子模拟,BSP,,BSP,＝,LogP+Barriers,－,Overhead,,BSP,提供了更方便的程设环境，,LogP,更好地利用了机器资源,,BSP,似乎更简单、方便和符合结构化编程,,作业（1）,TOP500,综述,,应用举例：新闻报道等,,选择某个型号的高性能计算机，撰写调研报告,,顾乃杰等，基于斐波那契序列的多播算法,,Brent,定理的证明和意义,,BSP,编程方法调研,23,模型与下界,不同的,PRAM,模型的相互模拟,,下界,,NP,完全理论,,P,完全理论,不同的,PRAM,模型的相互模拟,不同的,PRAM,模型,,PRAM-EREW,,PRAM-CREW,,PRAM-CRCW,,CPRAM-CRCW,,APRAM-CRCW,,PPRAM-CRCW,,,计算能力是相当的,PRAM-EREW,模拟,PPRAM-CRCW,定理1：一条,p-,处理器,PPRAM-CRCW,模型上的指令，可在,p-,处理器,PRAM-EREW,模型上用,O(logp),的时间实现。
证明思路：,,并发读指令和并发写指令,,(PPRAM-CRCW),并发读指令 ：处理器,Q,i,读取,M,i,单元中的内容,,(PRAM-EREW),处理器,P,i,设置数对,< M,i,, i >,,< M,i,, i >,按照字典序排序：时间,O(logp),,第一分量相同的数对组成块（通过树播送数据，完成数据分布）,,P,i,读取对于,< M,i,, i >,的数据：时间,O(1),,并发写指令：使用三元组,<,地址，处理器号，待写数据,>,,推论：,T,EREW,=O(T,PCRCW,logp,,),PRAM-CRCW,之间的模拟,CPRAM_CRCW,上算法可在,APRAM_CRCW,上正确执行,,APRAM_CRCW,上算法可在,PPRAM_CRCW,上正确执行,,,似乎计算能力是按,CPRAM_CRCW,，,APRAM_CRCW,，,PPRAM_CRCW,依次增强的在对处理器数目或对共享存储的容量不加限制时，三个模型是等效的最左俘获问题：,p,个处理器，“活跃”或者“非活跃”每个活跃的处理器有标记，值为,0,或,1,当且仅当处理器是编号最小的活跃处理器，标记为,1,CPRAM-CRCW,模拟,PPRAM-CRCW,定理,2,运行在,p-,处理器,PPRAM-CRCW,上时间为,T,的算法，可在,plogp-,处理器,CPRAM-CRCW,上运行时间为,O(T),。
证明思路：对于,PPRAM-CRCW,中每个参与写操作的处理器，使用,logp,个辅助处理器，构造一个完全二叉树来选取标号最小的活跃处理器定理,3 p-,处理器,PPRAM-CRCW,上的一条并发写指令，可在,p-,处理器,CPRAM-CRCW,模型上用,O(logp/log logp),时间实现证明思路,:,归纳法APRAM-CRCW,模拟,PPRAM-CRCW,定理,4 p-,处理器,PPRAM-CRCW,上的一条并发写指令，可在,p-,处理器,APRAM-CRCW,模型上用,O(log logp),时间实现证明思路：方根划分技术，递归求解,,,时间：,模拟的意义？,算法研究的两个方向,优化,,寻找更好的算法,,设计技巧,,一个新的算法（上界）,,可能性,,说明难以得到更好的算法,,证明技巧,,对模型、问题的更好认识（下界）,Gates, William H. and Christos H. Papadimitriou.,Bounds for sorting by prefix reversal.,,Discrete Mathematics,27 (1979), 47--57.,,Harvard University(1973) Microsoft (1975),Princeton University (MS 1974 and PhD 1976),上界与下界,问题描述： 仅通过前缀翻转（,prefix reversal,）操作对,n,个大小不同的序列排序。
前缀翻转： 将包含首个元素的子序列进行翻转,,,结果：,,给出算法，证明至多,(5n+5)/3,次操作可以排序完成,,给出例子，证明,17n/16,次操作无法完成排序,,改进：,,1995,年，新的下界结果,PRAM,模型的下界,理想的,PRAM,模型,,n,个处理器可访问无限的共享存储单元,,每个处理器有无限的私有存储单元,,一步计算分为三个阶段：读阶段、计算阶段、写阶段,,每一步计算允许任意数量的局部计算,,理想,PRAM,模型反映了通信的限制,,理想,PRAM,模型的下界对于标准,PRAM,模型同样成立,PRAM,模型的下界,PRAM-CREW,的下界,,无论多少处理器，计算,n,变元的布尔或需要,Ω,(,logn),的时间,,PRAM-EREW,的下界,,,p,个处理器，计算长度为,n,的计数零问题需要,Ω,(,logn-logp),的时间,,PRAM-CRCW,的下界,,计算,n,变量奇偶函数，使用多项式数目的处理器需要,Ω,(,logn/loglogn),的时间,NP,完全理论导引,,计算复杂性理论中最重要的理论,,,在工作中，遇到一个问题，找不到好的算法来解决，怎么办？,算法与好的算法,算法：,,为实现某个任务而构成的简单指令集,,有穷的计算良过程,,通过有限多次运算可以决定的过程,,图灵机,,好的算法：多项式时间算法,,指数时间算法往往在实际中不可接受,,各种串行计算模型是多项式时间等价的,,是否所有的问题都有好的算法？,,SAT,问题,,TSP,（,Traveling salesman problem),,,猜测,TSP,没有多项式时间算法（,J.Edmonds 1965,）,图灵机,有限状态控制器,,,,,,,,,,,,,,,,,,,,,,,,1,1,1,1,1,1,0,0,0,0,0,0,0,B,B,B,1,……,……,带子可读可写,,无限长的带子,,读写头可左移右移,图灵机,“实际的”的图灵机模型,,单带图灵机（,1TM,）,,多带图灵机（,kTM,）,,随机存取机（,RAM,）,,“实际的”,,单位时间内完成的工作量有一个多项式上界,,所有“实际的”计算模型多项式时间等价,非确定型图灵机（,NTM),,不现实的计算,,现实中的计算方式都是确定的,,解,SAT,问题的一个非确定型算法,,第一步：猜测一个变量的真值赋值；,,第二步：检查该赋值是否满足,,非确定型算法的计算时间：,,各种可能的计算过程的最短时间,非确定型图灵机（,NTM),有限状态控制器,,,,,,,,,,,,,,,,,,,,,,,,1,1,1,1,1,1,0,0,0,0,0,0,0,B,B,B,1,……,……,猜想模块,,,,,猜想阶段,,验证阶段,NTM,计算树,,,,,,,,,,,,,,,,,,,,,,计算过程：从根到叶节点的路径,P,类与,NP,类,判定问题：只有肯定和否定两种答案,,优化问题可以化作判定问题处理,,P,类 （,Polynomial),,具有多项式时间算法的判定问题形成的计算复杂性类,,NP,问题：,,在非确定型图灵机上多项式时间可解的问题,,在确定型图灵机上多项式时间可验证的问题,,P,类包含于,NP,类中,,NP,类问题在确定图灵机上指数时间可解,,非确定型图灵机和确定型图灵机的计算能力相当,计算难度的比较,——,归约,多项式时间归约（,Karp,归约,1972),,,问题,A,的实例,I,多项式时间内转化为问题,B,的实例,f(I),，对于,A,的输入,I,的回答与其对应的,B,的输入,f(I),一致，则称,A,可多项式归约于,B,，记为,,,如果,B,可以多项式时间求解，则,A,也可以多项式时间求解,NP,完全问题,NP,完全问题是,NP,问题中“最难”的问题,NP,完全问题,第一个,NP,完全问题（,Cook-levin,定理,1971,）,,可满足性问题是,NP,完全问题,,,如果一个,NP,完全问题,karp,归约到另一个,NP,问题，则该问题也是,NP,完全的,,,六个,NP,完全问题（,Karp 1972),,3SAT,，,3DM,，,VC,，团，,HC,，划分,,更多的,NP,完全问题,,1979,年：,300,多个,,1998,年：,2000,多个,P=?NP,（,P-NP,问题）,现在的估计,如果 ，则,NPC,问题无有效算法,P=NP,P,NPC,,NP,如何处理,NP,完全问题,实际中的,NP,完全问题不会消失,,证明难度并不会使问题得到解决,,,近似算法,,随机算法,,…………,,,并行计算,,理想的,PRAM,模型上可多项式时间解决,NP,完全问题,,P,完全理论导引,计算模型：,PRAM,,P,类,,NC,（,Nick’s Class,）类：在,PRAM,上，使用多项式数目的处理器，在多对数时间内可求解的问题。
NC,类在,P,类中,,有些问题难以在使用多项式数目的处理器，在多对数时间内求解,,图的深度优先搜索,,最大流问题,,线性规划问题,计算难度的比较,——,归约,NC-,归约,,问题,A,的实例,I,通过,NC,算法转化为问题,B,的实例,f(I),，对于,A,的输入,I,的回答与其对应的,B,的输入,f(I),一致，则称,A,可,NC,归约于,B,，记为,,,如果,B,可以使用多项式数目的处理器，在多对数时间内求解，则,A,也可以,P,完全问题,P,完全问题,CVP,（,Circuit Value Problem,）,,给定一组输入，确定由非门，二值或门，二值与门构成的电路的单个输入值,,,以下问题都是,P,完全的（通过,NC,归约可证）,,图的深度优先搜索,,最大流问题,,线性规划问题,P=?NC,（,P-NC,问题）,现在的估计,如果 ，则,PC,问题无好的并行算法,P=NC,NC,PC,,P,,Thanks,。