MPI程序设计ch4(阅读)课件

ParallelAlgorithms

Chapter

4

SortingandSelecting

inSynchronous

2022/11/26Y.XuCopyrightUSTC

ParallelAlgorithms

Chapte主要内容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上的排序、归并和选择算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.1一维线性阵列上的并行排序算法4.1.1奇偶转置排序算法4.1.2归拆排序算法2022/11/26Y.XuCopyrightUSTC4.1一维线性阵列上的并行排序算法4.1.1奇偶转置排序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步就可完成排序(证明略)2022/11/26Y.XuCopyrightUSTC4.1.1奇偶转置排序算法1.算法描述2022/11/24.1.1奇偶转置排序算法3.示例:n=77654321674523164725134627153Step1(odd)Step2(even)Step3(odd)Step4(even)Step5(odd)Step6(even)Step7(odd)426173524163752143657Finalresult12345672022/11/26Y.XuCopyrightUSTC4.1.1奇偶转置排序算法3.示例:n=77654324.1.1奇偶转置排序算法3.算法分析算法步骤①和②可在常数时间完成，整个算法执行次,所以总的时间t(n)=O(n),p(n)=n,c(n)=O(n^2)2022/11/26Y.XuCopyrightUSTC4.1.1奇偶转置排序算法3.算法分析2022/11/24.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步相同的操作;

交替重复上述两步,经次迭代后算法结束；2022/11/26Y.XuCopyrightUSTC4.1.2归拆排序算法1.算法描述2022/11/26Y.4.1.2归拆排序算法2.示例

2022/11/26Y.XuCopyrightUSTC4.1.2归拆排序算法2.示例2022/11/26Y4.1.2归拆排序算法3.算法分析

预处理:时间为;

第①和②步:时间为O(n/p);细节如下：

传送Si+1到Pi的时间为O(n/p),串行归并所需时间为2n/p,传送Si+1返回到Pi+1的时间为O(n/p);

整个算法经次迭代,所以总时间为

成本为当p≤logn时,算法是成本最优的2022/11/26Y.XuCopyrightUSTC4.1.2归拆排序算法3.算法分析2022/11/26Y.主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.2二维Mesh上的并行排序算法4.2.1处理器的编号方式4.2.2ShearSort排序算法4.2.3Thompson&Kung双调排序算法2022/11/26Y.XuCopyrightUSTC4.2二维Mesh上的并行排序算法4.2.1处理器的编4.2.1处理器的编号方式1.处理器间的基本操作2.编号方式

2022/11/26Y.XuCopyrightUSTC4.2.1处理器的编号方式1.处理器间的基本操作2022/4.2.2ShearSort排序算法1.算法描述:对于n×n阵列2.计算示例

2022/11/26Y.XuCopyrightUSTC4.2.2ShearSort排序算法1.算法描述:对4.2.2Thompson&Kung双调排序算法1.行主编号的双调排序算法

2022/11/26Y.XuCopyrightUSTC4.2.2Thompson&Kung双调排序算法1.行主4.2.2Thompson&Kung双调排序算法2.计算示例

1843157112089216521251019(a)4183151172082951625211910

(b)4720151118382919162521510

(c)4720151118832919162125105

(d)3411157818202521109191652

(e)23784591011151920161821252022/11/26Y.XuCopyrightUSTC4.2.2Thompson&Kung双调排序算法2.计算主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.3

Stone双调排序算法(书中4.1)Stone双调排序算法：Batcher双调排序网络在SIMD-SE上的实现。4.3.1均匀洗牌函数性质4.3.2Stone的观察及其计算模型4.3.3Stone双调并行排序算法2022/11/26Y.XuCopyrightUSTC4.3Stone双调排序算法(书中4.1)Stone4.3.1均匀洗牌函数性质1.均匀洗牌函数设有p=2m个处理器，二进制编号为pm-1…p1p0SH(pm-1…p1p0)=(pm-2…p0pm-1)2.性质

(1)连续洗牌m次后，数据项回到原来的处理器；

(2)相邻处理器中数据的二进制地址变化情况：初始时，仅在第0位不同；k次洗牌后，仅在m-k位不同

