Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


Presentation on theme: "中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月"— Presentation transcript:

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

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

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

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

5 均匀划分技术 划分方法 示例: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 均匀划分技术 例6.1 PSRS排序过程。N=27,p=3,PSRS排序如下: 国家高性能计算中心(合肥) 2019/4/18

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

8 方根划分技术 划分方法 示例: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

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

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

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

12 对数划分技术 划分方法 示例: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, B1: 16, 21 A0: 4, 6, A1: 10, 12, 15, 18, 20 A和B归并化为(A0, B0)和(A1, B1)的归并 国家高性能计算中心(合肥) 2019/4/18

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

14 功能划分技术 划分方法 示例:(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

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

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

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

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

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

20 双调归并网络 双调序列(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

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

22 双调归并网络 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

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

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

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

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

27 求最大值 算法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

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

29 计算前缀和 问题定义 串行算法: 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

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

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

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

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

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

35 表序问题 问题描述 示例: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

36 表序问题 算法: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

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

38 求森林的根 问题描述 一组有向树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

39 求森林的根 示例 算法: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

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

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

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

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

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

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


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

Similar presentations


Ads by Google