并行算法设计与分析3.ppt

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 平衡分组选择网络 3.1 Batcher归并和排序 3.1.1 比较操作和[0, 1]原理 3.1.2 奇偶归并网络 3.1.3 双调归并网络 3.1.4 Batcher排序网络 3.1.1 比较操作和[0,1]原理 1. Batcher比较器 比较和条件交换操作: CCI 比较器网络：用Batcher比较器连成的，完成某一功能的网络 假定：每次每个元素只能与另一个元素比较 比较器网络的参数：比较器数目、延迟级数 3.1.1 比较操作和[0,1]原理 2. [0, 1]原理(定理3.1): 如果一个n输入的网络能排序所有2n种0,1序列， 那么它也能排序n个数的任意序列。 3.1.2 奇偶归并网络 1. 网络构造 有序序列A:a1,a2,…,an B: b1,b2,…,bm 归并思想： A, B中奇数号元素进入奇归并器； A, B中偶数号元素进入偶归并器； 再将奇归并器与偶归并器的输出进行交叉比较 注: (m,n)规模划分为： 3.1.2 奇偶归并网络 2. 例：m=n=4 A=(2,4,6,8) B=(0,1,3,5) (4, 4)奇偶归并?2×(2, 2)奇偶归并＋1级交叉比较 3.1.2 奇偶归并网络 3. 复杂性分析 比较器个数 Knuth == 当m=n=2t时，不难推得 3.1.2 奇偶归并网络 3. 复杂性分析 延迟级数：穿过网络任一路线上的最多比较器数目 一般地有 当m=n=2t时，不难推得 3.1.3 双调归并网络 1. 定义及定理 定义3.5: 一个序列a1,a2,…,an是双调序列(Bitonic Sequence)，如果： (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,4,5,6,7,8) 都是双调序列。 ak 3.1.3 双调归并网络 2. 网络构造(依据Batcher定理) 2n个输入的双调序列两两比较形成2个大小为n的MIN和MAX序列 MIN和MAX序列是双调的，可以递归重复进行下去 3.1.3 双调归并网络 3. 例:双调序列(8,6,4,2,0,1,3,5)的(4,4)双调归并网络 3.1.3 双调归并网络 4. 复杂性分析 比较器数目 MIN比较器数 MAX比较器数 本级两两比较器数 当n=2t时 延迟级数 注：如何推导？ 3.1.3 双调归并网络 4. 复杂性分析 延迟级数 注：如何推导？ 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) 3.1.4 Batcher排序网络 2. 奇偶排序网络 基于奇偶归并网络 示例： B(8) 3.1.4 Batcher排序网络 3. 双调排序网络 基于双调归并网络 示例：B(8) 3.1.4 Batcher排序网络 4. 排序网络复杂性 奇偶排序网络 比较器数目 延迟级数 双调排序网络 比较器数目 延迟级数 主要内容 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 平衡分组选择网络 3.2.1 分组选择网络 1. 基于划分原理的(m,n)-选择过程 ①将n个输入数据划分成若干个大小相等的子序列(≥m)； ②使用Batcher排序网络对各子序列排序； ③将有序子序列形成双调序列，进