(3)主位变化：b0->bm-1->bm-2->,…,->b02022/11/26Y.XuCopyrightUSTC4.3.1均匀洗牌函数性质1.均匀洗牌函数2022/114.3.2Stone的观察及其计算模型1.Batcher比较器种类：(1)标有“0”为升序比较器；(2)标有“1”为降序比较器；(3)标有“-1”为恒序比较器。2.主位定义:双调排序网络中,每列两两比较的数据编号只有一位不同,该位称为列的主位。3.Stone的观察:级1序列:b0;级2序列:b1,b0;…;级m序列:bm-1,bm-2,…,b00000010100111001011101110000100010111001101011110000010100111001011101110001000011010101100111110000100010111001101011110000010100111001011101112022/11/26Y.XuCopyrightUSTC4.3.2Stone的观察及其计算模型1.Batcher4.3.2Stone的观察及其计算模型4.Stone并行计算模型n个存储单元n/2个比较器工作状态数组MASK[i]洗牌连接输出反馈输入第k级处理的实现：①进行m-k+1次洗牌，调整到正确的起始主位；②k次比较交换和k-1次洗牌2022/11/26Y.XuCopyrightUSTC4.3.2Stone的观察及其计算模型4.Stone并行4.3.3Stone双调并行排序算法

1.算法思想设n=2m，算法分为m级，对于第k级的描述为：

①连续均匀洗牌m-k+1次，将主位从b0->bm-1->,…,->bk-1，移动过程中不比较；②进行比较交换一次(从bk-1->,…,->b0位起，共进行k次)，如果到了b0位就结束；否则转③；③均匀洗牌一次，使主位下标降1，转②；2.

形式描述

P110算法4.1(略)2022/11/26Y.XuCopyrightUSTC4.3.3Stone双调并行排序算法

1.算法思想2024.3.3Stone双调并行排序算法3.示例

存储均匀洗牌比较2022/11/26Y.XuCopyrightUSTC4.3.3Stone双调并行排序算法3.示例4.3.3Stone双调并行排序算法

4.算法分析共进行m级循环(k=1~m)；第k级循环:均匀洗牌m次，比较交换k次共进行了O(m2)次操作

t(n)=O(log2n),p(n)=n/2,c(n)=O(nlog2n)2022/11/26Y.XuCopyrightUSTC4.3.3Stone双调并行排序算法

4.算法分析202主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.4

Akl并行k-选择算法4.4.1问题描述4.4.2Akl算法思想4.4.3示例4.4.4算法实现的时间复杂度

2022/11/26Y.XuCopyrightUSTC4.4Akl并行k-选择算法4.4.1问题描述2022/4.4.1问题描述2022/11/26Y.XuCopyrightUSTC4.4.1问题描述2022/11/26Y.XuCopyr4.4.2

Akl算法思想2022/11/26Y.XuCopyrightUSTC4.4.2Akl算法思想2022/11/26Y.XuCo4.4.3示例处理器数P1P2P3P4P5中值的中值6th在S1中，对S1再划分：6th在S2中2022/11/26Y.XuCopyrightUSTC4.4.3示例处理器数P1P2P3P4P5中值的中值6th4.4.4算法实现的时间复杂度2022/11/26Y.XuCopyrightUSTC4.4.4算法实现的时间复杂度2022/11/26Y.Xu主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.5

Valiant并行归并算法2022/11/26Y.XuCopyrightUSTC4.5Valiant并行归并算法2022/11/26Y.X4.5.1问题描述2022/11/26Y.XuCopyrightUSTC4.5.1问题描述2022/11/26Y.XuCopyr4.5.2时Valiant归并2022/11/26Y.XuCopyrightUSTC4.5.2时Valiant归并24.5.2时Valiant归并2022/11/26Y.XuCopyrightUSTC4.5.2时Valiant归并24.5.3时Valiant归并2022/11/26Y.XuCopyrightUSTC4.5.3时Valiant归并主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.7

Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC4.7Preparata并行枚举排序算法2022/11/24.7.1枚举排序的一般思想2022/11/26Y.XuCopyrightUSTC4.7.1枚举排序的一般思想2022/11/26Y.Xu4.7.1枚举排序的一般思想2022/11/26Y.XuCopyrightUSTC4.7.1枚举排序的一般思想2022/11/26Y.Xu4.7.2Preparata并行枚举排序2022/11/26Y.XuCopyrightUSTC4.7.2Preparata并行枚举排序2022/11/24.7.3算法描述2022/11/26Y.XuCopyrightUSTC4.7.3算法描述2022/11/26Y.XuCopy4.7.4算法分析2022/11/26Y.XuCopyrightUSTC4.7.4算法分析2022/11/26Y.XuCopy4.7.4算法分析2022/11/26Y.XuCopyrightUSTC4.7.4算法分析2022/11/26Y.XuCopy

