第四章并行算法的设计基础精选文档.ppt

第四章并行算法的设计基础2022/10/191现代密码学理论与实践之五本讲稿第一页，共二十八页第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程2022/10/192现代密码学理论与实践之五本讲稿第二页，共二十八页第四章 并行算法的设计基础 4.1 并行算法的基础知识 4.2 并行计算模型2022/10/193现代密码学理论与实践之五本讲稿第三页，共二十八页4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯2022/10/194现代密码学理论与实践之五本讲稿第四页，共二十八页 并行算法的定义和分类并行算法的定义 算法算法 并行算法：一些可同时执行的诸进程的集合，这些进程互相作并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。用和协调动作从而达到给定问题的求解。并行算法的分类 数值计算和非数值计算数值计算和非数值计算 同步算法和异步算法同步算法和异步算法 分布算法分布算法 确定算法和随机算法确定算法和随机算法2022/10/195现代密码学理论与实践之五本讲稿第五页，共二十八页4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯2022/10/196现代密码学理论与实践之五本讲稿第六页，共二十八页 并行算法的表达描述语言 可以使用类可以使用类AlgolAlgol、类、类PascalPascal等；等；在描述语言中引入并行语句。在描述语言中引入并行语句。并行语句示例 Par-doPar-do语句语句 for i=1 to n par-dofor i=1 to n par-do end for end for for allfor all语句语句 for all Pi,where 0for all Pi,where 0ikik end for end for 2022/10/197现代密码学理论与实践之五本讲稿第七页，共二十八页4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯2022/10/198现代密码学理论与实践之五本讲稿第八页，共二十八页 并行算法的复杂性度量串行算法的复杂性度量 最坏情况下的复杂度最坏情况下的复杂度(Worst-CASE Complexity)(Worst-CASE Complexity)期望复杂度期望复杂度(Expected Complexity)(Expected Complexity)并行算法的几个复杂性度量指标 运行时间运行时间t(n):t(n):包含计算时间和通讯时间，分别用计算时间包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。步和选路时间步作单位。n n为问题实例的输入规模。为问题实例的输入规模。处理器数处理器数p(n)p(n)并行算法成本并行算法成本c(n):c(n)=t(n)p(n)c(n):c(n)=t(n)p(n)总运算量总运算量W(n):W(n):并行算法求解问题时所完成的总的操作步数。并行算法求解问题时所完成的总的操作步数。2022/10/199现代密码学理论与实践之五本讲稿第九页，共二十八页 并行算法的复杂性度量Brent定理令令W(n)W(n)是某并行算法是某并行算法A A在运行时间在运行时间T(n)T(n)内所执行的运算内所执行的运算量，则量，则A A使用使用p p台处理器可在台处理器可在t(n)=O(W(n)/p+T(n)t(n)=O(W(n)/p+T(n)时间时间内执行完毕。内执行完毕。W(n)W(n)和和c(n)c(n)密切相关密切相关 P=O(W(n)/T(n)P=O(W(n)/T(n)时，时，W(n)W(n)和和c(n)c(n)两者是渐进一致的两者是渐进一致的 对于任意的对于任意的p p，c(n)W(n)c(n)W(n)2022/10/1910现代密码学理论与实践之五本讲稿第十页，共二十八页4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯2022/10/1911现代密码学理论与实践之五本讲稿第十一页，共二十八页 并行算法的同步 同步概念同步概念 同步是在时间上强使各执行进程在某一点必须互相等待；同步是在时间上强使各执行进程在某一点必须互相等待；可用软件、硬件和固件的办法来实现。可用软件、硬件和固件的办法来实现。同步语句示例同步语句示例 算法算法4.1 4.1 共享存储多处理器上求和算法共享存储多处理器上求和算法 输入：输入：A=(aA=(a0 0,a,an-1n-1),),处理器数处理器数p p 输出：输出：S=aS=ai i Begin Begin (1)S=0 (2.3)lock(S)(1)S=0 (2.3)lock(S)(2)for all Pi where 0 (2)for all Pi where 0i ip-1p-1 do S=S+Ldo S=S+L (2.1)L=0 (2.4)unlock(S)(2.1)L=0 (2.4)unlock(S)(2.2)for j=i to n step p do end for (2.2)for j=i to n step p do end for L=L+a L=L+aj j End End end for end for end for end for 2022/10/1912现代密码学理论与实践之五本讲稿第十二页，共二十八页 并行算法的通讯 通讯通讯 共享存储多处理器使用：共享存储多处理器使用：global read(X,Y)global read(X,Y)和和global write(X,Y)global write(X,Y)分布存储多计算机使用：分布存储多计算机使用：send(X,i)send(X,i)和和receive(Y,j)receive(Y,j)通讯语句示例通讯语句示例 算法算法4.2 4.2 分布存储多计算机上矩阵向量乘算法分布存储多计算机上矩阵向量乘算法 输入：处理器数输入：处理器数p,Ap,A划分为划分为B=A1.n,(i-1)r+1.ir,B=A1.n,(i-1)r+1.ir,x x划分为划分为w=w(i-1)r+1;ir w=w(i-1)r+1;ir 输出：输出：P P1 1保存乘积保存乘积AXAX Begin Begin (1)Compute z=Bw (1)Compute z=Bw (2)if i=1 then y (2)if i=1 then yi i=0 else receive(y,left)endif=0 else receive(y,left)endif (3)y=y+z (3)y=y+z (4)send(y,right)(4)send(y,right)(5)if i=1 then receive(y,left)(5)if i=1 then receive(y,left)End End 2022/10/1913现代密码学理论与实践之五本讲稿第十三页，共二十八页第四章 并行算法的设计基础 4.1 并行算法的基础知识 4.2 并行计算模型2022/10/1914现代密码学理论与实践之五本讲稿第十四页，共二十八页4.2 并行计算模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型2022/10/1915现代密码学理论与实践之五本讲稿第十五页，共二十八页 PRAM模型基本概念 由由FortuneFortune和和Wyllie1978Wyllie1978年提出，又称年提出，又称SIMD-SMSIMD-SM模型。有模型。有一个集中的共享存储器和一个指令控制器，通过一个集中的共享存储器和一个指令控制器，通过SMSM的的R/WR/W交换交换数据，隐式同步计算。数据，隐式同步计算。结构图Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory2022/10/1916现代密码学理论与实践之五本讲稿第十六页，共二十八页 PRAM模型分类(1)(1)PRAM-CRCWPRAM-CRCW并发读并发写并发读并发写 CPRAM-CRCW(Common PRAM-CRCW)CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据：仅允许写入相同数据 PPRAM-CRCW(Priority PRAM-CRCW)PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入：仅允许优先级最高的处理器写入 APRAM-CRCW(Arbitrary PRAM-CRCW)APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入：允许任意处理器自由写入 (2)(2)PRAM-CREWPRAM-CREW并发读互斥写并发读互斥写 (3)(3)PRAM-EREWPRAM-EREW互斥读互斥写互斥读互斥写 计算能力比较 PRAM-CRCWPRAM-CRCW是最强的计算模型，是最强的计算模型，PRAM-EREWPRAM-EREW可可logplogp倍模拟倍模拟PRAM-CREWPRAM-CREW和和PRAM-CRCW PRAM-CRCW 2022/10/1917现代密码学理论与实践之五本讲稿第十七页，共二十八页 PRAM模型优点 适合并行算法表示和复杂性分析，易于使用，隐藏了并行机适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节的通讯、同步等细节。缺点 不适合不适合MIMDMIMD并行机，忽略了并行机，忽略了SMSM的竞争、通讯延迟等因素的竞争、通讯延迟等因素2022/10/1918现代密码学理论与实践之五本讲稿第十八页，共二十八页4.2 并行计算模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型2022/10/1919现代密码学理论与实践之五本讲稿第十九页，共二十八页 异步APRAM模型基本概念 又称分相（又称分相（PhasePhase）PRAMPRAM或或MIMD-SMMIMD-SM。每个处理器有其。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过器异步执行；处理器通过SMSM进行通讯；处理器间依赖关进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。系，需在并行程序中显式地加入同步路障。指令类型(1)1)全局读全局读 (2)(2)全局写全局写 (3)(3)局部操作局部操作 (4)(4)同步同步 2022/10/1920现代密码学理论与实践之五本讲稿第二十页，共二十八页 异步APRAM模型 计算过程计算过程由同步障分开的全局相组成由同步障分开的全局相组成 2022/10/1921现代密码学理论与实践之五本讲稿第二十一页，共二十八页 异步APRAM模型计算时间 设局部操作为单位时间；全局读设局部操作为单位时间；全局读/写平均时间为写平均时间为d d，d d随着处理器数目的增加而增随着处理器数目的增加而增加；同步路障时间为加；同步路障时间为B=B(p)B=B(p)非降函数。非降函数。满足关系满足关系 ；或或 令令 为全局相内各处理器执行时间最长者，则为全局相内各处理器执行时间最长者，则APRAMAPRAM上的计算时间为上的计算时间为 优缺点 易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合有限，也不适合MIMD-DMMIMD-DM模型。模型。2022/10/1922现代密码学理论与实践之五本讲稿第二十二页，共二十八页4.2 并行计算模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型2022/10/1923现代密码学理论与实践之五本讲稿第二十三页，共二十八页 BSP模型基本概念 由由Valiant(1990)Valiant(1990)提出的，提出的，“块块”同步模型，是一种异步同步模型，是一种异步MIMD-DMMIMD-DM模型，支持消息传递系统，块内异步并行，块模型，支持消息传递系统，块内异步并行，块间显式同步。间显式同步。模型参数 p p：处理器数：处理器数(带有存储器带有存储器)l l：同步障时间：同步障时间(Barrier synchronization time)(Barrier synchronization time)g g：带宽因子：带宽因子(time steps/packet)=1/bandwidth(time steps/packet)=1/bandwidth 2022/10/1924现代密码学理论与实践之五本讲稿第二十四页，共二十八页 BSP模型 计算过程计算过程由若干超级步组成，由若干超级步组成，每个超级步计算模式为左图每个超级步计算模式为左图 优缺点优缺点 强调了计算和通讯的分离，强调了计算和通讯的分离，提供了一个编程环境，易于提供了一个编程环境，易于 程序复杂性分析。但需要显程序复杂性分析。但需要显 式同步机制，限制至多式同步机制，限制至多h h条条 消息的传递等。消息的传递等。2022/10/1925现代密码学理论与实践之五本讲稿第二十五页，共二十八页4.2 并行计算模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型2022/10/1926现代密码学理论与实践之五本讲稿第二十六页，共二十八页 logP模型基本概念 由由Culler(1993)Culler(1993)年提出的，是一种分布存储的、点到点通年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。同步。模型参数 L L：network latencynetwork latency o o：communication overheadcommunication overhead g g：gap=1/bandwidthgap=1/bandwidth P P：#processors#processors注：注：L L和和g g反映了通讯网络的容量反映了通讯网络的容量 2022/10/1927现代密码学理论与实践之五本讲稿第二十七页，共二十八页 logP模型 优缺点优缺点 捕捉了捕捉了MPCMPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。设计和分析。BSP vs.LogPBSP vs.LogP BSPBSPLogPLogP：BSPBSP块同步块同步BSPBSP子集同步子集同步BSPBSP进程对同步进程对同步LogPLogP BSPBSP可以常数因子模拟可以常数因子模拟LogPLogP，LogPLogP可以对数因子模拟可以对数因子模拟BSPBSP BSPBSPLogP+BarriersLogP+BarriersOverheadOverhead BSPBSP提供了更方便的程设环境，提供了更方便的程设环境，LogPLogP更好地利用了机器资源更好地利用了机器资源 BSPBSP似乎更简单、方便和符合结构化编程似乎更简单、方便和符合结构化编程 2022/10/1928现代密码学理论与实践之五本讲稿第二十八页，共二十八页