MPI程序设计ch4.ppt

Y.Xu Copyright USTC 主要内容 4.1 一维线性阵列上的并行排序算法 4.2 二维Mesh上的并行排序算法 4.3 Stone双调排序算法 书中4.1 4.4 Akl并行k-选择算法 4.5 Valiant并行归并算法 4.7 Preparata并行枚举排序算法 本章中: 4.1~4.3介绍的是SIMD-IN上的排序、归并和选择算法 4.4~4.8介绍的是SIMD-SM上的排序、归并和选择算法 4.1 一维线性阵列上的并行排序算法 4.1.1 奇偶转置排序算法 4.1.2 归拆排序算法 4.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+1彼此交换数据; 交替重复上述两步,经 次迭代后算法结束； 2.相关定理 1 正确性定理 略 2 奇偶排序算法至多经过n步就可完成排序 证明略 4.1.1 奇偶转置排序算法 3.示例: n 7 4.1.1 奇偶转置排序算法 3.算法分析 算法步骤①和②可在常数时间完成， 整个算法执行 次, 所以总的时间t n O n , p n n, c n O n^2 4.1.2 归拆排序算法 1.算法描述 假定:待排序列X[1..n], 处理器数p n, Pi i 1~p 存有子序列 Si: X[ i-1 n/p+1..in/p] 算法步骤： 首先, 每个处理器使用串行算法将各自的子序列排序; ①所有奇数编号的处理器,将Si和Si+1中归并之,并将归并结果 的前一半保留在本地,将后一半送入Pi+1; ②所有偶数编号的处理器作与第1步相同的操作; 交替重复上述两步,经 次迭代后算法结束； 4.1.2 归拆排序算法 2.示例 4.1.2 归拆排序算法 3.算法分析 预处理: 时间为 ; 第①和②步:时间为O n/p ; 细节如下： 传送Si+1到Pi的时间为O n/p , 串行归并所需时间为2n/p, 传送Si+1返回到Pi+1的时间为O n/p ; 整个算法经 次迭代,所以总时间为 成本为 当p≤logn时, 算法是成本最优的 主要内容 4.1 一维线性阵列上的并行排序算法 4.2 二维Mesh上的并行排序算法 4.3 Stone双调排序算法 书中4.1 4.4 Akl并行k-选择算法 4.5 Valiant并行归并算法 4.7 Preparata并行枚举排序算法 4.2 二维Mesh上的并行排序算法 4.2.1 处理器的编号方式 4.2.2 ShearSort排序算法 4.2.3 ThompsonKung双调排序算法 4.2.1 处理器的编号方式 1.处理器间的基本操作 2.编号方式 4.2.2 ShearSort排序算法 1.算法描述: 对于n×n阵列 2.计算示例 4.2.2 ThompsonKung双调排序算法 1.行主编号的双调排序算法 4.2.2 ThompsonKung双调排序算法 主要内容 4.1 一维线性阵列上的并行排序算法 4.2 二维Mesh上的并行排序算法 4.3 Stone双调排序算法 书中4.1 4.4 Akl并行k-选择算法 4.5 Valiant并行归并算法 4.7 Preparata并行枚举排序算法 4.3 Stone双调排序算法 书中4.1 Stone双调排序算法：Batcher双调排序网络 在SIMD-SE上的实现。 4.3.1 均匀洗牌函数性质 4.3.2 Stone的观察及其计算模型 4.3.3 Stone双调并行排序算法 4.3.1 均匀洗牌函数性质 1. 均匀洗牌函数 设有p 2m个处理器， 二进制编号为pm-1…p1p0 SH pm-1…p1p0 pm-2…p0pm-1 2. 性质 1 连续洗牌m次后，数据项回 到原来的处理器； 2 相邻处理器中数据的二进制 地址变化情况：初始时，仅 在第0位不同；k次洗牌后， 仅在m-k位不同 3 主位变化： b0- bm-1- bm-2- ,…, - b0 4.3.2 Stone的观察及其计算模型 1. Batcher比较器种类： 1 标有“0”为升序比较器； 2 标有“1”为降序比较器； 3 标有“-1”为恒序比较器。 2. 主位定义: 双调排序网络中,每列两两比较的数据编号只有一位不同,该位称为列的主位。 3. S