中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月 并 行 计 算 中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月

第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程

第六章 并行算法的基本设计技术 6. 1 划分设计技术 6. 2 分治设计技术 6. 3 平衡树设计技术 6. 4 倍增设计技术 6 第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术

6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术 6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术

均匀划分技术 划分方法 示例：MIMD-SM模型上的PSRS排序 begin n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p 示例：MIMD-SM模型上的PSRS排序 begin (1)均匀划分：将n个元素A[1..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. 国家高性能计算中心（合肥） 2019/4/18

均匀划分技术 例6.1 PSRS排序过程。N=27，p=3，PSRS排序如下： 国家高性能计算中心（合肥） 2019/4/18

6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术 6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术

方根划分技术 划分方法 示例：SIMD-CREW模型上的 Valiant归并(1975年发表) n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2) 示例：SIMD-CREW模型上的 Valiant归并(1975年发表) //有序组A[1..p]、B[1..q], (假设p<=q), 处理器数 begin (1)方根划分: A,B分别按 ； (2)段间比较: A划分元与B划分元比较(至多 对)， 确定A划分元应插入B中的区段； (3)段内比较: A划分元与B相应段内元素进行比较，并插入适当的位置； (4)递归归并: B按插入的A划分元重新分段，与A相应段(A除去原划分元) 构成了成对的段组，对每对段组递归执行(1)~(3)，直至A 组为0时，递归结束; 各组仍按 分配处理器； end. 国家高性能计算中心（合肥） 2019/4/18

方根划分技术 国家高性能计算中心（合肥） 2019/4/18

方根划分技术 国家高性能计算中心（合肥） 2019/4/18

6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术 6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术

对数划分技术 划分方法 示例：PRAM-CREW上的对数划分并行归并排序 n个元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn 示例：PRAM-CREW上的对数划分并行归并排序 (1)归并过程: 设有序组A[1..n]和B[1..m] j[i]=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 => j[1]=rank(blogm:A)=rank(b2:A)=rank(9:A)=3, j[2]=…=8 B0: 3, 9 B1: 16, 21 A0: 4, 6, 7 A1: 10, 12, 15, 18, 20 A和B归并化为(A0, B0)和(A1, B1)的归并 国家高性能计算中心（合肥） 2019/4/18

6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术 6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术

