并行算法的抽象模型.ppt

并行算法的抽象模型并行算法的抽象模型 并行算法的定义和分类•并行算法的定义–算法–并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解•并行算法的分类–数值计算和非数值计算–同步算法和异步算法–分布算法–确定算法和随机算法 并行算法的表达•描述语言–可以使用类Algol、类Pascal等；–在描述语言中引入并行语句•并行语句示例–Par-do语句（Do in parallle）算法要并行执行 for i=1 to n par-do …… end for–for all语句（几个处理器同时执行相同的操作） for all Pi, where 0≤i≤k …… end for  并行算法的复杂性度量•串行算法的复杂性度量–最坏情况下的复杂度(Worst-CASE Complexity)–期望复杂度(Expected Complexity)•并行算法的几个复杂性度量指标–运行时间t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。

n为问题实例的输入规模–处理器数p(n)–并行算法成本c(n): c(n)=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 (1)S=0 (2.3) lock(S) (2)for all Pi where 0≤i≤p-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=A[1..n,(i-1)r+1..ir], x划分为w=w[(i-1)r+1;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 抽象模型的概念抽象模型的概念•并行计算模型通常指从并行算法的设计和分析出发，将各种并行计算机（至少某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。

从更广的意义上说，并行计算模型为并行计算提供了硬件和软件界面，在该界面的约定下，并行系统硬件设计者和软件设计者可以开发对并行性的支持机制，从而提高系统的性能并行计算机的抽象模型并行计算机的抽象模型•并行计算机的理论模型是从物理模型并行计算机的理论模型是从物理模型抽象的；抽象的；•为开发并行算法提供了一种方便的框为开发并行算法提供了一种方便的框架；架； •用这些模型可求得并行计算机的理论用这些模型可求得并行计算机的理论性能界限；性能界限；•可在芯片制作前估算芯片区的可在芯片制作前估算芯片区的VLSIVLSI复复杂性和执行时间杂性和执行时间•一、时间与空间复杂性一、时间与空间复杂性•计算机求解一个规模为计算机求解一个规模为s s的问题的问题的算法复杂性取决于：的算法复杂性取决于：–执行时间执行时间–存储空间存储空间•时间复杂性：时间复杂性：•时间复杂性时间复杂性g(s)g(s)为为O(f(s))O(f(s))，可读，可读作作“数量级为数量级为f(s)f(s)”，如存在正的，如存在正的常量常量c c和和s0s0，则对所有，则对所有s>s0s>s0的非负的非负值就有值就有g(s)≤ cf(s) g(s)≤ cf(s) 。

•空间复杂性空间复杂性•为问题规模为问题规模s s的函数–渐近空间复杂性渐近空间复杂性(asymptotic spacecom(asymptotic spacecom——plexity)plexity)主要与大问题的数据存储有关，而程主要与大问题的数据存储有关，而程序序( (代码代码) )存储的需求和输入数据的存储不考虑存储的需求和输入数据的存储不考虑在内•串行算法的时间复杂性简称为串行复杂性串行算法的时间复杂性简称为串行复杂性; ;•并行算法的时间复杂性就称为并行复杂性并行算法的时间复杂性就称为并行复杂性; ;•并行复杂性应比串行复杂性低，至少是相并行复杂性应比串行复杂性低，至少是相近•只考虑确定性算法只考虑确定性算法•并行随机存取机模型并行随机存取机模型(Parallel (Parallel RandomRandom——Access MachineAccess Machine，，PRAM)PRAM)•目的：可用来开发并行算法和分析目的：可用来开发并行算法和分析可扩展性及复杂性可扩展性及复杂性 PRAM模型•基本概念–由Fortune和Wyllie1978年提出，又称SIMD-SM模型。

有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算•结构图Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory•在在PRAMPRAM上的一个并行程序由上的一个并行程序由n n个进程组个进程组成，其中第成，其中第i i个进程留驻在第个进程留驻在第i i个处理个处理器上，且由一串指令所组成器上，且由一串指令所组成•在每个基本时间步在每个基本时间步( (称为周期称为周期) )，每个，每个处理器执行一条指令处理器执行一条指令•这些指令包括数据传送、算这些指令包括数据传送、算/ /逻、控制逻、控制流以及流以及I/OI/O指令，在典型的顺序计算机指令，在典型的顺序计算机中均有这些指令中均有这些指令•1.1.同构性同构性•规模为规模为1 1的的PRAMPRAM退化为传统的退化为传统的RAMRAM这种机器为机器为SISDSISD •当处理器多于当处理器多于1 1个时，一个个时，一个PRAMPRAM将访问将访问多个数据流，且通常可执行多个指令流多个数据流，且通常可执行多个指令流因此因此PRAMPRAM是一个是一个MIMDMIMD机器。

机器•址空间址空间 •PRAMPRAM模型所有进程对所有存储单元均有模型所有进程对所有存储单元均有相等的访问时间相等的访问时间----均匀存储器访问均匀存储器访问(UMA)(UMA)模型–针对多计算机不合适针对多计算机不合适•--------在多计算机中，每个处理机有它自己的在多计算机中，每个处理机有它自己的分离地址空间这些机器被称为具有多地址分离地址空间这些机器被称为具有多地址空间多计算机的处理机间通信不是通过共空间多计算机的处理机间通信不是通过共享变量，而是借助消息传递享变量，而是借助消息传递 •存储器模型存储器模型•各种方案的主要区别在于如何协调各种方案的主要区别在于如何协调CWCW的冲突 •四种四种PRAMPRAM模型方案都与存储器读写如何处理模型方案都与存储器读写如何处理有关 (1)EREW-PRAM(1)EREW-PRAM模型模型——这种模型禁止一台以上这种模型禁止一台以上处理机同时读、写同一存储单元处理机同时读、写同一存储单元–(Snir(Snir，，19821982；；KarpKarp和和RamachandranRamachandran，，1988)1988)。

这是限制最大的这是限制最大的PRAMPRAM模型2)CREW-PRAM(2)CREW-PRAM模型模型——用互斥使写冲突避免用互斥使写冲突避免可以并行读同一存储单元可以并行读同一存储单元 (3)ERCW-PRAM(3)ERCW-PRAM模型模型——允许互斥读或并允许互斥读或并行写同一存储单元行写同一存储单元4)CRCW-PRAM(4)CRCW-PRAM模型模型——允许在同一时刻允许在同一时刻并行读或者并行写并行读或者并行写 PRAM模型•分类(1)PRAM-CRCW并发读并发写•CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据•PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入•APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入 (2)PRAM-CREW并发读互斥写 (3)PRAM-EREW互斥读互斥写 •计算能力比较–PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模拟PRAM-CREW和PRAM-CRCW •与物理模型的差异与物理模型的差异 •实际上，这种并行计算机是不存在的。

