碩士算法求和與掃描算法

1、1算法設計與分析李洪偉李洪偉 博士博士電子科技大學計算機科學與工程學院電子科技大學計算機科學與工程學院http:/ 求和與掃描算法基于不同計算模型的并行求和算法基于不同計算模型的并行求和算法基于不同計算模型的并行排序算法基于不同計算模型的并行排序算法基于功能劃分的并行排序算法基于功能劃分的并行排序算法其它并行排序算法其它并行排序算法比較器網絡上的并行排序算法比較器網絡上的并行排序算法32D Mesh Synchronized Parallel-Summationnn=s2 numbers arranged in a s s array，corresponding to the same s s

2、 array of n processors，number xij is stored in PijnStart from column s, adding the numbers of column s with the number of columns before s, obtaining s sub-sum in the first column.nStart from row s in column 1, adding numbers above row by row, obtaining the total sum and stored in P11.42D Mesh Synch

3、ronized Parallel-SummationAlgorithm SUM-2D-MESHfor i=s-1 downto 1 dofor all Pj,i (1=js) do in paralleltj,i = xj,i+1;xj,i = xj,i + tj,i ;for j = s-1 downto 1 doxj,1 = xj,1 + xj+1,1;Depth(Time): Q(n1/2), Work(Cost): n Q(n1/2) = Q(n3/2)5An Example 63D Cube Synchronized Parallel-SummationnAssume n=2m=s2

4、 numbers，m, s are integers. n processors arranged in a hypercube, processor Pi stores number xinOutline of algorithm：nAt each step, processors on the highest dimension space send the numbers to the one level lower processors and add to the stored number. 3D Cube Synchronized Parallel-SummationAlgori

