并行算法的设计基础课件.ppt

1、2022-12-211第四章第四章 并行算法的设计基础并行算法的设计基础 并行计算相关的研究分支并行计算相关的研究分支1.1.并行计算机体系结构并行计算机体系结构2.2.并行计算的性能评价并行计算的性能评价3.3.并行算法并行算法4.4.并行程序设计并行程序设计一、并行算法相关的基本概念及表示一、并行算法相关的基本概念及表示二、介绍几种并行计算模型二、介绍几种并行计算模型3.并行算法并行算法1.并行计算机体系结构并行计算机体系结构2.并行计算的性能评价并行计算的性能评价2022-12-212一、并行算法相关的基本概念及表示一、并行算法相关的基本概念及表示1.基本概念基本概念2.并行算法的表示并

2、行算法的表示3.并行算法的复杂性度量并行算法的复杂性度量4.并行算法的同步与通信并行算法的同步与通信2022-12-2131.1.基本概念基本概念定义定义1 1：算法算法：在有限步骤内求解某一特定问题的：在有限步骤内求解某一特定问题的一组无二义性的规则。一组无二义性的规则。定义定义2 2：并行算法并行算法是由一些独立的、可以并行运行是由一些独立的、可以并行运行的计算模块（进程）构成，模块（进程）之间的计算模块（进程）构成，模块（进程）之间能相互作用和协调，以完成对一个给定问题的能相互作用和协调，以完成对一个给定问题的求解。求解。2022-12-214根据算法的不同特征，可以对并行算法进根据算法

3、的不同特征，可以对并行算法进行不同的分类：行不同的分类：SIMDSIMD算法和算法和MIMDMIMD算法算法同步算法和异步算法同步算法和异步算法数值计算算法和非数值计算算法数值计算算法和非数值计算算法共享存储算法和分布存储算法共享存储算法和分布存储算法2022-12-215定义定义3 3：同步算法同步算法(synchronized algorithm):是指算是指算法的诸进程的执行必须相互等待的一类并行算法。法的诸进程的执行必须相互等待的一类并行算法。SIMDSIMD算法是同步算法中的一种特例。算法是同步算法中的一种特例。定义定义4 4：异步算法异步算法(asynchronous algori

4、thm):是指算是指算法的诸进程的执行不必相互等待的一类并行算法。法的诸进程的执行不必相互等待的一类并行算法。定义定义5 5：分布并行算法分布并行算法(distributed algorithm)：将：将同一任务分解为若干个子任务，使之分布在由通信同一任务分解为若干个子任务，使之分布在由通信链路连接的多个节点上协同完成运算的算法。链路连接的多个节点上协同完成运算的算法。分布式算法的执行时间，在很大程度上受通信开分布式算法的执行时间，在很大程度上受通信开销的影响。销的影响。2022-12-216定义定义6 6：确定算法确定算法 (deterministic algorithm)(determin

5、istic algorithm)：每：每个运算步骤上均确定唯一操作的算法。如线性方个运算步骤上均确定唯一操作的算法。如线性方程组求解的算法。程组求解的算法。不确定算法不确定算法 (non-deterministic algorithm)(non-deterministic algorithm)：在问题求解的搜索过程中，提出多种可供选择的在问题求解的搜索过程中，提出多种可供选择的操作，它们中的任一种都有希望获得问题的解答，操作，它们中的任一种都有希望获得问题的解答，但都不能肯定解出，有时甚至不能确定这些操作但都不能肯定解出，有时甚至不能确定这些操作中哪一种求解的可能性更大些。对此，只能选择中哪一

6、种求解的可能性更大些。对此，只能选择其中任意一种搜索下去。这种搜索方法称为不确其中任意一种搜索下去。这种搜索方法称为不确定算法。定算法。2022-12-217定义定义7 7：随机算法随机算法(randomized algorithm,(randomized algorithm,probabilistic algorithm)probabilistic algorithm)计算步骤具有随机计算步骤具有随机性的算法。在算法的某一步或某些步上，可以在性的算法。在算法的某一步或某些步上，可以在指定范围内随机地选择下一个演算步的走向。指定范围内随机地选择下一个演算步的走向。如果方法得当，可比一般算法更快