实际上，这种并行计算机是不存在的共享存储器共享存储器SIMDSIMD机是与机是与PRAMPRAM模型最接近模型最接近的结构•更确切地说，共享存储的同步更确切地说，共享存储的同步MIMDMIMD模式模式运行•四种四种PRAMPRAM方案中，方案中，EREWEREW和和CRCWCRCW是应是应用最普遍的模型用最普遍的模型–每个每个CRCWCRCW算法可用一个算法可用一个EREWEREW算法来模拟算法来模拟–CRCWCRCW算法比一个等效的算法比一个等效的EREWEREW要快，经证要快，经证明，最好的明，最好的n n—处理机处理机EREWEREW算法要比任一算法要比任一个个n-n-处理机处理机CRCWCRCW算法慢算法慢O(logn)O(logn)倍–对研究结构规则的并行性来说，用对研究结构规则的并行性来说，用PRAMPRAM比用实际机器模型要好得多比用实际机器模型要好得多–PRAMPRAM能指出实际并行计算机性能的上限能指出实际并行计算机性能的上限 PRAM模型•优点–适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节•缺点–不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素 异步APRAM模型•基本概念–又称分相（Phase）PRAM或MIMD-SM。

每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障•异步异步PRAMPRAM模型模型—APRAMAPRAM–是一个异步的是一个异步的PRAMPRAM模型，简记为模型，简记为APRAMAPRAM•模型特点：模型特点：–由由p p个处理器组成；个处理器组成；–每个处理器都有其本地存储器、局部时钟和局部每个处理器都有其本地存储器、局部时钟和局部程序；程序；–处理器间的通信经过共享全局存储器处理器间的通信经过共享全局存储器；•无全局时钟无全局时钟–各处理器异步地独立执行各自的指令；各处理器异步地独立执行各自的指令；•处理器任何时间依赖关系需明确地在各处理器的程处理器任何时间依赖关系需明确地在各处理器的程序中加入同步序中加入同步( (路路) )障障(Synchronization Barrier)(Synchronization Barrier)；；•一条指令可在非确定但有限的时间内完成一条指令可在非确定但有限的时间内完成•APRAMAPRAM模型中的指令类型有四类指令：模型中的指令类型有四类指令：•①①全局读全局读–将全局存储单元中的内容读入局存单元中；将全局存储单元中的内容读入局存单元中；•②②局部操作局部操作–对局存中的数执行操作，其结果存入局存中；对局存中的数执行操作，其结果存入局存中；•③全局写全局写–将局存单元中的内容写入全局存储单元中；将局存单元中的内容写入全局存储单元中；•④同步同步–同步是计算中的一个逻辑点，在该点各处理器同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后，才能执行其局部均需等待别的处理器到达后，才能执行其局部程序。

