《并行计算第二篇并行算法的设计.ppt》由会员分享，可在线阅读，更多相关《并行计算第二篇并行算法的设计.ppt（53页珍藏版）》请在三一办公上搜索。
1、并行计算,2009年3月10日,第二篇 并行算法的设计,第四章 并行算法的设计基础第五章 并行算法的一般设计策略第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程,第四章 并行算法的设计基础,4.1 并行算法的基础知识4.2 并行计算模型,4.1 并行算法的基础知识,4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通信,并行算法的定义和分类,并行算法的定义算法并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。并行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算
2、法和随机算法,并行算法的表达,描述语言可以使用类Algol、类Pascal等；在描述语言中引入并行语句。并行语句示例Par-do语句 for i=1 to n par-do end forfor all语句 for all Pi,where 0ik end for,并行算法的复杂性度量,串行算法的复杂性度量最坏情况下的复杂度(Worst-CASE Complexity)期望复杂度(Expected Complexity)并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。处理器数p(n)并行算法成本c(n):c(n)
3、=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=(a0,an-1),处理器数p 输出：S=ai Begin(
4、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 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
5、;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 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交换数据，隐式同步计算。结构图,PRAM模型,分类
6、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的竞
7、争、通讯延迟等因素,异步APRAM模型,基本概念又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。指令类型(1)全局读(2)全局写(3)局部操作(4)同步,异步APRAM模型,计算过程由同步障分开的全局相组成,异步APRAM模型,计算时间 设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为B=B(p)非降函数。满足关系；或 令 为全局相内各处理器执行时间最长者，则APRAM上的计算时间为 优缺点 易编程和分
8、析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。,BSP模型,基本概念由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。模型参数p：处理器数(带有存储器)l：同步障时间(Barrier synchronization time)g：带宽因子(time steps/packet)=1/bandwidth,BSP模型,计算过程由若干超级步组成，每个超级步计算模式为左图优缺点 强调了计算和通讯的分离，提供了一个编程环境，易于 程序复杂性分析。但需要显 式同步机制，限制至多h条 消息的传递
9、等。,logP模型,基本概念由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。模型参数L：network latencyo：communication overheadg：gap=1/bandwidthP：#processors注：L和g反映了通讯网络的容量,logP模型,优缺点 捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。BSP vs.LogPBSPLogP：BSP块同步BSP子集同步BSP进程对同步LogPBSP可以常数因子
10、模拟LogP，LogP可以对数因子模拟BSPBSPLogP+BarriersOverheadBSP提供了更方便的程设环境，LogP更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程,作业（1）,TOP500 综述应用举例：新闻报道等选择某个型号的高性能计算机，撰写调研报告顾乃杰等，基于斐波那契序列的多播算法Brent定理的证明和意义BSP编程方法调研,23,模型与下界,不同的PRAM模型的相互模拟下界NP完全理论P完全理论,不同的PRAM模型的相互模拟,不同的PRAM模型PRAM-EREWPRAM-CREWPRAM-CRCWCPRAM-CRCWAPRAM-CRCWPPRAM-CRCW计
11、算能力是相当的,PRAM-EREW模拟PPRAM-CRCW,定理1：一条p-处理器PPRAM-CRCW模型上的指令，可在p-处理器PRAM-EREW模型上用O(logp)的时间实现。证明思路：并发读指令和并发写指令(PPRAM-CRCW)并发读指令：处理器Qi读取Mi单元中的内容(PRAM-EREW)处理器Pi 设置数对按照字典序排序：时间O(logp)第一分量相同的数对组成块（通过树播送数据，完成数据分布）Pi读取对于的数据：时间O(1)并发写指令：使用三元组推论：TEREW=O(TPCRCW logp),PRAM-CRCW之间的模拟,CPRAM_CRCW上算法可在APRAM_CRCW上正确
12、执行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个
13、辅助处理器，构造一个完全二叉树来选取标号最小的活跃处理器。定理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,
14、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 次操作可以排序完成给出例
15、子，证明17n/16次操作无法完成排序改进：1995年，新的下界结果,PRAM模型的下界,理想的PRAM模型n个处理器可访问无限的共享存储单元每个处理器有无限的私有存储单元一步计算分为三个阶段：读阶段、计算阶段、写阶段每一步计算允许任意数量的局部计算理想PRAM模型反映了通信的限制理想PRAM模型的下界对于标准PRAM模型同样成立,PRAM模型的下界,PRAM-CREW的下界 无论多少处理器，计算n变元的布尔或需要(logn)的时间PRAM-EREW的下界 p个处理器，计算长度为n的计数零问题需要(logn-logp)的时间PRAM-CRCW的下界 计算n变量奇偶函数，使用多项式数目的处理器需
16、要(logn/loglogn)的时间,NP完全理论导引,计算复杂性理论中最重要的理论在工作中，遇到一个问题，找不到好的算法来解决，怎么办？,算法与好的算法,算法：为实现某个任务而构成的简单指令集有穷的计算良过程通过有限多次运算可以决定的过程图灵机好的算法：多项式时间算法指数时间算法往往在实际中不可接受各种串行计算模型是多项式时间等价的是否所有的问题都有好的算法？SAT问题TSP（Traveling salesman problem)猜测TSP没有多项式时间算法（J.Edmonds 1965）,图灵机,带子可读可写无限长的带子读写头可左移右移,图灵机,“实际的”的图灵机模型单带图灵机（1TM）多
17、带图灵机（kTM）随机存取机（RAM）“实际的”单位时间内完成的工作量有一个多项式上界所有“实际的”计算模型多项式时间等价,非确定型图灵机（NTM),不现实的计算现实中的计算方式都是确定的解SAT问题的一个非确定型算法第一步：猜测一个变量的真值赋值；第二步：检查该赋值是否满足非确定型算法的计算时间：各种可能的计算过程的最短时间,非确定型图灵机（NTM),猜想模块,猜想阶段验证阶段,NTM计算树,计算过程：从根到叶节点的路径,P类与NP类,判定问题：只有肯定和否定两种答案优化问题可以化作判定问题处理P类（Polynomial)具有多项式时间算法的判定问题形成的计算复杂性类NP问题：在非确定型图灵
18、机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题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归约到另一个
19、NP问题，则该问题也是NP完全的六个NP完全问题（Karp 1972)3SAT，3DM，VC，团，HC，划分更多的NP完全问题1979年：300多个1998年：2000多个,P=?NP（P-NP问题）,现在的估计,如果，则NPC问题无有效算法,P=NP,如何处理NP完全问题,实际中的NP完全问题不会消失证明难度并不会使问题得到解决近似算法随机算法并行计算理想的PRAM模型上可多项式时间解决NP完全问题,P完全理论导引,计算模型：PRAMP类NC（Nicks Class）类：在PRAM上，使用多项式数目的处理器，在多对数时间内可求解的问题。NC类在P类中有些问题难以在使用多项式数目的处理器，在多
20、对数时间内求解图的深度优先搜索最大流问题线性规划问题,计算难度的比较归约,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,Thanks,
