资源描述：
《西安交大并行计算理论赵银亮课件第六章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法 第六章并行算法的基本设计技术第七章并行算法的一般设计过程第六章并行算法的基本设计技术6.1划分设计技术6.2分治设计技术6.3平衡树设计技术6.4倍增设计技术6.5流水线设计技术6.3平衡树设计技术设计思想以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。示例求最大值计算前缀和算法6.8:SIMD-TC(SM)上求最大值算法beginfork=m-1to0doforj=2kto2k+1-1par-doA[j]=max{A[2j],A[2j+1]}e
2、ndforendforendA1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2A2n-1K=m-1K=m-2K=0……K=0t(n)=m×O(1)=O(logn)p(n)=n/2计算前缀和问题定义n个元素{x1,x2,…,xn}，前缀和是n个部分和：Si=x1*x2*…*xi,1≤i≤n这里*可以是＋或×串行算法：Si=Si－1*xi计算时间为O(n)并行算法：p154算法6.9SIMD-TC上非递归算法令A[i]=xi,i=1~n,B[h,j]和C[h,j]为辅助数组(h=0~
3、logn,j=1~n/2h)数组B记录由叶到根正向遍历树中各结点的信息(求和)数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和)例：n=8,p=8,C01~C08为前缀和PRAM求前缀和算法sequenceTSCAN(sequenceTx,⊕:T×T→T)x为B树第k层Scan返回为C树第k层y为B树第k-1层z为C树第k-1层由z构造出s，也就是C树第k层8个元素的数据流分析B树C树6.4倍增设计技术设计思想又称指针跳跃(pointerjumping)技术，特别适合于处理链表或有向树之类的数据结构；当递归调用时，所要处理数据之间的距离逐步
4、加倍，经过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]=
5、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(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表序问题算法：P155算法6.10(1)并行做：初始化p[k]和distance[k]//O(1)(2)执行次//O(logn)(2.1)对k并行地做//O(1)如果k的后继不等于
6、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中,如果是F中的一条弧，则p[i]=j(即j是i的双亲)；若i为根，则p[i]=i。求每个结点j(j=1~n)的树根s[j].示例初始时P[1]=p[2]=5p[3]=p[4]=p[5]=6P[6]=p[7]=8p[8]=8P[9]=10p[10]=11p[11
7、]=12p[12]=13p[13]=13s[i]=p[i]求森林的根示例第一次迭代后第二次迭代后算法：P157算法6.11运行时间：t(n)=O(logn)W(n)=O(nlogn)6.2分治设计技术6.2.1并行分治设计步骤6.2.2比较器排序网络6.2.3凸壳问题并行分治设计步骤将输入划分成若干个规模相等的子问题；同时(并行地)递归求解这些子问题；并行地归并子问题的解，直至得到原问题的解。Batcher归并、排序网络比较器操作和[0,1]原理奇偶归并网络双调归并网络Batcher排序网络2D-Mesh上的排序算法比较器操作和[0,1]原理Am
8、in(A,B)Bmax(A,B)Amin(A,B)Bmax(A,B)…n个输入n个输出第1级第2级第m级延迟级数？比较器个数？四个数的排
