ParallelAlgorithmsChapter2FundamentalTechniquesofParallelAlgorithms主要内容2.1平衡树方法算法2.1SIMD-SM上求最大值算法Beginfork=m-1to0doforj=2kto2k+1-1par-doA[j]=max{A[2j],A[2j+1]}endforendforend前缀和问题定义n个元素{x1,x2,…,xn}，前缀和是n个部分和：Si=x1*x2*…*xi,1≤i≤n这里*可以是＋或×串行算法：Si=Si－1*xi计算时间为O(n)并行算法：p56算法2.2SIMD-SM上非递归算法(高层描述)p58算法2.3SIMD-SM上非递归算法(底层描述)令A[i]=xi,i=1~n,B[h,j]和C[h,j]为辅助数组(h=0~logn,j=1~n/2h)数组B记录由叶到根正向遍历树中各结点的信息(求和)数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和)p56算法2.2SIMD-SM上非递归算法begin(1)forj=1tonpar-do//初始化B[0,j]=A[j]endif(2)forh=1tologndo//正向遍历forj=1ton/2hpar-doB[h,j]=B[h-1,2j-1]*B[h-1,2j]endforendfor主要内容主要内容设计思想又称指针跳跃(pointerjumping)技术，特别适合于处理链表或有向树之类的数据结构；当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2k的所有数据的计算。示例表序问题求森林的根表序问题：问题描述n个元素的列表L，求出每个元素在L中的次第号(秩或位序或rank(k))，rank(k)可视为元素k至表尾的距离；示例：n=7(1)p[a]=b,p[b]=c,p[c]=d,p[d]=e,p[e]=f,p[f]=g,p[g]=gr[a]=r[b]=r[c]=r[d]=r[e]=r[f]=1,r[g]=0(2)p[a]=c,p[b]=d,p[c]=e,p[d]=f,p[e]=p[f]=p[g]=gr[a]=r[b]=r[c]=r[d]=r[e]=2,r[f]=1,r[g]=0(3)p[a]=e,p[b]=f,p[c]=p[d]=p[e]=p[f]=p[g]=gr[a]=4,r[b]=4,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=0注：递归计算位序r(4)p[a]=p[b]=p[c]=p[d]=p[e]=p[f]=p[g]=gr[a]=6,r[b]=5,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=0表序问题：算法：P60算法2.4(1)并行做：初始化p[k]和distance[k]//O(1)(2)执行次//O(logn)(2.1)对k并行地做//O(1)如果k的后继不等于k的后继之后继，则(i)distance[k]=distance[k]+distance[p[k]](ii)p[k]=p[p[k]](2.2)对k并行地做rank[k]=distance[k]//O(1)运行时间：t(n)=O(logn)p(n)=n求森林的根问题描述一组有向树F中,如果<i,j>是F中的一条弧，则p[i]=j(即j是i的双亲)；若i为根，则p[i]=i。求每个结点j(j=1~n)的树根s[j].示例求森林的根示例第一次迭代后第二次迭代后算法：p61算法2.5运行时间：t(n)=O(logn)主要内容主要内容设计思想将原问题划分成若干个相同的子问题分而治之，若子问题仍然较大，则可以反复递归应用分治策略处理这些子问题，直至子问题易求解。求解步骤将输入划分成若干个规模相等的子问题；同时(并行地)递归求解这些子问题；并行地归并子问题的解成为原问题的解。示例SIMD-SM模型上的FFT递归算法FFT递归算法DFT离散富里叶变换的定义给定向量，DFT将A变换为，即写成矩阵形式为注：串行直接计算DFT需要O(n2)FFT递归算法：将原问题的DFT划分为两个规模为n/2的子问题的DFTSIMD-SM模型上的算法：p64算法2.7主要内容主要内容划分原理：设计思想将原问题划分成p个独立的规模几乎相等的子问题；p台处理器并行地求解各子问题。Remark:划分重点在于:子问题易解,组合成原问题的解方便;常见划分方法均匀划分•方根划分对数划分•功能划分均匀划分：方法:n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~