1、Parallel Algorithms1/Ch4Y.Xu Copyright USTC2022-12-9Parallel Algorithms Chapter 4 Sorting and Selecting in Synchronous2022-12-9Y.Xu Copyright USTC主要内容主要内容n4.1 一维线性阵列上的并行排序算法一维线性阵列上的并行排序算法n4.2 二维二维Mesh上的并行排序算法上的并行排序算法n4.3 Stone双调排序算法双调排序算法(书中书中4.1)n4.4 Akl并行并行k-选择算法选择算法n4.5 Valiant并行归并算法并行归并算法n4.7 Pr
2、eparata并行枚举排序算法并行枚举排序算法本章中本章中:4.14.3介绍的是介绍的是SIMD-IN上的排序、归并和选择算法上的排序、归并和选择算法4.44.8介绍的是介绍的是SIMD-SM上的排序、归并和选择算法上的排序、归并和选择算法2022-12-9Y.Xu Copyright USTC4.1 一维线性阵列上的并行排序算法一维线性阵列上的并行排序算法n4.1.1 奇偶转置排序算法奇偶转置排序算法n4.1.2 归拆排序算法归拆排序算法2022-12-9Y.Xu Copyright USTC4.1.1 奇偶转置排序算法奇偶转置排序算法1.算法描述算法描述 假定假定:待排序列待排序列X1.n
3、,处理器数处理器数p=n,Pi(i=1n)存有数存有数xi 算法步骤：算法步骤：所有奇数编号的处理器所有奇数编号的处理器Pi被激活被激活,接收来自接收来自Pi+1中的中的xi+1之副本之副本,如果如果xixi+1,则则Pi和和Pi+1彼此交换数据彼此交换数据;所有偶数编号的处理器所有偶数编号的处理器Pi被激活被激活,接收来自接收来自Pi+1中的中的xi+1之副本之副本,如果如果xixi+1,则则Pi和和Pi+1彼此交换数据彼此交换数据;交替重复上述两步交替重复上述两步,经经 次迭代后算法结束；次迭代后算法结束；2.相关相关定理定理 1)正确性定理正确性定理(略略)2)奇偶排序算法至多经过奇偶排
4、序算法至多经过n步就可完成排序步就可完成排序(证明略证明略)2/n2022-12-9Y.Xu Copyright USTC4.1.1 奇偶转置排序算法奇偶转置排序算法3.示例示例:n=77654321674523164725134627153Step 1(odd)Step 2(even)Step 3(odd)Step 4(even)Step 5(odd)Step 6(even)Step 7(odd)426173524163752143657Final result12345672022-12-9Y.Xu Copyright USTC4.1.1 奇偶转置排序算法奇偶转置排序算法3.算法分析算法分
5、析 算法步骤算法步骤和和可在常数时间完成，可在常数时间完成，整个算法执行整个算法执行 次次,所以总的时间所以总的时间t(n)=O(n),p(n)=n,c(n)=O(n2)2/n2022-12-9Y.Xu Copyright USTC4.1.2 归拆排序算法归拆排序算法1.算法描述算法描述 假定假定:待排序列待排序列X1.n,处理器数处理器数pbm-1-bm-2-,-b02022-12-9Y.Xu Copyright USTC4.3.2 Stone的观察及其计算模型的观察及其计算模型1.Batcher比较器种类比较器种类：(1)标有标有“0”为升序比较器；为升序比较器；(2)标有标有“1”为降序
6、比较器；为降序比较器；(3)标有标有“-1”为恒序比较器。为恒序比较器。2.主位定义主位定义:双调排序网络中双调排序网络中,每列两两比较的数据编号只有一位不同每列两两比较的数据编号只有一位不同,该位称为列的主位。该位称为列的主位。3.Stone的观察的观察:级级1序列序列:b0;级级2序列序列:b1,b0;级级m序列序列:bm-1,bm-2,b0000001010011100101110111000010001011100110101111000001010011100101110111000100001101010110011111000010001011100110101111000001
7、0100111001011101112022-12-9Y.Xu Copyright USTC4.3.2 Stone的观察及其计算模型的观察及其计算模型4.Stone并行计算模型并行计算模型n个存储单元个存储单元n/2个比较器个比较器工作状态数组工作状态数组MASKi洗牌连接洗牌连接输出输出反馈输入反馈输入第第k级处理的实现：级处理的实现：进行进行m-k+1次洗牌，调整到次洗牌，调整到 正确的起始主位；正确的起始主位；k次比较交换和次比较交换和k-1次洗牌次洗牌2022-12-9Y.Xu Copyright USTC4.3.3 Stone双调并行排序算法双调并行排序算法1.算法思想算法思想 设设
8、n=2m，算法分为，算法分为m级，对于第级，对于第k级的描述为：级的描述为：连续均匀洗牌连续均匀洗牌m-k+1次，将主位从次，将主位从b0-bm-1-,-bk-1，移动过程中不比较；移动过程中不比较；进行比较交换一次进行比较交换一次(从从bk-1-,-b0位起，共进行位起，共进行k次次)，如果到了如果到了b0位就结束；否则转位就结束；否则转；均匀洗牌一次，使主位下标降均匀洗牌一次，使主位下标降1 1，转，转；2.形式描述形式描述 P110算法算法4.1(略略)2022-12-9Y.Xu Copyright USTC4.3.3 Stone双调并行排序算法双调并行排序算法3.示例示例 存储存储均匀
9、洗牌均匀洗牌比较比较2022-12-9Y.Xu Copyright USTC4.3.3 Stone双调并行排序算法双调并行排序算法4.算法分析算法分析 共进行共进行m级循环级循环(k=1m)；第第k级循环级循环:均匀洗牌均匀洗牌m次，比较交换次，比较交换k次次 共进行了共进行了O(m2)次操作次操作 t(n)=O(log2n),p(n)=n/2,c(n)=O(nlog2n)2022-12-9Y.Xu Copyright USTC主要内容主要内容n4.1 一维线性阵列上的并行排序算法一维线性阵列上的并行排序算法n4.2 二维二维Mesh上的并行排序算法上的并行排序算法n4.3 Stone双调排序
10、算法双调排序算法(书中书中4.1)n4.4 Akl并行并行k-选择算法选择算法n4.5 Valiant并行归并算法并行归并算法n4.7 Preparata并行枚举排序算法并行枚举排序算法2022-12-9Y.Xu Copyright USTC4.4 Akl并行并行k-选择算法选择算法n4.4.1 问题描述问题描述n4.4.2 Akl算法思想算法思想n4.4.3 示例示例n4.4.4 算法实现的时间复杂度算法实现的时间复杂度 2022-12-9Y.Xu Copyright USTC4.4.1 问题描述问题描述2022-12-9Y.Xu Copyright USTC4.4.2 Akl算法思想算法思
11、想2022-12-9Y.Xu Copyright USTC4.4.3 示例示例处理器数处理器数P1P2P3P4P5中值的中值中值的中值6th在在S1中，对中，对S1再划分：再划分：6th在在S2中中2022-12-9Y.Xu Copyright USTC4.4.4 算法实现的时间复杂度算法实现的时间复杂度2022-12-9Y.Xu Copyright USTC主要内容主要内容n4.1 一维线性阵列上的并行排序算法一维线性阵列上的并行排序算法n4.2 二维二维Mesh上的并行排序算法上的并行排序算法n4.3 Stone双调排序算法双调排序算法(书中书中4.1)n4.4 Akl并行并行k-选择算法
12、选择算法n4.5 Valiant并行归并算法并行归并算法n4.7 Preparata并行枚举排序算法并行枚举排序算法2022-12-9Y.Xu Copyright USTC4.5 Valiant并行归并算法并行归并算法2022-12-9Y.Xu Copyright USTC4.5.1 问题描述问题描述2022-12-9Y.Xu Copyright USTC4.5.2 时时Valiant归并归并pqk 2022-12-9Y.Xu Copyright USTC4.5.2 时时Valiant归并归并pqk 2022-12-9Y.Xu Copyright USTC4.5.3 时时Valiant归并归并
13、pqrk 2022-12-9Y.Xu Copyright USTC主要内容主要内容n4.1 一维线性阵列上的并行排序算法一维线性阵列上的并行排序算法n4.2 二维二维Mesh上的并行排序算法上的并行排序算法n4.3 Stone双调排序算法双调排序算法(书中书中4.1)n4.4 Akl并行并行k-选择算法选择算法n4.5 Valiant并行归并算法并行归并算法n4.7 Preparata并行枚举排序算法并行枚举排序算法2022-12-9Y.Xu Copyright USTC4.7 Preparata并行枚举排序算法并行枚举排序算法2022-12-9Y.Xu Copyright USTC4.7.1
14、 枚举排序的一般思想枚举排序的一般思想2022-12-9Y.Xu Copyright USTC4.7.1 枚举排序的一般思想枚举排序的一般思想2022-12-9Y.Xu Copyright USTC4.7.2 Preparata并行枚举排序并行枚举排序2022-12-9Y.Xu Copyright USTC4.7.3 算法描述算法描述2022-12-9Y.Xu Copyright USTC4.7.4 算法分析算法分析2022-12-9Y.Xu Copyright USTC4.7.4 算法分析算法分析Parallel Algorithms44/Ch4Y.Xu Copyright USTC2022-12-9End of Chapter 4
