并行算法的设计与(4)

1、并行算法的设计与分析第4章排序与选择网络4.1 Batcher归并和排序网络归并和排序网络4.1.1 比较操作和比较操作和0,10,1原理原理1. Batcher比较器比较器 比较和条件交换操作比较和条件交换操作: CCI 比较器网络：用比较器网络：用Batcher比较器连成的，完成某一功能的网络比较器连成的，完成某一功能的网络 假定：每次每个元素只能与另一个元素比较假定：每次每个元素只能与另一个元素比较 比较器网络的参数：比较器数目、延迟级数比较器网络的参数：比较器数目、延迟级数2. 0, 1原理原理(定理定理4.1): 如果一个如果一个n输入的网络能排序所有输入的网络能排序所有2n种种0,

2、1序列，那么它也能排序序列，那么它也能排序n个个数的任意序列。数的任意序列。4.1.2 奇偶递归归并网络奇偶递归归并网络1. 递归递归网络构造网络构造v有序序列有序序列A: a1,a2,an B: b1,b2,bmv奇偶递归归并（算法）思想：奇偶递归归并（算法）思想：(1) A, B中奇数编号元素进入奇归并器中奇数编号元素进入奇归并器, 对这些奇数编号元素递归地进行对这些奇数编号元素递归地进行 奇偶归并奇偶归并,直到输入元素数为直到输入元素数为2止止;(2) A, B中偶数编号元素进入偶归并器，中偶数编号元素进入偶归并器， 对这些偶数编号元素递归地进行对这些偶数编号元素递归地进行 奇偶归并奇偶

3、归并,直到输入元素数为直到输入元素数为2止止;(3) 将步将步(1)奇归并器的输出与步奇归并器的输出与步(2)偶偶 归并器的输出进行交叉并行比较归并器的输出进行交叉并行比较. 注注: (m,n)规模划一分为二：规模划一分为二： 偶奇2/,2/2/,2/nmnm4.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级交叉并行比较级交叉并行比较24680135206341850236145