功能划分技术 划分方法 示例：(m, n)选择问题(求出n个元素中前m个最小者) 功能划分：要求每组元素个数必须大于m； n个元素A[1..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 国家高性能计算中心（合肥） 2019/4/18

功能划分技术 国家高性能计算中心（合肥） 2019/4/18

第六章 并行算法的基本设计技术 6. 1 划分设计技术 6. 2 分治设计技术 6. 3 平衡树设计技术 6. 4 倍增设计技术 6 第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术

6.2 分治设计技术 6.2.1 并行分治设计步骤 6.2.2 双调归并网络 6.2 分治设计技术 6.2.1 并行分治设计步骤 6.2.2 双调归并网络

并行分治设计步骤 将输入划分成若干个规模相等的子问题； 同时(并行地)递归求解这些子问题； 并行地归并子问题的解，直至得到原问题的解。 国家高性能计算中心（合肥） 2019/4/18

6.2 分治设计技术 6.2.1 并行分治设计步骤 6.2.2 双调归并网络 6.2 分治设计技术 6.2.1 并行分治设计步骤 6.2.2 双调归并网络

双调归并网络 双调序列(p149定义6.2) Batcher定理 (8,7,6,4,2,0,1,3,5) (1,2,3,4,5,6,7,8) (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=min{xi,xi+n/2}和 li=max{xi,xi+n/2}， 则小序列(s0,s1,…,sn-1)和大序列(l0,l1,…,ln-1) 仍是双调序列 国家高性能计算中心（合肥） 2019/4/18

双调归并网络 (4,4)双调归并网络 国家高性能计算中心（合肥） 2019/4/18

双调归并网络 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=min{xi,xi+n/2} (1.2) li=max{xi,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 国家高性能计算中心（合肥） 2019/4/18

第六章 并行算法的基本设计技术 6. 1 划分设计技术 6. 2 分治设计技术 6. 3 平衡树设计技术 6. 4 倍增设计技术 6 第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术

6.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和 6.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和

平衡树设计技术 设计思想 示例 以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。 求最大值 计算前缀和 国家高性能计算中心（合肥） 2019/4/18

6.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和 6.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和

求最大值 算法6.8: SIMD-TC(SM)上求最大值算法 Begin 图示 时间分析 end t(n)=m×O(1)=O(logn) for k=m-1 to 0 do for j=2k to 2k+1-1 par-do A[j]=max{A[2j], A[2j+1]} end for end 图示 时间分析 t(n)=m×O(1)=O(logn) p(n)=n/2 A1 An/4 An/2-1 An/2 An/2+1 An-2 An-1 An An+1 An+2 An+3 A2n-4 A2n-3 A2n-2 A2n-1 K=m-1 K=m-2 K=0 P1 P2 Pn/2-1 Pn/2 国家高性能计算中心（合肥） 2019/4/18

6.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和 6.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和

计算前缀和 问题定义 串行算法： Si=Si－1*xi 计算时间为 O(n) 并行算法：p154算法6.9 SIMD-TC上非递归算法 n个元素{x1,x2,…,xn}，前缀和是n个部分和： Si=x1*x2*…*xi, 1≤i≤n 这里*可以是＋或× 串行算法： Si=Si－1*xi 计算时间为 O(n) 并行算法：p154算法6.9 SIMD-TC上非递归算法 令A[i]=xi, i=1~n, B[h,j]和C[h,j]为辅助数组(h=0~logn, j=1~n/2h) 数组B记录由叶到根正向遍历树中各结点的信息(求和) 数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和) 国家高性能计算中心（合肥） 2019/4/18

计算前缀和 例：n=8, p=8, C01~C08为前缀和 国家高性能计算中心（合肥） 2019/4/18

第六章 并行算法的基本设计技术 6. 1 划分设计技术 6. 2 分治设计技术 6. 3 平衡树设计技术 6. 4 倍增设计技术 6 第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术

6.4 倍增设计技术 6.4.1 设计思想 6.4.2 表序问题 6.4.3 求森林的根

倍增设计技术 设计思想 示例 又称指针跳跃(pointer jumping)技术，特别适合于处理链表或有向树之类的数据结构； 当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2k的所有数据的计算。 示例 表序问题 求森林的根 国家高性能计算中心（合肥） 2019/4/18

6.4 倍增设计技术 6.4.1 设计思想 6.4.2 表序问题 6.4.3 求森林的根

表序问题 问题描述 示例：n=7 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]=g r[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]=g r[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]=g r[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]=g r[a]=6, r[b]=5, r[c]=4, r[d]=3, r[e]=2, r[f]=1, r[g]=0 国家高性能计算中心（合肥） 2019/4/18

表序问题 算法：P155算法6.10 (2)执行 次 //O(logn) (2.1)对k并行地做 //O(1) (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 国家高性能计算中心（合肥） 2019/4/18

6.4 倍增设计技术 6.4.1 设计思想 6.4.2 表序问题 6.4.3 求森林的根

求森林的根 问题描述 一组有向树F中, 如果<i, j>是F中的一条弧，则p[i]=j(即j是i的双亲)；若i为根，则p[i]=i。求每个结点j(j=1~n)的树根s[j]. 示例 初始时 P[1]=p[2]=5 p[3]=p[4]=p[5]=6 P[6]=p[7]=8 p[8]=8 P[9]=10 p[10]=11 p[11]=12 p[12]=13 p[13]=13 s[i]=p[i] 国家高性能计算中心（合肥） 2019/4/18

求森林的根 示例 算法：P157算法6.11 运行时间：t(n)=O(logn) W(n)=O(nlogn) 第一次迭代后 第二次迭代后 第一次迭代后 第二次迭代后 算法：P157算法6.11 运行时间：t(n)=O(logn) W(n)=O(nlogn) 国家高性能计算中心（合肥） 2019/4/18

第六章 并行算法的基本设计技术 6. 1 划分设计技术 6. 2 分治设计技术 6. 3 平衡树设计技术 6. 4 倍增设计技术 6 第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术

6.5 流水线设计技术 6.5.1 设计思想 6.5.2 5-point DFT的计算

流水线设计技术 设计思想 评注 将算法流程划分成p个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输入； 所有任务片断按同样的速率产生出结果。 评注 流水线技术是一种广泛应用在并行处理中的技术； 脉动算法(Systolic algorithm)是其中一种流水线技术； 国家高性能计算中心（合肥） 2019/4/18

6.5 流水线设计技术 6.5.1 设计思想 6.5.2 5-point DFT的计算

5-point DFT的计算 问题描述 5-point DFT的计算。应用秦九韶(Horner)法则， 国家高性能计算中心（合肥） 2019/4/18

5-point DFT的计算 示例：p(n)=n-1, t(n)=2n-2=O(n) 国家高性能计算中心（合肥） 2019/4/18