EndofChapter4

2022/11/26Y.XuCopyrightUSTC

EndofChapter4

2022/11/26Y

ParallelAlgorithms

Chapter

4

SortingandSelecting

inSynchronous

2022/11/26Y.XuCopyrightUSTC

ParallelAlgorithms

Chapte主要内容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上的排序、归并和选择算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.1一维线性阵列上的并行排序算法4.1.1奇偶转置排序算法4.1.2归拆排序算法2022/11/26Y.XuCopyrightUSTC4.1一维线性阵列上的并行排序算法4.1.1奇偶转置排序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步就可完成排序(证明略)2022/11/26Y.XuCopyrightUSTC4.1.1奇偶转置排序算法1.算法描述2022/11/24.1.1奇偶转置排序算法3.示例:n=77654321674523164725134627153Step1(odd)Step2(even)Step3(odd)Step4(even)Step5(odd)Step6(even)Step7(odd)426173524163752143657Finalresult12345672022/11/26Y.XuCopyrightUSTC4.1.1奇偶转置排序算法3.示例:n=77654324.1.1奇偶转置排序算法3.算法分析算法步骤①和②可在常数时间完成，整个算法执行次,所以总的时间t(n)=O(n),p(n)=n,c(n)=O(n^2)2022/11/26Y.XuCopyrightUSTC4.1.1奇偶转置排序算法3.算法分析2022/11/24.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步相同的操作;

交替重复上述两步,经次迭代后算法结束；2022/11/26Y.XuCopyrightUSTC4.1.2归拆排序算法1.算法描述2022/11/26Y.4.1.2归拆排序算法2.示例

2022/11/26Y.XuCopyrightUSTC4.1.2归拆排序算法2.示例2022/11/26Y4.1.2归拆排序算法3.算法分析

预处理:时间为;

第①和②步:时间为O(n/p);细节如下：

传送Si+1到Pi的时间为O(n/p),串行归并所需时间为2n/p,传送Si+1返回到Pi+1的时间为O(n/p);

整个算法经次迭代,所以总时间为

成本为当p≤logn时,算法是成本最优的2022/11/26Y.XuCopyrightUSTC4.1.2归拆排序算法3.算法分析2022/11/26Y.主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.2二维Mesh上的并行排序算法4.2.1处理器的编号方式4.2.2ShearSort排序算法4.2.3Thompson&Kung双调排序算法2022/11/26Y.XuCopyrightUSTC4.2二维Mesh上的并行排序算法4.2.1处理器的编4.2.1处理器的编号方式1.处理器间的基本操作2.编号方式

2022/11/26Y.XuCopyrightUSTC4.2.1处理器的编号方式1.处理器间的基本操作2022/4.2.2ShearSort排序算法1.算法描述:对于n×n阵列2.计算示例

2022/11/26Y.XuCopyrightUSTC4.2.2ShearSort排序算法1.算法描述:对4.2.2Thompson&Kung双调排序算法1.行主编号的双调排序算法

2022/11/26Y.XuCopyrightUSTC4.2.2Thompson&Kung双调排序算法1.行主4.2.2Thompson&Kung双调排序算法2.计算示例

1843157112089216521251019(a)4183151172082951625211910

(b)4720151118382919162521510

(c)4720151118832919162125105

(d)3411157818202521109191652

(e)23784591011151920161821252022/11/26Y.XuCopyrightUSTC4.2.2Thompson&Kung双调排序算法2.计算主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.3

