并行算法的设计基础课件

第四章并行算法的设计基础并行计算相关的研究分支1.并行计算机体系结构2.并行计算的性能评价3.并行算法4.并行程序设计一、并行算法相关的基本概念及表示二、介绍几种并行计算模型3.并行算法1.并行计算机体系结构2.并行计算的性能评价11/30/20221第四章并行算法的设计基础并行计算相关的研究分支一、并行算一、并行算法相关的基本概念及表示基本概念并行算法的表示并行算法的复杂性度量并行算法的同步与通信11/30/20222一、并行算法相关的基本概念及表示基本概念11/30/20221.基本概念定义1：算法：在有限步骤内求解某一特定问题的一组无二义性的规则。定义2：并行算法是由一些独立的、可以并行运行的计算模块（进程）构成，模块（进程）之间能相互作用和协调，以完成对一个给定问题的求解。11/30/202231.基本概念定义1：算法：在有限步骤内求解某一特定问题的一根据算法的不同特征，可以对并行算法进行不同的分类：SIMD算法和MIMD算法同步算法和异步算法数值计算算法和非数值计算算法共享存储算法和分布存储算法11/30/20224根据算法的不同特征，可以对并行算法进行不同的分类：11/30定义3：同步算法(synchronizedalgorithm):是指算法的诸进程的执行必须相互等待的一类并行算法。SIMD算法是同步算法中的一种特例。定义4：异步算法(asynchronousalgorithm):是指算法的诸进程的执行不必相互等待的一类并行算法。定义5：分布并行算法(distributedalgorithm)：将同一任务分解为若干个子任务，使之分布在由通信链路连接的多个节点上协同完成运算的算法。分布式算法的执行时间，在很大程度上受通信开销的影响。11/30/20225定义3：同步算法(synchronizedalgorith定义6：确定算法(deterministicalgorithm)：每个运算步骤上均确定唯一操作的算法。如线性方程组求解的算法。

不确定算法(non-deterministicalgorithm)：在问题求解的搜索过程中，提出多种可供选择的操作，它们中的任一种都有希望获得问题的解答，但都不能肯定解出，有时甚至不能确定这些操作中哪一种求解的可能性更大些。对此，只能选择其中任意一种搜索下去。这种搜索方法称为不确定算法。11/30/20226定义6：确定算法(deterministicalgori定义7：随机算法(randomizedalgorithm,probabilisticalgorithm)计算步骤具有随机性的算法。在算法的某一步或某些步上，可以在指定范围内随机地选择下一个演算步的走向。如果方法得当，可比一般算法更快地得出结果，并且能以较高的概率提供正确的结果。11/30/20227定义7：随机算法(randomizedalgorithm表示算法的要求无二义性力图直观、易懂不苛求严格的语法格式一般的串行算法常用类Pascal、类Algol表示2.并行算法的表示11/30/20228表示算法的要求2.并行算法的表示11/30/202281.par-do语句fori=1tonpar-do::endfor表示其间的n(i=1ton)次语句序列的执行可以并行完成表示k个处理器同时执行其间的语句序列2.forall语句forallPiwhere0i

k-1do::endfor并行算法常引入以下两条并行语句：11/30/202291.par-do语句表示其间的n(i=1ton)3.并行算法的复杂性度量令f(n)和g(n)是定义在自然数集合N上的两个函数，定义8：如果存在两个正数c和n0，使得对于所有的nn0均有f(n)

cg(n)，则标记为：

f(n)=(g(n))

我们称g(n)为f(n)的上界。定义9：如果存在两个正数c和n0，使得对于所有的nn0均有f(n)cg(n)，则标记为：

f(n)=(g(n))我们称g(n)为f(n)的下界。11/30/2022103.并行算法的复杂性度量令f(n)和g(n)是定义定义10：如果存在正数c1、c2

和n0，使得对于所有的nn0均有c1g(n)f(n)

c2g(n)，则标记为

f(n)=(g(n))我们称g(n)为f(n)的紧致界。即：如果f(n)=(g(n))且f(n)=(g(n))

则f(n)=(g(n))11/30/202211定义10：如果存在正数c1、c2和n0，使得对于所有

比较两个算法的时间复杂性函数g(n)和f(n)的阶的方法：用定义判断用求极限的方法来加以判断。若

则（1）当c≠0时，说明f(n)和g(n)同阶，记为f(n)=Θ(g(n))（2）当c=0时，说明f(n)比g(n)低阶，记为f(n)=O(g(n))（3）当c=∞时，说明f(n)比g(n)高阶，记为f(n)=Ω(g(n))11/30/20221211/30/202212并行算法的运行时间t(n)：对于输入规模为n的问题，在给定的并行计算模型之下求解问题所需的时间，也称为时间复杂性(timecomplexity)。运行时间=计算时间+通信时间处理器数p(n)：表示对给定的问题规模n，并行算法所用的处理器的个数。并行算法的成本c(n)：并行算法的运行时间t(n)与所需的处理器数p(n)之积，即c(n)=t(n)*p(n)11/30/202213并行算法的运行时间t(n)：对于输入规模为n的问题，例:(1)设f(n)=n2/2,g(n)=307n2，则因此，f(n)=n2/2与g(n)=307n2是同阶的。

(2)设f(n)=lgn，g(n)=n，则所以，f(n)=lgn比g(n)=n低阶。11/30/202214例:(1)设f(n)=n2/2,g(n)=307n2，则1定义11：一个并行算法最坏情况下的时间复杂性(worst-casetime-complexity)：对于所有输入规模为n的问题，在给定的并行计算模型之下求解问题所需的时间的最大值。定义12：一个并行算法的期望时间复杂性(expectedtime-complexity)：对于所有输入规模为n的问题，在给定的计算模型之下求解问题所需的时间的平均值。11/30/202215定义11：一个并行算法最坏情况下的时间复杂性(worst-定义13：一个并行算法最坏情况下的空间复杂性(worst-casespace-complexity)：对于所有输入规模为n的问题，在给定的并行计算模型之下求解问题所需的内存空间的最大值。定义14：一个并行算法的期望空间复杂性(expectedspace-complexity)：对于所有输入规模为n的问题，在给定的计算模型之下求解问题所需的内存空间的平均值。11/30/202216定义13：一个并行算法最坏情况下的空间复杂性(worst-c定义15：如果一个并行算法的成本与其对应的最佳串行算法的最坏情况下时间复杂性在同一个数量级上，则称该并行算法为成本最佳的(cost-optimal)或最佳并行算法(optimalparallelalgorithm)。总运算量W(n):(并行)算法中所要完成的总的操作数量(thenumberofcomputationaloperations)11/30/202217定义15：如果一个并行算法的成本与其对应的最佳串行算法的最坏4.并行算法中的同步与通信同步(synchronization)：使多个相关事件的发生保持相同的节奏，彼此之间能良好地配合。在并行算法的各进程异步执行过程中，为了确保各处理器的正确工作顺序和对共享存储器的访问，程序员需要在算法的适当位置设置同步点。下面给出一个利用lock和unlock构造的临界区完成数组求和的算法11/30/2022184.并行算法中的同步与通信同步(synchronizatibeginS=0forallPiwhere0ip-1doL=0forj=iton-1steppdoL=L

+ajendforlock(u)S=S+Lunlock(u)endforend[算法4.1.3]共享存储多处理机上求和算法输入：A=(a0,a1,…,an-1),处理器数p；输出：a0+a1+…+an-1存放在全局变量S

中。11/30/202219begin[算法4.1.3]共享存储多处理机上求和算法通信(communication)：把信息用一定手段通过某种介质或传输线路从一个点传送至另一点的过程。通信是在空间上对并发执行的进程实现数据交换。原语(primitive)：它由若干条机器指令构成的，用来完成特定功能的一段程序。原语有以下特点：不可中断性：一旦原语被开始执行，就应不间断地执行到结束；不可侵犯性：原语一旦被执行，中间不许插入任何其他操作。11/30/202220通信(communication)：把信息用一定手段通过某种通信可使用通信原语来表示：1.在共享存储的多处理机中，可使用1)globalread(X,Y)将全局存储器中数据X读入局部变量Y；2)globalwrite(U,V)将局部数据U写入共享存储变量V中。2.在分布存储的多计算机中，可使用1)send(X,i)或send(X,Pi)当前处理器发送数据X到Pi；2)receive(Y,j)或receive(Y,Pj)当前处理器从Pj接收数据Y。11/30/202221通信可使用通信原语来表示：11/30/202221[算法4.1.4]分布存储多计算机上矩阵向量相乘算法给定:一个n*n的矩阵A和一个向量X

a11a12a13……a1n-1a1na21a22a23……a2n-1a2n

A=a31a32a33……a3n-1a3n……..an1an2an3……ann-1annx1x2X=x3…xn计算:A*X，得到一个向量。假设r=n/p为一整数因为我们打算在分布存储的多计算机系统上运行该算法，被计算的数据只能分布在各个处理器的局部存储器上。11/30/202222[算法4.1.4]分布存储多计算机上矩阵向量相乘算法我们把A按列分为p个n*r的小矩阵A1,A2,…,Ap

把X按行分为p个r*1的小向量X1,X2,…,Xp计算A*X就转化为计算：A1X1+A2X2+…ApXp所以处理器Pi（其中1ip）将Ai和Xi存放在自己的局部存储器中，各处理器首先计算AiXi，然后利用通信实现数据求和。X1(r*1)X2(r*1)…Xp(r*1)A=A1A2

…ApX=

(n*r)(n*r)(n*r)11/30/202223我们把A按列分为p个n*r的小矩阵A1,A2我们假设处理器是以环结构组织的PiP2PpP111/30/202224我们假设处理器是以环结构组织的PiP2PpP111/30/2[算法4.1.4]分布存储多计算机上矩阵向量相乘算法输入：处理器数p，第i个A矩阵分量Ai于B中，第i个X向量分量Xi于w中;输出：A*X于P1变量y中。begincomputez=Bwifi=1theny=0elsereceive(y,left)endify=y+zsend(y,right)ifi=1thenreceive(y,left)end11/30/202225[算法4.1.4]分布存储多计算机上矩阵向量相乘算法11/p1p3p2p4计算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)y=y+zy(2)y=y+zy(3)y(4)结束11/30/202226p1p3p2p4计算z=Bw计算z=Bw计算z=Bw计算z=第四章并行算法的设计基础一、并行算法相关的基本概念及表示二、介绍几种并行计算模型二、介绍几种并行计算模型11/30/202227第四章并行算法的设计基础一、并行算法相关的基本概念及表示二、并行计算模型并行计算模型：从并行算法的设计和分析出发，将各种并行计算机（至少是某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。并行计算模型为并行计算提供了硬件和软件的界面，使硬件设计者和软件设计者可以开发并行性的支持机制，从而提高系统的性能。对并行算法的研制者，不会局限于某种具体的并行计算机来研究并行算法，而需借助于抽象的计算模型，它是设计和分析并行算法的基础。11/30/202228二、并行计算模型并行计算模型：从并行算法的设计和分析出发，将为了能对计算机系统进行简单、明确的描述，发现一般规律，通常在不同层次上进行抽象来定义模型。不同层次模型的关系图：编程模型计算模型体系结构模型机器模型用户系统硬件和操作系统互连网络的作用和执行通信的形式等计算机的费用和资源编程语言的语义11/30/202229为了能对计算机系统进行简单、明确的描述，发现一般规律，通常在并行计算模型的主要作用：它是并行算法实现的基础对同一问题在不同的模型上的不同解决办法，来比较该问题究竟更合理在哪一种模型上实现它给并行算法设计和分析提供了一个简单、方便的框架撇开了硬件的繁杂的细节它使并行算法设计具有一定的生命力集中精力开发应用问题自身的并行性和算法的性能，并使算法具有一定的通用性11/30/202230并行计算模型的主要作用：11/30/202230串行算法的研究已经相当成熟，它们基本上都是基于冯.诺依曼(vonNeumann)体系结构控制器运算器主存储器输出设备输入设备CPU高速缓存11/30/202231串行算法的研究已经相当成熟，它们基本上都是基于冯.诺依曼(v程序指令计数器r0r1r2r3:存储器累加器xn……x2x1只读输入磁带……y2y1只写输出磁带串行计算模型RAM(RandomAccessMachine)11/30/202232指令r0存储器累加器xn……x2x1只读输入磁带……y2y1RAM机器模型的指令系统与实际计算机的指令系统类似，有四类指令：1.控制流向指令，如jump;2.输入/输出指令，如read,write；3.累加器与存储器之间的传送数据指令，如load；4.算术运算指令，如add。11/30/202233RAM机器模型的指令系统与实际计算机的指令系统类似，有四类指PRAM模型

(ParallelRandomAccessMachineModel)1978年S.Fortune和J.Wyllie总结了阵列式结构的并行机和流水线结构的向量机的特点，将其抽象为具有如下特征的PRAM模型：1）有一个控制器2）有p（可有限或无限）台功能相同的处理器3）有一个容量无限的共享存储器4）每台处理器有自己的局部存储器5）处于激活状态的处理器必须执行相同的指令6）允许任何时刻各处理器均可通过共享存储器与其它处理器交换数据。11/30/202234PRAM模型

(ParallelRandomAccesPRAM模型----SIMD计算模型控制器互联网络全局共享存储器P1LM1P2LM2PpLMp……11/30/202235PRAM模型----SIMD计算模型控制器互联PRAM模型允许任何时刻各处理器均可通过共享存储器的共享单元与其它处理器交换数据。根据处理器对共享单元的存、取访问的不同约束条件进一步对PRAM模型分类：PRAM-EREW(ExclusiveRead,ExclusiveWrite)：不允许有读冲突和写冲突PRAM-CREW(ConcurrentRead,ExclusiveWrite)：每次允许多台处理器同时读同一共享单元内容，但不允许同时写。PRAM-CRCW(ConcurrentRead,ConcurrentWrite)：允许多台处理器同时读、写同一共享单元内容。11/30/202236PRAM模型允许任何时刻各处理器均可通过共享存储器的共享单PRAM-CRCW模型中允许同时写同一共享单元显然是不现实的，所以对PRAM-CRCW模型作了更进一步的约定：共用的

(Common)PRAM-CRCW：同时写同一共享单元的所有处理器必须写相同的值；优先的

(Priority)PRAM-CRCW：从同时要写同一共享单元的所有处理器中找出标号最小的处理器，将它的值写入共享地址中；任意的

(Arbitrary)PRAM-CRCW：从同时要写同一共享单元的所有处理器中任选一个处理器的值写入共享地址中。11/30/202237PRAM-CRCW模型中允许同时写同一共享单元显然是不现实PRAM模型上的算法的执行：1）输入数据存放在全局共享存储器中，并只有一个处理器处于激活状态；2）在每个计算步中，一个激活的处理器可做：从局部或全局存储器中读一个值完成一个RAM操作写值到局部或全局存储器中激活另一个处理器11/30/202238PRAM模型上的算法的执行：11/30/202238[算法4.2.1]在PRAM-EREW模型上求和算法输入：n个待求和的数A[0..(n-1)]输出：最终的n个数的和在A[0]中全局变量：n,A[0..(n-1)],jbegin*spawn(P0,P1,…,Pn/2-1)forallPiwhere0in/2-1doforj=0tologn-1doifimod2j=0and2i+2j<nthenA[2i]=A[2i]+A[2i+2j]endifendforendforend11/30/202239[算法4.2.1]在PRAM-EREW模型上求和算法spawn()：激活n个处理机例：n=12spawn()：激活n个处理机的时间为logn。时间11/30/202240spawn()：激活n个处理机例：n=12spa2.APRAM模型(AsynchronousPRAM)80年代初，人们总结了共享存储型多处理机结构的向量机的特点，将其抽象为具有如下特征的APRAM模型：1）有p（可有限或无限）个处理器；2）每个处理器有自己的控制器（局部时钟）；3）有一个容量无限的共享存储器；4）每台处理器有自己的局部存储器和局部程序；5）各处理器异步地、独立地执行各自的指令，处理器间的同步需明确地在各处理器的程序中加入障碍（路障）同步(barriersynchronization)指令；6）利用共享存储器实现处理器间的通信。11/30/2022412.APRAM模型(AsynchronousPRAAPRAM模型----MIMD计算模型控制器1互联网络全局共享存储器P1LM1P2LM2PpLMp……控制器2控制器p……11/30/202242APRAM模型----MIMD计算模型控制器1互联PRAM模型----SIMD计算模型（对比）控制器互联网络全局共享存储器P1LM1P2LM2PpLMp……11/30/202243PRAM模型----SIMD计算模型（对比）控制器互APRAM模型同样利用共享存储器实现处理器间的通信障碍(路障)同步

(barriersynchronization)：它在程序中设置一些障碍点，当处理器执行到障碍点时暂停，等待所有进程都执行到这个障碍点上，以此方法取得同步。11/30/202244APRAM模型同样利用共享存储器实现处理器间的通信11/3APRAM模型中的计算:计算是由一系列用同步障碍点分开的全局相（globalphase）组成的。在各全局相内每个处理器异步地运行其局部程序每个局部程序中的最后一条指令是一条障碍同步指令各处理器均可异步地读取和写入全局存储器，但在同一相（phase）内不允许两个处理器访问同一共享单元11/30/202245APRAM模型中的计算:11/30/202245处理器1处理器2处理器3

Phase1同步障碍readx1readx3readxnreadx2:::writetoB:writetoAwritetoCwritetoDreadBreadAreadC:::writetoBwritetoD:writetoCwritetoBreadD:readA::writetoBPhase2同步障碍Phase3同步障碍11/30/202246处理器1处理器2处理器3在APRAM模型上设计的算法的时间复杂性包括以下几个方面：假设一个局部操作取为1个单位时间全局读/写时间为d，它表示全局读/写的平均时间。该值应随着处理器的个数增加而增加。同步障碍的时间为B，B是处理器个数p的非递减函数B(p)。在APRAM中常假设：2dBp设tph为全局相内各处理器指令执行时间中最长者，则整个程序运行时间T应为：T=tph+B*同步障碍次数11/30/202247在APRAM模型上设计的算法的时间复杂性包括以下几个方面：13.LogP模型

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

(Latency,overLogP模型主要由以下4个参数来描述：1）L(Latency)最大延迟：在通信时包含一个或几个字的一个消息从源节点传到目标节点的时间的上限值。2）o(overhead)开销：处理器准备发送或接收一个消息的时间开销，在这段时间里处理器不能执行其它操作。3）g(gap)间隔：一台处理器发送或接收一组消息时，两个消息之间的最小时间间隔，其倒数即为处理器的通信带宽。4）P(Processor)节点数：处理器/存储器个数，假定每个局部操作需要1个单位时间（即一个处理器周期）。11/30/202249LogP模型主要由以下4个参数来描述：11/30/202LogP的参数示意图PiPkPj处理器ogLo消息下一个消息时间发送并接收一个消息共需2o+L个单位时间;处理器Pi在向处理器Pj发送消息后,在发送下一个消息之前必须等待g个时间单位。11/30/202250LogP的参数示意图PiPkPj处理器oLogP模型的特点处理机之间异步地工作，通过消息传递实现同步；消息延迟不确定，但延迟不会大于L，即任何消息经历的等待时间是不可预测的，但不会超过L；LogP模型支持了计算和通信的重叠；能够预测算法的实际运行时间。LogP模型抓住了网络与处理机之间的性能瓶颈。消息间隔参数g反映了通信带宽，当一台处理机发送的消息已到达这个容量限度时，再发送的消息将被阻塞。11/30/202251LogP模型的特点11/30/202251例2：在通信模式是一棵树的情况下求和算法假设P=8、L=5、g=4、o=2，我们考虑在时间为28个单位时间内最多可能求和的个数。P0P4P6P7P2P3P5P111/30/202252例2：在通信模式是一棵树的情况下求和算法假设P=84.BSP模型(BulkSynchronousParallel)BSP模型是一个分布存储的MIMD计算模型BSP模型的组成主要包括如下部分：1）若干个能进行处理和内存操作的处理器，2）一个用于在处理器之间传递消息的路由器，3）在定义的时间间隔内，对所有处理器进行同步的机制。一般情况下，假设这个全局同步机制是用特殊的硬件支持的。一个BSP程序是由一系列超步(superstep)组成的。11/30/2022534.BSP模型(BulkSynchronousPaBSP模型有以下三个重要参数：1）处理器数p2）路由器吞吐量g，（也称为带宽因子）3）全局同步之间的时间间隔L在一个超步中，一个处理机最多发送h个消息或接收h个消息。若有h个消息，则称此通信有一个h关系(h-relation)。g值的定义方式：每秒处理机所能完成的局部计算数与每秒路由器所能传输的数据量之比；或在一个h关系中,传递h个消息所需的时间为g.h。11/30/202254BSP模型有以下三个重要参数：11/30/202254BSP模型与APRAM模型类似，使用障碍同步使整个计算任务以紧同步方式进行各处理器局部计算全局通信障碍同步一个超步的执行时间：计算时间max+ghmax+l11/30/202255BSP模型与APRAM模型类似，使用障碍同步使整个计算BSP模型的主要特点：将处理器和路由器分开，即把计算任务和通信任务分开。路由器仅进行点到点的消息传递，不考虑互连网络的拓扑结构；利用硬件实现全局障碍同步使并行粒度增大(相对APRAM而言)，并能够实现紧耦合同步并行算法；兼顾了计算和通信的平衡问题；硬件可将L设置尽量小----这表示通信带宽会更宽些，在设计并行算法时应使L尽量大从而提高并行粒度。11/30/202256BSP模型的主要特点：11/30/2022565.C3模型(Computing,Communication,Congestion)1994年S.E.Hambrush等人在分析高性能可扩展的网络计算机系统特点的基础上提出了C3模型，它适用于粗粒度的并行系统。和BPS与LogP模型相似，C3计算模型也将计算划分为一系列超级步，同步出现在两个超级步之间，这个同步也是利用障碍同步机制来实现。拥塞(Congestion)：在通信网络中，当各输入站的呼叫数量超过网络的容量，或超过了网络处理的能力时，则称网络中发生了拥塞。11/30/2022575.C3模型(Computing,CommunicatC3模型主要由以下几个参数来描述：1）处理器的个数p；2）网络延迟h：网络中任意两节点间的距离的平均值；3）网络的对分宽度b：表示网络的带宽；4）启动时间s，即建立一个消息时的开销；5）消息包的长度l，即消息包所含字节数。消息包是处理机间通信的基本单位。11/30/202258C3模型主要由以下几个参数来描述：11/30/202258C3模型中用到的一些概念C3模型中考虑了两种路由方式：存储转发路由方式(store-and-forwardmode)：它是网络中信息交换的一种方式。转发中心不是将终端发出的信息立即传送到接收终端，而是先存储起来，等待适当的时机，选择空闲的信道，并按信息的优先级别转发到下一个转发中心或接收终端。虫孔(虫蚀)路由方式(wormholeroutingmode)：在平面网络结构的多处理机系统中进行路径选择的一种方法。它把消息分成若干个包，包又分成若干个称为迁移块(flit)的基本信息单元。每个包中的迁移块以流水线方式向前依次传送。只有包的头几个迁移块含有路径信息，因而一个包的所有迁移块必须一个跟着一个，而不能被别的消息包打断。11/30/202259C3模型中用到的一些概念C3模型中考虑了两种路由方式：11C3模型中用到的一些概念C3模型中考虑了两种发送/接收原语：1）阻塞发送和接收原语2）非阻塞发送和接收原语阻塞发送(blockingsend)：指一个源处理器从开始发送一条消息，直到它被目标处理器收到消息，源处理器的发送操作才结束。非阻塞的发送(non-blockingsend)：源处理器只需将要发送的消息放在发送缓冲器。非阻塞的发送不需考虑目标处理器什么时候接收到信息。11/30/202260C3模型中用到的一些概念C3模型中考虑了两种发送/接收各种并行计算模型的比较

模型属性PRAMAPRAMLogPBSPC3体系结构SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM计算模式同步计算异步计算异步计算异步计算异步计算同步方式自动同步障碍同步隐式同步障碍同步障碍同步计算粒度细/中粒度中/大粒度中/大粒度中/大粒度粗粒度通信方式共享变量共享变量发/收消息发/收消息发/收消息模型参数1(单位时间步)d:全局读/写时间B:同步时间L:通信延迟o:通信开销g:消息间隔P:处理器数p:处理器数g:带宽因子L:同步间隔l:消息包长度s:发送开销h:通信延迟11/30/202261各种并行计算模型的比较模型PRAMAPRAMLogPBS由于并行计算机正在处于飞速发展中，但尚未定型，因此到现在为止，还没有一个通用的并行计算模型。人们只能将某一类并行机的基本特征抽象出来，形成各种特定的并行计算模型，以便并行算法的设计与理论分析。11/30/202262由于并行计算机正在处于飞速发展中，但尚未定型，因此到现在为止PRAM模型是对一类共享的并行机特征抽取，它抛开了通信的干扰，可用于开发细粒度并行算法；LogP模型是对一类分布式并行计算机特征抽取，基于点对点通信的计算模型，集中分析处理机与网络之间的瓶颈问题；C3模型是对一类基于消息传递的分布式粗粒度系统特征抽取，集中反映的是网络拥挤和路由影响。11/30/202263PRAM模型是对一类共享的并行机特征抽取，它抛开了通信的干例1_1：在PRAM-EREW计算机上对两个N维向量A和B求内积s。假设用p个处理机完成该任务，并设N/p是整数，内积的值在LocalVal[0]中。VECTORMUL(PRAM-EREW):GlobalN,i,A[0..N-1],B[0..N-1],LocalVal[0..p-1]Localjbeginspawn(P0,P1,P2,…,Pp-1)forallPi,其中0ip-1dobeginLocalVal[i]=0;forj=i;j<NsteppdoLocalVal[i]=LocalVal[i]+A[j]*B[j];forj=0tologp-1doifimod2j+1==0andi+2j<pthenLocalVal[i]=LocalVal[i]+LocalVal[i+2j]end;end11/30/202264例1_1：在PRAM-EREW计算机上对两个N维向量A该算法的执行时间：假设一次乘法和加法各用一个单位时间激活p个处理机的时间：logp---spawn(P0,P1,P2,…,Pp-1)

各处理机计算局部和的时间：2N/p-------forj=i;j<NsteppdoLocalVal[i]=LocalVal[i]+A[j]*B[j];求全局和的时间：logpforj=0tologp-1doifimod2j+1==0andi+2j<pthenLocalVal[i]=LocalVal[i]+LocalVal[i+2j]整个算法的执行时间为：2logp+2N/p=(logp+N/p)相应的串行算法的执行时间为：2N当N>>p时，该PRAM算法的加速比为：2N/(2logp+2N/p)→p11/30/202265该算法的执行时间：11/30/202265例1_2：在APRAM计算模型上对两个N维向量A和B求内积。算法思想：整个算法仅需一个全局相。将数据分散在各个处理机的局部存储器中；在全局相中：局部计算：每个处理机在2N/p个单位时间内计算出局部和。全局计算：将各个处理机的局部和放到全局存储器中，并求总和。执行时间=(pd+p)

障碍同步。时间为B。11/30/202266例1_2：在APRAM计算模型上对两个N维向量A例1_3：在BSP计算机上对两个N维向量A和B求内积。假设用p=8个处理机完成该任务，用4个超步完成问题的求解。超步1：计算：每个处理机在2N/8个单位时间内计算出局部和。通信：处理机0，2，4，6将其局部和送给处理机1，3，5，7。完成1-relation通信。障碍同步。超步2：计算：处理机1，3，5，7各自完成一次加法。通信：处理机1，5将其局部和送给处理机3，7。完成1-relation通信。障碍同步。超步3：计算：处理机3，7各自完成一次加法。通信：处理机3将其局部和送给处理机7。完成1-relation通信。障碍同步。超步4：计算：处理机7完成一次加法，产生最终结果。不再需要通信和同步。11/30/202267例1_3：在BSP计算机上对两个N维向量A和B求该算法各个超步的执行时间：超步1：2N/8+g+l超步2：1+g+l超步3：1+g+l超步4：1该算法总的执行时间：2N/8+3g+3l+3若处理机的个数为p，则算法总的执行时间：2N/p+logp(g+l+1)相对PRAM算法，算法时间增加了g*logp和l*logp，显然BSP模型考虑了通信和同步开销。11/30/202268该算法各个超步的执行时间：11/30/202268第四章并行算法的设计基础并行计算相关的研究分支1.并行计算机体系结构2.并行计算的性能评价3.并行算法4.并行程序设计一、并行算法相关的基本概念及表示二、介绍几种并行计算模型3.并行算法1.并行计算机体系结构2.并行计算的性能评价11/30/202269第四章并行算法的设计基础并行计算相关的研究分支一、并行算一、并行算法相关的基本概念及表示基本概念并行算法的表示并行算法的复杂性度量并行算法的同步与通信11/30/202270一、并行算法相关的基本概念及表示基本概念11/30/20221.基本概念定义1：算法：在有限步骤内求解某一特定问题的一组无二义性的规则。定义2：并行算法是由一些独立的、可以并行运行的计算模块（进程）构成，模块（进程）之间能相互作用和协调，以完成对一个给定问题的求解。11/30/2022711.基本概念定义1：算法：在有限步骤内求解某一特定问题的一根据算法的不同特征，可以对并行算法进行不同的分类：SIMD算法和MIMD算法同步算法和异步算法数值计算算法和非数值计算算法共享存储算法和分布存储算法11/30/202272根据算法的不同特征，可以对并行算法进行不同的分类：11/30定义3：同步算法(synchronizedalgorithm):是指算法的诸进程的执行必须相互等待的一类并行算法。SIMD算法是同步算法中的一种特例。定义4：异步算法(asynchronousalgorithm):是指算法的诸进程的执行不必相互等待的一类并行算法。定义5：分布并行算法(distributedalgorithm)：将同一任务分解为若干个子任务，使之分布在由通信链路连接的多个节点上协同完成运算的算法。分布式算法的执行时间，在很大程度上受通信开销的影响。11/30/202273定义3：同步算法(synchronizedalgorith定义6：确定算法(deterministicalgorithm)：每个运算步骤上均确定唯一操作的算法。如线性方程组求解的算法。

不确定算法(non-deterministicalgorithm)：在问题求解的搜索过程中，提出多种可供选择的操作，它们中的任一种都有希望获得问题的解答，但都不能肯定解出，有时甚至不能确定这些操作中哪一种求解的可能性更大些。对此，只能选择其中任意一种搜索下去。这种搜索方法称为不确定算法。11/30/202274定义6：确定算法(deterministicalgori定义7：随机算法(randomizedalgorithm,probabilisticalgorithm)计算步骤具有随机性的算法。在算法的某一步或某些步上，可以在指定范围内随机地选择下一个演算步的走向。如果方法得当，可比一般算法更快地得出结果，并且能以较高的概率提供正确的结果。11/30/202275定义7：随机算法(randomizedalgorithm表示算法的要求无二义性力图直观、易懂不苛求严格的语法格式一般的串行算法常用类Pascal、类Algol表示2.并行算法的表示11/30/202276表示算法的要求2.并行算法的表示11/30/202281.par-do语句fori=1tonpar-do::endfor表示其间的n(i=1ton)次语句序列的执行可以并行完成表示k个处理器同时执行其间的语句序列2.forall语句forallPiwhere0i

k-1do::endfor并行算法常引入以下两条并行语句：11/30/2022771.par-do语句表示其间的n(i=1ton)3.并行算法的复杂性度量令f(n)和g(n)是定义在自然数集合N上的两个函数，定义8：如果存在两个正数c和n0，使得对于所有的nn0均有f(n)

cg(n)，则标记为：

f(n)=(g(n))

我们称g(n)为f(n)的上界。定义9：如果存在两个正数c和n0，使得对于所有的nn0均有f(n)cg(n)，则标记为：

f(n)=(g(n))我们称g(n)为f(n)的下界。11/30/2022783.并行算法的复杂性度量令f(n)和g(n)是定义定义10：如果存在正数c1、c2

和n0，使得对于所有的nn0均有c1g(n)f(n)

c2g(n)，则标记为

f(n)=(g(n))我们称g(n)为f(n)的紧致界。即：如果f(n)=(g(n))且f(n)=(g(n))

则f(n)=(g(n))11/30/202279定义10：如果存在正数c1、c2和n0，使得对于所有

比较两个算法的时间复杂性函数g(n)和f(n)的阶的方法：用定义判断用求极限的方法来加以判断。若

则（1）当c≠0时，说明f(n)和g(n)同阶，记为f(n)=Θ(g(n))（2）当c=0时，说明f(n)比g(n)低阶，记为f(n)=O(g(n))（3）当c=∞时，说明f(n)比g(n)高阶，记为f(n)=Ω(g(n))11/30/20228011/30/202212并行算法的运行时间t(n)：对于输入规模为n的问题，在给定的并行计算模型之下求解问题所需的时间，也称为时间复杂性(timecomplexity)。运行时间=计算时间+通信时间处理器数p(n)：表示对给定的问题规模n，并行算法所用的处理器的个数。并行算法的成本c(n)：并行算法的运行时间t(n)与所需的处理器数p(n)之积，即c(n)=t(n)*p(n)11/30/202281并行算法的运行时间t(n)：对于输入规模为n的问题，例:(1)设f(n)=n2/2,g(n)=307n2，则因此，f(n)=n2/2与g(n)=307n2是同阶的。

(2)设f(n)=lgn，g(n)=n，则所以，f(n)=lgn比g(n)=n低阶。11/30/202282例:(1)设f(n)=n2/2,g(n)=307n2，则1定义11：一个并行算法最坏情况下的时间复杂性(worst-casetime-complexity)：对于所有输入规模为n的问题，在给定的并行计算模型之下求解问题所需的时间的最大值。定义12：一个并行算法的期望时间复杂性(expectedtime-complexity)：对于所有输入规模为n的问题，在给定的计算模型之下求解问题所需的时间的平均值。11/30/202283定义11：一个并行算法最坏情况下的时间复杂性(worst-定义13：一个并行算法最坏情况下的空间复杂性(worst-casespace-complexity)：对于所有输入规模为n的问题，在给定的并行计算模型之下求解问题所需的内存空间的最大值。定义14：一个并行算法的期望空间复杂性(expectedspace-complexity)：对于所有输入规模为n的问题，在给定的计算模型之下求解问题所需的内存空间的平均值。11/30/202284定义13：一个并行算法最坏情况下的空间复杂性(worst-c定义15：如果一个并行算法的成本与其对应的最佳串行算法的最坏情况下时间复杂性在同一个数量级上，则称该并行算法为成本最佳的(cost-optimal)或最佳并行算法(optimalparallelalgorithm)。总运算量W(n):(并行)算法中所要完成的总的操作数量(thenumberofcomputationaloperations)11/30/202285定义15：如果一个并行算法的成本与其对应的最佳串行算法的最坏4.并行算法中的同步与通信同步(synchronization)：使多个相关事件的发生保持相同的节奏，彼此之间能良好地配合。在并行算法的各进程异步执行过程中，为了确保各处理器的正确工作顺序和对共享存储器的访问，程序员需要在算法的适当位置设置同步点。下面给出一个利用lock和unlock构造的临界区完成数组求和的算法11/30/2022864.并行算法中的同步与通信同步(synchronizatibeginS=0forallPiwhere0ip-1doL=0forj=iton-1steppdoL=L

+ajendforlock(u)S=S+Lunlock(u)endforend[算法4.1.3]共享存储多处理机上求和算法输入：A=(a0,a1,…,an-1),处理器数p；输出：a0+a1+…+an-1存放在全局变量S

中。11/30/202287begin[算法4.1.3]共享存储多处理机上求和算法通信(communication)：把信息用一定手段通过某种介质或传输线路从一个点传送至另一点的过程。通信是在空间上对并发执行的进程实现数据交换。原语(primitive)：它由若干条机器指令构成的，用来完成特定功能的一段程序。原语有以下特点：不可中断性：一旦原语被开始执行，就应不间断地执行到结束；不可侵犯性：原语一旦被执行，中间不许插入任何其他操作。11/30/202288通信(communication)：把信息用一定手段通过某种通信可使用通信原语来表示：1.在共享存储的多处理机中，可使用1)globalread(X,Y)将全局存储器中数据X读入局部变量Y；2)globalwrite(U,V)将局部数据U写入共享存储变量V中。2.在分布存储的多计算机中，可使用1)send(X,i)或send(X,Pi)当前处理器发送数据X到Pi；2)receive(Y,j)或receive(Y,Pj)当前处理器从Pj接收数据Y。11/30/202289通信可使用通信原语来表示：11/30/202221[算法4.1.4]分布存储多计算机上矩阵向量相乘算法给定:一个n*n的矩阵A和一个向量X

a11a12a13……a1n-1a1na21a22a23……a2n-1a2n

A=a31a32a33……a3n-1a3n……..an1an2an3……ann-1annx1x2X=x3…xn计算:A*X，得到一个向量。假设r=n/p为一整数因为我们打算在分布存储的多计算机系统上运行该算法，被计算的数据只能分布在各个处理器的局部存储器上。11/30/202290[算法4.1.4]分布存储多计算机上矩阵向量相乘算法我们把A按列分为p个n*r的小矩阵A1,A2,…,Ap

把X按行分为p个r*1的小向量X1,X2,…,Xp计算A*X就转化为计算：A1X1+A2X2+…ApXp所以处理器Pi（其中1ip）将Ai和Xi存放在自己的局部存储器中，各处理器首先计算AiXi，然后利用通信实现数据求和。X1(r*1)X2(r*1)…Xp(r*1)A=A1A2

…ApX=

(n*r)(n*r)(n*r)11/30/202291我们把A按列分为p个n*r的小矩阵A1,A2我们假设处理器是以环结构组织的PiP2PpP111/30/202292我们假设处理器是以环结构组织的PiP2PpP111/30/2[算法4.1.4]分布存储多计算机上矩阵向量相乘算法输入：处理器数p，第i个A矩阵分量Ai于B中，第i个X向量分量Xi于w中;输出：A*X于P1变量y中。begincomputez=Bwifi=1theny=0elsereceive(y,left)endify=y+zsend(y,right)ifi=1thenreceive(y,left)end11/30/202293[算法4.1.4]分布存储多计算机上矩阵向量相乘算法11/p1p3p2p4计算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)y=y+zy(2)y=y+zy(3)y(4)结束11/30/202294p1p3p2p4计算z=Bw计算z=Bw计算z=Bw计算z=第四章并行算法的设计基础一、并行算法相关的基本概念及表示二、介绍几种并行计算模型二、介绍几种并行计算模型11/30/202295第四章并行算法的设计基础一、并行算法相关的基本概念及表示二、并行计算模型并行计算模型：从并行算法的设计和分析出发，将各种并行计算机（至少是某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。并行计算模型为并行计算提供了硬件和软件的界面，使硬件设计者和软件设计者可以开发并行性的支持机制，从而提高系统的性能。对并行算法的研制者，不会局限于某种具体的并行计算机来研究并行算法，而需借助于抽象的计算模型，它是设计和分析并行算法的基础。11/30/202296二、并行计算模型并行计算模型：从并行算法的设计和分析出发，将为了能对计算机系统进行简单、明确的描述，发现一般规律，通常在不同层次上进行抽象来定义模型。不同层次模型的关系图：编程模型计算模型体系结构模型机器模型用户系统硬件和操作系统互连网络的作用和执行通信的形式等计算机的费用和资源编程语言的语义11/30/202297为了能对计算机系统进行简单、明确的描述，发现一般规律，通常在并行计算模型的主要作用：它是并行算法实现的基础对同一问题在不同的模型上的不同解决办法，来比较该问题究竟更合理在哪一种模型上实现它给并行算法设计和分析提供了一个简单、方便的框架撇开了硬件的繁杂的细节它使并行算法设计具有一定的生命力集中精力开发应用问题自身的并行性和算法的性能，并使算法具有一定的通用性11/30/202298并行计算模型的主要作用：11/30/202230串行算法的研究已经相当成熟，它们基本上都是基于冯.诺依曼(vonNeumann)体系结构控制器运算器主存储器输出设备输入设备CPU高速缓存11/30/202299串行算法的研究已经相当成熟，它们基本上都是基于冯.诺依曼(v程序指令计数器r0r1r2r3:存储器累加器xn……x2x1只读输入磁带……y2y1只写输出磁带串行计算模型RAM(RandomAccessMachine)11/30/2022100指令r0存储器累加器xn……x2x1只读输入磁带……y2y1RAM机器模型的指令系统与实际计算机的指令系统类似，有四类指令：1.控制流向指令，如jump;2.输入/输出指令，如read,write；3.累加器与存储器之间的传送数据指令，如load；4.算术运算指令，如add。11/30/2022101RAM机器模型的指令系统与实际计算机的指令系统类似，有四类指PRAM模型

(ParallelRandomAccessMachineModel)1978年S.Fortune和J.Wyllie总结了阵列式结构的并行机和流水线结构的向量机的特点，将其抽象为具有如下特征的PRAM模型：1）有一个控制器2）有p（可有限或无限）台功能相同的处理器3）有一个容量无限的共享存储器4）每台处理器有自己的局部存储器5）处于激活状态的处理器必须执行相同的指令6）允许任何时刻各处理器均可通过共享存储器与其它处理器交换数据。11/30/2022102PRAM模型

(ParallelRandomAccesPRAM模型----SIMD计算模型控制器互联网络全局共享存储器P1LM1P2LM2PpLMp……11/30/2022103PRAM模型----SIMD计算模型控制器互联PRAM模型允许任何时刻各处理器均可通过共享存储器的共享单元与其它处理器交换数据。根据处理器对共享单元的存、取访问的不同约束条件进一步对PRAM模型分类：PRAM-EREW(ExclusiveRead,ExclusiveWrite)：不允许有读冲突和写冲突PRAM-CREW(ConcurrentRead,ExclusiveWrite)：每次允许多台处理器同时读同一共享单元内容，但不允许同时写。PRAM-CRCW(ConcurrentRead,ConcurrentWrite)：允许多台处理器同时读、写同一共享单元内容。11/30/2022104PRAM模型允许任何时刻各处理器均可通过共享存储器的共享单PRAM-CRCW模型中允许同时写同一共享单元显然是不现实的，所以对PRAM-CRCW模型作了更进一步的约定：共用的

(Common)PRAM-CRCW：同时写同一共享单元的所有处理器必须写相同的值；优先的

(Priority)PRAM-CRCW：从同时要写同一共享单元的所有处理器中找出标号最小的处理器，将它的值写入共享地址中；任意的

(Arbitrary)PRAM-CRCW：从同时要写同一共享单元的所有处理器中任选一个处理器的值写入共享地址中。11/30/2022105PRAM-CRCW模型中允许同时写同一共享单元显然是不现实PRAM模型上的算法的执行：1）输入数据存放在全局共享存储器中，并只有一个处理器处于激活状态；2）在每个计算步中，一个激活的处理器可做：从局部或全局存储器中读一个值完成一个RAM操作写值到局部或全局存储器中激活另一个处理器11/30/2022106PRAM模型上的算法的执行：11/30/202238[算法4.2.1]在PRAM-EREW模型上求和算法输入：n个待求和的数A[0..(n-1)]输出：最终的n个数的和在A[0]中全局变量：n,A[0..(n-1)],jbegin*spawn(P0,P1,…,Pn/2-1)forallPiwhere0in/2-1doforj=0tologn-1doifimod2j=0and2i+2j<nthenA[2i]=A[2i]+A[2i+2j]endifendforendforend11/30/2022107[算法4.2.1]在PRAM-EREW模型上求和算法spawn()：激活n个处理机例：n=12spawn()：激活n个处理机的时间为logn。时间11/30/2022108spawn()：激活n个处理机例：n=12spa2.APRAM模型(AsynchronousPRAM)80年代初，人们总结了共享存储型多处理机结构的向量机的特点，将其抽象为具有如下特征的APRAM模型：1）有p（可有限或无限）个处理器；2）每个处理器有自己的控制器（局部时钟）；3）有一个容量无限的共享存储器；4）每台处理器有自己的局部存储器和局部程序；5）各处理器异步地、独立地执行各自的指令，处理器间的同步需明确地在各处理器的程序中加入障碍（路障）同步(barriersynchronization)指令；6）利用共享存储器实现处理器间的通信。11/30/20221092.APRAM模型(AsynchronousPRAAPRAM模型----MIMD计算模型控制器1互联网络全局共享存储器P1LM1P2LM2PpLMp……控制器2控制器p……11/