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一維線性