中科大多核并行计算课件.ppt

《中科大多核并行计算课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ParallelComputingChapter6SupplementFundamentalTechniquesofDesigningParallelAlgorithms2021/7/27基本设计技术6.1PartitioningPrinciple6.2Divide-and-ConquerStrategy6.3BalancedTreesMethod6.4DoublingTechniques6.5PipeliningTechniques2021/7/276.1划分设计技术设计思想将原问题划分成p个独立的几乎相等的子问题；p台处理器并

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

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

4、示例：m=n=4A=(2,4,6,8)B=(0,1,3,5)(4,4)2×(2,2)4×(1,1)(2,2)奇归并2468013520634185023614580236145801234568(2,2)偶归并交叉比较2021/7/276.1.4功能划分2.3奇偶排序网络基于奇偶归并网络示例：B(8)385172463815274613582467123456782021/7/276.1.4功能划分3.1定义及定理定义:一个序列a1,a2,…,an是双调序列(BitonicSequence)，如果：(1)存在一个ak(1≤k≤

5、n),使得a1≥…≥ak≤…≤an成立；或者(2)序列能够循环移位满足条件(1)示例：序列(1,3,5,7,8,6,4,2,0),(7,8,6,4,2,0,1,3,5)和(1,2,3,4,5,6,7,8)都是双调序列。ak定理(Batcher定理)：设序列a1,…,an,an+1,…,a2n是一个双调序列,记bi=min{ai,ai+n}==>MIN={b1,…,bn},ci=max{ai,ai+n}==>MAX={c1,…,cn},则(1)bi≤cj(1≤i,j≤n)(2)MIN和MAX序列仍是双调的2021/7/276.1.4

6、功能划分3.2双调归并网络构造(依据Batcher定理)2n个输入的双调序列两两比较形成2个大小为n的MIN和MAX序列MIN和MAX序列是双调的，可以递归重复进行下去MINMINMINMINMAXMAXMAXMAXMIN双调序列MAX双调序列2021/7/276.1.4功能划分3.3双调归并示例:双调序列(8,6,4,2,0,1,3,5)的(4,4)双调归并网络2个(2,2)双调归并网络864201358061432508163425MIN归并MAX归并01234568两两比较2021/7/276.1.4功能划分3.4双调排序网

7、络基于双调归并网络示例：B(8)831572463851724613587642123456782021/7/276.1.4功能划分基于划分原理的(m,n)-选择过程①将n个输入数据划分成若干个大小相等的子序列(≥m)；②使用Batcher排序网络对各子序列排序；③将有序子序列形成双调序列，进行两两对接；使用Batcher定理形成MAX,MIN序列，弃去MAX序列；再使用Batcher排序网络将MIN序列排成有序序列；④重复③直至MIN序列恰好包含所需的m个最小元素为止。2021/7/276.1.4功能划分(m,n)-选择示例：B

8、(4)奇偶排序137110241185153961216141710132481135915612141617423596124735691243分组双调对接比较取MIN双调对接比较取MIN分组Batcher奇偶排序分组Batcher奇偶排序202