程序•APRAMAPRAM模型中完成的计算模型中完成的计算 •计算是由一系列用同步障分开的全局相所组计算是由一系列用同步障分开的全局相所组成–在各全局相内，每个处理器异步地运行其在各全局相内，每个处理器异步地运行其局部程序；局部程序；•每个局部程序中的最后一条指令是一条同步每个局部程序中的最后一条指令是一条同步障指令；障指令；•各处理器均可异步地读取和写入全局存储器，各处理器均可异步地读取和写入全局存储器，–在同一相内不允许两个处理器访问同一单元在同一相内不允许两个处理器访问同一单元–不同的处理器访问存储单元总是由一同步障所分不同的处理器访问存储单元总是由一同步障所分开，所以指令完成时间上的差异并不影响整个开，所以指令完成时间上的差异并不影响整个计算计算 异步APRAM模型•计算过程由同步障分开的全局相组成 •APRAMAPRAM模型中的时间计算模型中的时间计算•使用使用APRAMAPRAM模型计算算法的时间复杂度时，模型计算算法的时间复杂度时，假定局部操作取单位时间；假定局部操作取单位时间；•全局读／写时间为全局读／写时间为d d–它定量化了通信延迟，代表读它定量化了通信延迟，代表读/ /写全局存写全局存储器的平均时间，储器的平均时间，d d随机器中的处理器增随机器中的处理器增加而增加；加而增加；•同步障的时间为同步障的时间为B B–它是处理器数它是处理器数P P的非降函数的非降函数B=B(P)B=B(P)。

•在在APRAMAPRAM中假定上述参数服从如下关系：中假定上述参数服从如下关系：•2≤d≤B≤P2≤d≤B≤P•同时：同时：B(P)∈∈O(dlogP)或或B(P)∈∈O(dlogP/logd)•令令t tphph为全局相内各处理器指令执行时间中为全局相内各处理器指令执行时间中最长者，则整个程序运行时间最长者，则整个程序运行时间T T为各相的时为各相的时间之和加上间之和加上B B乘以同步障次数，即乘以同步障次数，即: :•T=∑tT=∑tphph+B+B××同步障次数同步障次数APRAM模型•优缺点 易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型•BSPBSP模型模型–BSP-Bulk Synchronization ParallelBSP-Bulk Synchronization Parallel–1. BSP1. BSP模型的提出：模型的提出：–哈佛大学的哈佛大学的Leslie ValiantLeslie Valiant提出：提出：•块同步并行块同步并行(BSP)(BSP)，用以克服，用以克服PRAMPRAM模型的缺点，但保模型的缺点，但保留其简单性。

留其简单性–一个一个BSPBSP计算机由计算机由n n个结点个结点( (处理器和存储器对处理器和存储器对) )所组成 BSP模型•基本概念–由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步 •模型参数–p：处理器数(带有存储器)–l：同步障时间(Barrier synchronization time)–g：带宽因子(time steps/packet)=1/bandwidth 选路器吞吐率•特点：特点：–一个一个BSPBSP程序有程序有n n个进程，每个驻留在一个个进程，每个驻留在一个结点上基本时间单位是周期结点上基本时间单位是周期( (或时间步或时间步) )–程序按严格的超步序列执行程序按严格的超步序列执行–同步路障迫使进程等待同步路障迫使进程等待–BSPBSP计算机是计算机是MIMDMIMD系统系统–BSPBSP模型是超步级的松同步模型是超步级的松同步–在一个超步中，不同进程以不同速率异步在一个超步中，不同进程以不同速率异步执行–BSPBSP模型交互机制是共享变量或是消息传递模型交互机制是共享变量或是消息传递 BSP模型•计算过程由若干超级步组成，每个超级步计算模式为左图•优缺点 强调了计算和通讯的分离， 提供了一个编程环境，易于 程序复杂性分析。

但需要显 式同步机制，限制至多h条 消息的传递等•一个超步执行时间的确定一个超步执行时间的确定•计算时间计算时间w w–处理器中完成计算操作所需的最大处理器中完成计算操作所需的最大周期数 •同步开销为同步开销为L L•通信开销为通信开销为ghgh周期周期–g g是实现是实现h h关系的比例系数，常数关系的比例系数，常数•结论：结论：•执行一个超步的时间为执行一个超步的时间为w+gh+Lw+gh+L•关于关于BSPBSP模型的模型的实际优点和实际优点和评论：评论：•比起比起PRAMPRAM模型来，模型来，BSPBSP模型更为现实模型更为现实–除了用于进程管理的并行性开销外，除了用于进程管理的并行性开销外，它考虑了所有其他开销它考虑了所有其他开销 logP模型•基本概念–由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步•模型参数–L：network latency–o：communication overhead–g：gap=1/bandwidth–P：#processors注：L和g反映了通讯网络的容量  logP模型•优缺点 捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。

•BSP vs. LogP–BSPLogP：BSP块同步BSP子集同步BSP进程对同步＝LogP–BSP可以常数因子模拟LogP，LogP可以对数因子模拟BSP–BSP＝LogP+Barriers－Overhead–BSP提供了更方便的程设环境，LogP更好地利用了机器资源–BSP似乎更简单、方便和符合结构化编程 。