04-第04章-并行算法的设计基础-并行算法的设计-并行计算(共15章)

并行计算中国科学技术大学计算机科学与技术系中国科学技术大学计算机科学与技术系国家高性能计算中心国家高性能计算中心((合肥合肥))20042004年年1212月月第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第四章并行算法的设计基础4.1并行算法的基础知识4.2并行计算模型4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通讯国家高性能计算中心（合肥）52013/7/24Wednesday并行算法的定义和分类并行算法的定义并行算法的定义算法算法并行算法：一些可同时执行的诸进程的集合，这些进程并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。互相作用和协调动作从而达到给定问题的求解。并行算法的分类并行算法的分类数值计算和非数值计算数值计算和非数值计算同步算法和异步算法同步算法和异步算法分布算法分布算法确定算法和随机算法确定算法和随机算法4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通讯国家高性能计算中心（合肥）72013/7/24Wednesday并行算法的表达描述语言描述语言可以使用类可以使用类AlgolAlgol、类、类PascalPascal等；等；在描述语言中引入并行语句。在描述语言中引入并行语句。并行语句示例并行语句示例ParPar--dodo语句语句fori=1tonparfori=1tonpar--dodo…………endforendforforallforall语句语句forallPi,where0forallPi,where0≤≤ii≤≤kk…………endforendfor4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通讯国家高性能计算中心（合肥）92013/7/24Wednesday并行算法的复杂性度量串行算法的复杂性度量串行算法的复杂性度量最坏情况下的复杂度最坏情况下的复杂度(Worst(Worst--CASEComplexity)CASEComplexity)期望复杂度期望复杂度(ExpectedComplexity)(ExpectedComplexity)并行算法的几个复杂性度量指标并行算法的几个复杂性度量指标运行时间运行时间t(nt(n):):包含计算时间和通讯时间，分别用计算时包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。间步和选路时间步作单位。nn为问题实例的输入规模。为问题实例的输入规模。处理器数处理器数p(np(n))并行算法成本并行算法成本c(nc(n):):c(nc(n)=)=t(n)p(nt(n)p(n))总运算量总运算量W(nW(n):):并行算法求解问题时所完成的总的操作并行算法求解问题时所完成的总的操作步数。步数。国家高性能计算中心（合肥）102013/7/24Wednesday并行算法的复杂性度量BrentBrent定理定理令令W(nW(n))是某并行算法是某并行算法AA在运行时间在运行时间T(nT(n))内所执行的运算内所执行的运算量，则量，则AA使用使用pp台处理器可在台处理器可在t(nt(n)=)=O(W(n)/p+T(nO(W(n)/p+T(n))))时间时间内执行完毕。内执行完毕。W(nW(n))和和c(nc(n))密切相关密切相关P=P=O(W(n)/T(nO(W(n)/T(n))))时，时，W(nW(n))和和c(nc(n))两者是渐进一致的两者是渐进一致的对于任意的对于任意的pp，，c(n)c(n)››W(nW(n))4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通讯国家高性能计算中心（合肥）122013/7/24Wednesday并行算法的同步同步概念同步概念同步是在时间上强使各执行进程在某一点必须互相等待；同步是在时间上强使各执行进程在某一点必须互相等待；可用软件、硬件和固件的办法来实现。可用软件、硬件和固件的办法来实现。同步语句示例同步语句示例算法算法4.14.1共享存储多处理器上求和算法共享存储多处理器上求和算法输入：输入：A=(aA=(a00,,……,a,ann--11),),处理器数处理器数pp输出：输出：S=S=ΣΣaaiiBeginBegin(1)S=0(1)S=0(2.3)(2.3)lock(Slock(S))(2)forallPiwhere0(2)forallPiwhere0≤≤ii≤≤pp--11doS=S+LdoS=S+L(2.1)L=0(2.1)L=0(2.4)(2.4)unlock(Sunlock(S))(2.2)forj=itonsteppdoendfor(2.2)forj=itonsteppdoendforL=L=L+aL+ajjEndEndendforendforendforendfor国家高性能计算中心（合肥）132013/7/24Wednesday并行算法的通讯通讯通讯共享存储多处理器使用：共享存储多处理器使用：globalglobalread(X,Yread(X,Y))和和globalglobalwrite(X,Ywrite(X,Y))分布存储多计算机使用：分布存储多计算机使用：send(X,isend(X,i))和和receive(Y,jreceive(Y,j))通讯语句示例通讯语句示例算法算法4.24.2分布存储多计算机上矩阵向量乘算法分布存储多计算机上矩阵向量乘算法输入：处理器数输入：处理器数p,Ap,A划分为划分为B=A[1..n,(iB=A[1..n,(i--1)r+1..ir],1)r+1..ir],xx划分为划分为w=w[(iw=w[(i--1)r+1;ir]1)r+1;ir]输出：输出：PP11保存乘积保存乘积AXAXBeginBegin(1)Computez=(1)Computez=BwBw(2)ifi=1then(2)ifi=1thenyyii=0else=0elsereceive(y,leftreceive(y,left))endifendif(3)y=(3)y=y+zy+z(4)(4)send(y,rightsend(y,right))(5)ifi=1then(5)ifi=1thenreceive(y,leftreceive(y,left))EndEnd第四章并行算法的设计基础4.1并行算法的基础知识4.2并行计算模型4.2并行计算模型4.2.1PRAM模型4.2.2异步APRAM模型4.2.3BSP模型4.2.4logP模型国家高性能计算中心（合肥）162013/7/24WednesdayPRAM模型基本概念基本概念由由FortuneFortune和和Wyllie1978Wyllie1978年提出，又称年提出，又称SIMDSIMD--SMSM模型。模型。有一个集中的共享存储器和一个指令控制器，通过有一个集中的共享存储器和一个指令控制器，通过SMSM的的R/WR/W交换数据，隐式同步计算。交换数据，隐式同步计算。结构图结构图ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory国家高性能计算中心（合肥）172013/7/24WednesdayPRAM模型分类分类(1)(1)PRAMPRAM--CRCWCRCW并发读并发写并发读并发写CPRAMCPRAM--CRCW(CommonCRCW(CommonPRAMPRAM--CRCW)CRCW)：仅允许写入相同数据：仅允许写入相同数据PPRAMPPRAM--CRCW(PriorityCRCW(PriorityPRAMPRAM--CRCW)CRCW)：仅允许优先级最高的处理器写入：仅允许优先级最高的处理器写入APRAMAPRAM--CRCW(ArbitraryCRCW(ArbitraryPRAMPRAM--CRCW)CRCW)：允许任意处理器自由写入：允许任意处理器自由写入(2)(2)PRAMPRAM--CREWCREW并发读互斥写并发读互斥写(3)(3)PRAMPRAM--EREWEREW互斥读互斥写互斥读互斥写计算能力比较计算能力比较PRAMPRAM--CRCWCRCW是最强的计算模型，是最强的计算模型，PRAMPRAM--EREWEREW可可logplogp倍模拟倍模拟PRAMPRAM--CREWCREW和和PRAMPRAM--CRCWCRCWCRCWCREWEREWTTTCRCWCREWEREWTTT)log()log(pTOpTOTCRCWCREWEREW国家高性能计算中心（合肥）182013/7/24WednesdayPRAM模型优点优点适合并行算法表示和复杂性分析，易于使用，隐藏了适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节并行机的通讯、同步等细节。。缺点缺点不适合不适合MIMDMIMD并行机，忽略了并行机，忽略了SMSM的竞争、通讯延迟的竞争、通讯延迟等因素等因素4.2并行计算模型4.2.1PRAM模型4.2.2异步APRAM模型4.2.3BSP模型4.2.4logP模型国家高性能计算中心（合肥）202013/7/24Wednesday异步APRAM模型基本概念基本概念又称分相（又称分相（PhasePhase））PRAMPRAM或或MIMDMIMD--SMSM。每个处理。每个处理器有其局部存储器、局部时钟、局部程序；无全局时器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过钟，各处理器异步执行；处理器通过SMSM进行通讯；进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步处理器间依赖关系，需在并行程序中显式地加入同步路障。路障。指令类型指令类型((1)1)全局读全局读(2)(2)全局写全局写(3)(3)局部操作局部操作(4)(4)同步同步国家高性能计算中心（合肥）212013/7/24Wednesday异步APRAM模型计算过程计算过程由同步障分开的全局相组成由同步障分开的全局相组成国家高性能计算中心（合肥）222013/7/24Wednesday异步APRAM模型计算时间计算时间设局部操作为单位时间；全局读设局部操作为单位时间；全局读//写平均时间为写平均时间为dd，，dd随着处理器数随着处理器数目的增加而增加；同步路障时间为目的增加而增加；同步路障时间为B=B=B(pB(p))非降函数。非降函数。满足关系满足关系；；或或令令为全局相内各处理器执行时间最长者，则为全局相内各处理器执行时间最长者，则APRAMAPRAM上的计算时上的计算时间为间为优缺点优缺点易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合常有限，也不适合MIMDMIMD--DMDM模型。模型。pBd2)log()(pdOpBB)log/log(dpdOpht同步障次数BtTph4.2并行计算模型4.2.1PRAM模型4.2.2异步APRAM模型4.2.3BSP模型4.2.4logP模型国家高性能计算中心（合肥）242013/7/24WednesdayBSP模型基本概念基本概念由由Valiant(1990)Valiant(1990)提出的，提出的，““块块””同步模型，是一种异步同步模型，是一种异步MIMDMIMD--DMDM