第四章并行算法的设计基础

并行计算第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第四章并行算法的设计基础4.1并行算法的基础知识4.2并行计算模型4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通讯国家高性能计算中心（合肥）52019/12/20并行算法的定义和分类并行算法的定义算法并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。并行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通讯国家高性能计算中心（合肥）72019/12/20并行算法的表达描述语言可以使用类Algol、类Pascal等；在描述语言中引入并行语句。并行语句示例Par-do语句fori=1tonpar-do……endforforall语句forallPi,where0≤i≤k……endfor4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通讯国家高性能计算中心（合肥）92019/12/20并行算法的复杂性度量串行算法的复杂性度量最坏情况下的复杂度(Worst-CASEComplexity)期望复杂度(ExpectedComplexity)并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。处理器数p(n)并行算法成本c(n):c(n)=t(n)p(n)总运算量W(n):并行算法求解问题时所完成的总的操作步数。国家高性能计算中心（合肥）102019/12/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)4.1并行算法的基础知识4.1.1并行算法的定义和分类4.1.2并行算法的表达4.1.3并行算法的复杂性度量4.1.4并行算法中的同步和通讯国家高性能计算中心（合肥）122019/12/20并行算法的同步同步概念同步是在时间上强使各执行进程在某一点必须互相等待；可用软件、硬件和固件的办法来实现。同步语句示例算法4.1共享存储多处理器上求和算法输入：A=(a0,…,an-1),处理器数p输出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)forj=itonsteppdoendforL=L+ajEndendforendfor国家高性能计算中心（合肥）132019/12/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第四章并行算法的设计基础4.1并行算法的基础知识4.2并行计算模型4.2并行计算模型4.2.1PRAM模型4.2.2异步APRAM模型4.2.3BSP模型4.2.4logP模型国家高性能计算中心（合肥）162019/12/20PRAM模型基本概念由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。结构图ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory国家高性能计算中心（合肥）172019/12/20PRAM模型分类(1)PRAM-CRCW并发读并发写CPRAM-CRCW(CommonPRAM-CRCW)：仅允许写入相同数据PPRAM-CRCW(PriorityPRAM-CRCW)：仅允许优先级最高的处理器写入APRAM-CRCW(ArbitraryPRAM-CRCW)：允许任意处理器自由写入(2)PRAM-CREW并发读互斥写(3)PRAM-EREW互斥读互斥写计算能力比较PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模拟PRAM-CREW和PRAM-CRCWCRCWCREWEREWTTTCRCWCREWEREWTTT)log()log(pTOpTOTCRCWCREWEREW国家高性能计算中心（合肥）182019/12/20PRAM模型优点适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。缺点不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素4.2并行计算模型4.2.1PRAM模型4.2.2异步APRAM模型4.2.3BSP模型4.2.4logP模型国家高性能计算中心（合肥）202019/12/20异步APRAM模型基本概念又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。指令类型(1)全局读(2)全局写(3)局部操作(4)同步国家高性能计算中心（合肥）212019/12/20异步APRAM模型计算过程由同步障分开的全局相组成国家高性能计算中心（合肥）222019/12/20异步APRAM模型计算时间设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为B=B(p)非降函数。满足关系；或令为全局相内各处理器执行时间最长者，则APRAM上的计算时间为优缺点易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。pBd2)log()(pdOpBB)log/log(dpdOpht同步障次数BtTph4.2并行计算模型4.2.1PRAM模型4.2.2异步APRAM模型4.2.3BSP模型4.2.4logP模型国家高性能计算中心（合肥）242019/12/20BSP模型基本概念由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。模型参数p：处理器数(带有存储器)l：同步障时间(Barriersynchronizationtime)g：带宽因子(timesteps/packet)=1/bandwidth国家高性能计算中心（合肥）252019/12/20BSP模型计算过程由若干超级步组成，每个超级步计算模式为左图优缺点强调了计算和通讯的分离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多h条消息的传递等。各处理器局部计算全局通信路障同步图4.34.2并行计算模型4.2.1PRAM模型4.2.2异步APRAM模型4.2.3BSP模型4.2.4logP模型国家高性能计算中心（合肥）272019/12/20logP模型基本概念由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。模型参数L：networklatencyo：communicationoverheadg：gap=1/bandwidthP：#processors注：L和g反映了通讯网络的容量国家高性能计算中心（合肥）282019/12/20logP模型优缺点捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。BSPvs.LogPBSPLogP：BSP块同步BSP子集同步BSP进程对同步＝LogPBSP可以常数因子模拟LogP，LogP可以对数因子模拟BSPBSP＝LogP+Barriers－OverheadBSP提供了更方便的程设环境，LogP更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程