5、thm SUM-CC for i = log n - 1 downto 0 dod = 2i;for all Pj (0=jd) do in paralleltj = xj+d;xj = xj + tj ; Depth(Time): Q(log n), Work(Cost): Q(n O(log n) = Q (n log n)洗牌交換網絡洗牌交換網絡(Shuffle-Exchange network)由n = 2m個節(jié)點組成，設其編號為 (0, 1, , n1)。節(jié)點之間有兩種連接方式：洗牌方式（shuffle）和交換方式（exchange）。n在洗牌連接方式中，節(jié)點 i 和節(jié)點 j 相連當

6、且僅當（除了編號為 0 和 n1的節(jié)點，它們分別和自己相連）。n在交換連接方式中，奇偶相鄰的兩個節(jié)點互相連接成為n/2個節(jié)點對。 2 mod(1)jin10洗牌交換網絡n = 8 的洗牌交換網絡4567230111Shuffle-ExchangeParallel-Summation Algorithm SUM-SE for i = 1 to log n dofor all Pj (0=jn) do in parallelshuffle (xj); tj = xj; exchange (xj); xj = xj + tj ; Depth: Q (log n) Work: n Q (log n)

7、= Q (n log n)An Example 處理器 原始數據 子和1 子和2 子和3 結果P0 1 1 (10) 10 (28)28 (64) 64 (136) P1 2 9 (10) 18 (28)36 (64) 72 (136) P2 3 2 (12) 10 (28)28 (64) 64 (136)P3 4 10 (12) 18 (28)36 (64) 72 (136) P4 5 3 (14) 12 (32)28 (64) 64 (136) P5 6 11 (16) 20 (32)36 (64) 72 (136) P6 7 4 (16) 12 (32)28 (64) 64 (136)

8、P7 8 12 (16) 20 (32)36 (64) 72 (136) P8 9 5 (18) 14 (36)32 (72) 64 (136) P9 10 13 (18) 22 (36)40 (72) 72 (136)P10 11 6 (20) 14 (36)32 (72) 64 (136) P11 12 14 (20) 22 (36)40 (72) 72 (136) P12 13 7 (22) 16 (40)32 (72) 64 (136)P13 14 15 (22) 24 (40)40 (72) 72 (136) P14 15 8 (24) 16 (40)32 (72) 64 (136)

9、 P15 16 16 (24) 24 (40)40 (72) 72 (136) SIMD-SM Parallel-SummationAlgorithm SIMD-SM-PREFIX-SUM for i = 0 to log n - 1 do for j = 2i+1 to n do in parallel Pi read Sj- 2i and excute Sj = Sj + Sj- 2i ；Cost：Q(log n) P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14 P15 P16 S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S1

10、1 S12 S13 S14 S15 S16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 1 3 6 10 14 18 22 26 30 34 38 42 46 50 54 58 1 3 6 10 15 21 28 36 44 52 60 68 76 84 92 100 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136奇偶交換排序算法奇偶交換排序算法奇偶交換排序對該數組進行兩次掃描：偶數次掃描和奇數次掃描。在偶數次掃描時用數組中的偶

11、數位置上的元素與下一個相鄰的奇數位置上的元素進行比較，若為逆序則進行交換，使兩元素中值大者置入奇數單元。在奇數次掃描過程中，則是用數組的奇數位置上的元素與后面的偶數位置上的元素進行比較，若為逆序則進行交換，使兩元素中值大者置入偶數單元。每次掃描的結果都使得教較大的元素向數組后面移動，這樣經過 次迭代后，數組中的元素就是有序的了。/2n一維線性模型上的奇偶交換并行排序算法一維線性模型上的奇偶交換并行排序算法Algorithm Odd-Even Exchange Sorting(n)for( i=1; ixj+1 )xj xj+1;for (所有偶數處理器Pj) do in parallel /并

12、行處理if (xj xj+1 )xj xj+1; 超立方體超立方體網絡網絡上上的快速的快速排序排序算法算法 設頂點數p = 2d，待排序元素共有n個。算法思想描述如下：1. 首先將n個元素分配到p個處理器上，每個頂點分到n/p個元素。2. 一個處理器選擇一個合適的主元，再將這個主元廣播到其他的處理器中。3. 每個處理器在接收到主元后，把本地的元素分成兩個塊，其中一塊的元素小于主元，而另一塊的元素大于主元。超立方體超立方體網絡網絡上上的快速的快速排序排序算法算法 4. 兩個互為d維伙伴關系的處理器交換數據，低端處理器將大于主元的數傳遞給高端處理器，而高端處理器將小于或者等于主元的數傳送給低端處理

13、器。所謂互為d維伙伴關系的處理器是指兩個處理器的地址分別為0 xd-2xd-3 x0和1xd-2xd-3 x0，其中兩個地址中的xd-2xd-1 x0是相同的。低端處理器的地址首位為0，而高端處理器的地址首位為1。5. 每個處理器將本身的序列和收到的序列合并。比較器網絡上的并行排序比較器網絡上的并行排序 Batcher比較器是一個兩輸入和兩輸出的比較交換單元，可將兩輸入A和B進行比較，并將較大者置于標有“H”的輸出端，將較小者置于標有“L”的輸出端。 比較器網絡一般指由Batcher比較器構成的網絡，每個Batcher比較器可以執(zhí)行兩個數之間的比較與條件交換（CCI）操作。Batcher排序網

14、絡由一系列Batcher比較器組成，按照排序方法的不同，Batcher排序網絡可以分為奇偶歸并排序網絡和雙調排序網絡兩大類。 奇偶歸并網絡奇偶歸并網絡奇偶歸并網絡（Odd-Even Merging Network），簡記為OEM網絡。一個（l, 1）歸并網絡就是前面所示的比較器。對于一個（n, m）奇偶歸并網絡，可按下面的方法遞歸構造出來：首先將兩個輸入序列中奇數號碼的數輸入到“奇歸并器”，將偶數號碼的數輸入到“偶歸并器”。然后將兩個歸并器的有序輸出進行CCI操作：將偶歸并器的第i個輸出與奇歸并器的第i +1個輸出進行比較，當比較不能窮盡時，所剩下的奇或偶歸并器的輸出就是輸出序列中的最大者。下圖是一個（4,4）奇偶歸并網絡的結構 雙調歸并網絡雙調歸并網絡對于一個2n個輸入的雙調歸并網絡，首先將輸入數據并行地進行兩兩比較，分別形成兩個大小為n的MIN和MAX 序列。由Batcher定理可知，MIN和MAX都是雙調的，因此它們可繼續(xù)按前面的步驟形成4個大小為n/2的MIN和MAX 雙調序列。重復此過程，直到每個MIN和MAX序列中都只有兩個元素為止。下面是一個（4, 4）雙調歸并網絡的結構 Batcher 排序網絡排序網絡下面用奇偶歸并網絡和雙調歸并網絡構造一個輸入長度為n的任