课件多核并行计算

1、2022/8/3Parallel Computing Chapter 6 Supplement Fundamental Techniques of Designing Parallel Algorithms2022/8/3基本设计技术6.1 Partitioning Principle6.2 Divide-and-Conquer Strategy6.3 Balanced Trees Method6.4 Doubling Techniques 6.5 Pipelining Techniques2022/8/36.1 划分设计技术设计思想将原问题划分成p个独立的几乎相等的子问题；p台处理器并行地求

2、解各子问题。 Remark:划分重点在于:子问题易解,组合成原问题的解方便;有别于分治法常见划分方法均匀划分 方根划分 对数划分 功能划分(补)2022/8/36.1.4 功能划分方法: n个元素A1.n分成等长的p组，每组满足 某种特性。示例: (m, n)选择问题(求出n个元素中前m个最小者) - 功能划分：要求每组元素个数必须大于m； - 算法是基于Batcher排序网络，下面先介绍一些预备知识： 1.Batcher比较器 2.奇偶归并及排序网络: 网络构造、奇偶归并网络、奇偶排序网络 3.双调归并及排序网络: 定义与定理、网络构造、双调归并网络、双调排序网络2022/8/36.1.4

3、功能划分1. Batcher比较器比较和条件交换操作: CCI比较器网络：用Batcher比较器连成完成某一功能的网络假定：每次每个元素只能与另一个元素比较比较器网络的参数：比较器数目、延迟级数2022/8/36.1.4 功能划分2.1奇偶归并网络构造有序序列A:a1,a2,an B: b1,b2,bm归并思想：A, B中奇数号元素进入奇归并器；A, B中偶数号元素进入偶归并器；再将奇归并器与偶归并器的输出交叉比较注: (m,n)规模划分为：2022/8/36.1.4 功能划分2.2 奇偶归并示例：m=n=4 A=(2,4,6,8) B=(0,1,3,5)(4, 4)2(2, 2)4(1, 1

4、)(2,2)奇归并2468013520634185023614580236145801234568(2,2)偶归并交叉比较2022/8/36.1.4 功能划分2.3 奇偶排序网络基于奇偶归并网络示例： B(8)385172463815274613582467123456782022/8/36.1.4 功能划分3.1 定义及定理定义: 一个序列a1,a2,an是双调序列(Bitonic Sequence)，如果： (1)存在一个ak(1kn), 使得a1akan成立；或者 (2)序列能够循环移位满足条件(1)示例： 序列(1,3,5,7,8,6,4,2,0), (7,8,6,4,2,0,1,3,

5、5)和(1,2,3,4,5,6,7,8) 都是双调序列。 ak定理(Batcher定理)： 设序列a1,an,an+1, a2n是一个双调序列, 记 bi=minai, ai+n = MIN=b1,bn, ci=maxai, ai+n = MAX=c1,cn, 则 (1) bicj (1i, jn) (2) MIN和MAX序列仍是双调的 2022/8/36.1.4 功能划分3.2 双调归并网络构造(依据Batcher定理)2n个输入的双调序列两两比较形成2个大小为n的MIN和MAX序列MIN和MAX序列是双调的，可以递归重复进行下去MINMINMINMINMAXMAXMAXMAXMIN双调序列

6、MAX双调序列2022/8/36.1.4 功能划分3.3 双调归并示例:双调序列(8,6,4,2,0,1,3,5)的(4,4)双调归并网络2个(2,2)双调归并网络864201358061432508163425MIN归并MAX归并01234568两两比较2022/8/36.1.4 功能划分3.4 双调排序网络基于双调归并网络示例：B(8)831572463851724613587642123456782022/8/36.1.4 功能划分基于划分原理的(m,n)-选择过程 将n个输入数据划分成若干个大小相等的子序列(m)； 使用Batcher排序网络对各子序列排序； 将有序子序列形成双调序列，

7、进行 两两对接； 使用Batcher定理形成MAX,MIN序 列，弃去MAX序列； 再使用Batcher排序网络将MIN序列 排成有序序列； 重复直至MIN序列恰好包含所需 的m个最小元素为止。2022/8/36.1.4 功能划分(m,n)-选择示例：B(4)奇偶排序137110241185153961216141710132481135915612141617423596124735691243分组双调对接比较取MIN双调对接比较取MIN分组Batcher奇偶排序分组Batcher奇偶排序2022/8/312341234Prefix Sums on a Tree: More6.3 平衡树设计

8、技术2022/8/312341,33,76.3 平衡树设计技术Prefix Sums on a Tree: More2022/8/312341,33,713376.3 平衡树设计技术Prefix Sums on a Tree: More2022/8/3133736.3 平衡树设计技术Prefix Sums on a Tree: More2022/8/31337336.3 平衡树设计技术Prefix Sums on a Tree: More2022/8/313373336.3 平衡树设计技术Prefix Sums on a Tree: More2022/8/3136106.3 平衡树设计技术Pr

9、efix Sums on a Tree: More2022/8/3Properties:time:2 log nprocessors:2n 1costO(n log n)Comparison with PRAM algorithmasymptotically equivalentin practice, less efficientweaker model6.3 平衡树设计技术Prefix Sums on a Tree: More2022/8/3Specialized Circuit123456781357911131513610141822261361015212836depth (time

10、) = 3complexity (cost)= 3 8 = 246.3 平衡树设计技术2022/8/3Recursive Circuit12345678Circuit for4 inputsCircuit for4 inputs136105111826+123415212836101010106.3 平衡树设计技术2022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 13,4,5,1,7,262022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2,

11、6 Step 263,4,5,1,722022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 3263,4,5,172022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 4263,4,5172022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 51673,4522022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4

12、, 5, 1, 7, 2, 6 Step 612734562022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 712673452022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 812576432022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 912467532022/8/36.5 流水线设计技术Systolic排序算法示例: Sorting 3, 4, 5, 1, 7, 2, 6 Step 1012357642022/8/36.5 流水线设计技术Systolic排序算法示例: Sor