并行计算第二篇并行算法的设计

并行计算第二篇并行算法的设计第1页，共53页，2023年，2月20日，星期一第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计策略第六章并行算法的基本设计技术第七章并行算法的一般设计过程第2页，共53页，2023年，2月20日，星期一第四章并行算法的设计基础4.1并行算法的基础知识4.2并行计算模型

第3页，共53页，2023年，2月20日，星期一4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通信第4页，共53页，2023年，2月20日，星期一并行算法的定义和分类并行算法的定义算法并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。并行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法第5页，共53页，2023年，2月20日，星期一并行算法的表达描述语言可以使用类Algol、类Pascal等；在描述语言中引入并行语句。并行语句示例Par-do语句

fori=1tonpar-do……endforforall语句forallPi,where0≤i≤k……endfor第6页，共53页，2023年，2月20日，星期一并行算法的复杂性度量串行算法的复杂性度量最坏情况下的复杂度(Worst-CASEComplexity)期望复杂度(ExpectedComplexity)并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。处理器数p(n)并行算法成本c(n):c(n)=t(n)p(n)总运算量W(n):并行算法求解问题时所完成的总的操作步数。

第7页，共53页，2023年，2月20日，星期一并行算法的复杂性度量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)第8页，共53页，2023年，2月20日，星期一并行算法的同步同步概念同步是在时间上强使各执行进程在某一点必须互相等待；可用软件、硬件和固件的办法来实现。同步语句示例算法4.1共享存储多处理器上求和算法输入：A=(a0,…,an-1),处理器数p输出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1

doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)forj=itonsteppdoendforL=L+ajEndendforendfor第9页，共53页，2023年，2月20日，星期一并行算法的通信通信共享存储多处理器使用：globalread(X,Y)和globalwrite(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]输出：P1保存乘积AXBegin(1)Computez=Bw(2)ifi=1thenyi=0elsereceive(y,left)endif(3)y=y+z(4)send(y,right)(5)ifi=1thenreceive(y,left)End第10页，共53页，2023年，2月20日，星期一4.2并行计算模型4.2.1PRAM模型4.2.2异步APRAM模型4.2.3BSP模型4.2.4logP模型第11页，共53页，2023年，2月20日，星期一PRAM模型基本概念由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。结构图ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory第12页，共53页，2023年，2月20日，星期一PRAM模型分类PRAM-CRCW并发读并发写CPRAM-CRCW(CommonPRAM-CRCW)：仅允许写入相同数据PPRAM-CRCW(PriorityPRAM-CRCW)：仅允许优先级最高的处理器写入APRAM-CRCW(ArbitraryPRAM-CRCW)：允许任意处理器自由写入PRAM-CREW并发读互斥写PRAM-EREW互斥读互斥写计算能力比较PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模拟PRAM-CREW和PRAM-CRCW第13页，共53页，2023年，2月20日，星期一PRAM模型优点适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。缺点不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素第14页，共53页，2023年，2月20日，星期一异步APRAM模型基本概念又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。指令类型(1)全局读(2)全局写(3)局部操作(4)同步第15页，共53页，2023年，2月20日，星期一异步APRAM模型计算过程由同步障分开的全局相组成

第16页，共53页，2023年，2月20日，星期一异步APRAM模型计算时间

设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为B=B(p)非降函数。满足关系；或令为全局相内各处理器执行时间最长者，则APRAM上的计算时间为优缺点

易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。

第17页，共53页，2023年，2月20日，星期一BSP模型基本概念由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。

模型参数p：处理器数(带有存储器)l：同步障时间(Barriersynchronizationtime)g：带宽因子(timesteps/packet)=1/bandwidth第18页，共53页，2023年，2月20日，星期一BSP模型计算过程由若干超级步组成，每个超级步计算模式为左图优缺点

强调了计算和通讯的分离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多h条消息的传递等。第19页，共53页，2023年，2月20日，星期一logP模型基本概念由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。模型参数L：networklatencyo：communicationoverheadg：gap=1/bandwidthP：#processors注：L和g反映了通讯网络的容量

