《并行算法的设计与分析》.ppt
Y.Xu Copyright USTC,2023/5/30,Parallel Algorithms Chapter 3 Sorting and Selection on Comparison Network,2023/5/30,Y.Xu Copyright USTC,主要内容,3.1 Batcher归并和排序3.1.1 比较操作和0,1原理3.1.2 奇偶归并网络3.1.3 双调归并网络3.1.4 Batcher排序网络3.2(m,n)-选择网络 3.2.1 分组选择网络3.2.2 平衡分组选择网络,2023/5/30,Y.Xu Copyright USTC,3.1 Batcher归并和排序,3.1.1 比较操作和0,1原理3.1.2 奇偶归并网络3.1.3 双调归并网络3.1.4 Batcher排序网络,2023/5/30,Y.Xu Copyright USTC,3.1.1 比较操作和0,1原理,1.Batcher比较器比较和条件交换操作:CCI比较器网络：用Batcher比较器连成的，完成某一功能的网络假定：每次每个元素只能与另一个元素比较比较器网络的参数：比较器数目、延迟级数,2023/5/30,Y.Xu Copyright USTC,3.1.1 比较操作和0,1原理,2.0,1原理(定理3.1):如果一个n输入的网络能排序所有2n种0,1序列，那么它也能排序n个数的任意序列。,2023/5/30,Y.Xu Copyright USTC,3.1.2 奇偶归并网络,1.网络构造有序序列A:a1,a2,an B:b1,b2,bm归并思想：A,B中奇数号元素进入奇归并器；A,B中偶数号元素进入偶归并器；再将奇归并器与偶归并器的输出进行交叉比较注:(m,n)规模划分为：,2023/5/30,Y.Xu Copyright USTC,3.1.2 奇偶归并网络,2.例：m=n=4 A=(2,4,6,8)B=(0,1,3,5)(4,4)奇偶归并2(2,2)奇偶归并1级交叉比较,(2,2)奇归并,(2,2)偶归并,1级交叉比较,2023/5/30,Y.Xu Copyright USTC,3.1.2 奇偶归并网络,3.复杂性分析比较器个数 Knuth=当m=n=2t时，不难推得,2023/5/30,Y.Xu Copyright USTC,3.1.2 奇偶归并网络,3.复杂性分析延迟级数：穿过网络任一路线上的最多比较器数目 一般地有当m=n=2t时，不难推得,2023/5/30,Y.Xu Copyright USTC,3.1.3 双调归并网络,1.定义及定理定义3.5:一个序列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)和(1,2,3,4,5,6,7,8)都是双调序列。ak,定理3.3(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序列仍是双调的,2023/5/30,Y.Xu Copyright USTC,3.1.3 双调归并网络,2.网络构造(依据Batcher定理)2n个输入的双调序列两两比较形成2个大小为n的MIN和MAX序列MIN和MAX序列是双调的，可以递归重复进行下去,MIN双调序列,MAX双调序列,2023/5/30,Y.Xu Copyright USTC,3.1.3 双调归并网络,3.例:双调序列(8,6,4,2,0,1,3,5)的(4,4)双调归并网络,2个(2,2)双调归并网络,MIN归并,MAX归并,两两比较,2023/5/30,Y.Xu Copyright USTC,3.1.3 双调归并网络,4.复杂性分析比较器数目 MIN比较器数 MAX比较器数 本级两两比较器数 当n=2t时 延迟级数 注：如何推导？,2023/5/30,Y.Xu Copyright USTC,3.1.3 双调归并网络,4.复杂性分析延迟级数 注：如何推导？,2023/5/30,Y.Xu Copyright USTC,3.1.4 Batcher排序网络,1.排序网络原理(1)对输入数进行两两比较，形成长度为2的有序序列组；(2)对长度为2的有序序列组进行两两归并，形成长度为4的有序序列组；(3)重复上述步骤，直至形成两个长度为n/2的有序序列；(4)最后对长度为n/2的有序序列归并为一个完整的有序序列。注：记n元输入的Batcher排序网络为B(n)记(m,n)元输入的Batcher归并网络为B(m,n),2023/5/30,Y.Xu Copyright USTC,3.1.4 Batcher排序网络,2.奇偶排序网络基于奇偶归并网络示例：B(8),2023/5/30,Y.Xu Copyright USTC,3.1.4 Batcher排序网络,3.双调排序网络基于双调归并网络示例：B(8),2023/5/30,Y.Xu Copyright USTC,3.1.4 Batcher排序网络,4.排序网络复杂性奇偶排序网络比较器数目延迟级数双调排序网络比较器数目延迟级数,2023/5/30,Y.Xu Copyright USTC,主要内容,3.1 Batcher归并和排序3.1.1 比较操作和0,1原理3.1.2 奇偶归并网络3.1.3 双调归并网络3.1.4 Batcher排序网络3.2(m,n)-选择网络 3.2.1 分组选择网络3.2.2 平衡分组选择网络,2023/5/30,Y.Xu Copyright USTC,3.2.1 分组选择网络,1.基于划分原理的(m,n)-选择过程 将n个输入数据划分成若干个大小相等的子序列(m)；使用Batcher排序网络对各子序列排序；将有序子序列形成双调序列，进行 两两对接；使用Batcher定理形成MAX,MIN序 列，弃去MAX序列；再使用Batcher排序网络将MIN序列 排成有序序列；重复直至MIN序列恰好包含所需 的m个最小元素为止。,2023/5/30,Y.Xu Copyright USTC,3.2.1 分组选择网络,2.例：,B(4)奇偶排序,分组,双调对接比较取MIN,双调对接比较取MIN,分组Batcher奇偶排序,分组Batcher奇偶排序,2023/5/30,Y.Xu Copyright USTC,3.2.1 分组选择网络,3.正确性定理 P89定理3.44.复杂性分析比较器数目 延迟级数,2023/5/30,Y.Xu Copyright USTC,3.2.2 平衡分组选择网络,1.平衡分组选择过程 将n个输入数据划分成若干个大小相等的子序列；使用Batcher排序网络对各子序列排序；将有序子序列形成双调序列，进行两两对接；使用Batcher定理形成MAX,MIN序列，弃去MAX序列；对MIN序列进行双调归并形成有序序列；将有序子序列形成双调序列，进行两两对接；重复，直至恰好包含所需的m个最小元素为止。注:(1)用双调排序网络取代奇偶排序网络(第1次除外)(2)减少了比较器的级数,2023/5/30,Y.Xu Copyright USTC,3.2.2 平衡分组选择网络,2.例：,B(4)奇偶排序,分组,分组Batcher奇偶排序,双调对接比较取MIN,分组Batcher双调排序,双调对接比较取MIN,B(4)双调排序,2023/5/30,Y.Xu Copyright USTC,3.2.2 平衡分组选择网络,4.复杂性分析比较器数目 延迟级数 注：平衡分组选择网络比分组选择网络快了O(logm),Y.Xu Copyright USTC,2023/5/30,End of Chapter 3,
