并行算法的设计与分析.pptx

Parallel Algorithms1/Ch3Y.Xu Copyright USTC2024/9/6 周五Parallel Algorithms Chapter 3 Sorting and Selection on Comparison NetworkParallel Algorithms2/Ch32024/9/6 周五Y.Xu Copyright USTC主要内容主要内容n3.1 Batcher归并和排序归并和排序3.1.1 比较操作和比较操作和0,1原理原理3.1.2 奇偶归并网络奇偶归并网络3.1.3 双调归并网络双调归并网络3.1.4 Batcher排序网络排序网络n3.2(m,n)-选择网络选择网络 3.2.1 分组选择网络分组选择网络3.2.2 平衡分组选择网络平衡分组选择网络Parallel Algorithms3/Ch32024/9/6 周五Y.Xu Copyright USTC3.1 Batcher归并和排序归并和排序n3.1.1 比较操作和比较操作和0,1原理原理n3.1.2 奇偶归并网络奇偶归并网络n3.1.3 双调归并网络双调归并网络n3.1.4 Batcher排序网络排序网络Parallel Algorithms4/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.1 比较操作和比较操作和0,10,1原理原理1.Batcher比较器比较器比较和条件交换操作比较和条件交换操作:CCI比较器网络：用比较器网络：用Batcher比较器连成的，完成某一功能的网络比较器连成的，完成某一功能的网络假定：每次每个元素只能与另一个元素比较假定：每次每个元素只能与另一个元素比较比较器网络的参数：比较器数目、延迟级数比较器网络的参数：比较器数目、延迟级数Parallel Algorithms5/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.1 比较操作和比较操作和0,10,1原理原理2.0,1原理原理(定理定理3.1):如果一个如果一个n输入的网络能排序所有输入的网络能排序所有2n种种0,1序列，序列，那么它也能排序那么它也能排序n个数的任意序列。个数的任意序列。Parallel Algorithms6/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.2 奇偶归并网络奇偶归并网络1.网络构造网络构造n有序序列有序序列A:a1,a2,an B:b1,b2,bmn归并思想：归并思想：A,B中奇数号元素进入奇中奇数号元素进入奇归并器；归并器；A,B中偶数号元素进入偶中偶数号元素进入偶归并器；归并器；再将奇归并器与偶归并器再将奇归并器与偶归并器的输出进行交叉比较的输出进行交叉比较注注:(m,n)规模划分为：规模划分为：Parallel Algorithms7/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.2 奇偶归并网络奇偶归并网络2.例：例：m=n=4 A=(2,4,6,8)B=(0,1,3,5)(4,4)奇偶归并奇偶归并2(2,2)奇偶归并奇偶归并1级交叉比较级交叉比较(2,2)奇归并奇归并2468013520634185023614580236145801234568(2,2)偶归并偶归并1级交叉比较级交叉比较Parallel Algorithms8/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.2 奇偶归并网络奇偶归并网络3.复杂性分析复杂性分析n比较器个数比较器个数 Knuth =当当m=n=2t时，不难推得时，不难推得 Parallel Algorithms9/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.2 奇偶归并网络奇偶归并网络3.复杂性分析复杂性分析n延迟级数：延迟级数：穿过网络任一路线上的最多比较器数目穿过网络任一路线上的最多比较器数目 一般地有一般地有当当m=n=2t时，不难推得时，不难推得 Parallel Algorithms10/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.3 双调归并网络双调归并网络1.定义及定理定义及定理n定义定义3.5:一个序列一个序列a1,a2,an是双调序列是双调序列(Bitonic Sequence)，如果：，如果：(1)存在一个存在一个ak(1knkn),使得使得a1akan成立；或者成立；或者 (2)序列能够循环移位满足条件序列能够循环移位满足条件(1)n示例：示例：序列序列(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)都是双调序列。都是双调序列。akn定理定理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序列仍是双调的序列仍是双调的 Parallel Algorithms11/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.3 双调归并网络双调归并网络2.网络构造网络构造(依据依据Batcher定理定理)n2n个输入的双调序列两两比较形成个输入的双调序列两两比较形成2个大小为个大小为n的的MIN和和MAX序列序列nMIN和和MAX序列是双调的，可以递归重复进行下去序列是双调的，可以递归重复进行下去MINMINMINMINMAXMAXMAXMAXMIN双双调调序序列列MAX双双调调序序列列Parallel Algorithms12/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.3 双调归并网络双调归并网络3.例例:双调序列双调序列(8,6,4,2,0,1,3,5)的的(4,4)双调归并网络双调归并网络2个个(2,2)双调归并网络双调归并网络864201358061432508163425MIN归并归并MAX归并归并01234568两两比较两两比较Parallel Algorithms13/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.3 双调归并网络双调归并网络4.复杂性分析复杂性分析n比较器数目比较器数目 MIN比较器数比较器数 MAX比较器数比较器数 本级两两比较器数本级两两比较器数 当当n=2t时时 n延迟级数延迟级数 注：如何推导？注：如何推导？Parallel Algorithms14/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.3 双调归并网络双调归并网络4.复杂性分析复杂性分析n延迟级数延迟级数 注：如何推导？注：如何推导？Parallel Algorithms15/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.4 BatcherBatcher排序网络排序网络1.排序网络原理排序网络原理 (1)对输入数进行两两比较，形成长度为对输入数进行两两比较，形成长度为2的有序序列组；的有序序列组；(2)对长度为对长度为2的有序序列组进行两两归并，形成长度为的有序序列组进行两两归并，形成长度为4的有序序列组；的有序序列组；(3)重复上述步骤，直至形成两个长度为重复上述步骤，直至形成两个长度为n/2的有序序列；的有序序列；(4)最后对长度为最后对长度为n/2的有序序列归并为一个完整的有序序列。的有序序列归并为一个完整的有序序列。注：记注：记n元输入的元输入的Batcher排序网络为排序网络为B(n)记记(m,n)元输入的元输入的Batcher归并网络为归并网络为B(m,n)Parallel Algorithms16/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.4 BatcherBatcher排序网络排序网络2.奇偶排序网络奇偶排序网络n基于奇偶归并网络基于奇偶归并网络n示例：示例：B(8)38517246381527461358246712345678Parallel Algorithms17/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.4 BatcherBatcher排序网络排序网络3.双调排序网络双调排序网络n基于双调归并网络基于双调归并网络n示例：示例：B(8)83157246385172461358764212345678Parallel Algorithms18/Ch32024/9/6 周五Y.Xu Copyright USTC3.1.4 BatcherBatcher排序网络排序网络4.排序网络复杂性排序网络复杂性n奇偶排序网络奇偶排序网络比较器数目比较器数目延迟级数延迟级数n双调排序网络双调排序网络比较器数目比较器数目延迟级数延迟级数Parallel Algorithms19/Ch32024/9/6 周五Y.Xu Copyright USTC主要内容主要内容n3.1 Batcher归并和排序归并和排序3.1.1 比较操作和比较操作和0,1原理原理3.1.2 奇偶归并网络奇偶归并网络3.1.3 双调归并网络双调归并网络3.1.4 Batcher排序网络排序网络n3.2(m,n)-选择网络选择网络 3.2.1 分组选择网络分组选择网络3.2.2 平衡分组选择网络平衡分组选择网络Parallel Algorithms20/Ch32024/9/6 周五Y.Xu Copyright USTC3.2.1 分组选择网络分组选择网络1.基于划分原理的基于划分原理的(m,n)-选择过程选择过程 将将n个输入数据划分成若干个大小相等的子序列个输入数据划分成若干个大小相等的子序列(m)；使用使用Batcher排序网络对各子序列排序；排序网络对各子序列排序；将有序子序列形成双调序列，进行将有序子序列形成双调序列，进行 两两对接；两两对接；使用使用Batcher定理形成定理形成MAX,MIN序序 列，弃去列，弃去MAX序列；序列；再使用再使用Batcher排序网络将排序网络将MIN序列序列 排成有序序列；排成有序序列；重复重复直至直至MIN序列恰好包含所需序列恰好包含所需 的的m个最小元素为止。个最小元素为止。Parallel Algorithms21/Ch32024/9/6 周五Y.Xu Copyright USTC3.2.1 分组选择网络分组选择网络2.例：例：B(4)奇偶排序奇偶排序137110241185153961216141710132481135915612141617423596124735691243分组分组双调对接比较双调对接比较取取MIN双调对接比较双调对接比较取取MIN分组分组Batcher奇偶排序奇偶排序分组分组Batcher奇偶排序奇偶排序Parallel Algorithms22/Ch32024/9/6 周五Y.Xu Copyright USTC3.2.1 分组选择网络分组选择网络3.正确性定理正确性定理 P89定理定理3.44.复杂性分析复杂性分析n比较器数目比较器数目 n延迟级数延迟级数Parallel Algorithms23/Ch32024/9/6 周五Y.Xu Copyright USTC3.2.2 平衡分组选择网络平衡分组选择网络1.平衡分组选择过程平衡分组选择过程 将将n个输入数据划分成若干个大小相等的子序列；个输入数据划分成若干个大小相等的子序列；使用使用Batcher排序网络对各子序列排序；排序网络对各子序列排序；将有序子序列形成双调序列，进行两两对接；将有序子序列形成双调序列，进行两两对接；使用使用Batcher定理形成定理形成MAX,MIN序列，弃去序列，弃去MAX序列；序列；对对MIN序列进行双调归并形成有序序列；序列进行双调归并形成有序序列；将有序子序列形成双调序列，进行两两对接；将有序子序列形成双调序列，进行两两对接；重复，直至恰好包含所需的重复，直至恰好包含所需的m个最小元素为止。个最小元素为止。注注:(1)用双调排序网络取代奇偶排序网络用双调排序网络取代奇偶排序网络(第第1次除外次除外)(2)减少了比较器的级数减少了比较器的级数Parallel Algorithms24/Ch32024/9/6 周五Y.Xu Copyright USTC3.2.2 平衡分组选择网络平衡分组选择网络2.例：例：B(4)奇偶排序奇偶排序137110241185153961216141710132481135915612141617423596124735691243分组分组分组分组Batcher奇偶排序奇偶排序双调对接比较双调对接比较取取MIN分组分组Batcher双调排序双调排序双调对接比较双调对接比较取取MINB(4)双调排序双调排序Parallel Algorithms25/Ch32024/9/6 周五Y.Xu Copyright USTC3.2.2 平衡分组选择网络平衡分组选择网络4.复杂性分析复杂性分析n比较器数目比较器数目 n延迟级数延迟级数 注：平衡分组选择网络比分组选择网络快了注：平衡分组选择网络比分组选择网络快了O(logm)Parallel Algorithms26/Ch3Y.Xu Copyright USTC2024/9/6 周五End of Chapter 3