计算机软件及应用并行计算算法.pptx

串行算法的直接并行化串行算法的直接并行化设计方法描述快排序算法的并行化第1页/共144页 设计方法的描述设计方法的描述方法描述发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。许多并行编程语言都支持通过在原有的串行程序中加入并行原语（例如某些通信命令等）的方法将串行程序并行化。第2页/共144页设计方法的描述设计方法的描述评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一；不是所有的串行算法都可以直接并行化的；某些串行算法有内在的串行性，比如在某些串行算法中，每一步都要用到上一步的结果。只有当上一步完全结束后，下一步才能开始。这样，各步之间就不能并行，只能考虑其它的并行化办法。例如模拟退火算法，每个温度下迭代的出发点是上一个温度下迭代的结束点。这样就很难直接将各个温度的迭代并行起来。第3页/共144页设计方法的描述设计方法的描述评注一个好的串行算法并不能并行化为一个好的并行算法；另一方面，不好的串行算法并行化后也可能是优秀的并行算法。例如，串行算法中是没有冗余计算的。但是在并行算法中，使用适当的冗余计算也可能使并行算法效率更高。加入冗余计算的并行算法就可能比直接由串行算法并行化得到的算法效率高。又比如，枚举不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法。许多数值串行算法可以并行化为有效的数值并行算法。第4页/共144页设计方法的描述设计方法的描述假设我们想用求和的方法进行数值积分。设被积函数为f(x)，积分区间为a,b。为了积分，将区间a,b均匀分成N个小区间，每个小区间长 ，根据积分的定义 是第i 个小区间左端点的坐标，而 是f(x)在第i 个小区间上积分的近似值。如果使用串行算法，可以用循环和叠加完成上述求和。这个串行算法可以直接并行化。第5页/共144页设计方法的描述设计方法的描述假设有k台处理器，可以把这N个小区间上的计算任务分到各处理器：0号处理器负责第 个小区间上的计算和累加，1号处理器负责第 个小区间上的计算和累加，k-1号处理器负责第 个小区间上的计算和累加。k个处理器并行地计算出部分和，然后再把结果加到一起。第6页/共144页设计方法的描述设计方法的描述第7页/共144页 快排序算法的并行化快排序算法的并行化算法 PRAM-CRCW上的快排序二叉树构造算法 输入：序列(A1,An)和n个处理器 输出：供排序用的一棵二叉排序树 Begin (1)for each processor i do (2)repeat for each processor iroot do (1.1)root=i if(AiAfi)(Ai=Afiifi)then (1.2)fi=root (2.1)LCfi=i (1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif end for else (2.3)RCfi=i (2.4)if i=RCfi then exit else fi=RCfi endif endif end repeat End第8页/共144页 从问题描述开始设计并行算从问题描述开始设计并行算法法方法描述从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。评注挖掘问题的固有特性与并行的关系；设计全新的并行算法是一个挑战性和创造性的工作；利用串的周期性的PRAM-CRCW算法是一个很好的范例；第9页/共144页并行串匹配算法并行串匹配算法给定长度为n的正文串正文串T和长度为m的模式串模式串P，找出P在T中所有出现的位置称为串匹配问题。研究发现，两串能否匹配是与串本身的特性有关的。这种特性，就是串的周期性周期性。串可以分为周期的和非周期的。可以引入见证函数见证函数（Witness Function）来判断串的周期性。确定了串的周期性后就可以先研究非周期串的匹配，然后在此基础上再研究周期串的匹配。第10页/共144页并行串匹配算法并行串匹配算法对于非周期串的研究，就是如何利用见证函数快速地找出P在T中的位置。为此，引入竞争函数竞争函数duel(p,q)duel(p,q)。先把正文串分成小段，借助于见证函数并行地计算竞争函数值，找出那些可能匹配的位置。然后逐步扩大正文串分段的长度，并计算竞争函数值，在可能匹配的位置中排除那些不可能匹配的位置。最后在剩下的可能位置中验证哪些是符合要求的位置。第11页/共144页并行串匹配算法并行串匹配算法假设T=abaababaababaababaababa，n=23，P=abaababa，m=8。由见证函数可知P是非周期串。因为P只可能在前16个位置上与T匹配，所以在找所有“可能位置”时只考虑T的前16个字符。匹配时，先要计算见证函数值，然后由其计算 的值，找到可能匹配的位置。计算duel(p,q)时，可以所有的块并行计算。先将P和T分成长度为2的块，用模式块(ab)与正文块(ab)(aa)(ba)(ba)(ab)(ab)(aa)(ba)进行匹配可知模式块(ab)在位置1，4，6，9，11，14，16（即duel(p,q)的获胜者）出现匹配。再把P与T划分成长度为4的块，用模式块(abaa)与正文块(abaa)(baba)(abab)(aaba)进行匹配,可知在位置1，6，11，16出现匹配（位置4、9、14被淘汰）；最后用模式串(abaababa)在正文串的位置1，6，11，16进行检查，排除那些不匹配的位置。本例中这4个位置都匹配。第12页/共144页借用已有算法求解新问题借用已有算法求解新问题设计方法描述利用矩阵乘法求所有点对间最短路径第13页/共144页 设计方法的描述设计方法的描述方法描述找出求解问题和某个已解决问题之间的联系；改造或利用已知算法应用到求解问题上。评注 这是一项创造性的工作；使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。第14页/共144页利用矩阵乘法求所有点对间最短路利用矩阵乘法求所有点对间最短路径径计算原理设在一有向图中，各弧都赋予了非负整数权。图中一条路径的长度长度定义为该路径上所有的弧的权的和。图中两结点之间的最短路径最短路径是指它们之间长度最短的路径。设G为一个含有n个结点的有向图。矩阵W=(wij)是G中各弧上的权构成的矩阵，即W的元素wij是G中结点vi到结点vj的弧上的权（如果vi到vj无弧，则令wij=）。我们的目的是计算G中所有结点对之间的最短路。为此，记dij为结点vi到结点vj的最短路长，并记D=(dij)。用dij k表示从vi到vj至多经过k-1个中间结点的所有路径的长度的最小值，记Dk=(dijk)。因此dij 1=wij（ij），dij 1=0（i=j）。如果假设G中不包含权为负的有向圈，则dij=dij n-1，D=Dn-1第15页/共144页利用矩阵乘法求所有点对间最短路利用矩阵乘法求所有点对间最短路径径根据组合最优原理（Combinatorial Optimization Principle）有 从而可以从D1 开始，逐次计算出D2，D4，D8，Dn-1=D。为了从Dk/2计算Dk，可以借用标准的矩阵乘法。矩阵乘法执行的计算是 只需将矩阵乘法中的乘法操作换成加法操作，把矩阵乘法中的求和换求最小值操作即可。第16页/共144页利用矩阵乘法求所有点对间最短路利用矩阵乘法求所有点对间最短路径径计算原理 有向图G=(V,E)，边权矩阵W=(wij)nn，求最短路径长度矩阵D=(dij)nn，dij为vi到vj的最短路径长度。假定图中无负权有向回路，记d(k)ij为vi到vj至多有k-1个中间结点的最短路径长，Dk=(d(k)ij)nn，则 (1)d(1)ij=wij 当 ij(如果vi到vj之间无边存在记为)d(1)ij=0 当 i=j (2)无负权回路 dijd(n-1)ij (3)利用最优组合原理：d(k)ij=min1lnd(k/2)il+d(k/2)lj 视：”+”“”，“min”“”，则上式变为 d(k)ij=1lnd(k/2)ild(k/2)lj (4)应用矩阵乘法：D1 D2 D4 D2logn (=Dn)SIMD-CC上的并行算法：p139算法5.5第17页/共144页并行算法并行算法2 基本设计技术第18页/共144页并行算法的基本设计技术并行算法的基本设计技术划分设计技术分治设计技术平衡树设计技术倍增设计技术流水线设计技术第19页/共144页划分设计技术划分设计技术均匀划分技术方根划分技术对数划分技术功能划分技术第20页/共144页 均匀划分技术均匀划分技术划分方法n个元素A1.n分成p组，每组A(i-1)n/p+1.in/p，i=1p示例：MIMD-SM模型上的PSRS排序 begin (1)均匀划分：将n个元素A1.n均匀划分成p段，每个pi处理 A(i-1)n/p+1.in/p (2)局部排序：pi调用串行排序算法对A(i-1)n/p+1.in/p排序 (3)选取样本：pi从其有序子序列A(i-1)n/p+1.in/p中选取p个样本元素 (4)样本排序：用一台处理器对p2个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他pi (6)主元划分：pi按主元将有序段A(i-1)n/p+1.in/p划分成p段 (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中 (8)归并排序：各处理器对接收到的元素进行归并排序 end.第21页/共144页 均匀划分技术均匀划分技术例 PSRS排序过程。N=27，p=3，PSRS排序如下：第22页/共144页 方根划分技术方根划分技术划分方法n个元素A1.n分成A(i-1)n(1/2)+1.in(1/2)，i=1n(1/2)示例：SIMD-CREW模型上的 Valiant归并(1975年发表)/有序组A1.p、B1.q,(假设plogm=log4=2 =j1=rank(blogm:A)=rank(b2:A)=rank(9:A)=3,j2=8 B0:3,9 B1:16,21 A0:4,6,7 A1:10,12,15,18,20 A和B归并化为(A0,B0)和(A1,B1)的归并第26页/共144页 功能划分技术功能划分技术划分方法 n个元素A1.n分成等长的p组，每组满足某种特性。示例：(m,n)选择问题(求出n个元素中前m个最小者)功能划分：要求每组元素个数必须大于m；算法：p148算法6.4 输入：A=(a1,an);输出：前m个最小者；Begin (1)功能划分：将A划分成g=n/m组，每组含m个元素；(2)局部排序：使用Batcher排序网络将各组并行进行排序；(3)两两比较：将所排序的各组两两进行比较，从而形成MIN序列；(4)排序-比较：对各个MIN序列，重复执行第(2)和第(3)步，直至 选出m个最小者。End第27页/共144页 功能划分技术功能划分技术第28页/共144页分治设计技术分治设计技术并行分治设计步骤双调归并网络第29页/共144页 并行分治设计步骤并行分治设计步骤将输入划分成若干个规模相等的子问题；同时(并行地)递归求解这些子问题；并行地归并子问题的解，直至得到原问题的解。第30页/共144页 双调归并网络双调归并网络双调序列(p149定义6.2)(1,3,5,7,8,6,4,2,0)(8,7,6,4,2,0,1,3,5)(1,2,3,4,5,6,7,8)以上都是双调序列Batcher定理 给定双调序列(x0,x1,xn-1),对于si=minxi,xi+n/2和 l li=maxxi,xi+n/2，则小序列(s0,s1,sn-1)和大序列(l l0,l l1,l ln-1)仍是双调序列第31页/共144页 双调归并网络双调归并网络(4,4)双调归并网络第32页/共144页 双调归并网络双调归并网络Batcher双调归并算法 输入：双调序列X=(x0,x1,xn-1)输出：非降有序序列Y=(y0,y1,yn-1)Procedure BITONIC_MERG(x)Begin (1)for i=0 to n/2-1 par-do (1.1)si=minxi,xi+n/2 (1.2)l li=maxxi,xi+n/2 end for (2)Recursive Call:(2.1)BITONIC_MERG(MIN=(s0,sn/2-1)(2.2)BITONIC_MERG(MIN=(l l0,l ln/2-1)(3)output sequence MIN followed by sequence MAX End第33页/共144页平衡树设计技术平衡树设计技术设计思想求最大值计算前缀和第34页/共144页 平衡树设计技术平衡树设计技术设计思想 以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。示例求最大值计算前缀和 第35页/共144页 求最大值求最大值算法6.8:SIMD-TC(SM)上求最大值算法 Begin for k=m-1 to 0 do for j=2k to 2k+1-1 par-do Aj=maxA2j,A2j+1 end for end for end图示时间分析 t(n)=mO(1)=O(logn)p(n)=n/2A1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-1第36页/共144页 计算前缀和计算前缀和问题定义n个元素x1,x2,xn，前缀和是n个部分和：Si=x1*x2*xi,1in 这里*可以是或串行算法：Si=Si1*xi 计算时间为 O(n)并行算法：p154算法6.9 SIMD-TC上非递归算法 令Ai=xi,i=1n,Bh,j和Ch,j为辅助数组(h=0logn,j=1n/2h)数组B记录由叶到根正向遍历树中各结点的信息(求和)数组C记录由根到叶反向遍历树中各结点的信息(播送前缀 和)第37页/共144页 计算前缀和计算前缀和例：n=8,p=8,C01C08为前缀和第38页/共144页倍增设计技术倍增设计技术设计思想表序问题 求森林的根第39页/共144页 倍增设计技术倍增设计技术设计思想又称指针跳跃(pointer jumping)技术，特别适合于处理链表或有向树之类的数据结构；当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2k的所有数据的计算。示例表序问题求森林的根第40页/共144页 表序问题表序问题问题描述 n个元素的列表L，求出每个元素在L 中的次第号(秩或位序或rank(k)，rank(k)可视为元素k至表尾的距离；示例：n=7 (1)pa=b,pb=c,pc=d,pd=e,pe=f,pf=g,pg=g ra=rb=rc=rd=re=rf=1,rg=0 (2)pa=c,pb=d,pc=e,pd=f,pe=pf=pg=g ra=rb=rc=rd=re=2,rf=1,rg=0 (3)pa=e,pb=f,pc=pd=pe=pf=pg=g ra=4,rb=4,rc=4,rd=3,re=2,rf=1,rg=0 (4)pa=pb=pc=pd=pe=pf=pg=g ra=6,rb=5,rc=4,rd=3,re=2,rf=1,rg=0第41页/共144页 表序问题表序问题算法：P155算法6.10 (1)并行做：初始化pk和distancek /O(1)(2)执行 次 /O(logn)(2.1)对k并行地做 /O(1)如果k的后继不等于k的后继之后继，则 (i)distancek=distancek+distancepk (ii)pk=ppk (2.2)对k并行地做 rankk=distancek /O(1)运行时间：t(n)=O(logn)p(n)=n第42页/共144页 求森林的根求森林的根问题描述 一组有向树F中,如果是F中的一条弧，则pi=j(即j是i的双亲)；若i为根，则pi=i。求每个结点j(j=1n)的树根sj.示例 初始时 P1=p2=5 p3=p4=p5=6 P6=p7=8 p8=8 P9=10 p10=11 p11=12 p12=13 p13=13 si=pi第43页/共144页 求森林的根求森林的根示例 第一次迭代后 第二次迭代后算法：P157算法6.11运行时间：t(n)=O(logn)W(n)=O(nlogn)第44页/共144页流水线设计技术流水线设计技术设计思想5-point DFT的计算第45页/共144页 流水线设计技术流水线设计技术设计思想将算法流程划分成p个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输入；所有任务片断按同样的速率产生出结果。评注流水线技术是一种广泛应用在并行处理中的技术；脉动算法(Systolic algorithm)是其中一种流水线技术；第46页/共144页 5-point DFT5-point DFT的计算的计算问题描述 5-point DFT的计算。应用秦九韶(Horner)法则，第47页/共144页 5-point DFT5-point DFT的计算的计算示例：p(n)=n-1,t(n)=2n-2=O(n)第48页/共144页并行算法并行算法3 一般设计过程第49页/共144页并行算法的一般设计过程并行算法的一般设计过程PCAM设计方法学划分通讯组合映射小结第50页/共144页 PCAMPCAM设计方法学设计方法学设计并行算法的四个阶段划分(Partitioning)通讯(Communication)组合(Agglomeration)映射(Mapping)划分：分解成小的任务，开拓并发性；通讯：确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；映射：将每个任务分配到处理器上，提高算法的性能。第51页/共144页 PCAMPCAM设计过程设计过程第52页/共144页划分划分方法描述域分解功能分解划分判据第53页/共144页 划分方法描述划分方法描述充分开拓算法的并发性和可扩放性；先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；使数据集和计算集互不相交；划分阶段忽略处理器数目和目标机器的体系结构；能分为两类划分：域分解(domain decomposition)功能分解(functional decomposition)第54页/共144页域分解域分解 划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通讯；第55页/共144页域分解域分解域分解（Domain Decomposition）也叫数据划分，划分的对象是数据。这些数据可以是算法（或程序）的输入数据、计算的中间结果或计算的输出数据。域分解的步骤是：首先分解与问题相关的数据，如果可能的话，应使每份数据的数据量大体相等；然后再将每个计算关联到它所操作的数据上。由此就产生出一些任务，每个任务包括一些数据及其上的操作。当一个操作需要别的任务中的数据时，就会产生通信要求。域分解的经验方法是：优先集中在最大数据的划分和经常被访问的数据结构上。在不同的阶段，可能要对不同的数据结构进行操作或需要对同一数据结构进行不同的分解。在此情况下，要分别对待，然后再将各阶段设计的分解与算法装配到一起。第56页/共144页域分解域分解 示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：第57页/共144页域分解域分解 不规则区域的分解示例：第58页/共144页功能分解功能分解 划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠，意味着要重新进行域分解和功能分解；功能分解是一种更深层次的分解。第59页/共144页功能分解功能分解功能分解功能分解（Functional Decomposition）也叫计算划分，它首先关注被执行的计算的分解，而不是计算所需的数据，然后，如果所作的计算划分是成动的，再继续研究计算所需的数据。如果这些数据是不相交或相交很少的，就意味着划分是成功的；如果这些数据有相当的重叠，就会产生大量的通信，此时就暗示应考虑数据分解。尽管大多数并行算法采用域分解，但功能分解有时能揭示问题的内在结构，展示出优化的机会。单对数据进行研究往往很难做到这一点。功能分解的一个例子是搜索树。搜索树没有明显的可分解的数据结构，但易于进行细粒度的功能分解：开始时根生成一个任务，对其评价后，如果它不是一个解，就生成若干叶结点，这些叶结点可以分到各个处理器上并行地继续搜索。第60页/共144页功能分解功能分解 示例1：搜索树示例2：气候模型第61页/共144页划分判据划分判据 划分是否具有灵活性？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解，是否合理？第62页/共144页划分判据划分判据1）所划分的任务数是否高于目标机上处理器数目一个量级？若不是，在后面的设计步骤中将缺少灵活性。2）划分是否避免了冗余的计算和存储要求？若不是，则产生的算法对大型问题可能不是可扩展的。3）各任务的尺寸是否大致相当？若不是，则分配处理器时很难做到负载平衡。4）划分的任务数是否与问题尺寸成比例？理想情况下，问题尺寸的增加应引起任务数的增加而不是任务尺寸的增加。若不是这样，算法可能不能求解更大的问题，尽管有更多的处理器。5）是否采用了几种不同的划分法？多考虑几种选择可以提高灵活性。同时既要考虑域分解又要考虑功能分解。第63页/共144页通讯通讯方法描述四种通讯模式通讯判据第64页/共144页 通讯方法描述通讯方法描述通讯是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通讯；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通讯则限制了这种并发性；第65页/共144页 四种通讯模式四种通讯模式局部/全局通讯:局部通信中，每个任务只与少数的几个近邻任务通信；全局通信中，每个任务要与很多别的任务通信。结构化/非结构化通讯:结构化通信中，一个任务和其近邻形成规则的结构（如树、网格等）；非结构化通信中，通信网可能是任意图。静态/动态通讯:静态通信中，通信伙伴不随时间变化；动态通信中，通信伙伴可能动态变化。同步/异步通讯:同步通信中，接收方和发送方协同操作；异步通信中，接收方获取数据无需与发送方协同。第66页/共144页局部通讯局部通讯当一个任务仅要求与邻近的其它任务通信时，就呈现局部通信模式。例如在数值计算中的雅可比有限差分法。如果采用5点格式，迭代公式为 假设在二维网格上计算，并且处于(i,j)位置上的处理器负责计算xij。此时，计算每个xi,j(k)时，(i,j)位置上的处理器只需与其上、下、左、右的邻居处理器通信以获得xi-1,j(k-1)，xi+1,j(k-1)，xi,j-1(k-1)，xi,j+1(k-1)，并把 xi,j(k-1)发送给它们。第67页/共144页局部通讯局部通讯通讯限制在一个邻域内第68页/共144页全局通讯全局通讯在全局通信中，有很多任务参与交换数据。这可能造成过多的通信，从而限制了并行执行的机会。例如我们希望计算 为此，我们使用一个根进程S负责从各进程一次接收一个值（xi）并进行累加。这时就会出现全局通信的局面。第69页/共144页全局通讯全局通讯采用分治策略可以开拓求和的并行性：上式右边的两个求和可以同时执行，并且每一个仍可按同样的方式进一步分解。求和过程中，同一级上的求和可以并行执行。这样就可以避免全局通信，并提高算法的并行度。图中 表示处理器X至处理器Y上所有数据的和。第70页/共144页全局通讯全局通讯通讯非局部的例如：All to AllMaster-Worker53721第71页/共144页结构化通讯结构化通讯每个任务的通讯模式是相同的；下面是否存在一个相同通讯模式？第72页/共144页非结构化通讯非结构化通讯没有一个统一的通讯模式例如：无结构化网格第73页/共144页非结构化通讯非结构化通讯非结构化通信对算法设计的前期不会造成实质性的困难，但会使任务组合和处理器映射更为复杂。特别是要求组合策略既能创建尺寸大致相当的任务又要尽量减小任务间的通信时就需要非常复杂的算法，而这些算法在通信要求是动态的时又会在算法的执行过程中频繁地使用，所以必须权衡利弊。第74页/共144页通讯判据通讯判据 所有任务是否执行大致相当的通讯?是否尽可能的局部通讯？通讯操作是否能并行执行?同步任务的计算能否并行执行？第75页/共144页通讯判据通讯判据1）所有任务是否执行大致同样多的通信？若不是，所设计的算法的可扩展性可能会不好。2）每个任务是否只与少数的近邻通信？若不是，则可能导致全局通信。此时应设法将全局通信换成局部通信。3）诸通信操作能否并行执行？若不能，所设计的算法可能是低效的和不具可扩展性的。此时可试用分治策略来开发并行性。4）不同任务的计算能否并行执行？是否会因为等待数据而降低并行度？若不能并行执行，所设计的算法可能是低效的和不具可扩展性的。此时可考虑重新安排通信和计算的顺序以改善这种情况。第76页/共144页组合组合方法描述表面-容积效应重复计算组合判据第77页/共144页方法描述方法描述在任务划分和通信分析阶段，我们都没有考虑特定的并行机对执行效率的影响。在组合阶段，我们将重新考察划分和通信阶段所作的选择，力图得到一个在某一类并行机上能有效执行的并行算法。组合的目的是通过合并小尺寸的任务来减少任务数量和通信开销。第78页/共144页方法描述方法描述 组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通讯成本；在划分阶段，为了尽可能地开发问题的并行性，可能产生了大量的细粒度任务。但是大量的任务可能会增加通信开销和任务创建开销。保持映射和扩展的灵活性，降低软件工程成本；第79页/共144页表面表面-容积效应容积效应通讯量与任务子集的表面成正比，计算量与任务子集的体积成正比；增加重复计算有可能减少通讯量；第80页/共144页表面表面-容积效应容积效应通常，一个任务的通信需求正比与它所操作的数据域的表面积，而计算需求正比于它所操作的数据域的容积。因此一个计算单元的通信与计算之比随任务尺寸的增加而减小。例如在二维问题中，“表面积”即是数据域的周长，它正比于问题的尺寸，而“容积”指数据域的面积，它正比于问题尺寸的平方。以二维平面上的雅可比有限差分法5点格式为例。假设需要计算的数据是44矩阵。如果把计算每个元素算作一个任务，则有16个任务。每轮迭代中，每个任务都需要与其上下左右的任务通信，共需48次通信（当然这些通信中许多可以并行进行）。如上图（a）所示，每个箭头表示一次通信。第81页/共144页表面表面-容积效应容积效应第82页/共144页表面表面-容积效应容积效应如果将相邻的四个元素的计算作为一个任务则只需8次通信，如上图（b）所示。虽然每次通信要传递两个数据，但是相对于图（a），通信的次数和通信量都大大减少了。可见，当小任务组合为大任务后，原来的某些数据传递被包含在大任务里面了，它们不再表现为通信，实际计算时，这些数据交换可以通过直接读取内存完成。这正是增加粒度可以减少通信的原因。第83页/共144页表面表面-容积效应容积效应上例我们只想说明增加粒度可以减少通信次数和通信量。仔细思考我们会发现在上例中，图（b）的通信开销可能比图（a）大。设通信建立的时间为S，传递一个数据的时间为t。假设图（a）的通信方式是方向相同的所有通信同时执行。比如所有的任务同时先向左传递，那么所有向左的通信需时间S+t。同理，向其它三个方向的通信各需时间S+t。所以图（a）的通信开销是4(S+2t)。对图（b）也可进行相同的分析，但是图（b）中每个通信要传递两个数据，因此总的通信开销比图（a）大。第84页/共144页表面表面-容积效应容积效应上例中的通信是均匀的，且可以并行执行。实际上，实际问题的各小任务之间的通信很可能是不均匀的。比如一个问题可以分为A，B、C三个任务，A与B之间通信频繁，而它们与C之间通信很少。那么显然应该将 A和 B组合成一个大任务，以避免通信对它们并行执行造成的影响。但是组合之后，出现了一个较大的任务，完成这个大任务可能需要更长的时间。这时就需要权衡，看哪种方案更好。第85页/共144页重复计算重复计算重复计算（Replication Computation）也称为冗余计算。它是指采用多余的计算来减少通信和/或整个计算时间。重复计算减少通讯量，但增加了计算量，应保持恰当的平衡；重复计算的目标应减少算法的总运算时间；第86页/共144页重复计算重复计算假定在二叉树上求N个数的和，且要求最终在每个处理器上都有该结果。一种方法是先自叶向根求和，得到结果后再自根向叶播送，共需2 步。如下图所示。第87页/共144页重复计算重复计算示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。二叉树上求和，共需2logN步第88页/共144页重复计算重复计算以上述方式求和，处理器的利用率是逐级减半的。如果在每一级每个处理器均接收两个数据，求和后再发送给上一级的两个处理器，那么经过 步后，每个处理器中就都得到了N个数的全和。计算过程如下图所示。第89页/共144页重复计算重复计算示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。蝶式结构求和，使用了重复计算，共需logN步第90页/共144页灵活性和成本灵活性和成本 要维持一个算法的可移植性和可扩展性，创建可变数目的任务是很关键的。组合时往往会使问题的任务数的变化范围受到限制。根据经验，为了能在映射阶段达到负载平衡，任务数至少比处理器数多一个数量级。可用分析模型结合实际经验讨论最优的任务数。当然，灵活性并不意味着必须创建大量的任务。粒度可由编译或运行时的参数控制。重要的是不要对任务数进行不必要的限制。组合时的另一个问题是要尽量减少软件工程的代价，尤其是并行化一个串行程序时应尽量避免程序代码的大量修改。增加任务的粒度可以减少通信开销，但组合时也要使算法保持足够的灵活性并要尽量减少软件工程的成本。这几个目的有时是相互矛盾的，要权衡其利弊。第91页/共144页组合判据组合判据 增加粒度是否减少了通讯成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通讯？有没有减少并行执行的机会？第92页/共144页组合判据组合判据1）用增加局部性的方法实施组合是否减少了通信开销？若不是，能否换用别的组合策略以减少通信开销？2）如果使用了重复计算，是否权衡了其得失？3）如果组合已复制了数据，是否已证实这不会因限制问题尺寸和处理器数量的变化范围而牺牲了可扩展性？4）由组合产生的任务是否具有相似的计算和通信代价？5）任务数目是否仍然与问题尺寸成比例？若不是，算法是不可扩展的。6）如果组合减少了并行执行的机会，是否已证实现在的并发性仍能适应目前和将来的并行机？7）在不导致负载不平衡，不增加软件工程代价和不减少可扩展性的前提下，任务数能否再进一步减少？在其它条件相同时，创建较少的粗粒度任务的算法通常是高效的。8）如果是并行化现有的串行程序，是否考虑了修改串行代码的成本？如果此成本较高，应考虑别的组合策略。第93页/共144页映射映射方法描述负载平衡算法任务调度算法映射判据第94页/共144页方法描述方法描述映射映射阶段的任务是指定每个任务到哪个处理器上去执行。映射的目标是最小化全局执行时间和通信成本、最大化处理器的利用率，减少算法的总执行时间。为了达到以上目的，可采用以下策略：1）把能够并发执行的任务放在不同的处理器上以增加并行度；2）把需频繁通信的任务置于同一处理器上以提高局部性。这二者有时会冲突，需要权衡。对于某些基于域分解技术开发的算法，它们有固定数目的等尺寸的任务，通信结构化强，此时映射较简单。如果任务的工作量不同，通信是非结构化的，可采用负载平衡算法。对于基于功能分解开发的算法，常常会产生一些由短暂任务组成的计算，它们只在执行的开始与结束时需要与别的任务协调，此时可用任务调度算法进行任务分配。第95页/共144页方法描述方法描述 每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务 不同的处理器任务之间存在高通讯的 同一处理器映射实际是一种权衡，属于NP完全问题；第96页/共144页负载平衡算法负载平衡算法负载平衡算法负载平衡算法针对基于域分解技术开发的算法，有很多专用和通用的负载平衡技术（Load-Balancing Technigues）。局部算法局部算法 局部负载平衡算法的思想是通过从近邻迁入任务和向近邻迁出任务来达到负载平衡。比如，每个处理器周期性地与邻居比较负载的轻重。如果差异超过了某个阈值，就进行负载迁移。如果自己的负载轻且有邻居负载重，则从该邻居迁入一些任务。反之，如果自己的负载重，而别的邻居较空闲，则把自己的一部分负载迁给它。局部算法的优点是这个方案只利用局部的负载信息。同时，迁移任务时往往通信量很大，而此方案只在局部迁移，有利于提高效率。第97页/共144页负载平衡算法负载平衡算法概率方法概率方法（Probabilistic Method）此法的思想是将任务随机地分配给处理器，如果任务足够多，则每个处理器预计能分到大致等量的任务。此法的优点是低价和可扩展性好；缺点是要求跨处理器进行通信，并且只有当任务数远远多于处理器数时才能达到预期的效果。循环映射循环映射（Cyclic Mapping）此法又称为循环指派法，即轮流地给处理器分配计算任务。它实际上是概率方法的一种形式。此法适用于各计算任务呈明显的空间局部性的情况。总之，局部算法代价小，但当负载变化大时调整很慢；概率方法代价小，可扩展性好，但通信代价可能较大，且只适用于任务数远多于处理器数的情况；循环映射技术是概率映射的一种形式，而概率方法比其它技术易于导致可观的通信。第98页/共144页负载平衡算法负载平衡算法 静态的：事先确定；概率的：随机确定；动态的：执行期间动态负载；基于域分解的：递归对剖局部算法概率方法循环映射第99页/共144页任务调度算法任务调度算法任务调度算法任务调度算法任务调度算法的最关键之处是任务的分配策略。常用的调度模式有经理/雇员模式和非集中模式。经理经理/雇员模式雇员模式 在此模式中，有一个进程（经理）负责分配任务，每个雇员向经理请求任务，得到任务后执行任务。使用预取方法（以使计算和通信重叠）可以提高效率。这种方案的一种变体是层次经理层次经理/雇员模式雇员模式。在此模式中，雇员被分成不相交的集合，每个集合有一个小经理。雇员们从小经理那里领取任务，小经理从经理处领取任务。经理/雇员模式的缺点是经理进程容易成为系统的瓶颈。非集中模式非集中模式 它就是无中心管理者的分布式调度法。结束检测结束检测 任务调度算法需要一种机制来检测整个问题的计算何时结束。否则，空闲的雇员们将永不停止地发出任务请求。在经理/雇员模式中，经理可以判断雇员是否都空闲了。所有的雇员都空闲了就意味着整个问题的计算结束了。在非集中模式中结束检测则比较困难，因为没有一个进程知道全局的情况。第100页/共144页任务调度算法任务调度算法 任务放在集中的或分散的任务池中，使用任务调度算法将池中的任务分配给特定的处理器。下面是两种常用调度模式：经理/雇员模式非集中模式第101页/共144页映射判据映射判据 采用集中式负载平衡方案，是否存在通讯瓶颈？采用动态负载平衡方案，调度策略的成本如何？第102页/共144页映射判据映射判据1）如果采用集中式负载平衡方案，是否检查了中央管理者不会成为瓶