7、地得出结果，如果方法得当，可比一般算法更快地得出结果，并且能以较高的概率提供正确的结果。并且能以较高的概率提供正确的结果。2022-12-218表示算法的要求表示算法的要求 无二义性无二义性 力图直观、易懂力图直观、易懂 不苛求严格的语法格式不苛求严格的语法格式一般的串行算法常用类一般的串行算法常用类PascalPascal、类、类AlgolAlgol表示表示2.2.并行算法的表示并行算法的表示2022-12-2191.par-do语句语句 for i=1 to n par-do :end for 表示其间的表示其间的 n(i=1 to n(i=1 to n)n)次语句序列的执行次语句序列的执

8、行可以并行完成可以并行完成表示表示 k k 个个处理器同时处理器同时执行其间的执行其间的语句序列语句序列2.for all 语句语句 for all Pi where 0 i k-1 do :end for并行算法常引入以下两条并行语句：并行算法常引入以下两条并行语句：2022-12-21103.3.并行算法的复杂性度量并行算法的复杂性度量令令 f(n)f(n)和和 g(n)g(n)是定义在自然数集合是定义在自然数集合N N 上的两个函数，上的两个函数，定义定义8 8：如果存在两个正数如果存在两个正数 c c 和和 n n0 0，使得对于所有，使得对于所有的的 n n n n0 0 均有均有f

