《并行算法的设计与分析》4

《《并行算法的设计与分析》4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ParallelAlgorithmsChapter4SortingandSelectinginSynchronous2021/6/14Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法本章中:4.1~4.3介绍的是SIMD-IN上的排序、归并和选择算法4.4~4.8介绍的是SIMD-SM上的排序、归并和选择算法2021/6/14Y.

2、XuCopyrightUSTC4.1一维线性阵列上的并行排序算法4.1.1奇偶转置排序算法4.1.2归拆排序算法2021/6/14Y.XuCopyrightUSTC4.1.1奇偶转置排序算法1.算法描述假定:待排序列X[1..n],处理器数p=n,Pi(i=1~n)存有数x[i]算法步骤：①所有奇数编号的处理器Pi被激活,接收来自Pi+1中的x[i+1]之副本,如果x[i]>x[i+1],则Pi和Pi+1彼此交换数据;②所有偶数编号的处理器Pi被激活,接收来自Pi+1中的x[i+1]之副本,如果x[i]>x[i+1],则Pi和Pi

3、+1彼此交换数据;交替重复上述两步,经次迭代后算法结束；2.相关定理1)正确性定理(略)2)奇偶排序算法至多经过n步就可完成排序(证明略)2021/6/14Y.XuCopyrightUSTC4.1.1奇偶转置排序算法3.示例:n=77654321674523164725134627153Step1(odd)Step2(even)Step3(odd)Step4(even)Step5(odd)Step6(even)Step7(odd)426173524163752143657Finalresult12345672021/6/14Y.X

4、uCopyrightUSTC4.1.1奇偶转置排序算法3.算法分析算法步骤①和②可在常数时间完成，整个算法执行次,所以总的时间t(n)=O(n),p(n)=n,c(n)=O(n^2)2021/6/14Y.XuCopyrightUSTC4.1.2归拆排序算法1.算法描述假定:待排序列X[1..n],处理器数p

5、入Pi+1;②所有偶数编号的处理器作与第1步相同的操作;交替重复上述两步,经次迭代后算法结束；2021/6/14Y.XuCopyrightUSTC4.1.2归拆排序算法2.示例2021/6/14Y.XuCopyrightUSTC4.1.2归拆排序算法3.算法分析预处理:时间为;第①和②步:时间为O(n/p);细节如下：传送Si+1到Pi的时间为O(n/p),串行归并所需时间为2n/p,传送Si+1返回到Pi+1的时间为O(n/p);整个算法经次迭代,所以总时间为成本为当p≤logn时,算法是成本最优的2021/6/14Y.XuCo

6、pyrightUSTC主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2021/6/14Y.XuCopyrightUSTC4.2二维Mesh上的并行排序算法4.2.1处理器的编号方式4.2.2ShearSort排序算法4.2.3Thompson&Kung双调排序算法2021/6/14Y.XuCopyrightUSTC4.2.1处理器的编号方式1.处理器间的基本操作

7、2.编号方式2021/6/14Y.XuCopyrightUSTC4.2.2ShearSort排序算法1.算法描述:对于n×n阵列2.计算示例2021/6/14Y.XuCopyrightUSTC4.2.2Thompson&Kung双调排序算法1.行主编号的双调排序算法2021/6/14Y.XuCopyrightUSTC4.2.2Thompson&Kung双调排序算法2.计算示例1843157112089216521251019(a)4183151172082951625211910(b)47201511183829191625215

8、10(c)4720151118832919162125105(d)3411157818202521109191652(e)23784591011151920161821252021/6/14Y.XuCopyrightUSTC主要内容4.1一维线性阵