吉林大学研究所课程-并行计算课件-第4章—并行计算基本设计技术

1、并行算法的基本设计技术4.1 PA的一般设计方法的一般设计方法4.2 PA的基本设计过程的基本设计过程4.3 PA的常用设计技术的常用设计技术PA的一般设计方法n串行算法直接并行化串行算法直接并行化n借用法借用法n全新的方法全新的方法串行算法直接并行化n串行算法并非都可并行化串行算法并非都可并行化n好的串行算法不一定直接是好的并行算好的串行算法不一定直接是好的并行算法法n很多数值运算都可直接并行化很多数值运算都可直接并行化串行算法直接并行化步骤n 检测和开发现有程序内在的并行性检测和开发现有程序内在的并行性n并行编码并行实现并行编码并行实现借用法n找问题与原有方法之间的关系找问题与原有方法之间

2、的关系n设计相似算法设计相似算法n有丰富的经验基础有丰富的经验基础借用法n实例：实例：矩阵乘矩阵乘组合优化原理组合优化原理求现有点队的最短路径求现有点队的最短路径，节点，节点i和节点和节点j之之间的距离用间的距离用dijk表示表示全新的方法n根据一个给定问题的描述，重新设计或根据一个给定问题的描述，重新设计或发明一个并行算法发明一个并行算法n一般可以得到较好的并行算法一般可以得到较好的并行算法n是一个具有挑战性和创新性工作是一个具有挑战性和创新性工作n设计者应有较好的理解能力和设计背景设计者应有较好的理解能力和设计背景并行算法的基本设计技术4.1 PA的一般设计方法的一般设计方法4.2 PA的

3、基本设计过程的基本设计过程4.3 PA的常用设计技术的常用设计技术PA的基本设计过程P:partitioningC:communicationA:AgglomerationP1P2P3M:mapping划分（P）n目的目的n开发并行性的可行性开发并行性的可行性n方法方法n数据分解数据分解+功能分解功能分解n规划规划n常用的数据，通信频率的进程分为一组常用的数据，通信频率的进程分为一组n判判据据（Check list 的设计问题的设计问题）通信（C）n目的目的n根据任务执行的需要交换数据后；协调任务根据任务执行的需要交换数据后；协调任务的执行的执行n通信要求通信要求n在域分解中的确定通信要求在域

4、分解中的确定通信要求n在功能分解时，容易确定通信需求在功能分解时，容易确定通信需求通信（C）n通信模式通信模式n局部通信局部通信 结构化结构化 静态静态 同步同步n全局通信全局通信 非结构化非结构化 动态动态 异步异步n判判据据（测试表的设计问题测试表的设计问题）组合（A）n目的目的n按性能要求和时间的代价来考察前两阶段的按性能要求和时间的代价来考察前两阶段的结果对小的任务进行必要的组合以减少通信结果对小的任务进行必要的组合以减少通信开销和提交性能开销和提交性能n需回答需回答8个方面的问题个方面的问题n判据判据（测试表的设计问题测试表的设计问题）匹配（M）n目的目的n将每个任务分配到一个处理机

5、上，降低将每个任务分配到一个处理机上，降低通信开销和执行时间，提高处理机利用通信开销和执行时间，提高处理机利用率率n判据判据（涉及策略，方法和测试表设计等问题涉及策略，方法和测试表设计等问题）并行算法的基本设计技术4.1 PA的一般设计方法的一般设计方法4.2 PA的基本设计过程的基本设计过程4.3 PA的常用设计技术的常用设计技术PA的常用设计技术n从开发并行性的角度出发从开发并行性的角度出发 划分划分技术技术n从求解问题的策略出发从求解问题的策略出发 分治分治技术技术n充分利用时空特性充分利用时空特性 流水域流水域技术技术n针对问题自身特性针对问题自身特性设计设计 倍增技术、倍增技术、 破

6、对称技术、破对称技术、 平衡树技术平衡树技术Outlinen4.3.1 划分划分技术技术n4.3.2 分治策略分治策略n4.3.3 流水线技术流水线技术n4.3.4 倍增技术倍增技术n4.3.5 破对称技术破对称技术n4.3.6平衡树算法平衡树算法划分方法n基本出发点基本出发点n有效利用空闲处理器有效利用空闲处理器n大问题求解需要提大问题求解需要提高高求解速度求解速度n具体划分方法具体划分方法n均匀划分法均匀划分法n平方根划分平方根划分n对数划分对数划分n随机划分随机划分n功能划分功能划分对数划分法举例问题描述问题描述设设两非降数组两非降数组 A= A=（a1,a2,ana1,a2,an） B