4、802361458012345684.1.2 奇偶递归归并网络奇偶递归归并网络3. 复杂性分析复杂性分析v 比较器个数比较器个数 当m=n=2t时，展开，推得： 1),(),(1),(212222mnCCmnmnnmCnmnmMOEnmMOEMOE1log) 1(2) 1 , 1 ()2()2/,2/(2.) 1() 2()2/,2/(2) 1() 12/) 4/, 4/(2( 2) 1() 2/, 2/(2) 1() 2/, 2/(2) 2/, 2/(2),(1010102222121nnntnnnnCnnnCnnnnCnnnnCnnnCnnnCnnnCnnCtiitiMOEtiittMOE

5、tMOEMOEMOEMOEMOEMOE4.1.2 奇偶递归归并网络奇偶递归归并网络3. 复杂性分析复杂性分析v 延迟级数：延迟级数：穿过网络任一路线上的最多层次数穿过网络任一路线上的最多层次数 一般地有一般地有 当当m=n=2t时，展开，可以解得：时，展开，可以解得： 其他或100)2/,2/(),2/,2/(max110),(nmnmnmDnmDnmDMOEMOEMOE )2/,2/(1),(nmDnmDMOEMOE1log),(nnnDMOE4.1.3 双调归并网络双调归并网络1. 定义及定理定义及定理v 定义定义: 一个序列一个序列a1,a2,an是双调序列是双调序列(Bitonic S

6、equence)，如果：，如果： (1) 存在一个存在一个ak(1knkn), 使得使得a1akan成立；或者成立；或者 (2) 循环移位序列使之能够满足条件循环移位序列使之能够满足条件(1)。v 示例：示例： 序列序列(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) 都是双调序列。都是双调序列。 akv Batcher定理：定理： 设序列设序列a1,an,an+1, a2n是一个双调序列是一个双调序列, 记记 bi=minai, ai+n = MIN=b1,bn, ci=maxai, ai+n = MAX=c1,cn,

7、 则有：则有： (1) bicj ，1i, jn； (2) MIN和和MAX序列仍是双调的。序列仍是双调的。 4.1.3 双调归并网络双调归并网络2. 双调归并递归双调归并递归网络构造网络构造 (依据依据Batcher定理定理)v 2n个输入的双调序列两两比较形成个输入的双调序列两两比较形成2个大小为个大小为n的的MIN和和MAX序列。序列。v 并行递归地归并并行递归地归并MIN和和MAX双调序列，直到输入序列为双调序列，直到输入序列为2个元素为止。个元素为止。MINMINMINMINMAXMAXMAXMAX双调序列双调序列4.1.3 双调归并网络双调归并网络3. 示示例例: 双调序列双调序列

8、(8,6,4,2,0,1,3,5)的的(4,4)双调（递归）归并网络双调（递归）归并网络86420135806143250816342501234568两两比较两两比较2个个(2,2)双调归并网络双调归并网络MIN归并归并MAX归并归并4.1.3 双调归并网络双调归并网络4. 复杂性分析复杂性分析v 比较器数目比较器数目 MIN比较器数比较器数 MAX比较器数比较器数 本级两两比较器数本级两两比较器数 当当n=2t时时 v 延迟级数延迟级数nnDnDnDnnDnDnnDnMBITniMBITMBITMBITMBITMBITlog)2(1)2/(1(1)2/(11)2/(),2/(max110)

9、(loglog124.1.4 Batcher排序网络排序网络1. 排序网络原理（算法）排序网络原理（算法）倍增技术应用倍增技术应用 (1) 将将n个输入数看成长度分别为个输入数看成长度分别为1的的n个有序序列：对个有序序列：对n个输入个输入数进行两两比较，以形成长度分别为数进行两两比较，以形成长度分别为21的的n/21个有序序列个有序序列。 (2) 利用奇偶归并网络或者双调归并网络对长度为利用奇偶归并网络或者双调归并网络对长度为21的有序序的有序序列进行两两归并，形成长度分别为列进行两两归并，形成长度分别为22的的n/22个有序序列。个有序序列。 (3) 依次类推，第依次类推，第i次排序时，利

10、用奇偶归并网络或者双调归并次排序时，利用奇偶归并网络或者双调归并网络对长度为网络对长度为2i-1的有序序列进行两两归并，形成长度分别为的有序序列进行两两归并，形成长度分别为2i的的n/2i个有序序列。个有序序列。 (4) 最后，利用奇偶归并网络或者双调归并网络，归并长度分最后，利用奇偶归并网络或者双调归并网络，归并长度分别为别为n/21的的21个有序序列，以最终获得个有序序列，以最终获得20=1个完整的长度为个完整的长度为n的有序序列。的有序序列。 2. 奇偶排序网络（奇偶排序网络（OESN）v 对输入长度为对输入长度为n的数据序列，逐次使用奇偶归并网络进行并的数据序列，逐次使用奇偶归并网络进

11、行并行归并。行归并。v 示例：示例： OESN (n=8)38517246381527461358246712345678v奇偶排序网络的复杂性奇偶排序网络的复杂性 比较器数目比较器数目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(2i-1, 2i-1)=（logn+log2n）/2 Knuth推出，一般地推出，一般地

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

13、DsBIT(n): 当当n=2t时，展开有：时，展开有： DsBIT(n)= DsBIT(2t)=t i=1 DsBIT(2i)= t i=1 log2i =（logn+log2n）/24.2 (m, n)-选择网络选择网络v (m,n)选择问题：从选择问题：从n个数据中，选取前个数据中，选取前m个较小（大）元素。个较小（大）元素。4.2.1 分组选择网络分组选择网络 1.基于划分原理的基于划分原理的(m,n)-选择递归过程选择递归过程 将将n个输入数据划分成若干个个输入数据划分成若干个 ( n/m)大小相等的子序列；大小相等的子序列； 使用使用Batcher排序网络对各子排序网络对各子序列排

14、序；序列排序； 将有序子序列两两对接形成将有序子序列两两对接形成双调序列，对这些双调序列双调序列，对这些双调序列 使用使用Batcher定理进行两两比较交换形定理进行两两比较交换形成成MAX,MIN序列，弃去序列，弃去MAX序序列；再使用列；再使用Batcher排序（归并）排序（归并）网络将网络将MIN序列排成有序序列；序列排成有序序列； 重复重复直至直至MIN序列恰好包序列恰好包含所需的含所需的m个最小元素为止。个最小元素为止。2. 分组选择网络示例（分组选择网络示例（n=16, m=4）B(4)奇偶排序奇偶排序分组分组分组分组Batcher奇偶排序奇偶排序双调对接比较双调对接比较取取MIN

15、分组分组Batcher奇偶排序奇偶排序双调对接比较双调对接比较取取MIN1371102411851539612161417101324811359156121416174235961247356912433.分组选择网络的正确性定理分组选择网络的正确性定理 P.129 定理定理4.44. 复杂性分析复杂性分析v分组选择网络分组选择网络比较器数目比较器数目 v分组选择分组选择延迟级数延迟级数4.2.2 平衡分组选择网络平衡分组选择网络1. 平衡分组选择过程平衡分组选择过程 将将n个输入数据划分成个输入数据划分成g=n/m个长度为个长度为m的子序列；的子序列； 使用使用Batcher奇偶排序网络对

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