并行计算 Parallel Computing

Presentation on theme: "并行计算 Parallel Computing"— Presentation transcript:

1 并行计算 Parallel Computing
主讲人 孙广中 Spring, 2018

2 第二篇 并行算法的设计 第五章 并行算法与并行计算模型 第六章 并行算法基本设计策略 第七章 并行算法常用设计技术 第八章 并行算法一般设计过程

3 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 1. 1 均匀划分技术 7. 1. 2 方根划分技术 7. 1
第七章 并行算法常用设计技术 划分设计技术 均匀划分技术 方根划分技术 对数划分技术 功能划分技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术

4 均匀划分技术（1） 划分方法 示例：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. 国家高性能计算中心（合肥）

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

6 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 1. 1 均匀划分技术 7. 1. 2 方根划分技术 7. 1
第七章 并行算法常用设计技术 划分设计技术 均匀划分技术 方根划分技术 对数划分技术 功能划分技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术

7 方根划分技术（1） 划分方法 示例：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. 国家高性能计算中心（合肥）

8 方根划分技术（2） 国家高性能计算中心（合肥）

9 方根划分技术（3） 国家高性能计算中心（合肥）

10 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 1. 1 均匀划分技术 7. 1. 2 方根划分技术 7. 1
第七章 并行算法常用设计技术 划分设计技术 均匀划分技术 方根划分技术 对数划分技术 功能划分技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术

11 对数划分技术 划分方法 示例：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)的归并 国家高性能计算中心（合肥）

12 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 1. 1 均匀划分技术 7. 1. 2 方根划分技术 7. 1
第七章 并行算法常用设计技术 划分设计技术 均匀划分技术 方根划分技术 对数划分技术 功能划分技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术

13 功能划分技术（1） 划分方法 示例：(m, n)选择问题(求出n个元素中前m个最小者) 功能划分：要求每组元素个数必须大于m；
n个元素A[1..n]分成等长的p组，每组满足某种特性。 示例：(m, n)选择问题(求出n个元素中前m个最小者) 功能划分：要求每组元素个数必须大于m； 算法：p194算法7.4 输入：A=(a1,…,an); 输出：前m个最小者； Begin (1) 功能划分：将A划分成g=n/m组，每组含m个元素； (2) 局部排序：使用Batcher排序网络将各组并行进行排序； (3) 两两比较：将所排序的各组两两进行比较，从而形成MIN序列； (4) 排序-比较：对各个MIN序列，重复执行第(2)和第(3)步，直至 选出m个最小者。 End 国家高性能计算中心（合肥）

14 功能划分技术（2） 国家高性能计算中心（合肥）

15 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 2. 1 并行分治设计步骤 7. 2
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 并行分治设计步骤 双调归并网络 平衡树设计技术 倍增设计技术 流水线设计技术

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

17 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 2. 1 并行分治设计步骤 7. 2
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 并行分治设计步骤 双调归并网络 平衡树设计技术 倍增设计技术 流水线设计技术

18 双调归并网络（1） 双调序列(p195定义7.2) Batcher定理 (2)小数和大数序列仍是双调的
(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)有， (1) bi≤cj (1≤i, j≤n) (2)小数和大数序列仍是双调的 国家高性能计算中心（合肥）

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

20 双调归并网络（3） 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 国家高性能计算中心（合肥）

21 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 3. 1 设计思想 7. 3
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 设计思想 求最大值 计算前缀和 倍增设计技术 流水线设计技术

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

23 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 3. 1 设计思想 7. 3
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 设计思想 求最大值 计算前缀和 倍增设计技术 流水线设计技术

24 求最大值（1） 算法7.8: SIMD-TC(SM)上求最大值算法 Begin 图示 时间分析 end
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 国家高性能计算中心（合肥）

25 求最大值（2） SIMD-CRCW上常数时间求最大值算法 算法 SIMD-CRCW上枚举算法 //输入A[1..p]，p个不同元素
//B[1..p][1..p],M[1..p]为中间处理用的布尔数组, 如果M[i]＝1, 则A[i]为最大值 begin (1)for 1≤i, j≤p par-do //工作量O(p2); 时间O(1),因为允许同时读 if A[i]≥A[j] then B[i, j]=1 else B[i, j]=0 end if end for (2)for 1≤i≤p par-do //工作量O(p2); 时间O(1),因为允许同时写 M[i]=B[i,1]∧ B[i,2]∧… ∧B[i,p] end T(n)=O(1) W(n)=O(p2) 可以用p2个处理器实现 速度虽快，但不是WT最优 国家高性能计算中心（合肥）

26 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 3. 1 设计思想 7. 3
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 设计思想 求最大值 计算前缀和 倍增设计技术 流水线设计技术

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

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

