并行算法的设计与分析(4).ppt

1、并行算法的设计与分析,第4章 排序与选择网络,4.1 Batcher归并和排序网络,4.1.1 比较操作和0,1原理 1. Batcher比较器 比较和条件交换操作: CCI 比较器网络：用Batcher比较器连成的，完成某一功能的网络 假定：每次每个元素只能与另一个元素比较 比较器网络的参数：比较器数目、延迟级数 2. 0, 1原理(定理4.1): 如果一个n输入的网络能排序所有2n种0,1序列，那么它也能排序n个数的任意序列。,4.1.2 奇偶递归归并网络,1. 递归网络构造 有序序列A: a1,a2,an B: b1,b2,bm 奇偶递归归并（算法）思想： (1) A, B中奇数编号元素

2、进入奇归并器, 对这些奇数编号元素递归地进行 奇偶归并,直到输入元素数为2止; (2) A, B中偶数编号元素进入偶归并器， 对这些偶数编号元素递归地进行 奇偶归并,直到输入元素数为2止; (3) 将步(1)奇归并器的输出与步(2)偶 归并器的输出进行交叉并行比较. 注: (m,n)规模划一分为二：,4.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级交叉并行比较,4.1.2 奇偶递归归并网络,3. 复杂性分析 比较器个数 当m=n=2

3、t时，展开，推得：,4.1.2 奇偶递归归并网络,3. 复杂性分析 延迟级数：穿过网络任一路线上的最多层次数 一般地有 当m=n=2t时，展开，可以解得：,4.1.3 双调归并网络,1. 定义及定理 定义: 一个序列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 Batcher定理： 设序列a1,an,an+1

4、, a2n是一个双调序列, 记 bi=minai, ai+n = MIN=b1,bn, ci=maxai, ai+n = MAX=c1,cn, 则有： (1) bicj ，1i, jn； (2) MIN和MAX序列仍是双调的。,4.1.3 双调归并网络,2. 双调归并递归网络构造 (依据Batcher定理) 2n个输入的双调序列两两比较形成2个大小为n的MIN和MAX序列。 并行递归地归并MIN和MAX双调序列，直到输入序列为2个元素为止。,双调序列,4.1.3 双调归并网络,3. 示例: 双调序列(8,6,4,2,0,1,3,5)的(4,4)双调（递归）归并网络,两两比较,2个(2,2)双调

5、归并网络,MIN归并,MAX归并,4.1.3 双调归并网络,4. 复杂性分析 比较器数目 MIN比较器数 MAX比较器数 本级两两比较器数 当n=2t时 延迟级数,4.1.4 Batcher排序网络,1. 排序网络原理（算法）倍增技术应用 (1) 将n个输入数看成长度分别为1的n个有序序列：对n个输入数进行两两比较，以形成长度分别为21的n/21个有序序列。 (2) 利用奇偶归并网络或者双调归并网络对长度为21的有序序列进行两两归并，形成长度分别为22的n/22个有序序列。 (3) 依次类推，第i次排序时，利用奇偶归并网络或者双调归并网络对长度为2i-1的有序序列进行两两归并，形成长度分别为2

6、i的n/2i个有序序列。 (4) 最后，利用奇偶归并网络或者双调归并网络，归并长度分别为n/21的21个有序序列，以最终获得20=1个完整的长度为n的有序序列。,2. 奇偶排序网络（OESN） 对输入长度为n的数据序列，逐次使用奇偶归并网络进行并行归并。 示例： OESN (n=8),奇偶排序网络的复杂性 比较器数目CsOE(n): CsOE(n)= CsOE(n/2 |)+ CsOE(| n /2)+CMOE(n/2 |, | n /2 ), n=2 当n=2t 时，解上述递归方程得： 延迟级数DsOE(n): 当n=2t时，展开有： DsOE(n)= DsOE(2t)=t i=1 DMOE

7、(2i-1, 2i-1)=（logn+log2n）/2 Knuth推出，一般地DsOE(n):,3. 双调排序网络（BSN） 对输入长度为n的数据序列，逐次使用双调归并网络进行并行归并。 示例：BSN(n=8)，其中标有的比较器按降序输出。,双调排序网络的复杂性 比较器数目CsBIT(n): CsBIT(n)= CsBIT(n/2 |)+ CsBIT(| n/2 )+CMBIT(n ), n=2 当n=2t时，解上述递归方程得： 延迟级数DsBIT(n): 当n=2t时，展开有： DsBIT(n)= DsBIT(2t)=t i=1 DsBIT(2i)= t i=1 log2i =（logn+l

8、og2n）/2,4.2 (m, n)-选择网络,(m,n)选择问题：从n个数据中，选取前m个较小（大）元素。 4.2.1 分组选择网络 1.基于划分原理的(m,n)-选择递归过程 将n个输入数据划分成若干个 ( n/m)大小相等的子序列； 使用Batcher排序网络对各子 序列排序； 将有序子序列两两对接形成 双调序列，对这些双调序列 使用 Batcher定理进行两两比较交换形 成MAX,MIN序列，弃去MAX序 列；再使用Batcher排序（归并） 网络将MIN序列排成有序序列； 重复直至MIN序列恰好包 含所需的m个最小元素为止。,2. 分组选择网络示例（n=16, m=4）,B(4) 奇

9、偶排序,分组,分组Batcher奇偶排序,双调对接比较 取MIN,分组Batcher奇偶排序,双调对接比较 取MIN,3.分组选择网络的正确性定理 P.129 定理4.4 4. 复杂性分析 分组选择网络比较器数目 分组选择延迟级数,4.2.2 平衡分组选择网络,1. 平衡分组选择过程 将n个输入数据划分成g=n/m个长度为m的子序列； 使用Batcher奇偶排序网络对g个子序列排序； 将所有有序子序列形成双调序列，进行两两对接；使用 Batcher定理形成MAX,MIN序列，弃去MAX序列，调用Batcher双调排序网络成对地归并MIN序列得到有序序列； 重复步 ，直至恰好包含所需的m个 最小元素为止。 特点: (1) 用双调排序网络取代奇偶排序网络(第1次除外)。 (2) 减少了比较器的级数。,2. 平衡分组选择网络示例 P.130 (n=16, m=4),B