【正文】 A[1..n]分成 p組，每組 A[(i1)n/p+1..in/p]， i=1~p ? 示例： MIMDSM模型上的 PSRS排序 begin (1)均勻劃分：將 n個元素 A[1..n]均勻劃分成 p段，每個 pi處理 A[(i1)n/p+1..in/p] (2)局部排序： pi調(diào)用串行排序算法對 A[(i1)n/p+1..in/p]排序 (3)選取樣本： pi從其有序子序列 A[(i1)n/p+1..in/p]中選取 p個樣本元素 (4)樣本排序：用一臺處理器對 p2個樣本元素進(jìn)行串行排序 (5)選擇主元：用一臺處理器從排好序的樣本序列中選取 p1個主元，并 播送給其他 pi (6)主元劃分： pi按主元將有序段 A[(i1)n/p+1..in/p]劃分成 p段 (7)全局交換：各處理器將其有序段按段號交換到對應(yīng)的處理器中 (8)歸并排序：各處理器對接收到的元素進(jìn)行歸并排序 end. 均勻劃分技術(shù) ? 例 PSRS排序過程。矩陣乘法執(zhí)行的計算是 ? 只需將矩陣乘法中的乘法操作換成加法操作，把矩陣乘法中的求和換 求最小值 操作即可。如果假設(shè) G中不包含權(quán)為負(fù)的有向圈，則 dij = dij n1， D=Dn1 利用矩陣乘法求所有點對間最短路徑 ? 根據(jù)組合最優(yōu)原理（ Combinatorial Optimization Principle）有 ? 從而可以從 D1 開始，逐次計算出 D2 ， D4 ， D8， … ， Dn1=D。用 dij k表示從 vi到 vj至多經(jīng)過 k1個中間結(jié)點的所有路徑的長度的最小值，記Dk=(dijk) 。我們的目的是計算 G中所有結(jié)點對之間的最短路。 設(shè) G為一個含有 n個結(jié)點的有向圖。圖中一條路徑的 長度 定義為該路徑上所有的弧的權(quán)的和。 ? 評注 – 這是一項創(chuàng)造性的工作； – 使用矩陣乘法算法求解所有點對間最短路徑是一個很好的范例。本例中這 4個位臵都匹配。先將 P和 T分成長度為 2的塊，用模式塊 (ab) 與正文塊 (ab)(aa)(ba)(ba)(ab)(ab)(aa)(ba)進(jìn)行匹配可知模式塊 (ab)在位臵 1， 4， 6， 9， 11， 14， 16（即 duel(p,q)的獲勝者）出現(xiàn)匹配。 ? 匹配時，先要計算見證函數(shù)值，然后由其計算 的值，找到可能匹配的位臵。由見證函數(shù)可知 P是非周期串。最后在剩下的可能位臵中驗證哪些是符合要求的位臵。 ? 先把正文串分成小段，借助于見證函數(shù)并行地計算競爭函數(shù)值，找出那些可能匹配的位臵。 并行串匹配算法 ? 對于非周期串的研究，就是如何利用見證函數(shù)快速地找出P在 T中的位臵。 ? 可以引入 見證函數(shù) （ Witness Function）來判斷串的周期性。這種特性，就是串的 周期性 。 ? 評注 – 挖掘問題的固有特性與并行的關(guān)系； – 設(shè)計全新的并行算法是一個挑戰(zhàn)性和創(chuàng)造性的工作； – 利用串的周期性的 PRAMCRCW算法是一個很好的范例； 并行串匹配算法 ? 給定長度為 n的 正文串 T和長度為 m的 模式串 P，找出 P在 T中所有出現(xiàn)的位臵稱為串匹配問題。 k個處理器并行地計算出部分和，然后再把結(jié)果加到一起。這個串行算法可以直接并行化。為了積分，將區(qū)間[a,b]均勻分成 N個小區(qū)間，每個小區(qū)間長 ，根據(jù)積分的定義 是第 i 個小區(qū)間左端點的坐標(biāo)，而 是 f(x)在第 i 個小區(qū)間上積分的近似值。 設(shè)計方法的描述 ? 假設(shè)我們想用求和的方法進(jìn)行數(shù)值積分。但是將其直接并行化后可以得到比較好的并行算法。加入冗余計算的并行算法就可能比直接由串行算法并行化得到的算法效率高。例如，串行算法中是沒有冗余計算的。這樣就很難直接將各個溫度的迭代并行起來。這樣，各步之間就不能并行，只能考慮其它的并行化辦法。 設(shè)計方法的描述 ? 評注 – 由串行算法直接并行化的方法是并行算法設(shè)計的最常用方法之一； – 不是所有的串行算法都可以直接并行化的；某些串行算法有內(nèi)在的串行性，比如在某些串行算法中，每一步都要用到上一步的結(jié)果。并行算法 1 一般設(shè)計方法 并行算法的一般設(shè)計方法 ? 串行算法的直接并行化 ? 從問題描述開始設(shè)計并行算法 ? 借用已有算法求解新問題 串行算法的直接并行化 ? 設(shè)計方法描述 ? 快排序算法的并行化 設(shè)計方法的描述 ? 方法描述 – 發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造為并行算法。 – 許多并行編程語言都支持通過在原有的串行程序中加入并行原語（例如某些通信命令等）的方法將串行程序并行化。只有當(dāng)上一步完全結(jié)束后，下一步才能開始。例如模擬退火算法，每個溫度下迭代的出發(fā)點是上一個溫度下迭代的結(jié)束點。 設(shè)計方法的描述 ? 評注 – 一個好的串行算法并不能并行化為一個好的并行算法；另一方面，不好的串行算法并行化后也可能是優(yōu)秀的并行算法。但是在并行算法中，使用適當(dāng)?shù)娜哂嘤嬎阋部赡苁共⑿兴惴ㄐ矢?。又比如，枚舉不是一種好的串行算法。 – 許多數(shù)值串行算法可以并行化為有效的數(shù)值并行算法。設(shè)被積函數(shù)為 f(x)，積分區(qū)間為 [a,b]。如果使用串行算法，可以用循環(huán)和疊加完成上述求和。 設(shè)計方法的描述 ? 假設(shè)有 k臺處理器，可以把這 N個小區(qū)間上的計算任務(wù)分到各處理器： 0號處理器負(fù)責(zé)第 個小區(qū)間上的計算和累加， 1號處理器負(fù)責(zé)第 個小區(qū)間上的計算和累加， …… ， k1號處理器負(fù)責(zé)第 個小區(qū)間上的計算和累加。 設(shè)計方法的描述 快排序算法的并行化 ? 算法 PRAMCRCW上的快排序二叉樹構(gòu)造算法 輸入：序列 (A1,… ,An)和 n個處理器 輸出：供排序用的一棵二叉排序樹 Begin (1)for each processor i do (2)repeat for each processor iroot do ()root=i if (AiAfi)∨(A i=Afi∧if i) then ()fi=root ()LCfi=i ()LCi=RCi=n+1 ()if i=LCfi then exit else fi=LCfi endif end for else ()RCfi=i ()if i=RCfi then exit else fi=RCfi endif endif end repeat End 從問題描述開始設(shè)計并行算法 ? 方法描述 – 從問題本身描述出發(fā)，不考慮相應(yīng)的串行算法，設(shè)計一個全新的并行算法。 ? 研究發(fā)現(xiàn)，兩串能否匹配是與串本身的特性有關(guān)的。 ? 串可以分為周期的和非周期的。確定了串的周期性后就可以先研究非周期串的匹配，然后在此基礎(chǔ)上再研究周期串的匹配。為此，引入 競爭函數(shù) duel(p,q) 。然后逐步擴(kuò)大正文串分段的長度，并計算競爭函數(shù)值，在可能匹配的位臵中排除那些不可能匹配的位臵。 并行串匹配算法 ? 假設(shè) T=abaababaababaababaababa， n=23， P=abaababa， m=8。因為 P只可能在前 16個位臵上與 T匹配，所以在找所有 “ 可能位臵 ” 時只考慮 T的前 16個字符。 ? 計算 duel(p,q)時，可以所有的塊并行計算。 ? 再把 P與 T劃分成長度為 4的塊，用模式塊 (abaa)與正文塊(abaa)(baba)(abab)(aaba)進(jìn)行匹配 , 可知在位臵 1， 6， 11， 16出現(xiàn)匹配（位臵 14被淘汰）； ? 最后用模式串 (abaababa)在正文串的位臵 1， 6， 11， 16進(jìn)行檢查，排除那些不匹配的位臵。 借用已有算法求解新問題 ? 設(shè)計方法描述 ? 利用矩陣乘法求所有點對間最短路徑 設(shè)計方法的描述 ? 方法描述 – 找出求解問題和某個已解決問題之間的聯(lián)系； – 改造或利用已知算法應(yīng)用到求解問題上。 利用矩陣乘法求所有點對間最短路徑 ? 計算原理 設(shè)在一有向圖中，各弧都賦予了非負(fù)整數(shù)權(quán)。圖中兩結(jié)點之間的 最短路徑 是指它們之間長度最短的路徑。矩陣 W=(wij)是 G中各弧上的權(quán)構(gòu)成的矩陣，即 W的元素 wij是 G中結(jié)點 vi到結(jié)點 vj的弧上的權(quán)（如果 vi到 vj無弧，則令 wij=∞）。為此，記 dij為結(jié)點 vi到結(jié)點 vj的最短路長，并記 D=(dij)。因此 dij 1=wij（ i≠j）， dij 1=0 （ i=j）。為了從 Dk/2計算 Dk，可以借用標(biāo)準(zhǔn)的矩陣乘法。 利用矩陣乘法求所有點對間最短路徑 ? 計算原理 有向圖 G=(V,E)，邊權(quán)矩陣 W=(wij)n n，求最短路徑長度矩陣 D=(dij)n n，dij為 vi到 vj的最短路徑長度。 N=27， p=3， PSRS排序如下： 1 5 4 6 4 8 9 3 3 9 6 7 2 9 1 1 4 3 6 6 9 4 0 8 9 6 1 9 7 1 2 2 1 5 4 5 3 9 7 8 4 5 8 3 2 2 7 3 3 7 2 2 06 1 4 1 5 3 9 4 6 4 8 7 2 9 1 9 3 1 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 7 2 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 76 3 9 7 2 1 2 4 0 6 9 2 0 3 3 7 261 2 2 0 3 3 3 9 4 0 6 9 7 2 7 23 3 6 96 1 4 1 5 3 9 4 6 4 8 7 2 9 1 9 3 1 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 7 2 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 76 1 4 1 56 1 4 1 5 3 9 4 6 4 8 7 29 1 9 31 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 72 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 73 9 4 6 4 8 7 2 9 1 9 31 2 2 1 3 6 4 0 5 4 6 1 6 9 8 9 9 72 0 2 7 3 2 3 3 5 3 5 8 7 2 8 4 9 7圖 6 . 1( a ) 均 勻 劃 分 ：( b ) 局 部 排 序 ：( c ) 正 則 采 樣 ：( d ) 采 樣 排 序 ：( e ) 選 擇 主 元 ：( f ) 主 元 劃 分 ：( h ) 歸 并 排 序 ：( g ) 全 局 交 換 ： 方根劃分技術(shù) ? 劃分方法 n個元素 A[1..n]分成 A[(i1)n^(1/2)+1..in^(1/2)]， i=1~n^(1/2) ? 示例： SIMDCREW模型上的 Valiant歸并 (1975年發(fā)表 ) //有序組 A[1..p]、 B[1..q], (假設(shè) p=q), 處理器數(shù) begin (1)方根劃分 : A,B分別按 ； (2)段間比較 : A劃分元與 B劃分元比較 (至多 對 )， 確定 A劃分元應(yīng)插入 B中的區(qū)段；