29 计算前缀和（3） SIMD-SM上非递归算法 begin (1)for j=1 to n par-do //初始化 B[0,j]=A[j]
end if (2)for h=1 to logn do //正向遍历 for j=1 to n/2h par-do B[h,j]=B[h-1,2j-1]*B[h-1,2j] end for (3)for h=logn to 0 do //反向遍历 for j=1 to n/2h par-do (i) if j=even then //该结点为其父结点的右儿子 C[h,j]=C[h+1,j/2] end if (ii) if j=1 then //该结点为最左结点 C[h,1]=B[h,1] (iii) if j=odd>1 then //该结点为其父结点的左儿子 C[h,j]=C[h+1,(j-1)/2]*B[h,j] end for end 时间分析: (1) O(1) (2) O(logn) (3) O(logn) ==> t(n)=O(logn) , p(n)=n , c(n)=O(nlogn) 国家高性能计算中心（合肥）

30 Prefix Sums on a Tree: More
1 2 3 4 2019/1/2

31 Prefix Sums on a Tree: More
1 2 3 4 1,3 3,7 2019/1/2

32 Prefix Sums on a Tree: More
1 2 3 4 1,3 3,7 7 2019/1/2

33 Prefix Sums on a Tree: More
1 3 7 2019/1/2

34 Prefix Sums on a Tree: More
1 3 7 2019/1/2

35 Prefix Sums on a Tree: More
1 3 7 2019/1/2

36 Prefix Sums on a Tree: More
1 3 6 10 2019/1/2

37 Prefix Sums on a Tree: More
Properties: time: 2 log n processors: 2n – 1 cost O(n log n) Comparison with PRAM algorithm asymptotically equivalent in practice, less efficient weaker model 2019/1/2

38 1 2 3 4 5 6 7 8 9 11 13 15 10 14 18 22 26 21 28 36 depth (time) = 3 complexity (cost) = 3  8 = 24 Specialized Circuit 2019/1/2

39 1 1 Circuit for 4 inputs + 1 2 3 4 15 21 28 36 10 3 2 6 3 10 4 5 5 Circuit for 4 inputs 11 6 18 7 26 8 2019/1/2 Recursive Circuit

40 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 4 倍增设计技术 7. 4
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 设计思想 表序问题 求森林的根 流水线设计技术

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

42 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 4 倍增设计技术 7. 4
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 设计思想 表序问题 求森林的根 流水线设计技术

43 表序问题（1） 问题描述 示例：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 国家高性能计算中心（合肥）

44 表序问题（2） 算法：P200算法7.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 国家高性能计算中心（合肥）

45 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 4 倍增设计技术 7. 4
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 设计思想 表序问题 求森林的根 流水线设计技术

46 求森林的根（1） 问题描述 一组有向树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] 国家高性能计算中心（合肥）

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

48 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 4 倍增设计技术 7
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术 设计思想 point DFT的计算 多线程软件流水

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

50 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 4 倍增设计技术 7
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术 设计思想 point DFT的计算 多线程软件流水

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

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

53 第七章 并行算法常用设计技术 7. 1 划分设计技术 7. 2 分治设计技术 7. 3 平衡树设计技术 7. 4 倍增设计技术 7
第七章 并行算法常用设计技术 划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术 设计思想 point DFT的计算 多线程软件流水

54 多线程软件流水例子 问题描述：用多线程流水方法计算下面阵列：

55 多线程软件流水例子 问题描述：线程和流程设计：

56 3,4,5,1,7,2 6 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 1
2019/1/2

57 3,4,5,1,7 2 6 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 2
2019/1/2

58 3,4,5,1 7 2 6 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 3
2019/1/2

59 3,4,5 1 7 2 6 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 4
2019/1/2

60 3,4 5 2 1 6 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 5
2019/1/2

61 3 4 5 6 1 2 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 6
2019/1/2

62 3 4 5 1 2 6 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 7
2019/1/2

63 3 4 6 1 2 5 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 8
2019/1/2

64 3 5 1 2 4 6 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 9
2019/1/2

65 4 6 1 2 3 5 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 10
2019/1/2

66 5 1 2 3 4 6 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 11
2019/1/2

67 6 1 2 3 4 5 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 12
2019/1/2

68 1 2 3 4 5 6 7 Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 13
2019/1/2

69 作业 2. 习题7-10（P207） 1.以下是上三角方程组回代解法的串行算法的形式化描述。（算法10.1）
输入： An*n b = (b1 , … , bn)T 输出： x = (x1, … , xn)T Begin (1)for i=n downto 1 do (1.1)xi=bi/aii (1.2)for j=1 to i-1 do bj=bj-ajixi aji=0 endfor End ①请指出串行算法哪些部分可以并行化。②写出并行算法的形式化描述（需要注明计算 模型类型），分析你的算法的时间复杂度。 2. 习题7-10（P207）