9、(n)f(n)c c g(n)g(n)，则标记为：，则标记为：f(n)=f(n)=(g(n)(g(n)我们称我们称 g(n)g(n)为为 f(n)f(n)的的上界上界。定义定义9 9：如果存在两个正数如果存在两个正数 c c 和和 n n0 0，使得对于所有，使得对于所有的的 n n n n0 0 均有均有f(n)f(n)c c g(n)g(n)，则标记为：，则标记为：f(n)=f(n)=(g(n)(g(n)我们称我们称 g(n)g(n)为为 f(n)f(n)的的下界下界。2022-12-2111定义定义1010：如果存在正数：如果存在正数 c c1 1、c c2 2 和和 n n0 0，使得

10、对于，使得对于所有的所有的 n n n n0 0 均有均有c c1 1 g(n)g(n)f(n)f(n)c c2 2 g(n)g(n)，则标记为则标记为 f(n)=f(n)=(g(n)(g(n)我们称我们称 g(n)g(n)为为 f(n)f(n)的的紧致界紧致界。即：如果即：如果 f(n)=f(n)=(g(n)(g(n)且且 f(n)=f(n)=(g(n)(g(n)则则 f(n)=f(n)=(g(n)(g(n)2022-12-2112 比较两个算法的时间复杂性函数比较两个算法的时间复杂性函数g g(n n)和和f f(n n)的阶的的阶的方法：方法：n 用用定义定义判断判断n 用用求极限的方法

11、求极限的方法来加以判断。来加以判断。若若 则则（1 1）当）当c c00时，说明时，说明f f(n n)和和g g(n n)同阶，记为同阶，记为f f(n n)=)=(g g(n n)（2 2）当）当c c=0=0时，说明时，说明f f(n)(n)比比g g(n n)低阶，记为低阶，记为f f(n n)=)=O O(g g(n n)（3 3）当）当c c=时，说明时，说明f f(n)(n)比比g g(n n)高阶，记为高阶，记为f f(n n)=)=(g g(n n)cngnfn)()(lim2022-12-2113 并行算法的并行算法的运行时间运行时间 t(n)t(n)：对于输入规模为：对于

12、输入规模为 n n 的问题，在给定的并行计算模型之下求解问题所的问题，在给定的并行计算模型之下求解问题所需的时间，也称为需的时间，也称为时间复杂性时间复杂性 (time(time complexity)complexity)。运行时间运行时间 =计算时间计算时间 +通信时间通信时间 处理器数处理器数p(n)p(n)：表示对给定的问题规模：表示对给定的问题规模 n n，并行，并行算法所用的处理器的个数。算法所用的处理器的个数。并行算法的并行算法的成本成本c(n)c(n)：并行算法的运行时间：并行算法的运行时间 t(n)t(n)与所需的处理器数与所需的处理器数 p(n)p(n)之积，即之积，即c(

13、n)=t(n)c(n)=t(n)*p(n)p(n)2022-12-2114例例:(1)设设f(n)=n2/2,g(n)=307n2，则，则因此，因此，f(n)=n2/2与与g(n)=307n2是同阶的。是同阶的。(2)设设f(n)=lg n，g(n)=n，则，则所以，所以，f(n)=lg n比比g(n)=n低阶。低阶。0)/(lnlim)2ln/1()2ln/(lnlim)/(loglimnnnnnnnnn614/1)307/()2/(lim22nnn2022-12-2115定义定义1111：一个并行算法：一个并行算法最坏情况下的时间复杂性最坏情况下的时间复杂性(worst-case time

14、-complexity)(worst-case time-complexity)：对于所有输：对于所有输入规模为入规模为 n n 的问题，在给定的并行计算模型之下的问题，在给定的并行计算模型之下求解问题所需的时间的最大值。求解问题所需的时间的最大值。定义定义1212：一个并行算法的：一个并行算法的期望时间复杂性期望时间复杂性(expected time-complexity)(expected time-complexity)：对于所有输入：对于所有输入规模为规模为 n n 的问题，在给定的计算模型之下求解问的问题，在给定的计算模型之下求解问题所需的时间的平均值。题所需的时间的平均值。2022

15、-12-2116定义定义1313：一个并行算法：一个并行算法最坏情况下的空间复杂性最坏情况下的空间复杂性(worst-case space-complexity)(worst-case space-complexity)：对于所有输：对于所有输入规模为入规模为 n n 的问题，在给定的并行计算模型之下的问题，在给定的并行计算模型之下求解问题所需的内存空间的最大值。求解问题所需的内存空间的最大值。定义定义1414：一个并行算法的：一个并行算法的期望空间复杂性期望空间复杂性(expected(expected space-complexity)space-complexity)：对于所有输入规模为

16、：对于所有输入规模为 n n 的的问题，在给定的计算模型之下求解问题所需的内问题，在给定的计算模型之下求解问题所需的内存空间的平均值。存空间的平均值。2022-12-2117定义定义1515：如果一个并行算法的成本与其对应的最佳：如果一个并行算法的成本与其对应的最佳串行算法的最坏情况下时间复杂性在同一个数量串行算法的最坏情况下时间复杂性在同一个数量级上，则称该并行算法为级上，则称该并行算法为成本最佳的成本最佳的(cost-(cost-optimal)optimal)或最佳并行算法或最佳并行算法 (optimal parallel(optimal parallel algorithm)algor

17、ithm)。总运算总运算量量W(n):(W(n):(并行并行)算法中所要完成的总的操算法中所要完成的总的操作数量作数量(the number of computational(the number of computational operations)operations)2022-12-21184.4.并行算法中的同步与通信并行算法中的同步与通信同步同步(synchronization)(synchronization)：使多个相关事件的发：使多个相关事件的发生保持相同的节奏，彼此之间能良好地配合。生保持相同的节奏，彼此之间能良好地配合。在并行算法的各进程异步执行过程中，为了确保在并行算法

18、的各进程异步执行过程中，为了确保各处理器的正确工作顺序和对共享存储器的访问，各处理器的正确工作顺序和对共享存储器的访问，程序员需要在算法的适当位置设置同步点。程序员需要在算法的适当位置设置同步点。下面给出一个利用下面给出一个利用 lock lock 和和 unlock unlock 构造的临界构造的临界区完成数组求和的算法区完成数组求和的算法2022-12-2119begin S=0 for all Pi where 0 i p-1 do L=0 for j=i to n-1 step p do L=L+aj end for lock(u)S=S+L unlock(u)end forend算法

19、算法4.1.3 共享存储多处理机上求和算法共享存储多处理机上求和算法输入：输入：A=(a0,a1,an-1),处理器数处理器数 p；输出：输出：a 0+a 1+a n-1 存放在全局变量存放在全局变量S 中。中。2022-12-2120通信通信(communication)(communication)：把信息用一定手段通过：把信息用一定手段通过某种介质或传输线路从一个点传送至另一点的过某种介质或传输线路从一个点传送至另一点的过程。程。通信是在空间上对并发执行的进程实现数据交换。通信是在空间上对并发执行的进程实现数据交换。原语原语 (primitive)(primitive)：它由若干条机器指

20、令构成的，：它由若干条机器指令构成的，用来完成特定功能的一段程序。原语有以下特点：用来完成特定功能的一段程序。原语有以下特点：不可中断性不可中断性：一旦原语被开始执行，就应不间：一旦原语被开始执行，就应不间断地执行到结束；断地执行到结束；不可侵犯性不可侵犯性：原语一旦被执行，中间不许插入：原语一旦被执行，中间不许插入任何其他操作。任何其他操作。2022-12-2121通信可使用通信原语来表示：通信可使用通信原语来表示：1.1.在共享存储的多处理机中，可使用在共享存储的多处理机中，可使用1)global read(1)global read(X X,Y),Y)将全局存储器中数据将全局存储器中数据

21、 X X 读入局部变量读入局部变量 Y Y；2)global write(U,2)global write(U,V V)将局部数据将局部数据 U U 写入共享存储变量写入共享存储变量 V V 中。中。2.2.在分布存储的多计算机中，可使用在分布存储的多计算机中，可使用1)send(X,i)1)send(X,i)或或 send(X,Psend(X,Pi i)当前处理器发送数据当前处理器发送数据 X X 到到 P Pi i ；2)receive(Y,j)2)receive(Y,j)或或 receive(Y,Preceive(Y,Pj j)当前处理器从当前处理器从P Pj j 接收数据接收数据 Y

22、Y。2022-12-2122算法算法4.1.4 分布存储多计算机上矩阵向量相乘算法分布存储多计算机上矩阵向量相乘算法给定给定:一个一个 n*n 的矩阵的矩阵 A 和一个向量和一个向量 X a11 a12 a13 a1n-1 a1n a21 a22 a23 a2n-1 a2n A=a31 a32 a33 a3n-1 a3n .an1 an2 an3 ann-1 ann x1 x2X=x3 xn计算计算:A:A*X X，得到一个向量。假设，得到一个向量。假设 r=n/p r=n/p 为一整数为一整数因为我们打算在分布存储的多计算机系统上运行该因为我们打算在分布存储的多计算机系统上运行该算法，被计算

23、的数据只能分布在各个处理器的局部算法，被计算的数据只能分布在各个处理器的局部存储器上。存储器上。2022-12-2123我们把我们把 A A 按列分为按列分为 p p 个个 n n*r r 的小矩阵的小矩阵A A1 1,A,A2 2,A,Ap p 把把 X X 按行分为按行分为 p p 个个 r r*1 1 的小向量的小向量X X1 1,X,X2 2,X,Xp p计算计算 A A*X X就转化为计算就转化为计算：A A1 1 X X1 1+A+A2 2 X X2 2+A Ap p X Xp p所以处理器所以处理器P Pi i（其中（其中1 1 i i p p）将将A Ai i 和和 X Xi

24、i 存放存放在自己的局部存储器中，各处理器首先计算在自己的局部存储器中，各处理器首先计算 A Ai i X Xi i ，然后利用通信实现数据求和。，然后利用通信实现数据求和。X1(r*1)X2(r*1)Xp(r*1)A=A1 A2 Ap X=(n*r)(n*r)(n*r)2022-12-2124我们假设处理器是以环结构组织的我们假设处理器是以环结构组织的PiP2PpP12022-12-2125算法算法4.1.4 分布存储多计算机上矩阵向量相乘算法分布存储多计算机上矩阵向量相乘算法输入：输入：处理器数处理器数 p，第第 i 个个 A 矩阵分量矩阵分量 Ai 于于 B 中，中，第第 i 个个 X

25、向量分量向量分量 Xi于于 w 中中;输出：输出：A*X 于于 P1 变量变量 y 中。中。begin compute z=Bw if i=1 then y=0 else receive(y,left)endif y=y+z send(y,right)if i=1 then receive(y,left)end2022-12-2126p1p3p2p4计算计算z=Bw计算计算z=Bw计算计算z=Bw计算计算z=Bwy=0rec(y,p1)rec(y,p2)rec(y,p3)y=y+zsend(y,p2)send(y,p3)send(y,p4)rec(y,p4)send(y,p1)y=y+zy(1

26、)y=y+zy(2)y=y+zy(3)y(4)结束结束2022-12-2127第四章第四章 并行算法的设计基础并行算法的设计基础一、并行算法相关的基本概念及表示一、并行算法相关的基本概念及表示二、介绍几种并行计算模型二、介绍几种并行计算模型二、介绍几种并行计算模型二、介绍几种并行计算模型2022-12-2128二、并行计算模型二、并行计算模型并行计算模型并行计算模型：从并行算法的设计和分析出发，：从并行算法的设计和分析出发，将各种并行计算机（至少是某一类并行计算机）将各种并行计算机（至少是某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。的基本特征抽象出来，形成一个抽象的计算模型。

27、并行计算模型为并行计算提供了硬件和软件的界并行计算模型为并行计算提供了硬件和软件的界面，使硬件设计者和软件设计者可以开发并行性面，使硬件设计者和软件设计者可以开发并行性的支持机制，从而提高系统的性能。的支持机制，从而提高系统的性能。对并行算法的研制者，对并行算法的研制者，不会局限于不会局限于某种具体的并某种具体的并行计算机来研究并行算法，而需借助于抽象的计行计算机来研究并行算法，而需借助于抽象的计算模型，算模型，它是设计和分析并行算法的基础它是设计和分析并行算法的基础。2022-12-2129 为了能对计算机系统进行简单、明确的描述，发现一为了能对计算机系统进行简单、明确的描述，发现一般规律，

28、通常在不同层次上进行抽象来定义模型。般规律，通常在不同层次上进行抽象来定义模型。不同层次模型的关系图：不同层次模型的关系图：编程模型编程模型计算模型计算模型体系结构模型体系结构模型机器模型机器模型用户用户系统系统硬件和硬件和操作系统操作系统互连网络的作用和互连网络的作用和执行通信的形式等执行通信的形式等计算机的费用计算机的费用和资源和资源编程语言的语编程语言的语义义2022-12-2130并行计算模型的主要作用并行计算模型的主要作用：它是并行算法实现的基础它是并行算法实现的基础对同一问题在不同的模型上的不同解决办法，对同一问题在不同的模型上的不同解决办法，来比较该问题究竟更合理在哪一种模型上实

29、来比较该问题究竟更合理在哪一种模型上实现现它给并行算法设计和分析提供了一个简单、方它给并行算法设计和分析提供了一个简单、方便的框架便的框架撇开了硬件的繁杂的细节撇开了硬件的繁杂的细节它使并行算法设计具有一定的生命力它使并行算法设计具有一定的生命力集中集中精力开发应用精力开发应用问题自身问题自身的的并行性并行性和和算法算法的性能的性能，并使，并使算法算法具有一定的具有一定的通用性通用性2022-12-2131 串行算法的研究已经相当成熟，它们基本上都是串行算法的研究已经相当成熟，它们基本上都是基于基于冯冯.诺依曼诺依曼(von Neumann)体系结构体系结构控制器控制器运算器运算器主存储器主存

30、储器输出设备输出设备输入设备输入设备CPU高速缓存高速缓存2022-12-2132程序程序指令指令计数器计数器r0r1r2r3:存储器存储器累加器累加器xnx2x1只读输入磁带只读输入磁带y2y1只写输出磁带只写输出磁带串行计算模型串行计算模型RAM(Random Access Machine)RAM(Random Access Machine)2022-12-2133 RAMRAM机器模型的指令系统与实际计算机的指令系机器模型的指令系统与实际计算机的指令系统类似，有四类指令：统类似，有四类指令：1.1.控制流向指令，控制流向指令，如如 jump;jump;2.2.输入输入/输出指令，输出指令

31、，如如 read,writeread,write；3.3.累加器与存储器之间的传送数据指令，如累加器与存储器之间的传送数据指令，如 loadload；4.4.算术运算指令，算术运算指令，如如 addadd。2022-12-21341.PRAM 模型模型(Parallel Random Access Machine Model)19781978年年S.Fortune S.Fortune 和和 J.WyllieJ.Wyllie总结了阵列式结构的总结了阵列式结构的并行机和流水线结构的向量机的特点，将其抽象并行机和流水线结构的向量机的特点，将其抽象为具有如下特征的为具有如下特征的 PRAM PRAM

32、模型：模型：1 1）有一个控制器）有一个控制器2 2）有）有 p p（可有限或无限）台功能相同的处理器（可有限或无限）台功能相同的处理器3 3）有一个容量无限的共享存储器）有一个容量无限的共享存储器4 4）每台处理器有自己的局部存储器）每台处理器有自己的局部存储器5 5）处于激活状态的处理器必须执行相同的指令）处于激活状态的处理器必须执行相同的指令6 6）允许任何时刻各处理器均可通过共享存储器与其）允许任何时刻各处理器均可通过共享存储器与其它处理器交换数据。它处理器交换数据。2022-12-2135 PRAMPRAM模型模型-SIMD-SIMD计算模型计算模型控控 制制 器器互互 联联 网网

33、络络全全 局局 共共 享享 存存 储储 器器P P1 1LMLM1 1P P2 2LMLM2 2P Pp pLMLMp p2022-12-2136 PRAM PRAM 模型允许任何时刻各处理器均可通过共享存模型允许任何时刻各处理器均可通过共享存储器的共享单元与其它处理器交换数据。储器的共享单元与其它处理器交换数据。根据处理器对共享单元的存、取访问的不同约束条根据处理器对共享单元的存、取访问的不同约束条件进一步对件进一步对 PRAM PRAM 模型分类：模型分类：PRAM-EREWPRAM-EREW(Exclusive Read,Exclusive (Exclusive Read,Exclusi

34、ve Write)Write)：不允许有读冲突和写冲突：不允许有读冲突和写冲突PRAM-CREWPRAM-CREW(Concurrent Read,Exclusive (Concurrent Read,Exclusive Write)Write)：每次允许多台处理器同时读同一共享单：每次允许多台处理器同时读同一共享单元内容，但不允许同时写。元内容，但不允许同时写。PRAM-CRCWPRAM-CRCW(Concurrent Read,Concurrent (Concurrent Read,Concurrent Write)Write)：允许多台处理器同时读、写同一共享单：允许多台处理器同时读、写

35、同一共享单元内容。元内容。2022-12-2137 PRAM-CRCW 模型中允许同时写同一共享单元显然是模型中允许同时写同一共享单元显然是不现实的，所以不现实的，所以对对PRAM-CRCW 模型作了更进一步的模型作了更进一步的约定：约定：共用的共用的 (Common)PRAM-CRCW：同时写同一共享同时写同一共享单元的所有处理器必须写相同的值；单元的所有处理器必须写相同的值；优先的优先的 (Priority)PRAM-CRCW：从同时要写同从同时要写同一共享单元的所有处理器中找出标号最小的处一共享单元的所有处理器中找出标号最小的处理器，将它的值写入共享地址中；理器，将它的值写入共享地址中；

36、任意的任意的 (Arbitrary)PRAM-CRCW：从同时要写从同时要写同一共享单元的所有处理器中任选一个处理器同一共享单元的所有处理器中任选一个处理器的值写入共享地址中。的值写入共享地址中。2022-12-2138 PRAM PRAM 模型上的算法的执行：模型上的算法的执行：1 1）输入数据存放在全局共享存储器中，并只有）输入数据存放在全局共享存储器中，并只有一个处理器处于激活状态；一个处理器处于激活状态；2 2）在每个计算步中，一个激活的处理器可做：）在每个计算步中，一个激活的处理器可做：从局部或全局存储器中读一个值从局部或全局存储器中读一个值完成一个完成一个 RAM RAM 操作操作

37、写值到局部或全局存储器中写值到局部或全局存储器中激活另一个处理器激活另一个处理器2022-12-2139 算法算法4.2.1 4.2.1 在在 PRAM-EREW PRAM-EREW 模型上求和算法模型上求和算法输入：输入：n n个待求和的数个待求和的数 A 0.(n-1)A 0.(n-1)输出：最终的输出：最终的n n个数的和在个数的和在 A 0 A 0 中中全局变量：全局变量：n,A 0.(n-1),jn,A 0.(n-1),jbegin*spawn(P0,P1,Pn/2-1)for all Pi where 0 i n/2-1 do for j=0 to log n-1 do if i

38、mod 2j=0 and 2i+2j n then A 2i =A 2i +A 2i+2j endif endfor endforend2022-12-2140spawn()：激活激活 n 个处理机个处理机 例：例：n=12spawn()：激活激活 n 个处理机的时间为个处理机的时间为 log n 。时间2022-12-21412.APRAM 2.APRAM 模型模型 (Asynchronous PRAM)(Asynchronous PRAM)8080年代初，人们总结了共享存储型多处理机结构年代初，人们总结了共享存储型多处理机结构的向量机的特点，将其抽象为具有如下特征的的向量机的特点，将其抽象

39、为具有如下特征的 APRAM APRAM 模型：模型：1 1）有）有 p p（可有限或无限）个处理器；（可有限或无限）个处理器；2 2）每个处理器有自己的控制器（局部时钟）；）每个处理器有自己的控制器（局部时钟）；3 3）有一个容量无限的共享存储器；）有一个容量无限的共享存储器；4 4）每台处理器有自己的局部存储器和局部程序；）每台处理器有自己的局部存储器和局部程序；5 5）各处理器异步地、独立地执行各自的指令，处理）各处理器异步地、独立地执行各自的指令，处理器间的同步需明确地在各处理器的程序中加入障器间的同步需明确地在各处理器的程序中加入障碍（路障）同步碍（路障）同步 (barrier sy

40、nchronization)指指令；令；6 6）利用共享存储器实现处理器间的通信。）利用共享存储器实现处理器间的通信。2022-12-2142 APRAM APRAM 模型模型-MIMD-MIMD计算模型计算模型控制器控制器1互互 联联 网网 络络全全 局局 共共 享享 存存 储储 器器P1LM1P2LM2PpLMp控制器控制器2控制器控制器p2022-12-2143 PRAM模型模型-SIMD计算模型（计算模型（对比对比）控控 制制 器器互互 联联 网网 络络全全 局局 共共 享享 存存 储储 器器P1LM1P2LM2PpLMp2022-12-2144 APRAM APRAM 模型同样利用共

41、享存储器实现处理器间的模型同样利用共享存储器实现处理器间的通信通信 障碍障碍(路障路障)同步同步 (barrier synchronization)：它在程序中设置一些障碍点，当处理器执行到障它在程序中设置一些障碍点，当处理器执行到障碍点时暂停，等待所有进程都执行到这个障碍点碍点时暂停，等待所有进程都执行到这个障碍点上，以此方法取得同步。上，以此方法取得同步。2022-12-2145 APRAM APRAM 模型中的计算模型中的计算 :计算是由一系列用同步障碍点分开的计算是由一系列用同步障碍点分开的全局相全局相（global phaseglobal phase）组成的。）组成的。在各全局相内每

42、个处理器异步地运行其局部在各全局相内每个处理器异步地运行其局部程序程序每个局部程序中的最后一条指令是一条障碍每个局部程序中的最后一条指令是一条障碍同步指令同步指令各处理器均可异步地读取和写入全局存储器，各处理器均可异步地读取和写入全局存储器，但在同一相（但在同一相（phasephase）内不允许两个处理器）内不允许两个处理器访问同一共享单元访问同一共享单元2022-12-2146处理器处理器 1 1 处理器处理器 2 2 处理器处理器 3 3 Phase1同步障碍同步障碍read x1 read x3 read xnread x2 :write to B :write to A write t

43、o C write to Dread B read A read C :write to B write to D :write to C write to Bread D :read A :write to BPhase2同步障碍同步障碍Phase3同步障碍同步障碍2022-12-2147 在在APRAMAPRAM模型上设计的算法的时间复杂性包括以模型上设计的算法的时间复杂性包括以下几个方面：下几个方面：假设一个局部操作取为假设一个局部操作取为 1 1 个单位时间个单位时间 全局读全局读/写时间为写时间为 d d，它表示全局读，它表示全局读/写的平均时写的平均时间。该值应随着处理器的个数增加

44、而增加。间。该值应随着处理器的个数增加而增加。同步障碍的时间为同步障碍的时间为 B B，B B 是处理器个数是处理器个数 p p 的非递的非递减函数减函数 B(p)B(p)。在在 APRAM APRAM 中常假设：中常假设：2 2 d d B B p p 设设 t tphph 为全局相内各处理器指令执行时间中最长为全局相内各处理器指令执行时间中最长者，则整个程序运行时间者，则整个程序运行时间 T T 应为：应为：T=T=t tphph+B +B*同步障碍次数同步障碍次数2022-12-21483.Log P 3.Log P 模型模型 (Latency,overhead,gap,Processo

45、r)(Latency,overhead,gap,Processor)19931993年年D.Culler D.Culler 等人在分析了等人在分析了分布式存储计算机分布式存储计算机特特点的基础上，提出了点的基础上，提出了基于点到点通信基于点到点通信的多计算机模的多计算机模型型-Log P-Log P模型。模型。该模型虽未涉及到网络的具体结构，但充分说明了该模型虽未涉及到网络的具体结构，但充分说明了互联网络的性能特性：互联网络的性能特性：互连网络带宽的限制互连网络带宽的限制 通信中可观的延迟通信中可观的延迟 它是它是 MPPMPP 系统的模型系统的模型2022-12-2149 Log P Log

46、 P 模型主要由以下模型主要由以下4 4个参数来描述：个参数来描述：1 1）L L(Latency)最大延迟：在通信时包含一个或几个最大延迟：在通信时包含一个或几个字的一个消息从源节点传到目标节点的时间的上字的一个消息从源节点传到目标节点的时间的上限值。限值。2 2）o o(overhead)开销：处理器准备发送或接收一开销：处理器准备发送或接收一个消息的时间开销，在这段时间里处理器不能执个消息的时间开销，在这段时间里处理器不能执行其它操作。行其它操作。3 3）g g(gap)间隔：一台处理器发送或接收一组消息间隔：一台处理器发送或接收一组消息时，两个消息之间的最小时间间隔，其倒数即为时，两个

47、消息之间的最小时间间隔，其倒数即为处理器的通信带宽。处理器的通信带宽。4 4）P P(Processor)节点数：处理器节点数：处理器/存储器个数，假存储器个数，假定每个局部操作需要定每个局部操作需要 1 1 个单位时间（即一个处理个单位时间（即一个处理器周期）。器周期）。2022-12-2150Log P 的参数示意图的参数示意图PiPkPj处理器o gL o 消息下一个消息时间发送并接收一个消息共需发送并接收一个消息共需2o+L2o+L个单位时间个单位时间;处理器处理器 Pi Pi 在向处理器在向处理器 PjPj 发送消息后发送消息后,在发送下一个消息之前必须等待在发送下一个消息之前必须等

48、待 g g 个时间单位。个时间单位。2022-12-2151 LogPLogP模型的特点模型的特点处理机之间异步地工作，通过消息传递实现同步；处理机之间异步地工作，通过消息传递实现同步；消息延迟不确定，但延迟不会大于消息延迟不确定，但延迟不会大于L L，即任何消息，即任何消息经历的等待时间是不可预测的，但不会超过经历的等待时间是不可预测的，但不会超过L L；Log PLog P模型支持了模型支持了计算和通信计算和通信的的重叠重叠；能够预测算法的实际运行时间。能够预测算法的实际运行时间。Log PLog P模型抓住了网络与处理机之间的性能瓶颈。消模型抓住了网络与处理机之间的性能瓶颈。消息间隔参数

49、息间隔参数 g g 反映了通信带宽，当一台处理机发送反映了通信带宽，当一台处理机发送的消息已到达这个容量限度时，再发送的消息将被的消息已到达这个容量限度时，再发送的消息将被阻塞。阻塞。2022-12-2152例例2 2：在通信模式是一棵树的情况下求和算法：在通信模式是一棵树的情况下求和算法 假设假设P=8、L=5、g=4、o=2，我们考虑在时，我们考虑在时间为间为 28 个单位时间内最多可能求和的个数。个单位时间内最多可能求和的个数。P0P4P6P7P2P3P5P12022-12-21534.BSP 4.BSP 模型模型 (Bulk Synchronous Parallel)(Bulk Syn

50、chronous Parallel)BSP BSP 模型是模型是一个分布存储的一个分布存储的 MIMDMIMD 计算模型计算模型 BSP BSP 模型的组成主要包括如下部分：模型的组成主要包括如下部分：1 1）若干个能进行处理和内存操作的处理器，）若干个能进行处理和内存操作的处理器，2 2）一个用于在处理器之间传递消息的路由器，）一个用于在处理器之间传递消息的路由器，3 3）在定义的时间间隔内，对所有处理器进行同步）在定义的时间间隔内，对所有处理器进行同步的机制。一般情况下，假设这个全局同步机制是的机制。一般情况下，假设这个全局同步机制是用特殊的硬件支持的。用特殊的硬件支持的。一个一个 BSP