[计算机软件及应用]并行计算4算法.ppt

并行算法,1 一般设计方法,并行算法的一般设计方法,串行算法的直接并行化 从问题描述开始设计并行算法 借用已有算法求解新问题,串行算法的直接并行化,设计方法描述 快排序算法的并行化,设计方法的描述,方法描述 发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。 许多并行编程语言都支持通过在原有的串行程序中加入并行原语（例如某些通信命令等）的方法将串行程序并行化。,设计方法的描述,评注 由串行算法直接并行化的方法是并行算法设计的最常用方法之一； 不是所有的串行算法都可以直接并行化的；某些串行算法有内在的串行性，比如在某些串行算法中，每一步都要用到上一步的结果。只有当上一步完全结束后，下一步才能开始。这样，各步之间就不能并行，只能考虑其它的并行化办法。例如模拟退火算法，每个温度下迭代的出发点是上一个温度下迭代的结束点。这样就很难直接将各个温度的迭代并行起来。,设计方法的描述,评注 一个好的串行算法并不能并行化为一个好的并行算法；另一方面，不好的串行算法并行化后也可能是优秀的并行算法。例如，串行算法中是没有冗余计算的。但是在并行算法中，使用适当的冗余计算也可能使并行算法效率更高。加入冗余计算的并行算法就可能比直接由串行算法并行化得到的算法效率高。又比如，枚举不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法。 许多数值串行算法可以并行化为有效的数值并行算法。,设计方法的描述,假设我们想用求和的方法进行数值积分。设被积函数为f(x)，积分区间为a,b。为了积分，将区间a,b均匀分成N个小区间，每个小区间长 ，根据积分的定义 是第i 个小区间左端点的坐标，而 是f(x)在第i 个小区间上积分的近似值。如果使用串行算法，可以用循环和叠加完成上述求和。这个串行算法可以直接并行化。,设计方法的描述,假设有k台处理器，可以把这N个小区间上的计算任务分到各处理器：0号处理器负责第 个小区间上的计算和累加，1号处理器负责第 个小区间上的计算和累加，k-1号处理器负责第 个小区间上的计算和累加。k个处理器并行地计算出部分和，然后再把结果加到一起。,设计方法的描述,快排序算法的并行化,算法 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,从问题描述开始设计并行算法,方法描述 从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。 评注 挖掘问题的固有特性与并行的关系； 设计全新的并行算法是一个挑战性和创造性的工作； 利用串的周期性的PRAM-CRCW算法是一个很好的范例；,并行串匹配算法,给定长度为n的正文串T和长度为m的模式串P，找出P在T中所有出现的位置称为串匹配问题。 研究发现，两串能否匹配是与串本身的特性有关的。这种特性，就是串的周期性。 串可以分为周期的和非周期的。 可以引入见证函数（Witness Function）来判断串的周期性。确定了串的周期性后就可以先研究非周期串的匹配，然后在此基础上再研究周期串的匹配。,并行串匹配算法,对于非周期串的研究，就是如何利用见证函数快速地找出P在T中的位置。为此，引入竞争函数duel(p,q) 。 先把正文串分成小段，借助于见证函数并行地计算竞争函数值，找出那些可能匹配的位置。然后逐步扩大正文串分段的长度，并计算竞争函数值，在可能匹配的位置中排除那些不可能匹配的位置。最后在剩下的可能位置中验证哪些是符合要求的位置。,并行串匹配算法,假设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个位置都匹配。,借用已有算法求解新问题,设计方法描述 利用矩阵乘法求所有点对间最短路径,设计方法的描述,方法描述 找出求解问题和某个已解决问题之间的联系； 改造或利用已知算法应用到求解问题上。 评注 这是一项创造性的工作； 使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。,利用矩阵乘法求所有点对间最短路径,计算原理 设在一有向图中，各弧都赋予了非负整数权。图中一条路径的长度定义为该路径上所有的弧的权的和。图中两结点之间的最短路径是指它们之间长度最短的路径。 设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,利用矩阵乘法求所有点对间最短路径,根据组合最优原理（Combinatorial Optimization Principle）有 从而可以从D1 开始，逐次计算出D2 ， D4 ， D8，Dn-1=D。为了从Dk/2计算Dk，可以借用标准的矩阵乘法。矩阵乘法执行的计算是 只需将矩阵乘法中的乘法操作换成加法操作，把矩阵乘法中的求和换“求最小值“操作即可。,利用矩阵乘法求所有点对间最短路径,计算原理 有向图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,并行算法,2 基本设计技术,并行算法的基本设计技术,划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术,划分设计技术,均匀划分技术 方根划分技术 对数划分技术 功能划分技术,均匀划分技术,划分方法 n个元素A1n分成p组，每组A(i-1)n/p+1in/p，i=1p 示例：MIMD-SM模型上的PSRS排序 begin (1)均匀划分：将n个元素A1n均匀划分成p段，每个pi处理 A(i-1)n/p+1in/p (2)局部排序：pi调用串行排序算法对A(i-1)n/p+1in/p排序 (3)选取样本：pi从其有序子序列A(i-1)n/p+1in/p中选取p个样本元素 (4)样本排序：用一台处理器对p2个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他pi (6)主元划分：pi按主元将有序段A(i-1)n/p+1in/p划分成p段 (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中 (8)归并排序：各处理器对接收到的元素进行归并排序 end.,均匀划分技术,例 PSRS排序过程。N=27，p=3，PSRS排序如下：,方根划分技术,划分方法 n个元素A1n分成A(i-1)n(1/2)+1in(1/2)，i=1n(1/2) 示例：SIMD-CREW模型上的 Valiant归并(1975年发表) /有序组A1p、B1q, (假设p=q), 处理器数 begin (1)方根划分: A,B分别按 ； (2)段间比较: A划分元与B划分元比较(至多 对)， 确定A划分元应插入B中的区段； (3)段内比较: A划分元与B相应段内元素进行比较，并插入适当的位置； (4)递归归并: B按插入的A划分元重新分段，与A相应段(A除去原划分元) 构成了成对的段组，对每对段组递归执行(1)(3)，直至A 组为0时，递归结束; 各组仍按 分配处理器； end.,方根划分技术,方根划分技术,对数划分技术,划分方法 n个元素A1n分成A(i-1)logn+1ilogn，i=1n/logn 示例：PRAM-CREW上的对数划分并行归并排序 (1)归并过程: 设有序组A1n和B1m ji=rank(bilogm:A)为bilogm在A中的位序，即A中小于等于bilogm的元素个数 (2)例：A=(4,6,7,10,12,15,18,20), B=(3,9,16,21) n=8, m=4 =logm=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)的归并,功能划分技术,划分方法 n个元素A1n分成等长的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,功能划分技术,分治设计技术,并行分治设计步骤 双调归并网络,并行分治设计步骤,将输入划分成若干个规模相等的子问题； 同时(并行地)递归求解这些子问题； 并行地归并子问题的解，直至得到原问题的解。,双调归并网络,双调序列(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和 li=maxxi,xi+n/2， 则小序列(s0,s1,sn-1)和大序列(l0,l1,ln-1) 仍是双调序列,双调归并网络,(4,4)双调归并网络,双调归并网络,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) li=maxxi,xi+n/2 end for (2)Recursive Call: (2.1)BITONIC_MERG(MIN=(s0,sn/2-1) (2.2)BITONIC_MERG(MIN=(l0, ln/2-1) (3)output sequence MIN followed by sequence MAX End,平衡树设计技术,设计思想 求最大值 计算前缀和,平衡树设计技术,设计思想 以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。 示例 求最大值 计算前缀和,求最大值,算法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/2,计算前缀和,问题定义 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记录由根到叶反向遍历树中各结点的信息(播送前缀 和),计算前缀和,例：n=8, p=8, C01C08为前缀和,倍增设计技术,设计思想 表序问题 求森林的根,倍增设计技术,设计思想 又称指针跳跃(pointer jumping)技术，特别适合于处理链表或有向树之类的数据结构； 当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2k的所有数据的计算。 示例 表序问题 求森林的根,表序问题,问题描述 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,表序问题,算法：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,求森林的根,问题描述 一组有向树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,求森林的根,示例 第一次迭代后 第二次迭代后 算法：P157算法6.11 运行时间：t(n)=O(logn) W(n)=O(nlogn),流水线设计技术,设计思想 5-point DFT的计算,流水线设计技术,设计思想 将算法流程划分成p个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输入； 所有任务片断按同样的速率产生出结果。 评注 流水线技术是一种广泛应用在并行处理中的技术； 脉动算法(Systolic algorithm)是其中一种流水线技术；,5-point DFT的计算,问题描述 5-point DFT的计算。应用秦九韶(Horner)法则，,5-point DFT的计算,示例：p(n)=n-1, t(n)=2n-2=O(n),并行算法,3 一般设计过程,并行算法的一般设计过程,PCAM设计方法学 划分 通讯 组合 映射 小结,PCAM设计方法学,设计并行算法的四个阶段 划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping) 划分：分解成小的任务，开拓并发性； 通讯：确定诸任务间的数据交换，监测划分的合理性； 组合：依据任务的局部性，组合成更大的任务； 映射：将每个任务分配到处理器上，提高算法的性能。,PCAM设计过程,划分,方法描述 域分解 功能分解 划分判据,划分方法描述,充分开拓算法的并发性和可扩放性； 先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)； 使数据集和计算集互不相交； 划分阶段忽略处理器数目和目标机器的体系结构； 能分为两类划分： 域分解(domain decomposition) 功能分解(functional decomposition),域分解,划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据； 将数据分解成大致相等的小数据片； 划分时考虑数据上的相应操作； 如果一个任务需要别的任务中的数据，则会产生任务间的通讯；,域分解,域分解（Domain Decomposition）也叫数据划分，划分的对象是数据。这些数据可以是算法（或程序）的输入数据、计算的中间结果或计算的输出数据。 域分解的步骤是：首先分解与问题相关的数据，如果可能的话，应使每份数据的数据量大体相等；然后再将每个计算关联到它所操作的数据上。由此就产生出一些任务，每个任务包括一些数据及其上的操作。当一个操作需要别的任务中的数据时，就会产生通信要求。 域分解的经验方法是：优先集中在最大数据的划分和经常被访问的数据结构上。在不同的阶段，可能要对不同的数据结构进行操作或需要对同一数据结构进行不同的分解。在此情况下，要分别对待，然后再将各阶段设计的分解与算法装配到一起。,域分解,示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：,域分解,不规则区域的分解示例：,功能分解,划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解； 划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着要重新进行域分解和功能分解； 功能分解是一种更深层次的分解。,功能分解,功能分解（Functional Decomposition）也叫计算划分，它首先关注被执行的计算的分解，而不是计算所需的数据，然后，如果所作的计算划分是成动的，再继续研究计算所需的数据。如果这些数据是不相交或相交很少的，就意味着划分是成功的；如果这些数据有相当的重叠，就会产生大量的通信，此时就暗示应考虑数据分解。 尽管大多数并行算法采用域分解，但功能分解有时能揭示问题的内在结构，展示出优化的机会。单对数据进行研究往往很难做到这一点。 功能分解的一个例子是搜索树。搜索树没有明显的可分解的数据结构，但易于进行细粒度的功能分解：开始时根生成一个任务，对其评价后，如果它不是一个解，就生成若干叶结点，这些叶结点可以分到各个处理器上并行地继续搜索。,功能分解,示例1：搜索树 示例2：气候模型,划分判据,划分是否具有灵活性？ 划分是否避免了冗余计算和存储？ 划分任务尺寸是否大致相当？ 任务数与问题尺寸是否成比例？ 功能分解是一种更深层次的分解，是否合理？,划分判据,1）所划分的任务数是否高于目标机上处理器数目一个量级？若不是，在后面的设计步骤中将缺少灵活性。 2）划分是否避免了冗余的计算和存储要求？若不是，则产生的算法对大型问题可能不是可扩展的。 3）各任务的尺寸是否大致相当？若不是，则分配处理器时很难做到负载平衡。 4）划分的任务数是否与问题尺寸成比例？理想情况下，问题尺寸的增加应引起任务数的增加而不是任务尺寸的增加。若不是这样，算法可能不能求解更大的问题，尽管有更多的处理器。 5）是否采用了几种不同的划分法？多考虑几种选择可以提高灵活性。同时既要考虑域分解又要考虑功能分解。,通讯,方法描述 四种通讯模式 通讯判据,通讯方法描述,通讯是PCAM设计过程的重要阶段； 划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通讯； 功能分解确定了诸任务之间的数据流； 诸任务是并发执行的，通讯则限制了这种并发性；,四种通讯模式,局部/全局通讯:局部通信中，每个任务只与少数的几个近邻任务通信；全局通信中，每个任务要与很多别的任务通信。 结构化/非结构化通讯:结构化通信中，一个任务和其近邻形成规则的结构（如树、网格等）；非结构化通信中，通信网可能是任意图。 静态/动态通讯:静态通信中，通信伙伴不随时间变化；动态通信中，通信伙伴可能动态变化。 同步/异步通讯:同步通信中，接收方和发送方协同操作；异步通信中，接收方获取数据无需与发送方协同。,局部通讯,当一个任务仅要求与邻近的其它任务通信时，就呈现局部通信模式。例如在数值计算中的雅可比有限差分法。如果采用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)发送给它们。,局部通讯,通讯限制在一个邻域内,全局通讯,在全局通信中，有很多任务参与交换数据。这可能造成过多的通信，从而限制了并行执行的机会。 例如我们希望计算 为此，我们使用一个根进程S负责从各进程一次接收一个值（xi）并进行累加。这时就会出现全局通信的局面。,全局通讯,采用分治策略可以开拓求和的并行性： 上式右边的两个求和可以同时执行，并且每一个仍可按同样的方式进一步分解。求和过程中，同一级上的求和可以并行执行。这样就可以避免全局通信，并提高算法的并行度。图中 表示处理器X至处理器Y上所有数据的和。,全局通讯,通讯非局部的 例如： All to All Master-Worker,结构化通讯,每个任务的通讯模式是相同的； 下面是否存在一个相同通讯模式？,非结构化通讯,没有一个统一的通讯模式 例如：无结构化网格,非结构化通讯,非结构化通信对算法设计的前期不会造成实质性的困难，但会使任务组合和处理器映射更为复杂。特别是要求组合策略既能创建尺寸大致相当的任务又要尽量减小任务间的通信时就需要非常复杂的算法，而这些算法在通信要求是动态的时又会在算法的执行过程中频繁地使用，所以必须权衡利弊。,通讯判据,所有任务是否执行大致相当的通讯? 是否尽可能的局部通讯？ 通讯操作是否能并行执行? 同步任务的计算能否并行执行？,通讯判据,1）所有任务是否执行大致同样多的通信？若不是，所设计的算法的可扩展性可能会不好。 2）每个任务是否只与少数的近邻通信？若不是，则可能导致全局通信。此时应设法将全局通信换成局部通信。 3）诸通信操作能否并行执行？若不能，所设计的算法可能是低效的和不具可扩展性的。此时可试用分治策略来开发并行性。 4）不同任务的计算能否并行执行？是否会因为等待数据而降低并行度？若不能并行执行，所设计的算法可能是低效的和不具可扩展性的。此时可考虑重新安排通信和计算的顺序以改善这种情况。,组合,方法描述 表面-容积效应 重复计算 组合判据,方法描述,在任务划分和通信分析阶段，我们都没有考虑特定的并行机对执行效率的影响。在组合阶段，我们将重新考察划分和通信阶段所作的选择，力图得到一个在某一类并行机上能有效执行的并行算法。组合的目的是通过合并小尺寸的任务来减少任务数量和通信开销。,方法描述,组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行； 合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程； 通过增加任务的粒度和重复计算，可以减少通讯成本；在划分阶段，为了尽可能地开发问题的并行性，可能产生了大量的细粒度任务。但是大量的任务可能会增加通信开销和任务创建开销。 保持映射和扩展的灵活性，降低软件工程成本；,表面-容积效应,通讯量与任务子集的表面成正比，计算量与任务子集的体积成正比； 增加重复计算有可能减少通讯量；,表面-容积效应,通常，一个任务的通信需求正比与它所操作的数据域的表面积，而计算需求正比于它所操作的数据域的容积。因此一个计算单元的通信与计算之比随任务尺寸的增加而减小。例如在二维问题中，“表面积”即是数据域的周长，它正比于问题的尺寸，而“容积”指数据域的面积，它正比于问题尺寸的平方。 以二维平面上的雅可比有限差分法5点格式为例。假设需要计算的数据是44矩阵。如果把计算每个元素算作一个任务，则有16个任务。每轮迭代中，每个任务都需要与其上下左右的任务通信，共需48次通信（当然这些通信中许多可以并行进行）。如上图（a）所示，每个箭头表示一次通信。,表面-容积效应,表面-容积效应,如果将相邻的四个元素的计算作为一个任务则只需8次通信，如上图（b）所示。虽然每次通信要传递两个数据，但是相对于图（a），通信的次数和通信量都大大减少了。可见，当小任务组合为大任务后，原来的某些数据传递被“包含“在大任务里面了，它们不再表现为通信，实际计算时，这些数据交换可以通过直接读取内存完成。这正是增加粒度可以减少通信的原因。,表面-容积效应,上例我们只想说明增加粒度可以减少通信次数和通信量。仔细思考我们会发现在上例中，图（b）的通信开销可能比图（a）大。设通信建立的时间为S，传递一个数据的时间为t。假设图（a）的通信方式是方向相同的所有通信同时执行。比如所有的任务同时先向左传递，那么所有向左的通信需时间S+t。同理，向其它三个方向的通信各需时间S+t。所以图（a）的通信开销是4(S+2t)。对图（b）也可进行相同的分析，但是图（b）中每个通信要传递两个数据，因此总的通信开销比图（a）大。,表面-容积效应,上例中的通信是均匀的，且可以并行执行。实际上，实际问题的各小任务之间的通信很可能是不均匀的。比如一个问题可以分为A，B、 C三个任务，A与B之间通信频繁，而它们与C之间通信很少。那么显然应该将 A和 B组合成一个大任务，以避免通信对它们并行执行造成的影响。但是组合之后，出现了一个较大的任务，完成这个大任务可能需要更长的时间。这时就需要权衡，看哪种方案更好。,重复计算,重复计算（Replication Computation）也称为冗余计算。它是指采用多余的计算来减少通信和/或整个计算时间。 重复计算减少通讯量，但增加了计算量，应保持恰当的平衡； 重复计算的目标应减少算法的总运算时间；,重复计算,假定在二叉树上求N个数的和，且要求最终在每个处理器上都有该结果。一种方法是先自叶向根求和，得到结果后再自根向叶播送，共需2 步。如下图所示。,重复计算,示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 二叉树上求和，共需2logN步,重复计算,以上述方式求和，处理器的利用率是逐级减半的。如果在每一级每个处理器均接收两个数据，求和后再发送给上一级的两个处理器，那么经过 步后，每个处理器中就都得到了N个数的全和。计算过程如下图所示。,重复计算,示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 蝶式结构求和，使用了重复计算，共需logN步,灵活性和成本,要维持一个算法的可移植性和可扩展性，创建可变数目的任务是很关键的。组合时往往会使问题的任务数的变化范围受到限制。根据经验，为了能在映射阶段达到负载平衡，任务数至少比处理器数多一个数量级。可用分析模型结合实际经验讨论最优的任务数。当然，灵活性并不意味着必须创建大量的任务。粒度可由编译或运行时的参数控制。重要的是不要对任务数进行不必要的限制。 组合时的另一个问题是要尽量减少软件工程的代价，尤其是并行化一个串行程序时应尽量避免程序代码的大量修改。 增加任务的粒度可以减少通信开销，但组合时也要使算法保持足够的灵活性并要尽量减少软件工程的成本。这几个目的有时是相互矛盾的，要权衡其利弊。,组合判据,增加粒度是否减少了通讯成本？ 重复计算是否已权衡了其得益？ 是否保持了灵活性和可扩放性？ 组合的任务数是否与问题尺寸成比例? 是否保持了类似的计算和通讯？ 有没有减少并行执行的机会？,组合判据,1）用增加局部性的方法实施组合是否减少了通信开销？若不是，能否换用别的组合策略以减少通信开销？ 2）如果使用了重复计算，是否权衡了其得失？ 3）如果组合已复制了数据，是否已证实这不会因限制问题尺寸和处理器数量的变化范围而牺牲了可扩展性？ 4）由组合产生的任务是否具有相似的计算和通信代价？ 5）任务数目是否仍然与问题尺寸成比例？若不是，算法是不可扩展的。 6）如果组合减少了并行执行的机会，是否已证实现在的并发性仍能适应目前和将来的并行机？ 7）在不导致负载不平衡，不增加软件工程代价和不减少可扩展性的前提下，任务数能否再进一步减少？在其它条件相同时，创建较少的粗粒度任务的算法通常是高效的。 8）如果是并行化现有的串行程序，是否考虑了修改串行代码的成本？如果此成本较高，应考虑别的组合策略。,映射,方法描述 负载平衡算法 任务调度算法 映射判据,方法描述,映射阶段的任务是指定每个任务到哪个处理器上去执行。映射的目标是最小化全局执行时间和通信成本、最大化处理器的利用率，减少算法的总执行时间。为了达到以上目的，可采用以下策略： 1）把能够并发执行的任务放在不同的处理器上以增加并行度； 2）把需频繁通信的任务置于同一处理器上以提高局部性。 这二者有时会冲突，需要权衡。 对于某些基于域分解技术开发的算法，它们有固定数目的等尺寸的任务，通信结构化强，此时映射较简单。如果任务的工作量不同，通信是非结构化的，可采用负载平衡算法。对于基于功能分解开发的算法，常常会产生一些由短暂任务组成的计算，它们只在执行的开始与结束时需要与别的任务协调，此时可用任务调度算法进行任务分配。,方法描述,每个任务要映射到具体的处理器，定位到运行机器上； 任务数大于处理器数时，存在负载平衡和任务调度问题； 映射的目标：减少算法的执行时间 并发的任务 不同的处理器 任务之间存在高通讯的 同一处理器 映射实际是一种权衡，属于NP完全问题；,负载平衡算法,负载平衡算法 针对基于域分解技术开发的算法，有很多专用和通用的负载平衡技术（Load-Balancing Technigues）。 局部算法 局部负载平衡算法的思想是通过从近邻迁入任务和向近邻迁出任务来达到负载平衡。比如，每个处理器周期性地与邻居比较负载的轻重。如果差异超过了某个阈值，就进行负载迁移。如果自己的负载轻且有邻居负载重，则从该邻居迁入一些任务。反之，如果自己的负载重，而别的邻居较空闲，则把自己的一部分负载迁给它。局部算法的优点是这个方案只利用局部的负载信息。同时，迁移任务时往往通信量很大，而此方案只在局部迁移，有利于提高效率。,负载平衡算法,概率方法（Probabilistic Method） 此法的思想是将任务随机地分配给处理器，如果任务足够多，则每个处理器预计能分到大致等量的任务。此法的优点是低价和可扩展性好；缺点是要求跨处理器进行通信，并且只有当任务数远远多于处理器数时才能达到预期的效果。 循环映射（Cyclic Mapping） 此法又称为循环指派法，即轮流地给处理器分配计算任务。它实际上是概率方法的一种形式。此法适用于各计算任务呈明显的空间局部性的情况。 总之，局部算法代价小，但当负载变化大时调整很慢；概率方法代价小，可扩展性好，但通信代价可能较大，且只适用于任务数远多于处理器数的情况；循环映射技术是概率映射的一种形式，而概率方法比其它技术易于导致可观的通信。,负载平衡算法,静态的：事先确定； 概率的：随机确定； 动态的：执行期间动态负载； 基于域分解的： 递归对剖 局部算法 概率方法 循环映射,任务调度算法,任务调度算法 任务调度算法的最关键之处是任务的分配策略。常用的调度模式有经理/雇员模式和非集中模式。 经理/雇员模式 在此模式中，有一个进程（经理）负责分配任务，每个雇员向经理请求任务，得到任务后执行任务。使用预取方法（以使计算和通信重叠）可以提高效率。 这种方案的一种变体是层次经理/雇员模式。在此模式中，雇员被分成不相交的集合，每个集合有一个小经理。雇员们从小经理那里领取任务，小经理从经理处领取任务。经理/雇员模式的缺点是经理进程容易成为系统的瓶颈。 非集中模式 它就是无中心管理者的分布式调度法。 结束检测 任务调度算法需要一种机制来检测整个问题的计算何时结束。否则，空闲的雇员们将永不停止地发出任务请求。在经理/雇员模式中，经理可以判断雇员是否都空闲了。所有的雇员都空闲了就意味着整个问题的计算结束了。在非集中模式中结束检测则比较困难，因为没有一个进程知道全局的情况。,任务调度算法,任务放在集中的或分散的任务池中，使用任务调度算法将池中的任务分配给特定的处理器。下面是两种常用调度模式： 经理/雇员模式 非集中模式,映射判据,采用集中式负载平衡方案，是否存在通讯瓶颈？ 采用动态负载平衡方案，调度策略的成本如何？,映射判据,1）如果采用集中式负载平衡方案，是否检查了中央管理者不会成为瓶颈？ 2）如果采用动态负载平衡方案，是否衡量过不同策略的成本？ 3）如果采用概率或循环指派法，是否有足够多的任务？一般地，任务数应不少于处理器数的10倍。 4）如果要为一个问题设计一个SPMD程序，是否考虑过基于动态任务创建和消除的算法？,小 结,划分 域分解和功能分解 通讯 任务间的数据交换 组合 任务的合并使得算法更有效 映射 将任务分配到处理器，并保持负载平衡,并发的类型,并行程序必须以某种形式给出任务的并行性，它们可以以下面的方式给出： 数据并行 任务并行 流水并行 混合并行,数据并行,考虑下面的矩阵加法：A，B，C都是nn的矩阵，计算 C=A+B 为了计算C的每个元素，需要进行如下的计算： Ci,j=ai,j+bi,j 注意计算C的每个元素的操作都是一次加法，只是操作数不同而已，而且，每个元素的计算都是独立的，它们可以并行执行。 这种类型的并行性表现为：并行的在不同的数据上进行相同的操作，称为数据并行性。表现出这种并行性的问题通常称为数据并行（的问题）。数据并行问题的一个突出特点是对大多数的这类问题，数据并行性的程度（可以并行进行数据并行的操作数目）随着问题规模的增加而增大，这意味着对于这类问题，可以用较多的处理器来有效的处理更大规模的问题。这是一种比较简单的并行方式，幸运的是，在实际的应用中，有很多有趣的问题都是数据并行的。,任务并行,如果需要做如下的查询： Select all where （MODEL=“Accord” AND YEAR=“1996”） AND （COLOR=“Green” OR COLOR=“Black”）； 这个查询寻找数据库中所有1996年产的绿色或黑色的Accord车的资料。在关系数据库中，这个查询通常需要创建几个中间表，一种可能的情形如下：一个表包含所有的Accord车数据，一个表包含所有1996款的车，一个表包含所有绿色车，一个表包含所有的黑色车。然后在这些表上进行Join操作，更详细的说，数据库将求出前两个表的交集，从而得到1996款的Accord车的表，同时，将求出后两个表的并，得到绿色或黑色的车的表，最后，用这两个表求交集，就得到了最后的数据。上面的操作可以用下面的图来形象的表示。,任务并行,任务并行,图中的每个节点表示一个需要被计算的表（计算子任务），节点间的箭头给出了任务间的依赖关系。 在上面图中，只要所有必需的子任务已经完成，后续子任务就可以进行，因此，通常来说，很多的子任务都可以并行的执行。这种并行性表现为子任务的并行执行，因此被称为任务并行性。任务并行性比数据并行性要复杂一些（实际上，用任务并行性完全可以描述数据并行性的问题）。,流水并行,流水并行性是指在同一个数据流上同时的执行多个程序（后续的程序处理的是前面程序处理过的数据流）。流水并行性通常也被称为流水线。在流水线上，计算的并行性表现为：每个处理器上运行一个不同的程序，它们构成一个完整的处理流程，每个处理器把自己处理完的数据马上传递给（逻辑上）的下一个处理器。这样实际上形成了处理器间的一个流水线，因此称为流水并行性。,混合并行,很多的问题中的并行性表现为数据并行性，任务并行性和流水并行性的混合，某个问题表现出的流水并行性的数量通常独立于问题的规模，而任务和数据并行性则相反，他们通常会随问题规模的增长而增长。通常情况下，任务并行性可以用来开发粗粒度的并行性，而数据并行性用来开发细粒度的并行性，因此，任务并行性和数据并行性的组合可以用来有效的开发应用在大量处理器上的并行算法。,分解技术,设计并行算法的一个基本的步骤是描述完成给定任务所需要的计算，并把这些计算分解为可以并行执行的子任务集。对很多的问题来说，它们的任务图都包含了足够的并行性。对这样的任务图，各个任务可以在多个处理器上进行调度，从而使得问题得以并行的完成。但不幸的是，很多的问题的任务图中并不表现出如此丰富（或者称为直观）的并行性，相反的，它们往往包含一个任务或者多个需要串行执行的任务。对这样的问题，我们需要将总的计算任务进行分解为一个可以并行执行的子任务集，这个过程称为任务分解。一个好的任务分解应该具有下面的特点： 它应该有很高的并行度。并行度越高意味着这个分解后的任务可以在越多的处理器上并行的执行。 子任务间的交互（通信和同步）应该尽可能的少。交互少意味着处理器可以更专心的完成任务本身而不是其它由于通信和同步带来的额外计算和等待。,分解技术,很多情况下，这两个要求会产生冲突，也就是说，有很高的并行度的任务分解，通常需要子任务间的大量交互操作。如何平衡冲突是并行算法设计中的艺术。这一节中主要考虑如何提高子任务的并行度，关于子任务间的交互的讨论在下一节进行。 下面介绍几种用于任务分解的常用的方法。对不同的问题，这些方法并不总是可行，而且也不一定会得到最有效的并行算法，但对很多问题来说，这些方法可以提供一个好的并行化的“着眼点”。 其中的递归分解和数据分解可以被看成是相对通用的分解方法，因为它们可以用来对大多数的问题进行任务分解，而搜索分解要特殊一些，它只能应用于某些特定类型的问题。,递归分解,递归分解通常用来对采用Divide-and-conquer(分治)方法的问题进行任务分解。这种方法将任务分解为独立的子任务，这个分解的过程会递归的进行。问题的答案是所有的子任务的答案的组合。分-治策略表现出一种自然的并行性。 考虑下面的问题：对n个元素的序列A进行快速排序。快速排序算法是一种分治的算法。算法首先选取一个轴元素x，然后把A分成两个子序列A0和A1，其中A0中的所有元素小于x,而A1中的所有元素大于等于x,这是算法的分割部分。对得到的子序列递归地进行上面的分割过程，然后用经过排序的子序列组合成最后的结果序列A。快速排序的过程可以用下面的图来示例。,递归分解,递归分解,其中的深色的元素为选中的轴元素。 现在考虑如何根据算法的分-治特性来对快速排序算法进行任务分解。从上面的图可以看出，对任务树的每一层，每个子任务的继续分割是可以并行执行的，而且它们互相独立。因此对计算的分解实际上也是一棵树。算法开始时，只有一个序列（树的根节点），我们用一个处理器来完成对它的第一次分割。分割完成后，我们得到了第一层中的2个子序列，对这两个子序列的分割可以在两个处理器上分别进行，（如果序列足够长）树中的第i层中会出现2i个子序列，它们可以由2i个处理器独立并行完成。,递归分解,递归分解处理的问题（的串行算法）并不一定是递归的。比如下面的问题：n个元素的未排序序列A，求A的最小值。下面的串行算法对A采取逐个扫描的方法： Minimum(A, n) min = A0； for (i=1; in; i+) if (Ai min) min = Ai； return min； ,递归分解,这个算法本身没有表现出任何的并行性（实际上与min的使用有关）。一种可行的解决办法是采用分治的策略来重新得到一个算法，然后采用递归分解的方法来开发并行性。改写后的算法如下（递归算法）： Minimum(A, n) if (n = 1) return A0； lmin = Minimum(A, n/2)； rmin = Minimum(A+n/2,n-n/2)； if (lmin rmin) return lmin； else return rmin； 这个算法很好理解，思路与上面的快速排序几乎一样。上面算法的递归树如下图（对8个元素的序列进行操作）所示：,递归分解,递归分解,现在对任务的分解就简单多了。注意与前面的并行快速排序算法相反，这个分-治算法更多的计算时间花费在结果的组合阶段。因此，这个算法的并行版