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