第20页，共53页，2023年，2月20日，星期一logP模型优缺点

捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。BSPvs.LogPBSPLogP：BSP块同步BSP子集同步BSP进程对同步＝LogPBSP可以常数因子模拟LogP，LogP可以对数因子模拟BSPBSP＝LogP+Barriers－OverheadBSP提供了更方便的程设环境，LogP更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程

第21页，共53页，2023年，2月20日，星期一作业（1）TOP500综述应用举例：新闻报道等选择某个型号的高性能计算机，撰写调研报告顾乃杰等，基于斐波那契序列的多播算法Brent定理的证明和意义BSP编程方法调研第22页，共53页，2023年，2月20日，星期一23第23页，共53页，2023年，2月20日，星期一模型与下界不同的PRAM模型的相互模拟下界NP完全理论P完全理论第24页，共53页，2023年，2月20日，星期一不同的PRAM模型的相互模拟不同的PRAM模型PRAM-EREWPRAM-CREWPRAM-CRCWCPRAM-CRCWAPRAM-CRCWPPRAM-CRCW计算能力是相当的第25页，共53页，2023年，2月20日，星期一PRAM-EREW模拟PPRAM-CRCW定理1：一条p-处理器PPRAM-CRCW模型上的指令，可在p-处理器PRAM-EREW模型上用O(logp)的时间实现。证明思路：并发读指令和并发写指令(PPRAM-CRCW)并发读指令：处理器Qi读取Mi单元中的内容(PRAM-EREW)处理器Pi设置数对<Mi,i><Mi,i>按照字典序排序：时间O(logp)第一分量相同的数对组成块（通过树播送数据，完成数据分布）Pi读取对于<Mi,i>的数据：时间O(1)并发写指令：使用三元组<地址，处理器号，待写数据>推论：TEREW=O(TPCRCWlogp

)第26页，共53页，2023年，2月20日，星期一PRAM-CRCW之间的模拟CPRAM_CRCW上算法可在APRAM_CRCW上正确执行APRAM_CRCW上算法可在PPRAM_CRCW上正确执行似乎计算能力是按CPRAM_CRCW，APRAM_CRCW，PPRAM_CRCW依次增强的。在对处理器数目或对共享存储的容量不加限制时，三个模型是等效的。最左俘获问题：p个处理器，“活跃”或者“非活跃”。每个活跃的处理器有标记，值为0或1。当且仅当处理器是编号最小的活跃处理器，标记为1。第27页，共53页，2023年，2月20日，星期一CPRAM-CRCW模拟PPRAM-CRCW定理2运行在p-处理器PPRAM-CRCW上时间为T的算法，可在plogp-处理器CPRAM-CRCW上运行时间为O(T)。证明思路：对于PPRAM-CRCW中每个参与写操作的处理器，使用logp个辅助处理器，构造一个完全二叉树来选取标号最小的活跃处理器。定理3p-处理器PPRAM-CRCW上的一条并发写指令，可在p-处理器CPRAM-CRCW模型上用O(logp/loglogp)时间实现。证明思路:归纳法。第28页，共53页，2023年，2月20日，星期一APRAM-CRCW模拟PPRAM-CRCW定理4p-处理器PPRAM-CRCW上的一条并发写指令，可在p-处理器APRAM-CRCW模型上用O(loglogp)时间实现。证明思路：方根划分技术，递归求解时间：模拟的意义？第29页，共53页，2023年，2月20日，星期一算法研究的两个方向优化寻找更好的算法设计技巧一个新的算法（上界）可能性说明难以得到更好的算法证明技巧对模型、问题的更好认识（下界）第30页，共53页，2023年，2月20日，星期一Gates,WilliamH.andChristosH.Papadimitriou.Boundsforsortingbyprefixreversal.

