《并行算法的设计与分析》3

《《并行算法的设计与分析》3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ParallelAlgorithmsChapter3SortingandSelectiononComparisonNetwork2021/6/13Y.XuCopyrightUSTC主要内容3.1Batcher归并和排序3.1.1比较操作和[0,1]原理3.1.2奇偶归并网络3.1.3双调归并网络3.1.4Batcher排序网络3.2(m,n)-选择网络3.2.1分组选择网络3.2.2平衡分组选择网络2021/6/13Y.XuCopyrightUSTC3.1Batcher归并和排序3.1.1比较操作和[0,1]原理3.1.2奇偶归并网络3.1.3双调归并网络3.1.4Batcher排序

2、网络2021/6/13Y.XuCopyrightUSTC3.1.1比较操作和[0,1]原理1.Batcher比较器比较和条件交换操作:CCI比较器网络：用Batcher比较器连成的，完成某一功能的网络假定：每次每个元素只能与另一个元素比较比较器网络的参数：比较器数目、延迟级数2021/6/13Y.XuCopyrightUSTC3.1.1比较操作和[0,1]原理2.[0,1]原理(定理3.1):如果一个n输入的网络能排序所有2n种0,1序列，那么它也能排序n个数的任意序列。2021/6/13Y.XuCopyrightUSTC3.1.2奇偶归并网络1.网络构造有序序列A:a1,a2,…,

3、anB:b1,b2,…,bm归并思想：A,B中奇数号元素进入奇归并器；A,B中偶数号元素进入偶归并器；再将奇归并器与偶归并器的输出进行交叉比较注:(m,n)规模划分为：2021/6/13Y.XuCopyrightUSTC3.1.2奇偶归并网络2.例：m=n=4A=(2,4,6,8)B=(0,1,3,5)(4,4)奇偶归并2×(2,2)奇偶归并＋1级交叉比较(2,2)奇归并2468013520634185023614580236145801234568(2,2)偶归并1级交叉比较2021/6/13Y.XuCopyrightUSTC3.1.2奇偶归并网络3.复杂性分析比较器个数Knut

4、h==>当m=n=2t时，不难推得2021/6/13Y.XuCopyrightUSTC3.1.2奇偶归并网络3.复杂性分析延迟级数：穿过网络任一路线上的最多比较器数目一般地有当m=n=2t时，不难推得2021/6/13Y.XuCopyrightUSTC3.1.3双调归并网络1.定义及定理定义3.5:一个序列a1,a2,…,an是双调序列(BitonicSequence)，如果：(1)存在一个ak(1≤k≤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

5、,4,5,6,7,8)都是双调序列。ak定理3.3(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/6/13Y.XuCopyrightUSTC3.1.3双调归并网络2.网络构造(依据Batcher定理)2n个输入的双调序列两两比较形成2个大小为n的MIN和MAX序列MIN和MAX序列是双调的，可以递归重复进行下去MINMINMINMINMAXMA

6、XMAXMAXMIN双调序列MAX双调序列2021/6/13Y.XuCopyrightUSTC3.1.3双调归并网络3.例:双调序列(8,6,4,2,0,1,3,5)的(4,4)双调归并网络2个(2,2)双调归并网络864201358061432508163425MIN归并MAX归并01234568两两比较2021/6/13Y.XuCopyrightUSTC3.1.3双调归并网络4.复杂性分析比较器数目MIN比较器数MAX比较器数本级两两比较器数当n=2t时延迟级数注：如何推导？2021/6/13Y.XuCopyrightUSTC3.1.3双调归并网络4.复杂性分析延迟级数注：如何推

7、导？2021/6/13Y.XuCopyrightUSTC3.1.4Batcher排序网络1.排序网络原理(1)对输入数进行两两比较，形成长度为2的有序序列组；(2)对长度为2的有序序列组进行两两归并，形成长度为4的有序序列组；(3)重复上述步骤，直至形成两个长度为n/2的有序序列；(4)最后对长度为n/2的有序序列归并为一个完整的有序序列。注：记n元输入的Batcher排序网络为B(n)记(m,n)元输入的Batcher归并网络为B(m,n)2021/6/