7、= B=（b1,b2,bmb1,b2,bm）其中其中logmlogm和和K(m)=m/logmK(m)=m/logm都是整数都是整数要求：K(m)配对A和B的子序列（Ai,Bi）,使得 Bi =logm, Ai =n和对于所有1ik(m)-1,Ai和Bi中的每一个元素都大于Ai-1和Bi-1中的每一个元素对数划分法举例n定义定义nRank(x:X)表示表示x在在X中的位序号中的位序号n方法描述方法描述n先找先找B序列划分点序列划分点 b1*logm b2*logm b(i+1)*logmn再找再找A序列划分点序列划分点 a(b1*logm:A) a(b2*logm:A) a(b(i+1)log

8、m:A)n然后分组归并然后分组归并对数划分法举例-实现Begin j(0)0;j(k(m)-n for i=1 to k(m)-1 par_do (2.1) rank bi logm in A using binary search (2.2) j(i)rank(bi.logm:A) End for for i=0 to k(m)-1 par_do (3.1) Bi(bi.logm+1,b(i+1)logm) (3.2) Ai-(aj(i)+1,aj(i+1) 对数划分法举例-实例令令A=(4,6,7,10,12,15,18,20) B= (3,9,16,21) m=4 k(m)=4/log4

9、=2 应用上述算法则有：应用上述算法则有：对数划分法举例-实例nj(o)0 ; j(k(4)8/ 数组数组A中中 n=8, j(0)=0, j(2)=8nfor i=1 to k(4)-1 pardo/ k(4)=2,k(4)-1=1n(2.1) rank b1*log4 in A using binary search/rank b1*log4在在A中位序即中位序即rank(9:A)=3n(2.2) j(1)rank(b2:A) /j(1)3nEnd forn for i=0 to k(4)-1 par_don(3.1) Bo(bo*log4+1,b(0+1)log4)/Bo(b1,b2)=

10、(3,9)n(3,2) Ao230011204-070111011-1141110215-220010000-0151111011-140100000-050101011-160110113-081000102-2101010000-0111011011-1121100000-091001204-1131101215-0114215456810119131237241501013201450201201010010102Outlinen4.3.1 划分方法划分方法n4.3.2 分治策略分治策略n4.3.3 流水线技术流水线技术n4.3.4 倍增技术倍增技术n4.3.5 破对称技术破对称技术n4

11、.3.6平衡树算法平衡树算法平衡树算法n两个例子两个例子n求最大值求最大值n求前缀和求前缀和实例-求最大值n问题描述问题描述令令n=2m，A是一个是一个2n维德数组；维德数组；待待求最大值求最大值n个数开始存放个数开始存放A（n），），A（n+1），），A（2n-1）；）；将将求得的最大值于求得的最大值于A（1）n算法算法n输入：输入：n=2m个数存在数组个数存在数组A（n:2n-1）中）中n输出：最大值置于输出：最大值置于A（1）中）中实例-求最大值n算法实现算法实现Begin For k=m-1 to 0 do For j=2k to 2k+1-1 par_do A(j)MaxA(2j),

12、A(2j+1) End for End forEnd实例-求最大值n复杂度分析复杂度分析nT(n)=O(logn)np(n)=n/2实例-求最大值n例：（例：（4,6,8,0）这里）这里n=4,m=2,(n=2m), A=(0,0,0,0,4,6,8,0)解：解：K=m-1=1时，时，j=2k=2时，时，A(j)=A(2)=maxA(4),A(5)=6 4 6 j=2k+1或或-1=3时，时，A(j)=A(3)=maxA(6),A(7)=8 8 0 K=0时时， j=1 to 1 A(1)=maxA(2),A(3)=8 6 8 实例求前缀和n设设SIMO*字模型中有字模型中有 p=2qn2k

13、个个处理器处理器p1,pp 令令l=n/p=2k-q,将输将输入数组划分成入数组划分成P个子数组，使得处理器个子数组，使得处理器ps负责处理器子数组负责处理器子数组A(l-(s-1)+1),A(l(s-1)+2),s(ls)n在二叉树高度在二叉树高度H上，正向和反向便利中上，正向和反向便利中所产生的值所产生的值B(h,.)和和C(h,.)也以类似方式也以类似方式非配给各处理器非配给各处理器实例求前缀和n实例求前缀和n算法实现算法实现Begin (1) for j=1 to l=n/p do B(0,l(s-1)+j)=0) then for j=2k-h-q(s-1)+1 to 2k-h-qs

14、 doB(h,j)-B(h-1,2j-1)*B(h-1,2j) end for end if (2.2) if (s=2k-h) then B(h,s)=0) then for j=2k-h-q(s-1)+1 to 2k-h-qs do (1) if(j=even) then C(h,j)-C(h+1,j/2) end if (2) if(j=1) then C(h,1)1 then C(h,j)-C(h+1,(j-1)/2)*B(h,j) end if end for (3.2) if s2k-h then (1) if(s=even) then C(h,s)-C(h+1,s/2) end

15、if (2) if(s=1) then C(h,1)1) then C(h,s)-C(h+1,(s-1)/2)*B(h,s) end if end if end for end实例求前缀和n实例：实例：n=8,p=2时求前缀和时求前缀和n处理分布情况：处理分布情况：p1p1p1p1p1p1p1p1 p2 p2 p2p2p2p2p2实例求前缀和n以以p2情况为例情况为例第一步：第一步：p2将设置将设置B(0,5)=A(5),(0,6)=a(6) B(0,7)=A(7),(0,7)=a(7)第二步：正向遍历时，第二步：正向遍历时，p2在在h=1,2时是活动的，在时是活动的，在 h=3是是空闲空闲的，的，p2通过循环通过循环B(1,3),B(1,4) 和和B(3,2)第三步：反向遍历时，第三步：反向遍历时，p2在在h=3时是时是空闲空闲的，而在的，而在 h=2时是活动的时是活动的因此，因此，p2将产生：将产生：C(2,2),C(1,3),C(1,4),C(0,5),C(0,6),C(0,7),C(0,8)作业1. 在划分设计技术、分治设计技术、平衡树设计技术、在划分设计技术、分治设计技术、平衡树设计技术、倍增