DiscreteMathematics27(1979),47--57.HarvardUniversity(1973)Microsoft(1975)PrincetonUniversity(MS1974andPhD1976)第31页，共53页，2023年，2月20日，星期一上界与下界问题描述：仅通过前缀翻转（prefixreversal）操作对n个大小不同的序列排序。前缀翻转：将包含首个元素的子序列进行翻转结果：给出算法，证明至多(5n+5)/3次操作可以排序完成给出例子，证明17n/16次操作无法完成排序改进：1995年，新的下界结果第32页，共53页，2023年，2月20日，星期一PRAM模型的下界理想的PRAM模型n个处理器可访问无限的共享存储单元每个处理器有无限的私有存储单元一步计算分为三个阶段：读阶段、计算阶段、写阶段每一步计算允许任意数量的局部计算理想PRAM模型反映了通信的限制理想PRAM模型的下界对于标准PRAM模型同样成立第33页，共53页，2023年，2月20日，星期一PRAM模型的下界PRAM-CREW的下界无论多少处理器，计算n变元的布尔或需要Ω(logn)的时间PRAM-EREW的下界p个处理器，计算长度为n的计数零问题需要Ω(logn-logp)的时间PRAM-CRCW的下界计算n变量奇偶函数，使用多项式数目的处理器需要Ω(logn/loglogn)的时间第34页，共53页，2023年，2月20日，星期一NP完全理论导引计算复杂性理论中最重要的理论在工作中，遇到一个问题，找不到好的算法来解决，怎么办？第35页，共53页，2023年，2月20日，星期一算法与好的算法算法：为实现某个任务而构成的简单指令集有穷的计算良过程通过有限多次运算可以决定的过程图灵机好的算法：多项式时间算法指数时间算法往往在实际中不可接受各种串行计算模型是多项式时间等价的是否所有的问题都有好的算法？SAT问题TSP（Travelingsalesmanproblem)猜测TSP没有多项式时间算法（J.Edmonds1965）第36页，共53页，2023年，2月20日，星期一图灵机有限状态控制器1111110000000BBB1…………带子可读可写无限长的带子读写头可左移右移第37页，共53页，2023年，2月20日，星期一图灵机“实际的”的图灵机模型单带图灵机（1TM）多带图灵机（kTM）随机存取机（RAM）“实际的”单位时间内完成的工作量有一个多项式上界所有“实际的”计算模型多项式时间等价第38页，共53页，2023年，2月20日，星期一非确定型图灵机（NTM)不现实的计算现实中的计算方式都是确定的解SAT问题的一个非确定型算法第一步：猜测一个变量的真值赋值；第二步：检查该赋值是否满足非确定型算法的计算时间：各种可能的计算过程的最短时间第39页，共53页，2023年，2月20日，星期一非确定型图灵机（NTM)有限状态控制器1111110000000BBB1…………猜想模块猜想阶段验证阶段第40页，共53页，2023年，2月20日，星期一NTM计算树计算过程：从根到叶节点的路径第41页，共53页，2023年，2月20日，星期一P类与NP类判定问题：只有肯定和否定两种答案优化问题可以化作判定问题处理P类 （Polynomial)具有多项式时间算法的判定问题形成的计算复杂性类NP问题：在非确定型图灵机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题P类包含于NP类中NP类问题在确定图灵机上指数时间可解非确定型图灵机和确定型图灵机的计算能力相当第42页，共53页，2023年，2月20日，星期一计算难度的比较——归约多项式时间归约（Karp归约1972)问题A的实例I多项式时间内转化为问题B的实例f(I)，对于A的输入I的回答与其对应的B的输入f(I)一致，则称A可多项式归约于B，记为如果B可以多项式时间求解，则A也可以多项式时间求解第43页，共53页，2023年，2月20日，星期一NP完全问题NP完全问题是NP问题中“最难”的问题第44页，共53页，2023年，2月20日，星期一NP完全问题第一个NP完全问题（Cook-levin定理1971）可满足性问题是NP完全问题如果一个NP完全问题karp归约到另一个NP问题，则该问题也是NP完全的六个NP完全问题（Karp1972)3SA