Stone双调排序算法(书中4.1)Stone双调排序算法：Batcher双调排序网络在SIMD-SE上的实现。4.3.1均匀洗牌函数性质4.3.2Stone的观察及其计算模型4.3.3Stone双调并行排序算法2022/11/26Y.XuCopyrightUSTC4.3Stone双调排序算法(书中4.1)Stone4.3.1均匀洗牌函数性质1.均匀洗牌函数设有p=2m个处理器，二进制编号为pm-1…p1p0SH(pm-1…p1p0)=(pm-2…p0pm-1)2.性质

(1)连续洗牌m次后，数据项回到原来的处理器；

(2)相邻处理器中数据的二进制地址变化情况：初始时，仅在第0位不同；k次洗牌后，仅在m-k位不同

(3)主位变化：b0->bm-1->bm-2->,…,->b02022/11/26Y.XuCopyrightUSTC4.3.1均匀洗牌函数性质1.均匀洗牌函数2022/114.3.2Stone的观察及其计算模型1.Batcher比较器种类：(1)标有“0”为升序比较器；(2)标有“1”为降序比较器；(3)标有“-1”为恒序比较器。2.主位定义:双调排序网络中,每列两两比较的数据编号只有一位不同,该位称为列的主位。3.Stone的观察:级1序列:b0;级2序列:b1,b0;…;级m序列:bm-1,bm-2,…,b00000010100111001011101110000100010111001101011110000010100111001011101110001000011010101100111110000100010111001101011110000010100111001011101112022/11/26Y.XuCopyrightUSTC4.3.2Stone的观察及其计算模型1.Batcher4.3.2Stone的观察及其计算模型4.Stone并行计算模型n个存储单元n/2个比较器工作状态数组MASK[i]洗牌连接输出反馈输入第k级处理的实现：①进行m-k+1次洗牌，调整到正确的起始主位；②k次比较交换和k-1次洗牌2022/11/26Y.XuCopyrightUSTC4.3.2Stone的观察及其计算模型4.Stone并行4.3.3Stone双调并行排序算法

1.算法思想设n=2m，算法分为m级，对于第k级的描述为：

①连续均匀洗牌m-k+1次，将主位从b0->bm-1->,…,->bk-1，移动过程中不比较；②进行比较交换一次(从bk-1->,…,->b0位起，共进行k次)，如果到了b0位就结束；否则转③；③均匀洗牌一次，使主位下标降1，转②；2.

形式描述

P110算法4.1(略)2022/11/26Y.XuCopyrightUSTC4.3.3Stone双调并行排序算法

1.算法思想2024.3.3Stone双调并行排序算法3.示例

存储均匀洗牌比较2022/11/26Y.XuCopyrightUSTC4.3.3Stone双调并行排序算法3.示例4.3.3Stone双调并行排序算法

4.算法分析共进行m级循环(k=1~m)；第k级循环:均匀洗牌m次，比较交换k次共进行了O(m2)次操作

t(n)=O(log2n),p(n)=n/2,c(n)=O(nlog2n)2022/11/26Y.XuCopyrightUSTC4.3.3Stone双调并行排序算法

4.算法分析202主要内容4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法4.3Stone双调排序算法(书中4.1)4.4Akl并行k-选择算法4.5Valiant并行归并算法4.7Preparata并行枚举排序算法2022/11/26Y.XuCopyrightUSTC主要内容4.1一维线性阵列上的并行排序算法2022/11/4.4

Akl并行k-选择算法4.4.1问题描述4.4.2Akl算法思想4.4.3示例4.4.4算法实现的时间复杂度

2022/11/26Y.XuCopyrightUSTC4.4Akl并行k-选择算法4.4.1问题描述2022/4.4.1问题描述2022/11/26Y.XuCopyrightUSTC4.4.1问题描述2022/11/26Y.XuCopyr4.4.2

Akl算法思想2022/11/26Y.XuCopyrightUSTC4.4.2Akl算法思想2022/11/26Y.XuCo4.4.3示例处理器数P1P2P3P4P5中值的中值6th在S1中，对S1再划分：6th在S2中2022/11/26Y.XuCopyrightUSTC4.4.3示例处理器数P1P2P3P4P5中值的中值6th4.4.4算法实现的时间复杂度2022/11/26Y.XuCopyrightUSTC4.4.4算法实现的时间复杂度2022/11/26Y.Xu主要内容4.1一维线性